Abstract
Although plan space planners have been shown to be flexible and efficient in plan generation, they do suffer from the problem of "looping" - that is they may spend an inordinate amount of time doing locally seemingly useful but globally useless refinements. In this paper, I review the anatomy of looping and argue that looping is intimately tied to the production of non-minimal solutions. I then propose two classes of admissible pruning techniques based on the notion of plan minimality. I show that the first one is admissible for planners which do not protect their establishments but allow a precondition to be reestablished any number of times. The second one is admissible for planners which protect their establishments through causal links. I also discuss the complexity of the proposed pruning strategies and then potential applications.
Introduction: The Looping Problem in Plan-Space Planning
Automated planning typically falls into two categories: state-space planning and plan-space planning. While plan-space planners offer significant flexibility in handling complex constraints, they are notoriously susceptible to "looping." This occurs when the planner enters an infinite search branch, repeatedly adding operators that appear locally beneficial but are globally redundant. Unlike state-space planners, which can detect loops by checking for revisited states, plan-space planners lack a straightforward mechanism to identify when they are treading old ground in a new way.
Plan Minimality as a Pruning Criterion
The core insight of this work is that looping in plan-space is fundamentally a problem of generating non-minimal plans—plans containing redundant steps that do not contribute to the final goal. By enforcing plan minimality, we can effectively prune these infinite branches.
Subbarao Kambhampati proposes two "admissible" pruning strategies, meaning they safely discard redundant paths without risking the loss of optimal solutions. These strategies are tailored to the specific architecture of the planner.
Pruning Strategies
1. Nsat-prune for Non-Causal Link Planners
For planners like TWEAK or UA, which allow preconditions to be re-established multiple times without explicit protection, the Nsat-prune strategy is employed. This method involves constructing an "Nsatplan"—a version of the current partial plan where only "necessarily true" preconditions are maintained. If the resulting Nsatplan is found to be non-minimal, the entire search branch can be safely pruned.
2. Cutset-prune for Causal Link Planners
Planners such as SNLP or UCPOP use "causal links" to protect established conditions from being undone by subsequent steps. For these systems, the Cutset-prune strategy analyzes the causal dependency graph.
This strategy identifies "np-cutsets" (sets of necessary links) and "pp-cutsets" (sets of possible links). By comparing these cutsets across different steps (as shown in Figure 2), the algorithm can detect if a step is redundant. If a step's contributions are entirely subsumed by other parts of the plan, it will never lead to a minimal solution and is thus pruned.
Theoretical and Empirical Validation
The paper provides formal proofs (Theorems 2 and 3) establishing the admissibility of both Nsat-prune and Cutset-prune. These strategies ensure that the planner remains complete with respect to minimal plans.
Empirically, these techniques are shown to terminate search on notoriously difficult problems like the "hf/he" puzzle, where standard planners would loop indefinitely. The strategies were also tested using simplified Blocks-World domains to demonstrate how domain axioms (e.g., a block cannot be both clear and supporting another block) can further refine the pruning process.
Complexity and Practical Considerations
While theoretically powerful, these pruning checks come with computational costs. Checking for full plan minimality is generally NP-hard. However, the proposed strategies offer polynomial-time approximations that are effective in practice. The author suggests a strategic application of these checks—for instance, only invoking them when a plan exceeds a certain depth threshold—to balance the overhead against the benefits of search space reduction.
Conclusion
By linking the problem of looping to plan minimality, this research provides a robust framework for improving the efficiency of plan-space planners. These pruning strategies not only speed up search but also provide critical "failure reasons" that can be leveraged by Explanation-Based Learning (EBL) systems to further optimize future planning tasks.
Summary updated