An ILP Heuristic for Total-Order HTN Planning

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 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. Our current heuristic proves to be more efficient than the one we build on, though it still performs worse than other existing (admissible) heuristics.