Abstract
Hierarchical task network (HTN) planning is wellknown for being an efficient planning approach.
This is mainly due to the success of the HTN planning system SHOP2. However, its performance depends on hand-designed search control knowledge.
At the time being, there are only very few domainindependent heuristics, which are designed for differing hierarchical planning formalisms. Here, we
propose an admissible heuristic for standard HTN
planning, which allows to find optimal solutions
heuristically. It bases upon the so-called task decomposition graph (TDG), a data structure reflecting reachable parts of the task hierarchy. We show
(both in theory and empirically) that rebuilding
it during planning can improve heuristic accuracy
thereby decreasing the explored search space. The
evaluation further studies the heuristic both in terms
of plan quality and coverage