Solving complex planning tasks through extraction of subproblems
Jana Koehler · 1998
The paper introduces an approach to derive a total ordering between increasing sets of subgoals by defining a relation over atomic goals. The ordering is represented in a so-called goal agenda that is used by the planner to incrementally plan for the increasing sets of subgoals. This can lead to an exponential complexity reduction because the solution to a complex planning problem is found by solving easier subproblems. Since only a polynomial overhead is caused by the goal agenda computation, a potential exists to dramatically speed up planning algorithms as we demonstrate in the empirical evaluation. Introduction How to effectively plan for interdependent subgoals has been in the focus of AI planning research for a very long time (Chapman 1987). But until today planners have made only some progress to solve larger sets of subgoals and scalability of classical planning systems is still a problem. Previous approaches fell into two categories: On one hand, one can focus on...