Lose the Order, Keep the Hierarchy: Deordering HTN Plans
Summary
This paper adapts two plan deordering techniques from classical planning to hierarchical task network planning, showing a substantial reduction in ordering constraints while maintaining plan validity.
View Cached Full Text
Cached at: 09/04/26, 06:14 AM
# Lose the Order, Keep the Hierarchy: Deordering HTN Plans Source: [https://arxiv.org/abs/2609.03912](https://arxiv.org/abs/2609.03912) [View PDF](https://arxiv.org/pdf/2609.03912) > Abstract:Hierarchical Task Network \(HTN\) planning is a powerful planning formalism based on task decomposition\. Although most of the literature studied plan generation, comparatively less attention has been paid to post\-plan optimization\. In particular, plan deordering has been extensively studied in classical planning but remains under\-researched in the HTN setting\. Plan deordering removes unnecessary ordering constraints between actions in a plan whilst keeping the plan valid\. In this paper, we adapt two established plan deordering techniques from classical planning by extending the techniques to account for hierarchical decomposition constraints\. We evaluate our proposed approaches on the IPC 2023 Partial\-Order HTN benchmarks and we compare them against Optiplan, an HTN planner that generates partially ordered plans directly\. Our results show a substantial reduction in number of ordering constraints in both our implementations\. Although we also observe a reduction in critical path length, the improvements are less pronounced\. ## Submission history From: Damien Pellier \[[view email](https://arxiv.org/show-email/d87f68ae/2609.03912)\] **\[v1\]**Thu, 3 Sep 2026 14:27:58 UTC \(17 KB\)
Similar Articles
Towards Numerical TOHTN Planning with SMT-based HTN-SAT Encoding
This paper investigates numerical Totally-Ordered HTN planning by extending SAT-based encodings with SMT to handle numeric fluents, introduces a benchmark suite, and shows competitive performance as a baseline for future work.
Learning and Reusing Policy Decompositions for Hierarchical Generalized Planning with LLM Agents
This paper introduces HCL-GP, a dynamic policy-learning framework that integrates generalized planning and hierarchical task decomposition to enable LLM-based agents to learn and reuse executable policy components, significantly improving performance on the AppWorld benchmark.
Do Agents Need to Plan Step-by-Step? Rethinking Planning Horizon in Data-Centric Tool Calling
This paper argues that full-horizon planning with lazy replanning is more efficient than step-by-step execution for data-centric LLM agent tasks, using fewer tokens while maintaining accuracy.
Hierarchical Decision Making with Structured Policies: A Principled Design via Inverse Optimization
This paper proposes a principled hierarchical RL-OC framework that uses inverse optimization to design the lower-level policy objective from expert demonstrations, ensuring alignment with long-term task goals. It outperforms baselines on resource allocation and collision avoidance tasks.
Learning a hierarchy
OpenAI research proposes hierarchical reinforcement learning where agents break down complex tasks into sequences of high-level actions rather than low-level ones, significantly improving efficiency for long-horizon tasks by reducing search complexity from thousands of steps to dozens.