Compiling HTN Plan Verification Problems into HTN Planning Problems

Authors

  • Daniel Höller Saarland University, Saarland Informatics Campus, Saarbrücken, Germany
  • Julia Wichlacz Saarland University, Saarland Informatics Campus, Saarbrücken, Germany
  • Pascal Bercher The Australian National University, Canberra, Australia
  • Gregor Behnke University of Freiburg, Freiburg, Germany University of Amsterdam, ILLC, The Netherlands

Keywords:

Plan Verification, HTN Planning, Problem Compilation

Abstract

Plan Verification is the task of deciding whether a sequence of actions is a solution for a given planning problem. In HTN planning, the task is computationally expensive and may be up to NP-hard. However, there are situations where it needs to be solved, e.g. when a solution is post-processed, in systems using approximation, or just to validate whether a planning system works correctly (e.g. for debugging or in a competition). There are verification systems based on translations to propositional logic and on techniques from parsing. Here we present a third approach and translate HTN plan verification problems into HTN planning problems. These can be solved using any HTN planning system. We collected a new benchmark set based on models and results of the 2020 International Planning Competition. Our evaluation shows that our compilation outperforms the approaches from the literature.

Downloads

Published

2022-06-13

How to Cite

Höller, D., Wichlacz, J., Bercher, P., & Behnke, G. (2022). Compiling HTN Plan Verification Problems into HTN Planning Problems. Proceedings of the International Conference on Automated Planning and Scheduling, 32(1), 145-150. Retrieved from https://ojs.aaai.org/index.php/ICAPS/article/view/19795