Lose the Order, Keep the Hierarchy: Deordering HTN Plans
Takudzwa Togarepi, Gaspard Quenard, Damien Pellier, Humbert Fiorino
cs.AI
Quick verdict
Adapts PRF and MaxSAT deordering to HTN plans, cutting constraints ~10% and critical path ~11% on 71 IPC 2023 tasks; promising but small-scale.
Summary
This method paper brings plan deordering—removing unnecessary ordering constraints from a valid plan—to HTN planning, where the authors argue it has not been explicitly studied. They adapt two classical techniques. HTN-PRF extends Bäckström's (1998) PRF algorithm: an ordering between two primitive actions is kept only if the decomposition tree mandates it or the pair fails a simple-concurrency (interference) test. HTN-MaxSAT reformulates deordering as partial weighted MaxSAT, extending Muise, McIlraith, and Beck (2012): hard clauses preserve hierarchy-mandated orderings, precondition support via adders/deleters, transitivity, and the original order direction, while soft clauses minimize remaining constraints, yielding a guaranteed minimal deordering for a fixed action set. Sequential plans from PANDA on the IPC 2023 Partial-Order HTN benchmarks serve as input; Optiplan, which emits partially ordered plans directly, is the baseline. Across 71 instances in five domains (PCP, Rover, Satellite, Transport, Um-Translog), both methods cut mean ordering constraints by 9.84% (HTN-PRF) and 9.99% (HTN-MaxSAT) and mean critical path by 10.91%/11.03%; the largest reduction is Satellite (27.67% constraints), while PCP shows no reduction. Both stay below Optiplan's 137.90 mean constraints in aggregate, but Optiplan's plans are longer and it is actually ahead in Satellite, Transport and Um-Translog, so the comparison is not like-for-like. Main limitations: small per-domain samples (Rover n=4), means without variance or significance tests, no runtime reporting for the deordering step, and no analysis of why PCP is fully incompressible.
Review complete
Assessment at a glance
5
risk flags identified
● high 0
● medium 2
● low 3
4 strengths · 4 weaknesses · 5 author questions
AI text signal = Binoculars zero-shot detector score over 20 sampled passages (Fast-DetectGPT co-reported) — absence does not prove human authorship, and a flag does not imply misconduct.
Levels reflect verification complexity — not a quality score. Evolve never rates your paper.
Key claims under review
- Plan deordering had not been explicitly studied under HTN decomposition constraints, and this paper provides the first adaptation of established classical techniques (PRF and MaxSAT) to that setting.
- Both HTN-PRF and HTN-MaxSAT preserve decomposition-mandated orderings (≺H) while removing constraints not needed for causal or hierarchical validity, keeping plans valid HTN solutions.
- On the IPC 2023 Partial-Order HTN benchmarks (71 instances, five domains), the methods cut mean ordering constraints by 9.84%/9.99% and mean critical path by 10.91%/11.03% relative to the input PANDA plans.
- HTN-MaxSAT produces minimal deorderings and matches or beats HTN-PRF in every domain, most visibly in Rover (26.92% vs 17.95% constraint reduction).
- Post-hoc deordering of PANDA plans yields fewer mean constraints in aggregate than plans generated directly by Optiplan (137.90), although Optiplan's plans are longer.
Strengths
Real, underexplored problem with a clean formal treatment
The paper positions HTN deordering as unstudied (citing the Bercher-Haslum-Muise 2024 survey framing) and cleanly extends the Geier-Bercher (2011) formalism: the decomposition-tree-induced mandatory orderings (≺H ⊆ Dt) are made explicit and injected into both algorithms, which is the core conceptual step.
Two complementary methods with an optimality guarantee
HTN-PRF (Algorithm 1) is a cheap greedy pass; HTN-MaxSAT (Eqs. 1-8) guarantees minimal deordering via hard clauses for hierarchy, transitivity, and causal support (γ over adders/deleters) and soft clauses minimizing constraints. The data supports the expected ordering: HM ≥ HP everywhere, with the largest gap in Rover (26.92% vs 17.95% constraint reduction).
Internally consistent, transparent evaluation
Conservative tone in claims
Weaknesses
Optiplan comparison conflates plan length with deordering quality
No statistical reporting
No runtime or scalability data for the contribution itself
Coverage and validity checks
Full Review Report
$1.99 · one-timeUnlock the complete preliminary analysis Evolve produced for this paper.
Report preview
Scope & Claims
The paper addresses post-plan optimization for Hierarchical Task Network (HTN) planning, specifically **plan deordering**: removing unnecessary ordering constraints between primitive actions of an already-generated plan while keeping it valid. The authors claim — consistently with the Bercher, Haslum, and Muise (2024) survey framing they cite — that deordering has not been explicitly studied under HTN decomposition constraints. Two contributions follow: (1) **HTN-PRF**, adapting Bäckström's (1998) PRF algorithm, which keeps an ordering only if the decomposition tree mandates it (≺H) or the pair fails the simple-concurrency test of Definition 6 (Algorithm 1); (2) **HTN-MaxSAT**, a partial weighted MaxSAT encoding extending Muise, McIlraith, and Beck (2012): hard clauses preserve hierarchy orderings (Eq. 1), enforce irreflexivity, aI/aG anchoring, and transitivity (Eqs. 2-4), enforce causal support via adders/deleters (Eqs. 5-6) and forbid reversal of the input order (Eq. 7); soft clauses (Eq. 8) minimize remaining constraints, guaranteeing a minimal deordering for a fixed action set. The claims are modest and mostly supported by the data.
The remaining sections cover Methodology Assessment, Statistical Evidence, Results & Reproducibility, Limitations & Risks, and Verdict & Recommendations.
- All 4 strengths & 4 weaknesses, analyzed in detail
- 5 risk flags with severity, section & reviewer questions
- Methods & statistical evidence assessment
- 5 questions a peer reviewer would ask
- Full six-dimension evaluation report & recommendations
One-time purchase · this paper only
One-time purchase, this paper only. AI-generated preliminary analysis — not peer review.
Frequently asked questions
What is HTN plan deordering?
It is a post-plan optimization that removes unnecessary ordering constraints between actions of an already-generated HTN plan while keeping the plan valid. Orderings mandated by the hierarchical decomposition (methods) are always preserved; only orderings not required by causal interference are dropped, producing flexible partial-order plans that permit more parallel execution.
How much improvement does the paper report?
On 71 IPC 2023 Partial-Order HTN instances across five domains, the two methods reduced mean ordering constraints by 9.84% and 9.99% and mean critical path length by 10.91% and 11.03%. Gains varied widely: up to 27.67% constraint reduction in Satellite, but exactly zero improvement in the PCP domain.
Is the code and benchmark data available?
Yes. The implementation is public on GitHub (gaspard-quenard/sibylsat, deordering branch), the input plans come from the publicly available PANDA planner, and the benchmarks are the public IPC 2023 Partial-Order HTN set.
How does this compare with Optiplan?
Optiplan generates partially ordered plans directly during planning. The deordered PANDA plans have fewer mean constraints in aggregate (120.72/120.52 vs 137.90), but Optiplan's plans are longer, and per domain Optiplan is actually ahead in Satellite, Transport and Um-Translog — so the comparison mostly reflects plan-generation strategy rather than deordering quality.
About this review
This is an AI-generated preliminary review by Evolve.Pub, produced from the openly available text of the paper. It is not peer review and does not represent the authors' views. The canonical record of the paper is at the publisher link above.
- MaxSAT clauses (5)-(6) and the γ definition are garbled by PDF extraction (boolean/set operators mangled); the review relies on the surrounding prose, which states their intended semantics (deleter exclusion between adder and consumer, and full precondition support) unambiguously. The rest of the text, including all tables, extracted cleanly through the references with no truncation.
Go deeper on this paper
Wrote a paper? Stress-test it before reviewers do.
Upload your manuscript for the same structured scrutiny — reasoning, statistics, evidence, figures, and reproducibility.