Abstract
Non-linear planning often suffers from "goal-clobbering," where the actions taken to achieve one objective inadvertently undo the conditions required for another. This paper introduces Goal-Clobbering Avoidance (GCA), a technique that leverages pre-compiled domain knowledge to identify and prevent these conflicts at the sequence level. By imposing ordering constraints early in the search process, GCA significantly reduces planning time and search space complexity, as demonstrated in the Blocksworld domain.
Introduction
In non-linear planning, the objective is to determine a set of actions and their partial ordering to reach a goal state. A significant challenge in this process is interaction, specifically "clobbering." Clobbering occurs when an operator intended to satisfy one goal destroys a condition necessary for another. Traditional planners typically use the Modal Truth Criterion (MTC) to detect such interactions locally as operators are added. However, this reactive approach often leads to inefficient searching, particularly in complex scenarios like Sussman’s Anomaly, where conflicting preconditions (e.g., arm-empty or clear block) create a dense web of potential failures.
Methodology
Goal-Clobbering Avoidance (GCA) shifts the focus from individual operators to entire sequences. Instead of reacting to conflicts after they appear, GCA proactively avoids them by applying sequence-level constraints.
The core of GCA lies in "goal-clobbering judgements"—pre-determined rules derived from domain properties. For instance, in the Blocksworld domain (see Figure 5), the system can determine that any sequence of actions resulting in (on B C) will necessarily invalidate (on A B). By identifying these inevitable conflicts early, the planner can constrain the entire sequence for one goal to follow the completion of another, even before specific operators for sub-goals are selected. This abstract approach to "how" goals are achieved allows for high-level ordering decisions that prune the search space effectively.
Results and Discussion
The GCA method was evaluated using the Blocksworld benchmark within the PRODIGY planning system. Implementation in a totally-ordered version of PRODIGY resulted in substantial reductions in planning time. The framework's strength lies in its domain-independence; while demonstrated here with blocks, it is applicable to any domain where goal-clobbering judgements can be formalized.
However, several limitations remain. At present, the derivation of goal-clobbering judgements is not fully automated, though work is ongoing to integrate this with the STATIC compiler. Furthermore, while GCA has proven effective in totally-ordered planners, its performance in purely partially-ordered planners is still under investigation. Finally, the system must be extended to handle "conditional goal-clobberings," where conflicts only arise under specific initial conditions.
Conclusion
GCA provides a proactive mechanism for managing goal interactions in non-linear planning. By moving from reactive local conflict detection to proactive sequence-level constraint satisfaction, it offers a promising path toward more efficient and scalable planning systems.
Summary updated