
252 Chapter 11 Hierarchical Task Network Planning
Table
11.1 Complexity of plan-existence for HTN planning.
Restrictions Must the
on nonprimitive HTNs be Are variables allowed?
tasks totally ordered? No Yes
No Undecidable
a
Undecidable
a,b
None Yes In exptime;indexptime;
d
pspace-hard expspace-hard
“Regularity” (≤ 1
nonprimitive task, Does not pspace- expspace-
which must follow matter complete complete
c
all primitive tasks)
No nonprimitive No np-complete np-complete
tasks Yes Polynomial time np-complete
a
Decidable if we impose acyclicity restrictions.
b
Undecidable even when the planning domain is fixed in advance.
c
In pspace when the planning domain is fixed in