A Heuristic for Optimal Total-Order HTN Planning Based on Integer Linear Programming

Abstract

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. Show more