A Generic Method to Guide HTN Progression Search with Classical Heuristics

Authors

  • Daniel Höller Ulm University
  • Pascal Bercher Ulm University
  • Gregor Behnke Ulm University
  • Susanne Biundo Ulm University

DOI:

https://doi.org/10.1609/icaps.v28i1.13900

Keywords:

HTN Planning, Progression, Heuristic Search

Abstract

HTN planning combines actions that cause state transition with grammar-like decomposition of compound tasks that additionally restricts the structure of solutions. There are mainly two strategies to solve such planning problems: decomposition-based search in a plan space and progression-based search in a state space. Existing progression-based systems do either not rely on heuristics (e.g. SHOP2) or calculate their heuristics based on extended or modified models (e.g. GoDeL). Current heuristic planners for standard HTN models (e.g. PANDA) use decomposition-based search. Such systems represent search nodes more compactly due to maintaining a partial order between tasks, but they have no current state at hand during search. This makes the design of heuristics difficult. In this paper we present a progression-based heuristic HTN planning system: We (1) provide an improved progression algorithm, prove its correctness, and empirically show its efficiency gain; and (2) present an approach that allows to use arbitrary classical (non-hierarchical) heuristics in HTN planning. Our empirical evaluation shows that the resulting system outperforms the state-of-the-art in HTN planning.

Downloads

Published

2018-06-15

How to Cite

Höller, D., Bercher, P., Behnke, G., & Biundo, S. (2018). A Generic Method to Guide HTN Progression Search with Classical Heuristics. Proceedings of the International Conference on Automated Planning and Scheduling, 28(1), 114-122. https://doi.org/10.1609/icaps.v28i1.13900