Program synthesis for generalized planning

Abstract

Generalized planning is the problem of finding an algorithm-like solution called generalized plan to multiple planning instances. The two main tasks to perform in generalized planning are synthesizing and validating generalized plans. In this thesis, we represent generalized plans as a planning programs, enhanced with conditional goto conditions, or finite state controllers. Then, we compile generalized planning problems to PDDL such that we can compute programs using off-the-shelf classical planners. Because solutions to generalized planning are similar to algorithms, we can build libraries of previous knowledge and reuse them if necessary using a call stack. This feature extends to planning programs with procedures, hierarchical finite state controllers and allows recursion. Finally, we introduce new application areas for planning, e.g. unsupervised classification of instances or context-free grammar generation, by defining non-deterministic choice functions for planning programs.

La Planificació Generalitzada és el problema de trobar una solució en forma d'algorisme anomenat pla generalitzat a múltiples instàncies de planificació. Les principals tasques són la síntesi i la validació de plans generalizats. En aquesta tesi, representem els plans generalizats com programes de planificació millorats amb salts condicionals, o controladors d'estat finits. Després, compilem problemes de planificació generalitzada a PDDL per poder computar-los amb qualsevol planificador clàssic que estigui llest per utilitzar-se. Com les solucions són algorismes, podem construir llibreries de coneixement previ y reutilitzar-les amb una pila de trucades. Aquesta característica s'estén als programes de planificació amb procediments, als controladors d'estat finits jeràrquics i permet recursivitat. Finalmente, donem a conèixer noves àrees on aplicar planificació, per exemple la classificació no supervisada d'instàncies o la generació de gramàtica lliure de context, gràcies a la definició d'una funció d'elecció no determinista.

La Planificación Generalizada es el problema de encontrar una solución en forma de algoritmo llamada plan generalizado a múltiples instancias de planificación. Las principales tareas son la síntesis y la validación de planes generalizados. En esta tesis, representamos los planes generalizados como programas de planificación mejorados con saltos condicionales, o controladores de estado finitos. Después, compilamos problemas de planificación generalizada a PDDL tal que podamos computarlos utilizando cualquier planificador clásico que esté listo para usarse. Como las soluciones son algoritmos, podemos construir librerías de conocimiento previo y reutilizarlas con una pila de llamadas. Esta característica se extiende a los programas de planificación con procedimientos, a los controladores de estado finitos jerárquicos y permite recursividad. Finalmente, damos a conocer nuevas areas dónde aplicar planificación, por ejemplo la clasificación no supervisada de instancias o la generación de gramática libre de contexto, gracias a la definición de una función de elección no determinista.