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

Paul Zaidins, Robert P. Goldman, Ugur Kuter, Dana Nau, Mark Roberts · 2025

Read HTN Plan Repair Algorithms Compared: Strengths and Weaknesses of Different Methods by Paul Zaidins, Robert P. Goldman, Ugur Kuter, Dana Nau, Mark Roberts (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-16209.txt.

Introduction

Paul Zaidins and four co-authors compare three algorithms that repair broken plans in hierarchical planning systems. Their 2025 paper studies HTN planning, where tasks break into subtasks, and repairs that patch a plan when the world changes mid-course. The three tools, SHOPFixer, IPyHOPPER, and Rewrite, were built on different ideas.

Theory shows the three in fact solve three different repair problems, with unlike search spaces and unlike kinds of fixes. That mismatch explains much of their varied performance. Benchmark trials then chart run times and problem coverage for each. Traits like replanning from scratch and backjumping over plan trees drive the gaps. The authors give planners a basis for picking a repair method by need.

Catalog record

CREATORPaul Zaidins, Robert P. Goldman, Ugur Kuter, Dana Nau, Mark Roberts
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE53 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2504-16209

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

HTN Plan Repair Algorithms Compared: Strengths and Weaknesses of Different Methods Paul Zaidins, Robert P. Goldman, Ugur Kuter, Dana Nau, Mark Roberts 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. 1 Introduction Dynamic control and management of plans during execution is challenging in many multi- and hierarchically-organized agent systems, e.g., military operations, warehouse automation, and other practical applications. During execution, agents’ plans may fail due to precondition failures induced by exogenous events or by actions of other agents. Fox et al. 2006 showed that in the face of disruptions, plan repair could provide new plans faster and with fewer revisions than replanning from scratch. They used the term “stability” to refer to the new plan’s similarity to the old one, by analogy to the term from control theory. Agent systems using Hierarchical Task Network (HTN) planning generate by decomposing high-level (more abstract) tasks into lower-level (less abstract) subtasks before or during execution. Generalizing stable plan repair from classical planning to HTN planning requires localization of disruptions, errors and failures in the hierarchies, and it uses problem refinement methods that take advantage of such localizations to provide better stability ( Goldman, Kuter, and Freedman 2020 ) . Early work on hierarchical plan repair introduced validation graphs to hierarchical partial-order planning, using the validation graphs to identify disruptions and make patches in the partial-order plans ( Kambhampati and Hendler 1992 ) . Several recent algorithms, namely SHOPFixer ( Goldman, Kuter, and Freedman 2020 ) , IPyHOPPER ( Zaidins, Roberts, and Nau 2023 ) , and an unnamed algorithm that we will call Rewrite ( Höller et al. 2020b ) , have developed state-of-the art plan-repair strategies. They build on several previous methods ( Ayan et al. 2007 ; Kuter 2012 ; Bansod et al. 2022 ; Bercher et al. 2014 ) . This paper analyzes the formal properties and performance of IPyHOPPER , SHOPFixer , and Rewrite . We compare them formally, and empirically evaluate their performance in a series of benchmark planning problems. The following paragraphs summarize our contributions: 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 . 2. The sets of solutions for the three algorithms are distinct but not disjoint. 3. We prove other relationships among the sets of solutions. Second, we empirically evaluate algorithm performance on three domains drawn from the International Planning Competition (IPC): Openstacks, Rovers, and Satellites. Here are our primary empirical findings: 4. Rewrite is often the slowest algorithm, because it extensively rederives plans. 5. The causal links and backjumping of SHOPFixer are useful for larger problems in improving performance by narrowing the size of the search space. 6. The chronological backtracking and simple forward simulation of IPyHOPPER can outperform more sophesticated methods for smaller problems due to its minimal overhead. 2 Preliminaries We begin with the usual classical definitions ( Ghallab, Nau, and Traverso 2004 ) , e.g., a state s is a set of ground atoms, an action a ’s preconditions are \operatorname{pre}(a) (in the general case, a First Order Logic formula), and if s satisfies \operatorname{pre}(a) then a is applicable in s and \gamma(s,a) is the resulting state. A plan is a possibly-empty action sequence \pi= \langle a_{1},\ldots,a_{n}\rangle . Applicability of \pi in a state s_{0} , and the state \gamma(s_{0},\pi) produced by applying it, are defined in the usual way. To denote the parts of \pi before and after a_{i} , we will write \pi[\prec a_{i}]=\langle a_{1},\ldots,a_{i-1}\rangle and \pi[\succ a_{i}]=\langle a_{i+1},\ldots,a_{n}\rangle. An HTN planning domain is a pair \Sigma=(\Sigma_{c},\mathcal{M}) , where \Sigma_{c} is a classical planning domain and \mathcal{M} is a set of methods (see ( Ghallab, Nau, and Traverso 2004 ) for details). We will only consider total-order HTN planning, in which every method’s subtasks are totally ordered. We let M be the set of all ground instances of the methods in \mathcal{M} . A decomposition tree (d-tree), T , represents a recursive decomposition of a task or a task sequence. For a single task t , T has a root node labeled with t . For a task sequence \tau=\langle t_{1},\ldots,t_{n}\rangle , T has an empty root node whose children are d-trees for the tasks t_{1},\ldots,t_{n} . The primitive tasks (i.e., actions) in T have no children. Each nonprimitive task t^{\prime} in T has a child node labeled with a ground method that is relevant for t^{\prime} . Each ground method m in T has a sequence of child nodes labeled with m ’s subtasks, or if m has no subtasks then it has one child node labeled by a dummy action with no preconditions and no effects (this simplifies some of the recursive definitions in the next section). We represent T ’s subtrees with the following notation. T[t] is the subtree having t as its root; T[\prec t] is the subtree containing t ’s postorder predecessors (i.e., nodes before t in a postorder traversal); T[\preceq t] is the subtree containing both T[\prec t] and t ; and T[\succ t] and T[\succeq t] work similarly. An HTN planning problem is a triple P=(\Sigma,s_{0},\tau_{0}) , where \Sigma is the HTN planning domain, s_{0} is the initial state, and \tau_{0}=\langle t_{1},\ldots,t_{n}\rangle is a (possibly empty) sequence of tasks to accomplish. A solution tree for P is a decomposition tree for \tau_{0} that is applicable in s_{0} . Suppose we have executed part of a solution tree T for P . Let \pi=\operatorname{plan}(T) be the sequence of actions at the leaves of T , a_{c} be the last executed action, and s_{c} be the current state (see Figure 1 ), which will equal \gamma(s_{0},\pi[\preceq a_{c}]) unless a disruption occurs. Then the executed and unexecuted parts of T are T_{x}=T[\preceq a_{c}] and T_{u}=T[\succ a_{c}] , and the executed and unexecuted parts of \pi are \pi_{x}=\pi[\preceq a_{c}]=\operatorname{plan}(T_{x}) and \pi_{u}=\pi[\succ a_{c}]=\operatorname{plan}(T_{u}) . A task t in T is fully executed if T[t] is a subtree of T[\preceq a_{c}] , unexecuted if T[t] is a subtree of T[\succ a_{c}] , and partially executed otherwise. Figure 1: States and tasks relevant for repair of T . 3 HTN Plan Repair Algorithms Differences among the three algorithms color the experimental results and are critical to their interpretation. Briefly: • Because Rewrite (or RW for short) always respects \pi_{x} , it considers unsolvable

Read the complete text