AAAI Publications, Twenty-Fourth International Conference on Automated Planning and Scheduling

Font Size: 
On the Feasibility of Planning Graph Style Heuristics for HTN Planning
Ron Alford, Vikas Shivashankar, Ugur Kuter, Dana Nau

Last modified: 2014-05-10


In classical planning, the polynomial-time computability of propositional delete-free planning (planning with only positive effects and preconditions) led to the highly successful Relaxed Graphplan heuristic. We present a hierarchy of new computational complexity results for different classes of propositional delete-free HTN planning, with two main results: We prove that finding a plan for the delete-relaxation of a propositional HTN problem is NP-complete: hence unless P=NP, there is no directly analogous GraphPlan heuristic for HTN planning. However, a further relaxation of HTN planning (delete-free HTN planning with task insertion) is polynomial-time computable. Thus, there may be a possibility of using this or other relaxations to develop search heuristics for HTN planning.


HTN planning; Heuristics; Complexity

Full Text: PDF