On the Decidability of HTN Planning with Task Insertion
Thomas Geier and Pascal Bercher
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 into the task network generated by task decomposition, one obtains a form of planning often referred to as ``hybrid planning''. We provide a theorem that yields an upper complexity bound for the plan existence problem for HTN planning with task insertion and thus show its decidability.