Program synthesis for generalized planning

dc.contributor
Universitat Pompeu Fabra. Departament de Tecnologies de la Informació i les Comunicacions
dc.contributor.author
Segovia Aguas, Javier
dc.date.accessioned
2018-11-14T13:06:46Z
dc.date.available
2018-11-14T13:06:46Z
dc.date.issued
2018-10-05
dc.identifier.uri
http://hdl.handle.net/10803/663753
dc.description.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.
en_US
dc.description.abstract
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.
en_US
dc.description.abstract
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.
en_US
dc.format.extent
174 p.
en_US
dc.format.mimetype
application/pdf
dc.language.iso
eng
en_US
dc.publisher
Universitat Pompeu Fabra
dc.rights.license
L'accés als continguts d'aquesta tesi queda condicionat a l'acceptació de les condicions d'ús establertes per la següent llicència Creative Commons: http://creativecommons.org/licenses/by-nc-nd/4.0/
dc.rights.uri
http://creativecommons.org/licenses/by-nc-nd/4.0/
*
dc.source
TDX (Tesis Doctorals en Xarxa)
dc.subject
Classical planning
en_US
dc.subject
Generalized planning
en_US
dc.subject
Automated programming
en_US
dc.subject
Program synthesis
en_US
dc.title
Program synthesis for generalized planning
en_US
dc.type
info:eu-repo/semantics/doctoralThesis
dc.type
info:eu-repo/semantics/publishedVersion
dc.subject.udc
62
en_US
dc.contributor.authoremail
javier.segovia@upf.edu
en_US
dc.contributor.director
Jonsson, Anders
dc.embargo.terms
cap
en_US
dc.rights.accessLevel
info:eu-repo/semantics/openAccess
dc.description.degree
Programa de doctorat en Tecnologies de la Informació i les Comunicacions


Documents

tjsa.pdf

1.018Mb PDF

Aquest element apareix en la col·lecció o col·leccions següent(s)