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
Impact
Export
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