Bound to Plan: Exploiting Classical Heuristics via Automatic Translations of Regularizable HTN Problems. Ron Alford, G. B., Daniel H�ller, P. B., & Susanne Biundo, D. A. .
abstract   bibtex   
Hierarchical Task Network (HTN) Planning is an expressive formalism used to encode domain-specific search control knowledge and to reason about procedural structures. Yet the cornucopia of modern heuristic search techniques remains largely unincorporated in current HTN planners, in part because these search techniques rely on size-bounded data structures that do not exist for all HTN problems. However, many HTN problems are either tail-recursive, allowing SHOP2-style progression-based HTN planners to reason about relatively small task networks, or acyclic, which provides termination guarantees for decomposition planners such as PANDA. We formally define size bounds for HTN progression, and show that we can find the minimum and maximum progression bound for acyclic and tail-recursive HTN problems in polynomial time. This allows us to provide three automatic translations of tail-recursive HTN problems to PDDL: linear and quadratic STRIPS translations of totally-ordered and partially-ordered problems, respectively, and a linear translation of partially-ordered problems for ADL-capable planners. Finally, we show that PDDL planners can efficiently plan with this translated HTN knowledge on a variety of domains.
@inproceeduings {icaps16-148,
  track    = {Main Track},
  title    = {Bound to Plan: Exploiting Classical Heuristics via Automatic Translations of Regularizable HTN Problems},
  author   = {Ron Alford, Gregor Behnke, Daniel H�ller, Pascal Bercher, Susanne Biundo, David Aha},
  abstract = {Hierarchical Task Network (HTN) Planning is an expressive formalism used to encode domain-specific search control knowledge and to reason about procedural structures. Yet the cornucopia of modern heuristic search techniques remains largely unincorporated in current HTN planners, in part because these search techniques rely on size-bounded data structures that do not exist for all HTN problems. However, many HTN problems are either tail-recursive, allowing SHOP2-style progression-based HTN planners to reason about relatively small task networks, or acyclic, which provides termination guarantees for decomposition planners such as PANDA. We formally define size bounds for HTN progression, and show that we can find the minimum and maximum progression bound for acyclic and tail-recursive HTN problems in polynomial time. This allows us to provide three automatic translations of tail-recursive HTN problems to PDDL: linear and quadratic STRIPS translations of totally-ordered and partially-ordered problems, respectively, and a linear translation of partially-ordered problems for ADL-capable planners. Finally, we show that PDDL planners can efficiently plan with this translated HTN knowledge on a variety of domains.},
  keywords = {Classical planning,Search techniques,HTN and knowledge-based planning,Complexity analysis}
}
Downloads: 0