Resumen de Generation and exploitation of intermediate goals in automated planning

Vidal Alcázar Saiz

• 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. ----------------------------------------------------------