Pith. sign in

REVIEW 5 major objections 5 minor 21 references

HTN Plan Repair Algorithms Compared: Strengths and Weaknesses of Different Methods

T0 review · 5 major / 5 minor · reviewed 2026-08-16 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read This paper proves that three HTN plan repair algorithms—Rewrite, SHOPFixer, and IPyHOPPER—correspond to three different definitions of the repair problem, with every SHOPFixer solution also an IPyHOPPER solution and any solution that is…

desk verdict Useful empirical head-to-head, but the formal set-relationship theorems don't hold up as written—the repair-point definitions diverge from the algorithms, so the Venn diagram is unproven. read the letter →

arxiv 2504.16209 v1 pith:I5O7E7AE submitted 2025-04-22 cs.AI

Paul Zaidins , Robert P. Goldman , Ugur Kuter , Dana Nau , Mark Roberts This is my paper · ORCID
classification cs.AI
keywords hierarchicaltasknetworkplanningplanrepairstabilitySHOPFixerIPyHOPPERrewritingcausal-linkanalysisbackjumping
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper asks a practical question: when an executing hierarchical task network (HTN) plan is disrupted, what counts as a repair, and which algorithm should you use? The authors pin down three recent repair algorithms—Rewrite, SHOPFixer, and IPyHOPPER—by showing that each one embodies a different formal definition of the repair problem. They prove that the three solution sets are distinct but overlapping, with SHOPFixer's solutions a subset of IPyHOPPER's, and with any plan that is both a Rewrite solution and an IPyHOPPER solution also a SHOPFixer solution. On benchmarks from three planning domains, Rewrite is usually the slowest because it replans from scratch while forcing the executed prefix to be preserved, while causal-link analysis and backjumping help SHOPFixer on larger problems and IPyHOPPER's lightweight simulation wins on smaller ones. The upshot is that the right repair method depends on which notion of repairability an application needs.

What carries the argument

The load-bearing machinery is the recursive precondition function $pre^*$, which annotates every node of a decomposition tree with the accumulated preconditions of its ancestor methods, so that a tree—not just its action sequence—can be declared applicable in a state. Using that function, the paper partitions repair problems into Classes 2, 3, and 4, and proves that two nondeterministic recursive algorithms, SHOPFixer and IPyHOPPER, have solution sets identical to Classes 3 and 4 respectively, while Rewrite corresponds to the anomaly-repair definition of Class 2. The 'replace' operation, which swaps subtrees of the unexecuted part of the plan, carries the construction of repairs, and the inclusion theorems are established by showing that each relaxation from Class 3 to Class 4 loosens constraints without adding any.

What would settle it

Enumerate all small repair problems in a simple domain, run the actual deterministic SHOPFixer and IPyHOPPER implementations to collect every solution tree they can return, and compare those sets against the Class 3 and Class 4 definitions; a single returned tree that violates its class definition, or a class-defined repair that the implementation never finds, would refute the correspondence for the measured systems. The same comparison could be run for the inclusion theorem by searching for a tree that is simultaneously a Rewrite solution and an IPyHOPPER solution but not a SHOPFixer solution.

Watch

Extended reading notes

Core claim

The paper's central discovery is that 'fixing an HTN plan' is not one task but three, and that the three contemporary algorithms sit exactly on those three definitions. It defines Class 2 (anomaly repair), in which the domain is rewritten so the last executed action produces the observed state and the new plan must reproduce the executed action prefix; Class 3 (predicted-task-failure repair), in which the unexecuted part of the decomposition tree must be applicable in the current state, checking ancestor method preconditions; and Class 4 (predicted-action-failure repair), which checks only action preconditions. The paper proves that the set of Class 3 solutions equals the set of SHOPFixer solutions, the set of Class 4 solutions equals the set of IPyHOPPER solutions, and that SHOPFixer's solutions are strictly contained in IPyHOPPER's while Rewrite's and IPyHOPPER's overlap only inside SHOPFixer's set. Empirically, on Rovers, Satellite, and Openstacks benchmarks, Rewrite is frequently the slowest because it rederives plans, SHOPFixer's causal-link analysis and backjumping pay off on harder problems, and IPyHOPPER's minimal overhead wins on easy ones.

Load-bearing premise

The load-bearing premise is that the nondeterministic pseudocode versions of SHOPFixer and IPyHOPPER faithfully describe the deterministic implementations whose runtimes are measured; if the real search procedures explore different spaces than these abstractions, the proven coverage relationships may not apply to the reported systems.

Editorial extensions

If this is right

  • Any plan that both Rewrite and IPyHOPPER can produce is also producible by SHOPFixer, so a disagreement between Rewrite and IPyHOPPER cannot be resolved outside SHOPFixer's solution set.
  • SHOPFixer's anticipatory causal-link analysis costs runtime on small problems but narrows the search space on large ones, so applications with hard, densely constrained domains should expect SHOPFixer to pay off.
  • Rewrite's exact-prefix requirement makes it the only one of the three whose repair guarantees that the already-executed actions are literally preserved, but that same requirement makes it unable to solve problems where the repair must re-do part of the executed structure.
  • Empirically, choosing a repair algorithm is a runtime-versus-coverage tradeoff; the paper's class definitions predict which problems each algorithm will solve without running it.
  • A system that needs maximum repair coverage should prefer IPyHOPPER, since every SHOPFixer repair is available to it, while Rewrite alone will declare some repairable problems unsolvable.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Inference: Because the coverage theorems are proved for nondeterministic pseudocode, running the real implementations on exhaustively enumerable small problems and comparing their returned trees to the Class 3 and Class 4 definitions would localize any divergence between theory and measured systems.
  • Inference: The need to add a 'reset' action in Openstacks suggests that repairability is partly an artifact of how the domain is engineered, so a testable extension is to measure how each algorithm's coverage shifts as disturbances are made more or less reversible.
  • Inference: The SF ⊆ IPH inclusion suggests a hybrid repair strategy that starts with IPyHOPPER's cheap simulation and escalates to SHOPFixer-style causal-link backjumping only when the search space grows, which might combine the runtime advantage on small problems with better coverage on large ones.
  • Inference: Rewrite's ability to prove many Rovers problems unrepairable within the time limit means its compilation can serve as an unsolvability oracle for the anomaly-repair definition, a diagnostic the other two algorithms do not directly offer.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

5 major / 5 minor

Summary. The paper compares three recent HTN plan repair algorithms—SHOPFixer (SF), IPyHOPPER (IPH), and Rewrite (RW)—both theoretically and empirically. It introduces four classes of HTN plan-repair problems, claims that Class 2 corresponds to RW, Class 3 to SF, and Class 4 to IPH, and proves set relationships among the solution sets (SF ⊆ IPH, and RW ∩ IPH ⊆ SF). The empirical part reports success rates and runtimes on Rovers, Satellite, and Openstacks domains, with the main qualitative findings that RW is often slowest, SF's causal-link analysis and backjumping help on larger problems, and IPH's minimal overhead helps on smaller problems.

Significance. The conceptual framing—that the three algorithms embody three different definitions of plan repair—is valuable and, if rigorously established, would be a useful contribution to the HTN planning literature. The empirical study is broad and the paper is candid about implementation confounds such as different languages, a lifted RW implementation, and the added 'reset' operator. However, the central theoretical results are not yet reliable: the proofs of the characterization theorems are sketches, contain copy-paste errors and direction mistakes, and the definitions do not align with the algorithm pseudocode. The empirical success rates also appear to conflict with the claimed set inclusions. The paper is promising but requires a substantial revision of the theoretical section and a reconciliation of theory with the reported data.

major comments (5)
  1. [Section 4, Class 3/4 vs. Algorithms 1–2] The repair-point spaces of the formal definitions and the algorithms do not match. Class 3 says 'the repair point may be any task tr in Tu[⪯af]', and by the paper's own notation Tu[⪯af] contains only af and its postorder predecessors, not ancestors of af. Algorithms 1 and 2, however, nondeterministically choose 'any ancestor ta of af' and replace the subtree rooted at ta. An ancestor replacement can succeed where no in-prefix replacement can, so the solution sets of the definitions and the algorithms can differ. A minimal two-level HTN example can separate them. This directly undermines Theorems 1 and 2, and consequently the Venn diagram in Figure 2 is not established as written.
  2. [Section 4, Class 3 starting state vs. Algorithm 2 line 2] There is a second mismatch: Class 3 repairs using the state sr immediately before T[tr] (or sc for partially executed tr), whereas Algorithm 2 line 2 requires the replacement tree Ta to be applicable in γ(sc, Tu[≺af]), the state immediately before the failed action. When tr is an ancestor of af with executed subtasks in between, these states differ. The one-paragraph proofs of Theorems 1 and 2 never bridge this gap, so the claimed equivalence between Class 3/4 and the algorithms is unsupported.
  3. [Section 4, Theorems 2 and 5 proofs] Theorem 2's proof ends with 'Class 4 is equivalent to the set of solutions producible by SF', which appears to be a copy-paste error; it should say IPH. Theorem 5's proof contains a direction error: it asserts 'Every Class 4 solution meets the criteria of Class 3 solutions', which would imply IPH ⊆ SF, the opposite of the theorem's claim that SF ⊆ IPH. These errors, combined with the repair-point mismatch, indicate that the proof arguments are not reliable.
  4. [Section 4, Theorem 6 proof] The proof of Theorem 6 relies on the claim that 'every subtree of an applicable solution tree must be applicable'. This is false under the paper's tree-applicability definition: pre∗ includes method preconditions of ancestors up to the root, and removing a subtree can remove the context those preconditions provide. A subtree of an applicable tree is not necessarily applicable when considered as a standalone decomposition tree. The proof needs a different argument or a corrected statement.
  5. [Section 6, Tables 1 and S1] The empirical success rates appear to conflict with Theorems 5 and 6. For example, Rovers problem 5 shows RW and IPH at 100% success while SF is 94%, and problem 10 shows IPH at 74% while SF is 100%. If the theorems are about solution sets, these data require explanation: e.g., the implementations are deterministic, timeouts limit search, or the success trials for RW and IPH are not on the same instances. As written, the empirical section neither reconciles these observations nor discusses how nondeterminism and timeout interact with the set-inclusion claims.
minor comments (5)
  1. [Section 1] There is a typo: 'sophesti cated' should be 'sophisticated'.
  2. [Section 3, Figure 3] The proof of Theorems 3 and 4 refers to states s1, s2, s3 and methods m1, m2, m3, but Figure 3 is not fully labeled in the text; a reader cannot easily verify the claimed counterexample. Please add explicit state and method annotations.
  3. [Section 4, Algorithms 1–2] The pseudocode's line 4 tests 'if T′r is None', yet T′r was introduced as a decomposition tree; the possibility of None should be stated explicitly when the nondeterministic choice set is empty.
  4. [Section 5, Openstacks] The added 'reset' operator is a known confound; the paper mentions it but does not quantify how much it affects RW's success. A sensitivity analysis or at least a discussion of which trials required reset would strengthen the empirical claims.
  5. [General] The abstract and introduction use formatted names like R EWRITE and IP YHOPPER; this is visually awkward and occasionally breaks across lines. Standard 'RW', 'IPH', 'SF' notation would be clearer.

Circularity Check

1 steps flagged · score 4.0 of 10

Partial circularity: the formal Classes 3/4 are written to match SF/IPH success tests, so Theorems 1-2 are largely restatements; set-relationship theorems and benchmarks remain independent.

  1. self definitional [Section 4, 'Plan Repair Definitions' (Classes 3 and 4) and Theorems 1-2]
    "First, to enable comparison with REWRITE's definition of plan repair (Höller et al. 2020b), we formally define the notions of plan repair used by IPyHOPPER and SHOPFixer. This enables us to prove the following results: 1. The definitions correctly characterize the search spaces of IPyHOPPER and SHOPFixer."

    The classes are introduced as formalizations of the two algorithms' existing repair behavior, and their base/induction clauses are written to mirror the algorithms' success tests. Class 4's base case is 'plan(T'u) is applicable in sc' and its induction uses 'pre(a'f)' - exactly Algorithm 1 lines 6 and 9. Class 3 similarly mirrors Algorithm 2's T'u-applicability and 'pre*(a'f)' tests. Theorems 1 and 2 then assert equality by one-paragraph 'mimicry' proofs, so the claimed correspondence is largely a restatement of the definitional choices rather than an independent derivation. It is only partial circularity: Class 3/4 define the repair point as 'any task tr in Tu[⪯af]', while Algorithms 1-2 choose 'an ancestor of af', so the theorems are not fully forced and contain an unsupported gap.

full rationale

The central circularity concern is limited to the specification-to-algorithm half of the paper. The formal definitions in Section 4 are explicitly introduced as the notions of plan repair 'used by IPyHOPPER and SHOPFixer', and the base/induction tests of Classes 3 and 4 coincide with the success tests of Algorithms 2 and 1 (T'u-applicability vs plan-applicability; pre* vs pre). Theorems 1 and 2 therefore certify a correspondence that was built into the definitions, though not completely: the repair-point condition 'tr in Tu[⪯af]' differs from the algorithms' nondeterministic choice of 'an ancestor of af', so the equality claims are not a pure tautology and the one-paragraph proofs leave a genuine correctness gap (as does Theorem 2's concluding sentence, which says Class 4 equals the solutions producible by SF, and Theorem 5's reversed containment argument). Those are correctness risks, not additional circularity. Theorems 3, 4, 5, 6 and the Venn-diagram relationships among RW, SF, and IPH are substantive set-theoretic claims rather than definitions, and the empirical benchmark comparison is self-contained, uses external IPC-derived domains, and involves no fitted parameter renamed as a prediction. The self-citations to the prior SF and IPH papers are references to the objects under comparison, not load-bearing evidence for the present derivation.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

No numerical free parameters are fitted to data. The theoretical results depend on standard HTN semantics plus several modeling assumptions, most importantly that the nondeterministic pseudocode faithfully represents the implemented algorithms and that the author-written Rewrite implementation preserves the original algorithm's semantics. The empirical comparison additionally depends on benchmark-specific design choices: a 300s timeout, tailored disturbances, and an added reset operator in Openstacks.

assumptions (5)
  • domain assumption Total-order HTN planning is an adequate restriction; all three algorithms are analyzed only for total-order methods.
    Section 2 states 'We will only consider total-order HTN planning'; the theorems and empirical domains are confined to this setting, so extension to partial-order HTN planning is not established.
  • domain assumption The pre* function captures all correctness conditions for a decomposition tree, with method preconditions inherited by the first action in the method.
    Section 4 defines pre* recursively and identifies tree applicability with satisfaction of pre* at each action. The equivalence theorems (Class 3 = SF, Class 4 = IPH) rest on this definition, but actual HTN planners may check method preconditions in different ways.
  • ad hoc to paper Nondeterministic Algorithms 1 and 2 faithfully model the deterministic implementations SHOPFixer and IPyHOPPER whose runtimes are measured.
    Theorems 1 and 2 reason about nondeterministic versions; the empirical section measures the actual systems. The paper does not prove that the search behavior is identical, so theory-to-experiment transfer assumes fidelity.
  • ad hoc to paper The authors' own lifted implementation of Rewrite, using SHOP3 as the backend, preserves the semantics of Holler et al.'s original algorithm.
    Section 3 says no runnable implementation was available and the authors reimplemented it with extensions; empirical claims about Rewrite depend on this reimplementation being faithful.
  • ad hoc to paper The added 'reset' operator in Openstacks and the choice of deviations do not systematically bias the comparison.
    Section 5 says deviations were defined to avoid unsolvability and a reset operation was added; this is an ad hoc modeling decision that affects all three algorithms but may not generalize to other domains.

how reviews work

0 comments
Cite this review

Pith. "Pith review of HTN Plan Repair Algorithms Compared: Strengths and Weaknesses of Different Methods." pith.science (2026). https://pith.science/paper/I5O7E7AE

@misc{pith2026250416209,
  author       = {Pith},
  title        = {Pith review of: HTN Plan Repair Algorithms Compared: Strengths and Weaknesses of Different Methods},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/I5O7E7AE}},
  note         = {Machine review of arXiv:2504.16209}
}
read the original abstract

This paper provides theoretical and empirical comparisons of three recent hierarchical plan repair algorithms: SHOPFixer, IPyHOPPER, and Rewrite. Our theoretical results show that the three algorithms correspond to three different definitions of the plan repair problem, leading to differences in the algorithms' search spaces, the repair problems they can solve, and the kinds of repairs they can make. Understanding these distinctions is important when choosing a repair method for any given application. Building on the theoretical results, we evaluate the algorithms empirically in a series of benchmark planning problems. Our empirical results provide more detailed insight into the runtime repair performance of these systems and the coverage of the repair problems solved, based on algorithmic properties such as replanning, chronological backtracking, and backjumping over plan trees.

Figures

Figures reproduced from arXiv: 2504.16209 by the authors.

Figure 2
Figure 2. Venn diagram displaying the relationships among [PITH_FULL_IMAGE:figures/full_fig_p002_2.png] view at source ↗
Figure 1
Figure 1. States and tasks relevant for repair of T. To denote the parts of π before and after ai , we will write π[≺ ai ] = ⟨a1, . . . , ai−1⟩ and π[≻ ai ] = ⟨ai+1, . . . , an⟩. An HTN planning domain is a pair Σ = (Σc,M), where Σc is a classical planning domain and M is a set of meth￾ods (see (Ghallab, Nau, and Traverso 2004) for details). We will only consider total-order HTN planning, in which ev￾ery method’s subtasks are… view at source ↗
Figure 3
Figure 3. Example demonstrating that there are classes of [PITH_FULL_IMAGE:figures/full_fig_p005_3.png] view at source ↗
Figures from the paper (2 more)
Figure 6
Figure 6. Figure 6: Each algorithm’s runtimes in msec (semi-log plot) on the Rovers repair problems that the algorithm did not solve successfully. Problem IPH % success SF % success 3 64% 72% 5 100% 94% 6 80% 80% 10 74% 100% 13 96% 100% 20 36% 100% [PITH_FULL_IMAGE:figures/full_fig_p007_6.png]
Figure 5
Figure 5. Figure 5: Each algorithm’s runtimes in msec (semi-log plot) on the Rovers repair problems that the algorithm solved suc￾cessfully. Openstacks For Openstacks, both SF and RW solved all the repair problems. IPH solved almost all, but failed for a small number (see [PITH_FULL_IMAG…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

21 extracted references · 19 canonical work pages

  1. [1]

    , " * write output.state after.block = add.period write newline

    ENTRY address archivePrefix author booktitle chapter edition editor eid eprint howpublished institution isbn journal key month note number organization pages publisher school series title type volume year label extra.label sort.label short.list INTEGERS output.state before.all mid.sentence after.sentence after.block FUNCTION init.state.consts #0 'before.a...

  2. [2]

    write newline

    " write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 global.max substring 't := if while FUNCTION word.in bbl.in capitalize " " * FUNCT...

  3. [3]

    Ayan, F.; Kuter, U.; Yaman, F.; and Goldman, R. P. 2007. HOTRiDE: Hierarchical Ordered Task Replanning in Dynamic Environments . In ICAPS-07 Workshop PlanEx

    work page 2007

  4. [4]

    Bacchus, F.; and Yang, Q. 1992. The expected value of hierarchical problem-solving. In AAAI, 369--374. Citeseer

    work page 1992

  5. [5]

    Bansod, Y.; Patra, S.; Nau, D.; and Roberts, M. 2022. HTN Replanning from the Middle. The International FLAIRS Conference Proceedings, 35

    work page 2022

  6. [6]

    Bercher, P.; Biundo, S.; Geier, T.; Hoernle, T.; Nothdurft, F.; Richter, F.; and Schattenberg, B. 2014. Plan, Repair , Execute , Explain --- How Planning Helps to Assemble Your Home Theater . In Proceedings of ICAPS, volume 24, 386--394

    work page 2014

  7. [7]

    Bit-Monnot, A. 2023. Experimenting with Lifted Plan-Space Planning as Scheduling: Aries in the 2023 IPC. In 2023 International Planning Competition at the 33rd International Conference on Automated Planning and Scheduling

    work page 2023

  8. [8]

    Fernandez-Olivares, J.; Vellido, I.; and Castillo, L. 2021. Addressing HTN Planning with Blind Depth First Search. Proceedings of 10th International Planning Competition: Planner and Domain Abstracts--Hierarchical Task Network (HTN) Planning Track (IPC 2020), 1--4

    work page 2021

Show all 21 references
  1. [9]

    Fox, M.; Gerevini, A.; Long, D.; and Serina, I. 2006. Plan Stability: Replanning versus Plan Repair. In ICAPS

    2006

  2. [10]

    Gerevini, A.; Haslum, P.; Long, D.; Saetti, A.; and Dimopoulos, Y. 2009. Deterministic Planning in the Fifth IPC: PDDL3 and Experimental Evaluation of the Planners. AI, 173(5-6): 619--668

    2009

  3. [11]

    S.; and Traverso, P

    Ghallab, M.; Nau, D. S.; and Traverso, P. 2004. Automated Planning: Theory and Practice. Amsterdam Boston: Elsevier/Morgan Kaufmann

    2004

  4. [12]

    P.; and Kuter, U

    Goldman, R. P.; and Kuter, U. 2019. Hierarchical Task Network Planning in Common Lisp : The Case of SHOP3 . In Proceedings of the 12th European Lisp Symposium . Genova, Italy

    2019

  5. [13]

    P.; Kuter, U.; and Freedman, R

    Goldman, R. P.; Kuter, U.; and Freedman, R. G. 2020. Stable Plan Repair for State-Space HTN Planning . In HPlan 2020 Working Notes . Nancy, France

    2020

  6. [14]

    Hoffmann, J. 2011. Analyzing Search Topology without Running Any Search: On the Connection between Causal Graphs and h^* . JAIR, 41: 155--229

    2011

  7. [15]

    H \"o ller, D.; Behnke, G.; Bercher, P.; Biundo, S.; Fiorino, H.; Pellier, D.; and Alford, R. 2020 a . HDDL : An Extension to PDDL for Expressing Hierarchical Planning Problems. In Proceedings of AAAI 2020). AAAI Press

    2020

  8. [16]

    o ller, D.; Bercher, P.; Behnke, G.; and Biundo, S. 2020 b . HTN Plan Repair via Model Transformation . In Schmid, U.; Kl \

    H \"o ller, D.; Bercher, P.; Behnke, G.; and Biundo, S. 2020 b . HTN Plan Repair via Model Transformation . In Schmid, U.; Kl \"u gl, F.; and Wolter, D., eds., KI 2020: Advances in Artificial Intelligence , volume 12325 of Lecture Notes in Computer Science , 88--101. Cham: Spr...

    2020

  9. [17]

    Kambhampati, S.; and Hendler, J. A. 1992. A Validation-Structure-Based Theory of Plan Modification and Reuse. AIJ , 55: 193--258

    1992

  10. [18]

    Kuter, U. 2012. Dynamics of Behavior and Acting in Dynamic Environments: Forethought, Reaction, and Plan Repair. Technical Report 2012-1, SIFT

    2012

  11. [19]

    Long, D.; and Fox, M. 2003. The 3rd IPC : Results and Analysis . JAIR, 20: 1--59

    2003

  12. [20]

    Yang, Q. 1997. Generating Abstraction Hierarchies. Intelligent Planning: A Decomposition and Abstraction Based Approach, 189--206

    1997

  13. [21]

    Zaidins, P.; Roberts, M.; and Nau, D. 2023. Implicit Dependency Detection for HTN Plan Repair. In Proceedings of the ICAPS HPlan Workshop . Prague, Czech Republic

    2023

Pith tools

Reviewed August 16, 2026 · model on record in the stance chip above.