Detecting and resolving unsolvable planning problems is an active research area that has recently received increased attention. Nevertheless, unsolvability remains a significant challenge, particularly when it comes to efficiently identifying potential causes for a problem’s unsolvability. To address this challenge, we propose a method that computes modifications to the planning task. Specifically, given an unsolvable planning problem, our approach identifies a cardinality-minimal set of state variables whose removal renders the problem solvable. Existing literature typically relies on subset enumeration to identify such sets. While effective for small variable sets, we find that this approach becomes impractical for larger sets due to its high computational cost. To overcome this limitation, we introduce a novel method based on hitting set duality, a well-established technique for solving various combinatorial problems. Our results show that this new approach consistently outperforms subset enumeration for medium-sized and large result sets. We validate the effectiveness of our method through experiments on modified problems from the 2016 International Planning Competition on Unsolvability.

HTN planning requires the decomposition of compound tasks into primitive and executable actions. In the currently most frequently used formalism, compound tasks lack explicit preconditions and effects. Those are, however, useful, e.g., for pruning techniques, heuristics, or the comprehension of domains. Previously, we introduced and formalized different kinds of inferred preconditions and effects of compound tasks based on their decomposition methods together with a complexity analysis. In this paper, we present an empirical evaluation of computing these inferred preconditions and effects using the IPC benchmark sets. Specifically, we analyze their frequency of occurrence and compare the performance of an approximation to the exact preconditions and effects. Our goal is to provide a comprehensive overview of the proposed techniques, enabling researchers to determine the extent to which they can be utilized in their given application.

In this paper we study the computational complexity of several reasoning tasks centered around the bounded plan existence problem. We do this for standard classical planning and hierarchical task network (HTN) planning and each for a grounded and a lifted representation. Whereas bounded plan existence complexity is known for classical planning, it has not yet been studied for HTN planning. For plan verification, results were available for both formalisms except for the lifted HTN planning. We will present lower and upper bounds of the complexity of plan verification in lifted HTN planning and provide novel insights into its grounded counterpart, in which we show that verification is not just NP-complete in the general case, but already for a severely restricted special case. Finally, we show the complexity concerning verifying the optimality of a given plan and discuss its connection to the bounded plan existence problem.

Heuristic Search is still the most successful approach to hierarchical planning, both for finding any and for finding an optimal solution. Yet, there exist only a very small handful of heuristics for HTN planning – so there is still huge potential for improvements. It is especially noteworthy that there does not exist a single heuristic that’s tailored towards special cases. In this work we propose the very first specialized HTN heuristic, tailored towards totally ordered HTN problems. Our heuristic builds on an existing NP-complete and admissible delete-and-ordering relaxation ILP heuristic, but partially incorporates ordering constraints while reducing the number of ILP constraints. It exploits inferred preconditions and effects of compound tasks and is also admissible thus allowing to find optimal solutions. Our heuristic demonstrates improved performance (ILP) or comparable performance (LP) to the previous heuristic, suggesting the success of the model reduction. Compared to the current state-of-the art heuristic for optimal HTN planning, our heuristic is less efficient on average, but more informed and dominates it in roughly as many cases as it gets dominated by the other, making it a more efficient alternative in several domains.

In HTN planning the choice of decomposition methods used to refine compound tasks is key to finding a valid plan. Based on inferred preconditions and effects of compound tasks, we propose a look-ahead technique for search-based total-order HTN planning that can identify inevitable refinement choices and in some cases dead-ends. The former occurs when all but one decomposition method for some task are proven infeasible for turning a task network into a solution, whereas the latter occurs when all methods are proven infeasible. We show how it can be used for pruning, as well as to strengthen heuristics and to reduce the search branching factor. An empirical evaluation proves its potential as incorporating it improves an existing HTN planner such that it is the currently best performing one in terms of coverage and IPC score.

Explainable robotics refers to the challenge of designing robots that can make their decisions transparent to humans. Recently, a number of approaches to task plan explanation have been proposed, which enable robots to explain each step in their plan to humans. These approaches have in common that they are based on the causal links in the plan. We discuss problems with using causal links for plan explanation. Particularly, their inability to distinguish enabling actions from requiring actions can lead to counter-intuitive explanations. We propose an extension that allows for making this relevant distinction and demonstrate how it can be applied to create a robot that explains its actions.

In Hierarchical Task Network (HTN) planning, compound tasks need to be refined into executable (primitive) action sequences. In contrast to their primitive counterparts, compound tasks do not specify preconditions or effects. Thus, their implications on the states in which they are applied are not explicitly known: they are "hidden" in and depending on the decomposition structure. We formalize several kinds of preconditions and effects that can be inferred for compound tasks in totally ordered HTN domains. As relevant special case we introduce a problem relaxation which admits reasoning about preconditions and effects in polynomial time. We provide procedures for doing so, thereby extending previous work, which could only deal with acyclic models. We prove our procedures to be correct and complete for any totally ordered input domain. These results are embedded into an encompassing complexity analysis of the inference of preconditions and effects of compound tasks, an investigation that has not been made so far.

We study PO and POCL plans with regard to their makespan – the execution time when allowing the parallel execution of causally independent actions. Partially ordered (PO) plans are often assumed to be equivalent to partial order causal link (POCL) plans, where the causal relationships between actions are explicitly represented via causal links. As a first contribution, we study the similarities and differences of PO and POCL plans, thereby clarifying a common misconception about their relationship: There are PO plans for which there does not exist a POCL plan with the same orderings. We prove that we can still always find a POCL plan with the same makespan in polynomial time. As another main result we prove that turning a PO or POCL plan into one with minimal makespan by only removing ordering constraints (called deordering) is NP-complete. We provide a series of further results on special cases and implications, such as reordering, where orderings can be changed arbitrarily.