PSPACE Planning With Expressivity Beyond STRIPS: Plan Constraints via Unordered HTNs, ILPs, Numerical Goals, and More

To better capture real-world problems, Hierarchical Task Network (HTN) planning and numerical planning provide enhanced modeling capabilities over classical planning. However, the plan existence problem in these formalisms is generally undecidable. We identify restricted fragments that remain PSPACE-complete, matching the complexity of classical planning, while being more expressive. The most important result proves that plan existence in unordered HTN planning, i.e. ignoring all ordering relations, is PSPACEcomplete. The result motivates a strong preference for unordered HTN models, a largely ignored fragment that deserves more attention. To bridge the gap between the tractable fragments of numerical and HTN planning, we introduce new formalisms that use Integer Linear Programs, Presburger formulas, and grammatical constraints to express action sequence restrictions within PSPACE, offering practical alternatives when the HTN structure is too complex to model.