Algoritmo de programación dinámica en paraleloaplicación a problemas de control

Résumé

La Programación Dinámica es una potente herramienta que permite la resolución de una amplia familia de problemas de optimización dentro de la teoría del control, El principal inconveniente, compartido con todas las técnicas de optimización de tipo combinatorio, es su alto coste computacional. Esto hace que la solución exacta no pueda ser obtenida en ocasiones en un tiempo razonable. Por este motivo, en las últimas décadas y coincidiendo con el desarrollo de los sistemas de computación (software y hardware) se han venido desarrollando diversas técnicas que permiten una considerble reducción de la complejidad computacional, aunque a veces los niveles alcanzados siguen sin ser suficientemente válidos. Por otra parte, los algoritmos de Programación Dinámica pueden ser reformulados para su ejecución en un computador paralelo, de manera que la solución se obtenga en un tiempo mucho menor. Si bien hace pocos años los computadores paralelos eran enormemente costosos, hoy en día es posible implementar computadores paralelos virtuales, a un coste aceptable y fácilmente escalables, a su partir de redes de estaciones de trabajo ordinarias, lo que genéricamente se denomina como cluster. Frente a los supercomputadores paralelos comerciales, los clusters hacen uso del sistema operativo Linux y de herramientas de programación que siguen la filosofía del software libre. De este modo, todo el software y la documentación necesarios para montar, configurar y mantener el cluster se encuentran disponibles de manera libre y gratuita en Intenet. Así es posible obtener sistemas de muy alto rendimiento a bajo costo. En esta Tesis se desarrollan algoritmos paralelos de Programación Dinámica generales para clusters, utilizando el paso de mensajes como paradigma de programación, que sean de utilidad en el campo de control de procesos.