Effective Search Techniques for Non-classical Planning via Reformulation

Automated planning is a branch of AI that addresses the problem of generating a course of action to achieve a specified objective, given an initial state of the world. It is an area that is central to the development of intelligent agents and autonomous robots. In the last decade, automated planning has seen significant progress in terms of scalability, much of it achieved by the development of heuristic search approaches. Many of these advances, are only immediately applicable to so-called classical planning tasks. However, there are compelling applications of planning that are non-classical. An example is the problem of web service composition, in which the objective is to automatically compose web artifacts to achieve the objective of a human user. In doing so, not only the hard goals but also the \emph{preferences} of the user---which are usually not considered in the classical model---must be considered. % Also, the automated composition %should deal with abstract representations of the web %artifacts---which may also not adjust to the classical model. In this thesis we show that many of the most successful advances in classical planning can be leveraged for solving compelling non-classical problems. In particular, we focus on the following non-classical planning problems: planning with temporally extended goals; planning with rich, temporally extended preferences; planning with procedural control, and planning with procedural programs that can sense the environment. We show that to efficiently solve these problems we can use a common approach: reformulation. For each of these planning tasks, we propose a reformulation algorithm that generates another, arguably simpler instance. Then, if necessary, we adapt existing techniques to make the reformulated instance solvable efficiently. In particular, we show that both the problems of planning with temporally extended goals and with procedural control can be mapped into classical planning. Planning with rich user preferences, even after reformulation, cannot be mapped into classical planning and thus we develop specialized heuristics, based on existing heuristics, together with a branch-and-bound algorithm. Finally, for the problem of planning with programs that sense, we show that under certain conditions programs can be reduced to simple operators, enabling the use of a variety of existing planners. In all cases, we show experimentally that the reformulated problems can be solved effectively by either existing planners or by our adapted planners, outperforming previous approaches.Ph