HTN planning combines actions that cause state transition with grammar-like decomposition of compound tasks that additionally restricts the structure of solutions. There are mainly two strategies to solve such planning problems: decomposition-based search in a plan space and progression-based search in a state space. Existing progression-based systems do either not rely on heuristics (e.g. SHOP2) or calculate their heuristics based on extended or modified models (e.g. GoDeL). Current heuristic planners for standard HTN models (e.g. PANDA) use decomposition-based search. Such systems represent search nodes more compactly due to maintaining a partial order between tasks, but they have no current state at hand during search. This makes the design of heuristics difficult. In this paper we present a progression-based heuristic HTN planning system: We (1) provide an improved progression algorithm, prove its correctness, and empirically show its efficiency gain; and (2) present an approach that allows to use arbitrary classical (non-hierarchical) heuristics in HTN planning. Our empirical evaluation shows that the resulting system outperforms the state-of-the-art in HTN planning.

Plan- and Goal Recognition (PGR) is the task of inferring the goals and plans of an agent based on its actions. A few years ago, an approach has been introduced that successfully exploits the performance of planning systems to solve it. That way, no specialized solvers are needed and PGR benefits from present and future research in planning. The approach uses classical planning systems and needs to plan (at least) once for every possible goal. However, models in PGR are often structured in a hierarchical way, similar to Hierarchical Task Networks (HTNs). These models are strictly more expressive than those in classical planning and can describe partially ordered sets of tasks or multiple goals with interleaving plans. We present the approach PGR as HTN Planning that enables the recognition of complex agent behavior by using unmodified, off-the-shelf HTN planners. Planning is thereby needed only once, regardless of how many possible goals there are. Our evaluation shows that current planning systems are able to handle large models with thousands of possible goals and that the approach results in high recognition rates.

In this paper, we propose a novel SAT-based planning approach for hierarchical planning by introducing the SAT-based planner totSAT for the class of totally-ordered HTN planning problems. We use the same general approach as SAT planning for classical planning does: bound the problem, translate the problem into a formula, and if the formula is not satisfiable, increase the bound. In HTN planning, a suitable bound is the maximum depth of decomposition. We show how totally-ordered HTN planning problems can be translated into a SAT formula, given this bound. Furthermore, we have conducted an extensive empirical evaluation to compare our new planner against state-of-the-art HTN planners. It shows that our technique outperforms any of these systems.

Interaction with users is a key capability of planning systems that are applied in real-world settings. Such a system has to be able to react appropriately to requests issued by its users. Most of these systems are based on a generated plan that is continually criticised by him, resulting in a mixed-initiative planning system. We present several practically relevant requests to change a plan in the setting of hierarchical task network planning and investigate their computational complexity. On the one hand, these results provide guidelines when constructing algorithms to execute the respective requests, but also provide translations to other well-known planning queries like plan existence or verification. These can be employed to extend an existing planner such that it can form the foundation of a mixed-initiative planning system simply by adding a translation layer on top.

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.

Hierarchical Task Network (HTN) planning with Task Insertion (TIHTN planning) is a formalism that hybridizes classical planning with HTN planning by allowing the insertion of operators from outside the method hierarchy. This additional capability has some practical benefits, such as allowing more flexibility for design choices of HTN models: the task hierarchy may be specified only partially, since "missing required tasks" may be inserted during planning rather than prior planning by means of the (predefined) HTN methods. While task insertion in a hierarchical planning setting has already been applied in practice, its theoretical properties have not been studied in detail, yet — only EXPSPACE membership is known so far. We lower that bound proving NEXPTIME-completeness and further prove tight complexity bounds along two axes: whether variables are allowed in method and action schemas, and whether methods must be totally ordered. We also introduce a new planning technique called acyclic progression, which we use to define provably efficient TIHTN planning algorithms.

Modern technical devices are often too complex for many users to be able to use them to their full extent. Based on planning technology, we are able to provide advanced user assistance for operating technical devices. We present a system that assists a human user in setting up a complex home theater consisting of several HiFi devices. For a human user, the task is rather challenging due to a large number of different ports of the devices and the variety of available cables. The system supports the user by giving detailed instructions how to assemble the theater. Its performance is based on advanced user-centered planning capabilities including the generation, repair, and explanation of plans.

Nominal schemas have recently been introduced as a new approach for the integration of DL-safe rules into the Description Logic framework. The efficient processing of knowledge bases with nominal schemas remains, however, challenging. We address this by extending the well-known optimisation of absorption as well as the standard tableau calculus to directly handle the (absorbed) nominal schema axioms. We implement the resulting extension of standard tableau calculi in a novel reasoning system and we integrate further optimisations. In our empirical evaluation, we show the effect of these optimisations and we find that the proposed approach performs well even when compared to other DL reasoners with dedicated rule support.

In hierarchical planning, landmarks are tasks that occur on any search path leading from the initial plan to a solution. In this work, we present novel domain-independent planning strategies based on such hierarchical landmarks. Our empirical evaluation on four benchmark domains shows that these landmark-aware strategies outperform established search strategies in many cases.

Human users who execute an automatically generated plan want to understand the rationale behind it. Knowledge-rich plans are particularly suitable for this purpose, because they provide the means to give reason for causal, temporal, and hierarchical relationships between actions. Based on this information, focused arguments can be generated that constitute explanations on an appropriate level of abstraction. In this paper, we present a formal approach to plan explanation. Information about plans is represented as first-order logic formulae and explanations are constructed as proofs in the resulting axiomatic system. With that, plan explanations are provably correct w.r.t. the planning system that produced the plan. A prototype plan explanation system implements our approach and first experiments give evidence that finding plan explanations is feasible in real-time.