Landmark Generation in HTN Planning

Authors

  • Daniel Höller Saarland University, Saarland Informatics Campus, Saarbrücken, Germany
  • Pascal Bercher The Australian National University, College of Engineering and Computer Science, Canberra, Australia

DOI:

https://doi.org/10.1609/aaai.v35i13.17405

Keywords:

Other Foundations of Planning, Routing & Scheduling, Deterministic Planning

Abstract

Landmarks (LMs) are state features that need to be made true or tasks that need to be contained in every solution of a planning problem. They are a valuable source of information in planning and can be exploited in various ways. LMs have been used both in classical and hierarchical planning, but while there is much work in classical planning, the techniques in hierarchical planning are less evolved. We introduce a novel LM generation method for Hierarchical Task Network (HTN) planning and show that it is sound and incomplete. We show that every complete approach is as hard as the co-class of the underlying HTN problem, i.e. coNP-hard for our setting (while our approach is in P). On a widely used benchmark set, our approach finds more than twice the number of landmarks than the approach from the literature. Though our focus is on LM generation, we show that the newly discovered landmarks bear information beneficial for solvers.

Downloads

Published

2021-05-18

How to Cite

Höller, D., & Bercher, P. (2021). Landmark Generation in HTN Planning. Proceedings of the AAAI Conference on Artificial Intelligence, 35(13), 11826-11834. https://doi.org/10.1609/aaai.v35i13.17405

Issue

Section

AAAI Technical Track on Planning, Routing, and Scheduling