Lose the Order, Keep the Hierarchy: Deordering HTN Plans

arXiv cs.AI Papers
hierarchical-task-network plan-deordering htn-planning ai-planning optimization

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.

arXiv:2609.03912v1 Announce Type: new 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.
Original Article
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

Topology-Consistent Task Planning over Cellular Workflow Complexes for LLM-based Agents

arXiv cs.AI

The paper presents TopoPlanner, a topology-consistent planning framework that lifts tool dependency graphs into cellular workflow complexes to guide LLM tool planning, enabling handling of verification-correction loops, branch merging, and reusable intermediate states beyond sequential or DAG-like workflows, with consistent gains over baselines on four benchmarks.