On the Decidability of HTN Planning with Task Insertion

Geier, Thomas; Bercher, Pascal

doi:10.5591/978-1-57735-516-8/IJCAI11-327

On the Decidability of HTN Planning with Task Insertion

Thomas Geier, Pascal Bercher

Download BibTeX Cite

Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence. Pages 1955-1960.

https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-327

Abstract

The field of deterministic AI planning can roughly be divided into two approaches - classical state-based planning and hierarchical task network (HTN) planning. The plan existence problem of the former is known to be decidable while it has been proved undecidable for the latter. When extending HTN planning by allowing the unrestricted insertion of tasks and ordering constraints, one obtains a form of planning which is often referred to as hybrid planning. We present a simplified formalization of HTN planning with and without task insertion. We show that the plan existence problem is undecidable for the HTN setting without task insertion and that it becomes decidable when allowing task insertion. In the course of the proof, we obtain an upper complexity bound of EXPSPACE for the plan existence problem for propositional HTN planning with task insertion.

Thomas Geier, and Pascal Bercher. 2011. On the Decidability of HTN Planning with Task Insertion. In Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11. IJCAI, 1955–1960. https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-327

@inproceedings{ijcai2011p327,
  title     = {On the Decidability of HTN Planning with Task Insertion},
  author    = {Geier, Thomas and Bercher, Pascal},
  booktitle = {Proceedings of the Twenty-Second International Joint Conference on
               Artificial Intelligence, {IJCAI-11}},
  publisher = {AAAI Press/International Joint Conferences on Artificial Intelligence},
  editor    = {Toby Walsh},
  pages     = {1955--1960},
  year      = {2011},
  month     = {7},
  doi       = {10.5591/978-1-57735-516-8/IJCAI11-327},
  url       = {https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-327},
}

TY  - CPAPER
TI  - On the Decidability of HTN Planning with Task Insertion
AU  - Geier, Thomas
AU  - Bercher, Pascal
T2  - Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11
PB  - AAAI Press/International Joint Conferences on Artificial Intelligence
PY  - 2011
SP  - 1955
EP  - 1960
DO  - 10.5591/978-1-57735-516-8/IJCAI11-327
UR  - https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-327
ER  -