Generation and exploitation of intermediate goals in automated planning

e-Archivo Repository

Show simple item record

dc.contributor.advisor Borrajo Millán, Daniel
dc.contributor.advisor Fernández Arregui, Susana
dc.contributor.author Alcázar Saiz, Vidal
dc.date.accessioned 2014-12-04T15:41:25Z
dc.date.available 2014-12-04T15:41:25Z
dc.date.issued 2014-07
dc.date.submitted 2014-07-11
dc.identifier.uri http://hdl.handle.net/10016/19767
dc.description Mención Internacional en el título de doctor
dc.description.abstract In automated planning, domain-independent planners often scale poorly. This is due to the exponential blow up of the effort necessary to solve a planning task as its size increases. One of the most popular ways of addressing this problem is splitting the planning problem into several smaller ones. Each subproblem is in theory exponentially easier to solve than the original one, so planners that divide the original task will tend to scale much better. To divide the task into smaller ones, we need to find domain-independent methods to derive intermediate goals. In this thesis we will study different approaches that generate and exploit intermediate goals, without limiting ourselves to simply splitting the original problem. Three main lines of research will be pursued. The first one deals with regression, first tackling its shortcomings and then using it both in bidirectional search and as a way to derive novel heuristics based on intermediate goals. In the second one we propose sampling the search space randomly and using the randomly-sampled subgoals in a tree-like algorithms that effectively balances exploration and exploitation. Finally, in the third one we study the properties of the landmark graph, which represents precedence constraints among subgoals of the task. As a contribution, we propose different characterizations of the landmark graph that improve over its original formulation by providing more information, both formal properties of the task and finer orderings of subgoals exploitable by planners that already use landmarks. ----------------------------------------------------------
dc.description.abstract En planificación automática, los planificadores independientes de dominio a menudo escalan pobremente. Esto se debe a la explosión exponencial del esfuerzo necesario para resolver una tarea de planificación según su tamaño incrementa. Uno de las formas más populares de abordar este problema es dividiendo el problema de planificación en varios problemas más pequeños. Para separar la tarea en tareas más pequeñas, hay que encontrar métodos independientes de dominio capaces de derivar metas intermedias. En esta tesis se estudiarán diferentes aproximaciones que generen y aprovechen metas intermedias, sin limitarnos a una mera subdivisión del problema original. Tres líneas de investigación serán exploradas. La primera trata sobre regresión, primero encarando sus limitaciones y después usándola tanto en búsqueda bidireccional como en nuevas heurísticas basadas en metas intermedias. En la segunda línea proponemos muestrear aleatoriamente el espacio de búsqueda y usar las submetas muestreadas aleatoriamente en un algoritmo basado en árboles aleatorios que balancea exploración y explotación de forma efectiva. Finalmente, en la tercera línea de investigación estudiamos las propiedades del grafo de landmarks, el cual representa las restricciones de precedencia entre submetas de la tarea. Como contribución, proponemos diferentes caracterizaciones del grafo de landmarks que mejoran su formulación original proporcionando más información, tanto propiedades formales de la tarea como ordenaciones de submetas más informadas aprovechables por planificadores que emplean landmarks.
dc.format.mimetype application/pdf
dc.language.iso eng
dc.rights Atribución-NoComercial-SinDerivadas 3.0 España
dc.rights.uri http://creativecommons.org/licenses/by-nc-nd/3.0/es/
dc.subject.other Automated planning
dc.subject.other Intermediate goals
dc.title Generation and exploitation of intermediate goals in automated planning
dc.type doctoralThesis
dc.subject.eciencia Informática
dc.rights.accessRights openAccess
dc.description.degree Programa Oficial de Doctorado en Ciencia y Tecnología Informática
dc.description.responsability Presidente: José Manuel Molina López.- Secretario: Héctor Geffner.- Vocal: Joerg Hoffmann
dc.contributor.departamento Universidad Carlos III de Madrid. Departamento de Informática
 Find Full text

Files in this item

*Click on file's image for preview. (Embargoed files's preview is not supported)


The following license files are associated with this item:

This item appears in the following Collection(s)

Show simple item record