Descomposición y resolución concurrente de problemas de planificación independiente del dominio

Résumé

En los últimos años, el área de planificación en Inteligencia Artificial ha experimentado grandes avances. Problemas que hace diez años eran imposibles de resolver con un planificador automático, se solucionan ahora en pocos segundos. Este rápido incremento en el rendimiento de los sistemas de planificación se debe, básicamente, a la introducción de nuevas técnicas, como la planificación basada en grafos, que supuso un antes y un después en esta disciplina. A medida que los nuevos planificadores son capaces de resolver ciertos problemas, se proponen otros nuevos, cada vez más complejos, lo que implica que los sistemas deben evolucionar al mismo ritmo. Así, surgen una nueva tendencia que consiste en incorporar a los planificadores técnicas cuya eficacia ya ha sido probada en otros contextos: búsqueda heurística, búsqueda local, model-checking, etc., que tienen un gran éxito. Otra de las aproximaciones a la resolución de problemas que ha sido utilizada dentro del área de planificación es la descomposición de problemas. Existen diversos sistemas basados en diferentes metodologías de descomposición de problemas: "divide y vencerás", jerarquías de abstracción, planificación de redes jerárquicas, etc. Esta tesis introduce una nueva técnica de descomposición de problemas basada en la metodología "divide y vencerás", que trata de mitigar algunos de los inconvenientes que presentan otros sistemas basados en esta misma metodología, como la dificultad que existe para identificar los distintos subproblemas y para combinar las soluciones obtenidas a los mismos. En este trabajo de tesis se estudia, en primer lugar, un criterio que permite identificar los distintos subproblemas en los que se puede descomponer un problema dado. Para ello, se determina un conjunto de literales que deben alcanzarse en todo plan solución y se establece un orden entre ellos. Estos literales que deben alcanzarse en todo plan soluc