arXiv:2504.16209v1 Announce Type: new
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.
Comparing Hierarchical Plan Repair Algorithms
In this paper, we delve into a comparison of three hierarchical plan repair algorithms: SHOPFixer, IPyHOPPER, and Rewrite. By examining the theoretical and empirical aspects of these algorithms, we gain a deeper understanding of their search spaces, problem-solving capabilities, and the types of repairs they can perform. This multi-disciplinary analysis is crucial for selecting the most suitable repair method for various applications.
Theoretical Comparisons
Our theoretical investigation reveals that each algorithm addresses a distinct definition of the plan repair problem. This fundamental discrepancy leads to variations not only in the algorithms’ search spaces but also in the repair problems they can effectively tackle and the nature of repairs they can generate. By comprehending these discernible dissimilarities, we can make informed choices when selecting a repair method for specific planning scenarios.
Empirical Evaluation
To support our theoretical findings, we conducted a comprehensive empirical evaluation using a series of benchmark planning problems. This evaluation offers a more nuanced understanding of the runtime repair performance of these systems, as well as the coverage of repair problems they can solve. We focused on critical algorithmic properties such as replanning, chronological backtracking, and backjumping over plan trees to gain insights into the effectiveness and efficiency of each algorithm.
By combining theoretical analysis and empirical evaluations, we gain a holistic perspective on the hierarchical plan repair algorithms. This multi-disciplinary approach allows us to assess the strengths and weaknesses of each algorithm, guiding us in making informed decisions when applying them in real-world applications.