Publication: Generation and exploitation of intermediate goals in automated planning
Loading...
Identifiers
Publication date
2014-07
Defense date
2014-07-11
Authors
Tutors
Journal Title
Journal ISSN
Volume Title
Publisher
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. ----------------------------------------------------------
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.
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.
Description
Mención Internacional en el título de doctor
Keywords
Automated planning, Intermediate goals