How Good is Perfect? On the Incompleteness of A* for Total-Order HTN Planning

Abstract

This paper reveals the inherent limitations of A* in HTN planning by identifying various cycle types induced by the task hierarchy and analyzing their effects on the termination of the algorithm. We prove that A* even with the perfect heuristic, and for the special case of totally ordered problems, which are known to be decidable, is incomplete. An especially interesting results is that having a visited list (i.e., graph search) with the null heuristic has better termination guarantees than tree search with the perfect heuristic. We provide a polynomial-time test for detecting those cycles that render A* incomplete, and analyzed all existing benchmark domains from the most-recent international planning competition. Results show that in more than half of all domains, A* tree search would be incomplete even with the perfect heuristic, and in roughly 40% of cases A* graph search might also be incomplete depending on the provided heuristic function. We also point to a normal form that preserves semantics and guarantees completeness of the resulting models, though implementation and testing remains for future work.