Simplificación de los procesos de decisión de Markov mediante reglamentación de acciones y priorización de estados

Resumen

Para que se puedan construir rumbos de acción en ambientes reales, se debe considerar que las acciones pueden tener efectos distintos en el mundo (no determinismo) y ponderar el potencial de algún plan alternativo para alcanzar las metas del problema, considerando sus costes y recompensas (metas extendidas). Al respecto, la planificación basada en teoría de decisiones ha permitido solucionar problemas estocásticos, estableciendo rumbos de acción que involucran cantidades de información difíciles de procesar por el ser humano, evaluando sus fortalezas y debilidades con base en las teorías de probabilidad y de utilidad. Esta metodología ha incrementado últimamente su investigación debido al éxito de los procesos de decisión de Markov (MDPs) en problemas de investigación de operaciones, teoría de control, economía e inteligencia artificial, entre otros. Sin embargo, el problema de resolver los MDPs de considerables dimensiones con precisión y rapidez ha conducido a un reto computacional. Dado que el esfuerzo computacional es significativo, la investigación actual se centra en la búsqueda de técnicas superiores de aceleración. Por ejemplo, las propiedades de convergencia de sus métodos de solución actuales dependen, en gran medida, del orden de las operaciones de actualización. Por un lado, algoritmos tales como el de ordenamiento topológico han sido capaces de encontrar buenos ordenamientos, pero sus costes de inicio han sido usualmente altos. Por otro lado, los métodos de ruta más corta tales como el clásico algoritmo de Dijkstra, que está basado en colas de prioridad, han sido aplicados exitosamente a la solución de procesos de decisión de Markov de ruta determinística más corta. En esta tesis se propone un nuevo algoritmo de iteración de valor basado en el algoritmo de Dijkstra para resolver MDPs de ruta estocástica más corta. A diferencia de otros enfoques priorizados tales como el barrido priorizado mejorado, el enfoque aquí propuesto es capaz de tratar con múltiples estados meta y de inicio y, puesto que sucesivamente se actualiza cada estado utilizando la ecuación de Bellman, este enfoque garantiza la convergencia a la solución óptima. Además este algoritmo utiliza la función de valor actual como métrica de prioridad, puesto que el algoritmo de Dijkstra sugiere que un orden de actualización más adecuado está dado por el valor de la programación dinámica funcional. Los resultados experimentales obtenidos en una tarea de estrategias de navegación marítima en bote de vela muestran la factibilidad del enfoque propuesto. Se comprobó que el algoritmo propuesto reduce considerablemente el tiempo de solución requerido por el algoritmo de iteración de valor, desde un crecimiento de orden cuadrático -en función del número de estados- hasta uno de orden cercano a la linealidad.