Source-linked AI summary
Lose the Order, Keep the Hierarchy: Deordering HTN Plans
Takudzwa Togarepi, Gaspard Quenard, Damien Pellier, Humbert Fiorino
TL;DR
HTN plan deordering remains under-researched despite the importance of reducing unnecessary ordering constraints while preserving validity. This paper adapts PRF and partial weighted MaxSAT to account for hierarchical decomposition constraints and evaluates them on IPC 2023 Partial-Order HTN benchmarks. Both approaches substantially reduce ordering constraints and critical-path length, although effectiveness depends on input-plan quality and many harder instances remain unsolved.
Problem
HTN research has focused more on plan generation than post-plan optimization, and deordering under HTN decomposition constraints has not been explicitly studied.
Method
The paper adapts PRF and partial weighted MaxSAT deordering techniques to preserve hierarchical decomposition constraints in HTN plans.
Results
Both approaches significantly reduce ordering constraints and critical-path length, producing more flexible partial-order plans.
Takeaways & Limitations
HTN post-plan deordering can produce more flexible plans by removing constraints not required by hierarchy or action interactions.
Takeaways & Limitations
Effectiveness depends heavily on input sequential-plan quality, and most harder instances were unsolved.
Abstract
from arXiv · showhide
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.
Introduction
HTN research has focused more on plan generation than post-plan optimization, while deordering under hierarchical decomposition constraints remains largely unexplored. This paper adapts two classical deordering techniques to HTN planning and evaluates them against direct partial-order planning.
- Motivation: HTN research has studied plan generation extensively, but comparatively fewer works address optimization of already generated plans.Plan optimization is defined as improving a plan after generation.
- Motivation: Deordering removes unnecessary action-ordering constraints while preserving plan validity, increasing flexibility and potentially enabling parallel execution.A minimum deordering removes no further ordering constraint without invalidating the plan.
- Contribution: No prior work had explicitly studied HTN deordering under decomposition constraints, motivating adaptations of PRF and partial weighted MaxSAT methods.The paper compares its post-plan optimization with Optiplan, which generates partially ordered plans directly.
- Evaluation: The approaches are evaluated on the IPC 2023 Partial-Order HTN benchmarks against Optiplan.The evaluation applies the techniques to plans generated by PANDA.
- Results: The results show significant reductions in both ordering constraints and critical-path length after post-plan optimization.The abstract reports that critical-path improvements are less pronounced than ordering-constraint reductions.
Formalism
The paper formalizes HTN and STRIPS planning, task networks, decomposition, decomposition trees, and valid HTN solutions. Its representation preserves hierarchical ordering constraints alongside primitive-action ordering relations.
- Planning formalisms: HTN planning recursively decomposes abstract tasks into primitive tasks, while STRIPS planning represents executable actions through preconditions and effects.HTN abstract tasks cannot be executed directly; primitive tasks can modify the state.
- HTN structure: An HTN method replaces an abstract task with a task network containing primitive and/or abstract tasks.A method is a tuple (c, tn), where c is the abstract task and tn is its replacement network.
- HTN structure: A task network consists of tasks, ordering constraints, and a function assigning each task a name.A primitive task network contains only primitive tasks, and an executable network has an executable linearization.
- Decomposition: A decomposition refines an abstract task by replacing it with the task network specified by an applicable method.Repeated decomposition transforms the initial task network into a primitive task network.
- Decomposition: A decomposition tree records refinement from the initial abstract task to primitive leaves and induces a partial order over its nodes.The hierarchy induces mandatory ordering constraints that must be preserved during deordering.
- HTN solutions: A valid HTN solution is a primitive task network reachable by decomposition whose every linearization is executable and satisfies the goal.The solution is represented using primitive actions, ordering relations, and a decomposition tree.
HTN-PRF Algorithm
HTN-PRF extends the classical PRF algorithm by preserving hierarchy-induced and non-concurrency orderings while removing other constraints. It produces a valid partial-order HTN plan but does not guarantee an optimal deordering.
- Algorithm: HTN-PRF examines each ordered pair of primitive actions in an HTN solution and constructs a new ordering relation.The algorithm returns the action set, transitive ordering closure, and decomposition tree.
- Constraint preservation: The algorithm preserves an ordering when it is induced by the decomposition hierarchy or required by simple non-concurrency conditions.Non-concurrency includes interference involving an action’s additions, preconditions, and deletions.
- Constraint removal: HTN-PRF removes an ordering only when neither hierarchical constraints nor non-concurrency criteria require it.The resulting plan is partial-order while retaining the decomposition tree.
- Limitation: HTN-PRF produces a partial-order plan but does not guarantee an optimal deordering.The paper addresses this limitation with an HTN-adapted partial weighted MaxSAT approach.
HTN-MaxSAT deordering
HTN-MaxSAT formulates deordering as a partial weighted MaxSAT problem that preserves hierarchy and plan-validity constraints while optimizing removable orderings. The encoding retains all actions and uses ordering variables to represent candidate relations.
- MaxSAT formulation: HTN-MaxSAT encodes the deordering problem as a partial weighted MaxSAT instance to generate optimal deorderings.Hard clauses must be satisfied, while soft-clause weights are maximized.
- Variables: Each pair of primitive actions receives an ordering variable, while all original actions remain present in the final partial-order plan.The formulation therefore does not require action-membership variables.
- Hard constraints: Hard clauses preserve hierarchy-induced orderings and enforce acyclicity, transitivity, action placement between dummy initial and goal actions, and the absence of self-loops.The initial and goal dummy actions are denoted aI and aG.
- Causal constraints: Causal constraints require each precondition to be supported by an earlier producer without an intervening deleter.The formulation uses clauses that combine producer support with protection against deleting actions.
- Optimization objective: Soft clauses reward removing ordering constraints that are not tied to dummy actions or induced by the hierarchy.The original sequential ordering is not reversed while unnecessary constraints are removed.
Evaluation
The evaluation measures reductions in ordering constraints and critical-path length after deordering, comparing HTN-PRF and HTN-MaxSAT with Optiplan across IPC 2023 Partial-Order HTN benchmarks. Both HTN approaches substantially reduce ordering constraints, while critical-path reductions vary by domain and are constrained by unsolved instances.
- The experiments evaluate ordering constraints and critical-path length on IPC 2023 Partial-Order HTN benchmarks, using PANDA-generated plans as inputs.Results are compared with Optiplan, and domain means plus weighted values are reported.
- Table 1 compares mean ordering constraints and mean critical-path length for HTN-PRF, HTN-MaxSAT, and Optiplan.HTN-MaxSAT has marginally fewer mean ordering constraints than HTN-PRF and a slightly shorter mean critical path.
- 27.67% is the largest mean reduction in ordering constraints, achieved by HTN-MaxSAT in the Satellite domain.HTN-MaxSAT performs at least as well as HTN-PRF across domains and outperforms it in Rover by close to 9%.
- Both HTN approaches significantly reduce ordering constraints except in PCP, while Transport improvements are limited because PANDA solved few harder instances.The percentage improvements are computed relative to the original sequential plan.
- The largest critical-path reduction occurs in Rover, whereas PCP remains totally ordered with no reduction in either metric.Critical-path reductions follow a pattern similar to ordering-constraint reductions.
Conclusion
The paper presents two HTN plan-deordering approaches that preserve hierarchy-related constraints while removing unnecessary ordering constraints. Both reduce ordering constraints and critical-path length, but effectiveness depends on input-plan quality and many harder instances remain unsolved.
- HTN-PRF preserves hierarchy-enforced and concurrency-required ordering constraints, while HTN-MaxSAT guarantees a minimal deordering for a given input plan.HTN-MaxSAT formulates deordering as a partially weighted MaxSAT problem.
- Both approaches significantly reduce ordering constraints and critical-path length, producing more flexible partial-order plans.The reported effectiveness depends heavily on the quality of the input sequential plan.
- Larger reductions occur on harder instances, but most harder instances remain unsolved.This limits how broadly the observed improvements can be interpreted.