On the Feasibility of Planning Graph Style Heuristics for HTN Planning

Authors

  • Ron Alford University of Maryland, College Park
  • Vikas Shivashankar University of Maryland, College Park
  • Ugur Kuter SIFT, LLC
  • Dana Nau University of Maryland, College Park

DOI:

https://doi.org/10.1609/icaps.v24i1.13630

Keywords:

HTN planning, Heuristics, Complexity

Abstract

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.

Downloads

Published

2014-05-10

How to Cite

Alford, R., Shivashankar, V., Kuter, U., & Nau, D. (2014). On the Feasibility of Planning Graph Style Heuristics for HTN Planning. Proceedings of the International Conference on Automated Planning and Scheduling, 24(1), 2-10. https://doi.org/10.1609/icaps.v24i1.13630

Issue

Vol. 24 (2014): Twenty-Fourth International Conference on Automated Planning and Scheduling

Section

Full Technical Papers