RT Dissertation/Thesis
T1 Generation and exploitation of intermediate goals in automated planning
A1 Alcázar Saiz, Vidal
AB In automated planning, domain-independent planners often scale poorly. This isdue to the exponential blow up of the effort necessary to solve a planning task asits size increases. One of the most popular ways of addressing this problem issplitting the planning problem into several smaller ones. Each subproblem is intheory exponentially easier to solve than the original one, so planners that dividethe original task will tend to scale much better.To divide the task into smaller ones, we need to find domain-independent methodsto derive intermediate goals. In this thesis we will study different approachesthat generate and exploit intermediate goals, without limiting ourselves to simplysplitting the original problem. Three main lines of research will be pursued. Thefirst one deals with regression, first tackling its shortcomings and then using it bothin bidirectional search and as a way to derive novel heuristics based on intermediategoals. In the second one we propose sampling the search space randomly andusing the randomly-sampled subgoals in a tree-like algorithms that effectively balancesexploration and exploitation. Finally, in the third one we study the propertiesof the landmark graph, which represents precedence constraints among subgoals ofthe task. As a contribution, we propose different characterizations of the landmarkgraph that improve over its original formulation by providing more information,both formal properties of the task and finer orderings of subgoals exploitable byplanners that already use landmarks. ----------------------------------------------------------
AB En planificación automática, los planificadores independientes de dominio a menudoescalan pobremente. Esto se debe a la explosión exponencial del esfuerzo necesariopara resolver una tarea de planificación según su tamaño incrementa. Uno delas formas más populares de abordar este problema es dividiendo el problema deplanificación en varios problemas más pequeños.Para separar la tarea en tareas más pequeñas, hay que encontrar métodos independientesde dominio capaces de derivar metas intermedias. En esta tesis seestudiarán diferentes aproximaciones que generen y aprovechen metas intermedias,sin limitarnos a una mera subdivisión del problema original. Tres líneas deinvestigación serán exploradas. La primera trata sobre regresión, primero encarandosus limitaciones y después usándola tanto en búsqueda bidireccional como ennuevas heurísticas basadas en metas intermedias. En la segunda línea proponemosmuestrear aleatoriamente el espacio de búsqueda y usar las submetas muestreadasaleatoriamente 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 lasrestricciones de precedencia entre submetas de la tarea. Como contribución, proponemosdiferentes caracterizaciones del grafo de landmarks que mejoran su formulación original proporcionando más información, tanto propiedades formales dela tarea como ordenaciones de submetas más informadas aprovechables por planificadoresque emplean landmarks.
YR 2014
FD 2014-07
LK https://hdl.handle.net/10016/19767
UL https://hdl.handle.net/10016/19767
LA eng
NO Mención Internacional en el título de doctor
DS e-Archivo
RD 18 may. 2024