Hierarchical Planning : Expressivity Analysis, Solving Techniques, and Problem Compilations

Abstract

Automated planning enables systems to act in a goal-directed way and flexibly react on their environment and other agents. This makes it a valuable technology for intelligent systems. Based on a model of the environment and a goal to reach or a task to accomplish, those systems come up with a detailed plan on how to achieve it. Two widely-used approaches to planning are classical planning and hierarchical planning. Classical planning comes with a large number of domain-independent solving techniques that enable a simple adaptation to new application domains. The motivation to use a hierarchy (which is usually defined on the things to do, the tasks) is manifold: some application domains can be modeled much more intuitive using hierarchical structures, the hierarchy can be exploited to communicate with a human user on different levels of abstraction, and it has often been used to guide the search to find solutions more quickly. Further it enables the definition of more complex behavior patterns than possible with commonly-used non-hierarchical formalisms. In both classical and hierarchical planning, there is a range of slightly different formalisms that come with different properties. This thesis advances the state of the art in hierarchical planning along three lines of research. We provide an expressivity analysis of common planning formalisms, novel solving techniques for hierarchical planning, and compilations to solve three problems related to planning.

We first systematically investigate the expressivity of different classical and hierarchical planning formalisms. To this end, we compare them with formal languages and show what kind of languages can be expressed by which formalism. We show that the expressivity ranges from a subset of the regular languages for basic classical planning to a (non-context-free) subset of the context-sensitive languages for the most widely-used hierarchical formalism called Hierarchical Task Network (HTN) planning.

We introduce novel solving techniques for HTN planning. We start with a new input language that became the standard for the 2020 International Planning Competition (IPC) and a grounding technique to compile the first-order model used to specify the planning domain into a propositional model as required for most planning systems. Then we show how HTN planners based on heuristic search can benefit from the sophisticated domain-independent heuristics developed for classical planning. We introduce a generic method to use them to guide the HTN search. Our system outperforms the participants of the 2020 IPC and several other systems from the literature. We further show that our techniques can also be used to find optimal plans, i.e. plans with minimal action cost.

Besides plan generation, there are several related tasks to solve when applying planning in intelligent systems. For three of them, we show how they can be compiled into standard planning problems. This enables the use of standard planning systems to solve the problems instead of coming up with specialized solvers. We introduce compilations for (1) plan and goal recognition, the task of identifying the goals and plans of other agents, (2) plan repair, the task of coming up with a novel plan when the execution of an initial one failed, and (3) plan verification, the task of deciding whether a given sequence of actions is a solution for a given problem.

In reference to IEEE copyrighted material which is used with permission in this thesis, the IEEE does not endorse any of Ulm University's products or services. Internal or personal use of this material is permitted. If interested in reprinting/republishing IEEE copyrighted material for advertising or promotional purposes or for creating new collective works for resale or redistribution, please go to http://www.ieee.org/publications_standards/publications/rights/rights_link.html to learn how to obtain a License from RightsLink.