The performance of a heuristic search depends substantially on the quality of its heuristic functions. A preferred heuristic is accurate, fast to query, and takes little memory. Recent research has explored two routes for building highperformance heuristics. Memory-based heuristics use a precomputed database containing optimal distances between a set of pivot states and all other states in the search graph. More pivot states tend to increase heuristic accuracy while slowing down heuristic computation and increasing memory cost. Alternatively, formula-based heuristics produced via program synthesis capture information about the search graph in short, human-readable formulae. These formulae have negligible memory cost and are fast to query, but generally perform worse than a memory-based heuristic. This paper presents the first empirical comparison between the two approaches for pathfinding. We find that formulabased heuristics can yield better performance than memorybased heuristics with a small number of pivots while being still more compact. With more pivots memory-based heuristics yield better speed-ups but take orders of magnitude more memory. We then investigate the degradation of search performance as the map changes and find that the performance of formula-based heuristics degrades more gracefully than that of memory-based heuristics.

In this paper, we consider the plan verification problem for totally ordered (TO) HTN planning. The problem is proved to be solvable in polynomial time by recognizing its connection to the membership decision problem for context-free grammars. Currently, most HTN plan verification approaches do not have special treatments for the TO configuration, and the only one features such an optimization still relies on an exhaustive search. Hence, we will develop a new TOHTN plan verification approach in this paper by extending the standard CYK parsing algorithm which acts as the best decision procedure in general.

The problem of hierarchical plan verification focuses on checking whether an action sequence is a valid hierarchical plan the action sequence is executable and a goal task can be decomposed into it. The existing parsing-based verifier works on lifted domain models. In this paper we study whether grounding of the models could improve efficiency of the verifier. We also explore additional implementation improvements to increase the speed of the verifier.

There are multiple formalisms describing hierarchical planning domain models, however many of them do not show semantics of some features such as empty decomposition methods and extensive constraints. In this short paper we describe the semantics of a hierarchical domain model with these extensive constraints and show how empty decomposition methods would work within it. We also compare this model with other models and present some transformations of model properties.

Verifying HTN plans is an intractable problem with two existing approaches to solve the problem. One technique is based on compilation to SAT. Another method is using parsing, and it is currently the fastest technique for verifying HTN plans and the only technique supporting state constraints. In this paper, we propose an extension of the parsing-based approach to verify totally-ordered HTN plans more efficiently. This problem is known to be tractable if no state constraints are included, and we show theoretically and empirically that the modified parsing approach achieves better performance than the currently fastest HTN plan verifier when applied to totally-ordered HTN plans.

Hierarchical task network (HTN) planning is a model-based approach to planning. The HTN domain model consists of tasks and methods to decompose them into subtasks until obtaining primitive tasks (actions). There are recent methods for verifying if a given action sequence is a valid HTN plan. However, if the plan is invalid, all existing verification methods only say so without explaining why the plan is invalid. In the paper, we propose a method that corrects a given action sequence to form a valid HTN plan by deleting the minimal number of actions. This plan correction explains what is wrong with a given action sequence concerning the HTN domain model.

Hierarchical Task Networks were proposed as a method to describe plans by decomposition of tasks to subtasks until primitive tasks, actions, are obtained. Valid plans - sequences of actions - must adhere both to causal dependencies between the actions and to the structure given by the decomposition of the goal task. Plan verification aims at finding if a given plan is valid, that is, if it is causally consistent and it can be obtained by decomposition of some task. The paper describes a novel parsing-based approach for hierarchical plan verification that is orders of magnitude faster than existing methods.