A Generic Method to Guide HTN Progression Search with Classical Heuristics

A Generic Method to Guide HTN Progression Search with Classical Heuristics. Höller, D., Bercher, P., Behnke, G., & Biundo, S. In Proceedings of the 28th International Conference on Automated Planning and Scheduling (ICAPS 2018), pages 114–122, 2018. AAAI Press. This paper won the ICAPS 2018 Best Student Paper Award

Paper

Video of presentation doi abstract bibtex 6 downloads

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.

@InProceedings{Hoeller2018ProgressionHeuristics,
  author                    = {Daniel H{\"{o}}ller and Pascal Bercher and Gregor Behnke and Susanne Biundo},
  title                     = {A Generic Method to Guide {HTN} Progression Search with Classical Heuristics},
  booktitle                 = {Proceedings of the 28th International Conference on Automated Planning and Scheduling ({ICAPS 2018})},
  note                      = {<b><i>This paper won the ICAPS 2018 Best Student Paper Award</i></b>},
  publisher                 = {{AAAI} Press},
  year                      = {2018},
  pages                     = {114--122},
  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.},
  doi                       = {10.1609/icaps.v28i1.13900},
  url_Paper                 = {https://bercher.net/publications/2018/Hoeller2018ProgressionHeuristics.pdf},
  url_video_of_presentation = {https://www.youtube.com/watch?v=KOZuIkJaC0w},
  keywords                  = {conference}
}

Downloads: 6