{"id":"fc88acd7-1ad2-4da6-b1d4-1d84555d1144","arxiv_id":"2504.16209","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"SHOPFixer, IPyHOPPER, and Rewrite correspond to three distinct definitions of HTN plan repair, with solution sets that overlap but are not equal, and with different runtime tradeoffs across benchmark domains.","lead":"This paper compares three algorithms that repair hierarchical task network (HTN) plans after execution failures, both theoretically and on benchmark problems. It shows the algorithms solve different but overlapping repair problems, which helps practitioners choose the right repair method.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The formal equality theorems (Thm 1-2) are unsupported as written: Class 3 confines repair points to T_u[⪯af], excluding ancestors of the failed action, while Algorithms 1-2 allow any ancestor of af; a minimal two-level HTN example can separate the two solution sets.","rationale":"Theorems 1-2 are the backbone of the paper's theoretical contribution; if the solution-set equalities are wrong, the Venn diagram in Fig. 2 and the qualitative explanations in Section 3 lose their formal grounding. The proofs as written do not establish those equalities because the repair-point spaces in the formal classes and in Algorithms 1-2 differ. Class 3 confines repair points to T_u[⪯af], a postorder-prefix set that, for an action af, contains no ancestor of af; the algorithms allow any ancestor of af. Replacing an ancestor can be the only way to repair and revisits decisions that the stability-oriented formal repair is not defined to revisit. There is also a state mismatch (sr versus γ(sc,T_u[≺af])) and the proof of Theorem 5 inverts the containment direction. The reader worried about the gap between nondeterministic abstraction and deterministic implementation; this concern sits one step earlier, between the formal definitions and the pseudocode that the theorems claim to characterize. The concrete two-level domain makes the discrepancy visible: with a method precondition destroyed by the disturbance, the formal class can only replace the failed primitive b, which cannot help, while Algorithm 2 can replace its ancestor U and succeed. Running that enumeration would either refute the theorems as stated or force a clarification and reproof. The empirical comparison may still be useful, but the central formal claim is not verifiable as written, so the paper should not be accepted with the current CONDITIONAL verdict; it needs a correction or a rebuttal before the theoretical contribution can be assessed.","tokens_in":17302,"tokens_out":21494,"duration_ms":210413,"concrete_test":"Construct a total-order HTN domain: initial task R; method m1 decomposes R into [a,U]; original method m2 (precondition s) decomposes U into [b,d]; alternative method m2' (no precondition) decomposes U into [e]. Actions: a pre p eff q; b pre q eff r; d pre s eff done; e pre q∧¬r eff done. Initial state {p,s}; the plan a,b,d is valid. After executing a, the disturbance deletes s, so sc={p,q,¬s}. Then pre*(b)={p,q,s} fails at sc, so the first predicted failure is af=b. Enumerate the Class 3/Class 4 repair sets: T_u[⪯b]={b}, and replacing b cannot restore s, so no Class 3 or Class 4 repair exists. Enumerate Algorithm 1/2 with its line-2 choice: ta=U, replace U by [e] via m2', applicable in sc and successful.","verdict_should_be":"UNVERDICTED","load_bearing_attack":"Section 4's central claim is the set-equality The Theorems 1 and 2 (Class 3 = SF, Class 4 = IPH). The proofs are one-paragraph 'mimicry' arguments that never align the formal repair-point definition with Algorithms 1-2. The concrete discrepancy is the repair-point space. In Class 3 (and Class 4, which inherits the repair-point definition), the repair point is any task tr in T_u[⪯af], the postorder-prefix subtree ending at af; for a failed action af, this set contains no ancestor of af. Algorithms 1 and 2 instead nondeterministically select any ancestor task 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 differ. A second discrepancy is the application state: Class 3 evaluates a replacement tree at sr, the state immediately before the chosen task, with a separate partially-executed branch, while Algorithm 2 line 2 requires applicability in γ(sc,T_u[≺af]), the state immediately before the failed action. The proof sketches do not bridge either mismatch. Theorem 2's proof also ends by saying Class 4 is equivalent to the solutions producible by SF, and Theorem 5's proof states the containment in the wrong direction. As written, the Venn diagram in Fig. 2 is not established.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":17652,"tokens_out":7909,"duration_ms":70335,"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":[{"comment":"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.","section":"Section 4, Class 3/4 vs. Algorithms 1–2"},{"comment":"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.","section":"Section 4, Class 3 starting state vs. Algorithm 2 line 2"},{"comment":"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.","section":"Section 4, Theorems 2 and 5 proofs"},{"comment":"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.","section":"Section 4, Theorem 6 proof"},{"comment":"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.","section":"Section 6, Tables 1 and S1"}],"minor_comments":[{"comment":"There is a typo: 'sophesti cated' should be 'sophisticated'.","section":"Section 1"},{"comment":"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.","section":"Section 3, Figure 3"},{"comment":"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.","section":"Section 4, Algorithms 1–2"},{"comment":"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.","section":"Section 5, Openstacks"},{"comment":"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.","section":"General"}],"recommendation":"major_revision","confidential_remarks":"The paper has a useful core idea and a substantial empirical study, but the theoretical section needs a careful rewrite. The copy-paste errors in the theorem proofs and the mismatch between the formal repair-point definition and the algorithm pseudocode suggest that the proofs were not fully checked. I would like to see the authors fix the definition/algorithm alignment, correct the proofs of Theorems 2, 5, and 6, and discuss how the reported empirical success rates can coexist with the claimed subset relations. If these points are addressed thoroughly, the paper could become a solid contribution."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague—quick take on arXiv:2504.16209. The paper compares three HTN plan repair algorithms (SHOPFixer, IPyHOPPER, Rewrite) both formally and empirically. What's genuinely new: it's the first head-to-head experimental comparison on shared benchmark domains, and it makes a useful conceptual distinction between repair-by-rewrite (RW), repair-by-restarting-at-failed-task (IPH), and repair-by-backjumping-over-causal-links (SF). The empirical section is honest about its confounds: different implementation languages, an author-written reimplementation of RW (since the original isn't available), and no released code/data. The observations that RW is slower because it replans from scratch, that SF pays overhead for causal-link analysis but scales better on harder problems, and that IPH's simple chronological backtracking wins on easy problems—these all ring true and will be cited.\n\nThe soft spot is the formal part. Theorems 1 and 2 claim that Class 3 solutions equal SF solutions and Class 4 equal IPH solutions. But the definitions don't match the algorithms. Class 3 restricts the repair point to Tu[⪯af]—the postorder prefix ending at the failed action af—which excludes any ancestor of af. Algorithms 1 and 2 explicitly nondeterministically choose any ancestor of af as the repair point. That's a real gap: an ancestor replacement can succeed where an in-prefix replacement can't. There's also a state mismatch: Class 3 evaluates replacements in sr (the state immediately before the chosen task), while the algorithms require applicability in γ(sc,Tu[≺af]), the state immediately before af. The proofs are one-paragraph mimicry arguments that never address these discrepancies. Theorem 2's proof literally says 'Class 4 is equivalent to the set of solutions producible by SF'—a copy-paste spillover, and Theorem 5's proof has the subset relation backwards mid-paragraph. So the Venn diagram in Figure 2 is not established by this paper.\n\nIs this fatal to the whole paper? Not entirely. The empirical comparison stands on its own, and the taxonomy of repair definitions is a useful organizing principle even if the set-equality claims are wrong. But the theoretical results are the paper's headline contribution, and they're currently not credible. A revision that fixes the definitions to match the algorithms (either by broadening Class 3 to allow ancestors, or by restricting the algorithms to in-prefix repairs) and gives step-level proofs would make this a solid contribution. As it stands, I'd send it to peer review but brace for major revision. The empirical part deserves a reviewer, the formal part needs rework.\n\nRecommendation: engage with it—cite the empirical comparison, be careful about citing the set relationships. Worth reading for anyone doing HTN plan repair.","headline":"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.","tokens_in":18114,"tokens_out":4891,"would_cite":true,"duration_ms":41539,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"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…","keywords":["hierarchical task network planning","plan repair","plan stability","SHOPFixer","IPyHOPPER","plan rewriting","causal-link analysis","backjumping"],"falsifier":"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.","tokens_in":17086,"feed_emoji":"🔧","tokens_out":9177,"duration_ms":71672,"temperature":0.7,"pith_summary":"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.","feed_headline":"Every SHOPFixer repair is an IPyHOPPER repair","feed_subtitle":"Maps three HTN repair algorithms to three repair classes and shows Rewrite is often the slowest.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Defines the rewrite-based plan repair problem (Class 2) that the paper implements as RW and proves theorems against.","marker":"(Höller et al. 2020b)"},{"why":"Introduces SHOPFixer with causal-link analysis and backjumping, whose solution set the paper characterizes as Class 3.","marker":"(Goldman, Kuter, and Freedman 2020)"},{"why":"Introduces IPyHOPPER and its simulation-based repair approach, whose solution set the paper characterizes as Class 4.","marker":"(Zaidins, Roberts, and Nau 2023)"},{"why":"Supplies the baseline HTN and classical planning definitions, including method preconditions, on which the pre*() function is built.","marker":"(Ghallab, Nau, and Traverso 2004)"},{"why":"Establishes plan stability and the empirical claim that repair beats replanning, the motivation for stable repair.","marker":"(Fox et al. 2006)"},{"why":"Describes the SHOP3 planner used to generate original plans and to run the RW and SF experiments.","marker":"(Goldman and Kuter 2019)"},{"why":"Presents the progression-based IPyHOP planner that IPyHOPPER augments with simulation.","marker":"(Bansod et al. 2022)"}],"fun_headline_variants":["Three repair tasks, three algorithms, one mapping","Fixing HTN plans: one task, three definitions","SHOPFixer repairs are a strict subset of IPyHOPPER's","Rewrite is often the slowest HTN repair method","Plan repair is not one problem but three"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Three repair tasks, three algorithms, one mapping","Fixing HTN plans: one task, three definitions","SHOPFixer repairs are a strict subset of IPyHOPPER's","Rewrite is often the slowest HTN repair method","Plan repair is not one problem but three"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000211,"raw_usage":{"total_tokens":1412,"prompt_tokens":937,"completion_tokens":475,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":553,"completion_tokens_details":{"reasoning_tokens":395}},"tokens_in":553,"tokens_out":475,"duration_ms":4416,"temperature":1.0,"reasoning_tokens":395,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-16T11:09:34.953988+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"P.; Kuter, U.; and Freedman, R","cited_arxiv_id":null,"evidence_quote":"Introduces SHOPFixer with causal-link analysis and backjumping, whose solution set the paper characterizes as Class 3."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Introduces IPyHOPPER and its simulation-based repair approach, whose solution set the paper characterizes as Class 4."},{"cited_title":"S.; and Traverso, P","cited_arxiv_id":null,"evidence_quote":"Supplies the baseline HTN and classical planning definitions, including method preconditions, on which the pre*() function is built."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Establishes plan stability and the empirical claim that repair beats replanning, the motivation for stable repair."},{"cited_title":"P.; and Kuter, U","cited_arxiv_id":null,"evidence_quote":"Describes the SHOP3 planner used to generate original plans and to run the RW and SF experiments."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Presents the progression-based IPyHOP planner that IPyHOPPER augments with simulation."}],"review_version":1}