Lose the Order, Keep the Hierarchy: Deordering HTN Plans

• URL: http://arxiv.org/abs/2609.03912v1
• Date: Thu, 03 Sep 2026 14:27:58 GMT
• Title: Lose the Order, Keep the Hierarchy: Deordering HTN Plans
• Abstract summary: Hierarchical Task Network (HTN) planning is a powerful planning formalism based on task decomposition.<n>Plan deordering has been extensively studied in classical planning but remains under-researched in the HTN setting.<n>We adapt two established plan deordering techniques from classical planning by extending the techniques to account for hierarchical decomposition constraints.
• Score: 0.7773045483342574
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Contrastive Energy Fields for Inference-Time Procedure Planning in Instructional Videos [48.22554718706414]
  We propose CEFITO, a procedure planning approach that learns a predictor to express an action-conditioned representation space.<n>Unlike prior methods, CEFITO explicitly reasons over the action space by omitting irrelevant actions during inference-time planning.
  arXiv  Detail & Related papers  (2026-08-17T11:56:11Z)
• PlanningBench: Generating Scalable and Verifiable Planning Data for Evaluating and Training Large Language Models [52.48858778580074]
  Planning is a fundamental capability for large language models (LLMs)<n>PlanningBench is a framework for generating scalable, diverse, verifiable planning data for both evaluation and training.
  arXiv  Detail & Related papers  (2026-05-20T08:10:15Z)
• Satisficing and Optimal Generalised Planning via Goal Regression (Extended Version) [16.43772461453855]
  Generalised planning (GP) refers to the task of synthesising programs that solve families of related planning problems.<n>We introduce a novel, yet simple method for GP: given a set of training problems, for each problem, compute an optimal plan for each goal atom in some order.<n>We formalise and prove the conditions under which our method is guaranteed to learn valid generalised plans and state space pruning axioms for search.
  arXiv  Detail & Related papers  (2025-11-14T09:16:32Z)
• DeepPlanner: Scaling Planning Capability for Deep Research Agents via Advantage Shaping [74.34061104176554]
  We propose DeepPlanner, an end-to-end RL framework that effectively enhances the planning capabilities of deep research agents.<n>Our approach shapes token-level advantage with an entropy-based term to allocate larger updates to high entropy tokens, and selectively upweights sample-level advantages for planning-intensive rollouts.
  arXiv  Detail & Related papers  (2025-10-14T20:47:05Z)
• HyperTree Planning: Enhancing LLM Reasoning via Hierarchical Thinking [109.09735490692202]
  We propose HyperTree Planning (HTP), a novel reasoning paradigm that constructs hypertree-structured planning outlines for effective planning.<n> Experiments demonstrate the effectiveness of HTP, achieving state-of-the-art accuracy on the TravelPlanner benchmark with Gemini-1.5-Pro, resulting in a 3.6 times performance improvement over o1-preview.
  arXiv  Detail & Related papers  (2025-05-05T02:38:58Z)
• Improving Plan Execution Flexibility using Block-Substitution [0.0]
  Partial-order plans in AI planning facilitate execution flexibility due to their less-constrained nature. Plan deordering removes unnecessary action orderings within a plan, while plan reordering modifies them arbitrarily to minimize action orderings. This study, in contrast with traditional plan deordering and reordering strategies, improves a plan's flexibility by substituting its subplans with actions outside the plan for a planning problem.
  arXiv  Detail & Related papers  (2024-06-05T09:30:48Z)
• Some Orders Are Important: Partially Preserving Orders in Top-Quality Planning [15.20541905857507]
  We propose specifying a subset of actions the orders between which are important, interpolating between the top-quality and unordered top-quality planning problems. We explore the ways of adapting partial order reduction search pruning techniques to address this new computational problem.
  arXiv  Detail & Related papers  (2024-04-01T22:10:12Z)
• Planning as In-Painting: A Diffusion-Based Embodied Task Planning Framework for Environments under Uncertainty [56.30846158280031]
  Task planning for embodied AI has been one of the most challenging problems. We propose a task-agnostic method named 'planning as in-painting' The proposed framework achieves promising performances in various embodied AI tasks.
  arXiv  Detail & Related papers  (2023-12-02T10:07:17Z)
• Lifted Sequential Planning with Lazy Constraint Generation Solvers [28.405198103927955]
  This paper studies the possibilities made open by the use of Lazy Clause Generation (LCG) based approaches to Constraint Programming (CP) We propose a novel CP model based on seminal ideas on so-called lifted causal encodings for planning as satisfiability. We report that for planning problem instances requiring fewer plan steps our methods compare very well with the state-of-the-art in optimal sequential planning.
  arXiv  Detail & Related papers  (2023-07-17T04:54:58Z)
• Divide-and-Conquer Monte Carlo Tree Search For Goal-Directed Planning [78.65083326918351]
  We consider alternatives to an implicit sequential planning assumption. We propose Divide-and-Conquer Monte Carlo Tree Search (DC-MCTS) for approximating the optimal plan. We show that this algorithmic flexibility over planning order leads to improved results in navigation tasks in grid-worlds.
  arXiv  Detail & Related papers  (2020-04-23T18:08:58Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.