Low-level motion planning techniques must be combined with high-level task planning formalisms in order to generate realistic plans that can be carried out by humans and robots. Previous attempts to integrate these two planning formalisms mostly used either Classical Planning or HTN Planning. Recently, we developed Hierarchical Goal Networks (HGNs), a new hierarchical planning formalism that combines the advantages of HTN and Classical planning, while mitigating some of the disadvantages of each individual formalism. In this paper, we describe our ongoing research on designing a planning formalism and algorithm that exploits the unique features of HGNs to better integrate task and motion planning. We also describe how the proposed planning framework can be instantiated to solve assembly planning problems involving human-robot teams.

Hierarchical planning has attracted renewed interest in the last couple of years. As a consequence, the time was right to establish a workshop devoted entirely to hierarchical planning – an insight shared by many supporters. In this paper we report on the first ICAPS workshop on Hierarchical Planning held in Delft, The Netherlands, in 2018 as well as on the second workshop held in Berkeley, CA, USA, in 2019. Hierarchical planning approaches incorporate hierarchies in the domain model. In the most common form, the hierarchy is defined among tasks, leading to the distinction between primitive and abstract tasks.

From a theoretical perspective, judging the expressivity of planning formalisms helps to understand the relationship of different representations and to infer theoretical properties. From a practical point of view, it is important to be able to choose the best formalism for a problem at hand, or to ponder the consequences of introducing new representation features. Most work on the expressivity is based either on compilation approaches, or on the computational complexity of the plan existence problem. Recently, we introduced a new notion of expressivity. It is based on comparing the structural complexity of the set of solutions to a planning problem by interpreting the set as a formal language and classifying it with respect to the Chomsky hierarchy. This is a more direct measure than the plan existence problem and enables also the comparison of formalisms that can not be compiled into each other. While existing work on that last approach focused on different hierarchical problem classes, this paper investigates STRIPS with and without conditional effects; though we also tighten some existing results on hierarchical formalisms. Our second contribution is a discussion on the language-based expressivity measure with respect to the other approaches.

The recent approaches of extending the GRAPHPLAN algorithm to handle more expressive planning formalisms raise the question of what the formal meaning of ``expressive power'' is. We formalize the intuition that expressive power is a measure of how concisely planning domains and plans can be expressed in a particular formalism by introducing the notion of ``compilation schemes'' between planning formalisms. Using this notion, we analyze the expressiveness of a large family of propositional planning formalisms, ranging from basic STRIPS to a formalism with conditional effects, partial state specifications, and propositional formulae in the preconditions. One of the results is that conditional effects cannot be compiled away if plan size should grow only linearly but can be compiled away if we allow for polynomial growth of the resulting plans. This result confirms that the recently proposed extensions to the GRAPHPLAN algorithm concerning conditional effects are optimal with respect to the ``compilability'' framework. Another result is that general propositional formulae cannot be compiled into conditional effects if the plan size should be preserved linearly. This implies that allowing general propositional formulae in preconditions and effect conditions adds another level of difficulty in generating a plan.