@inproceedings{13e9ad2c558242d2a986bd339700812e,
title = "On the decidability of HTN planning with task insertion",
abstract = "The field of deterministic AI planning can roughly be divided into two approaches - classical statebased 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.",
author = "Thomas Geier and Pascal Bercher",
year = "2011",
doi = "10.5591/978-1-57735-516-8/IJCAI11-327",
language = "English",
isbn = "978-1-57735-515-1",
volume = "22",
series = "IJCAI International Joint Conference on Artificial Intelligence",
publisher = "AAAI Press",
pages = "1955--1961",
booktitle = "Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence",
note = "22nd International Joint Conference on Artificial Intelligence, IJCAI 2011 ; Conference date: 16-07-2011 Through 22-07-2011",
}