Raghavan Snntvasan and

IJCAI 1995

TL;DR

This paper tackles the "looping" problem in plan-space planning, where planners can get stuck in infinite search loops generating non-minimal solutions. The authors introduce two novel pruning strategies, "Nsat-prune" and "Cutset-prune," based on plan minimality, which are shown to be admissible for different classes of planners, significantly improving efficiency and preventing infinite loops.

What Problem Does This Paper Address?

Plan-space planning, a popular approach to automated reasoning, excels at generating flexible and efficient plans. However, a significant challenge it faces is "looping," where the planner can spend an inordinate amount of time exploring redundant or globally useless search paths. This looping is intimately tied to the generation of non-minimal solutions – plans that are valid but contain unnecessary steps. Unlike state-space planners, which can terminate even on unsolvable problems due to finite state spaces, plan-space planners can enter infinite loops, especially when dealing with unsolvable problems or when not employing effective pruning. Existing pruning techniques, often based on detecting inconsistencies in partial plans, are insufficient to prevent this looping behavior. This paper aims to address this by proposing new pruning strategies specifically designed for plan-space planners, grounded in the concept of plan minimality.

Methods

The paper introduces two main pruning strategies:

  • Nsat-prune: This strategy generalizes the notion of plan minimality to incomplete plans. It defines a "Nsatplan" as the core set of preconditions that must be satisfied for a plan to be considered complete. A partial plan is then pruned if its Nsatplan is not minimal (i.e., if its Nsatplan can be further simplified without losing necessary preconditions). This approach is shown to be admissible for "non-causal link planners" (like UA and TO) that allow preconditions to be re-established multiple times.
  • Cutset-prune: This strategy is designed for "causal link planners" (like SNLP) that protect their established preconditions using causal links. It leverages the causal dependencies within a plan, represented as a graph. A plan is pruned if there exist two steps, a' and a'', such that the set of causal links supporting a'' (its "pp-cutset") is dominated by the set of causal links originating from a' (its "np-cutset"), and certain other conditions related to ordering and open conditions are met. Intuitively, this means a part of the plan is redundant and can be removed without affecting the plan's correctness, indicating a non-minimal solution.

Datasets

Not discussed in the paper. The paper focuses on theoretical contributions and uses illustrative examples from standard AI planning domains (like the blocks world) for demonstration.

Key Insights and Ideas

  • Looping is fundamentally linked to non-minimal solutions: The paper argues convincingly that the problem of infinite looping in plan-space planning is a direct consequence of generating plans that are not minimal.
  • Minimality needs to be extended to incomplete plans: To effectively prune search paths before complete, non-minimal solutions are generated, the concept of minimality must be applied to incomplete partial plans.
  • Different planner architectures require different pruning strategies: The paper highlights a crucial distinction between "causal link planners" and "non-causal link planners," demonstrating that a pruning strategy admissible for one class may be inadmissible for the other. This underscores the importance of tailoring pruning techniques to the underlying planning mechanism.
  • The "Nsatplan" concept provides a novel way to assess incomplete plan minimality: By focusing on the essential preconditions, Nsat-prune offers a principled way to identify redundant steps in partial plans.
  • Causal link analysis can reveal redundancy: The "Cutset-prune" strategy elegantly uses the structure of causal links to identify and prune plans that are guaranteed to lead to non-minimal solutions.

Key Results

  • Nsat-prune is admissible for non-causal link planners (UA, TO): The paper proves that this strategy does not prevent the planner from finding all minimal solutions.
  • Nsat-prune is inadmissible for causal link planners (SNLP, UCPOP): The paper provides counterexamples showing that pruning non-minimal incomplete plans can lead to the loss of minimal complete solutions for these planners.
  • Cutset-prune is admissible for causal link planners: This strategy is proven to be sound and complete for planners that use causal links to protect establishments.
  • The paper demonstrates how these strategies prevent looping: Using examples like the "hf/he" problem, the authors show how Nsat-prune and Cutset-prune effectively prune the problematic branches, avoiding infinite search.
  • Complexity considerations: While full minimality checking is NP-hard, the paper suggests using weaker, polynomial-time necessary conditions for minimality to maintain admissibility while improving efficiency.

Limitations and Future Work

  • Computational Cost: Checking for minimality, especially full minimality, can be computationally expensive (NP-hard). The paper acknowledges this and suggests using weaker, polynomial-time necessary conditions.
  • TWEAK Inadmissibility: The paper notes that Nsat-prune is not admissible for TWEAK, a specific non-causal link planner, due to its "unambiguousness" property. This suggests that even within non-causal link planners, subtle differences can impact admissibility.
  • Future Work: The authors suggest that these pruning strategies can be used to guide learning systems (e.g., explanation-based learning) to learn effective control rules for avoiding looping branches. They also point to the utility of these strategies in conjunction with depth-limited search. The paper also mentions the potential for using weaker minimality checks to improve practical performance.

Summary updated

BibTeX
@inproceedings{1995raghavan,
  title = {{Raghavan Snntvasan and}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1995},
}
Figure