I Always Told My Mom That Order Is Overrated: Unordered HTN Planning Is in PSPACE and Models Problems Beyond STRIPS

Abstract

Hierarchical Task Network planning is (in)famous for offering great modeling power but making plan existence undecidable. To lift the computational barrier, it is common to enforce orders between all tasks, which allows for an EXPTIME computation. We show that the opposite extreme, using no ordering constraints, reduces complexity further to PSPACE. This unites benefits of STRIPS and HTN planning in a single formalism: It matches the complexity of STRIPS planning while provably giving modelers more expressive power. We observe the same benefit for more, partially new, planning formalisms along the way to the main result. This motivates that these formalisms have similar merit on their own.