When human beings tackle a massive problem, our natural instinct is to divide and conquer: break the global objective down into smaller, manageable subgoals, solve each one individually, and combine the results. Early artificial intelligence planning systems operated on this exact heuristic, known as the linear assumption.
However, in complex or highly coupled environments, this intuitive strategy completely breaks down. The core issue is subgoal interference (often called clobbering or negative goal interaction): the actions required to achieve a new subgoal frequently undo or violate the conditions established by a previously solved subgoal. Understanding why this interference happens—and how automated planners bypass it—is central to modern AI planning.
The Linear Assumption and Why It Fails
The linear assumption posits that multi-goal problems can be solved sequentially. A planner handles Goal A, locks its state, and then moves on to Goal B.
As Austin Tate demonstrated in Interacting Goals And Their Use, this assumption fails because actions have side effects. In non-linear environments, achieving a subsequent goal often necessitates the temporary or permanent destruction of a prior goal's state. When a system lacks a mechanism to handle these interdependencies, it falls into a goal protection deadlock.
Stephen A. Vere characterized this deadlock in Splicing Plans to Achieve Misordered Goals as a scenario where a planner satisfies one objective only to find that the next objective requires violating the state established by the first. If the planner strictly protects already achieved states, the remaining global goal becomes entirely unreachable, paralyzing the system (Bastian Bischoff et al. in Solving the 15-Puzzle Game Using Local Value-Iteration).
To build intuition, imagine a robot tasked with painting a floor and sealing the doorway. If it seals the doorway first (Subgoal A) and then paints the floor (Subgoal B), it must step on the wet paint to exit, destroying Subgoal B. If it paints the floor first and then seals the door, it might trap itself. The subgoals cannot be solved in isolation; their execution must be carefully interleaved.
The Blind Spot of Delete-Relaxation
Modern automated planners rely heavily on heuristics to navigate massive state spaces. A common approach to generating these heuristics is delete-relaxation, a simplification where actions are assumed to only add positive facts to the world and never delete or destroy existing states.
While delete-relaxation makes computing heuristics mathematically cheap, it introduces a dangerous blind spot. As Hyun Kim explained in Effective Graph-Based Heuristics for Contingent Planning, delete-relaxed frameworks are fundamentally incapable of modeling negative interactions. They assume that because an action helps achieve Goal B, its destructive consequences on Goal A can be ignored.
This mismatch leads to serialization failures. As Dominik Drexler et al. noted in Expressing and Exploiting the Common Subgoal Structure of Classical Planning Domains Using Sketches, greedy or width-based algorithms get trapped in dead ends because their heuristics cannot foresee that reaching a specific target state requires a temporary, intentional reversal of previously satisfied subgoals.
Resolving Interference via Least-Commitment
To resolve subgoal interference without resorting to exhausting, brute-force backtracking, planners must move away from strict chronological ordering during the design phase. This shift is achieved through partial-order planning and the strategy of least-commitment.
In his seminal paper Nonlinear Planning: A Rigorous Reconstruction, David Chapman formalized the Truth Criterion for partial-order plans. Instead of forcing actions into a rigid total sequence from the outset, a partial-order planner leaves the chronological order of steps flexible. It treats a plan as a network of actions with causal links. If the planner detects that a newly added action will "clobber" an existing causal link, it uses promotion or demotion—either forcing the destructive action to happen before the link is established, or delaying it until after the condition is no longer needed.
This flexible structure enables plan splicing. Subbarao Kambhampati et al. demonstrated in Relative Utility of EBG based Plan Reuse in Partial Ordering vs. Total Ordering Planning that partial-order planners excel at reusing and adapting past plans because they can flexibly interleave or splice new actions into the middle of an existing sequence to satisfy interacting constraints, bypassing the rigid barriers of total-order systems.
Total-Order Planning (Rigid, prone to clobbering):
[Achieve Goal A] ──> [Achieve Goal B (Destroys Goal A!)] ──> Failure
Partial-Order Planning (Flexible Splicing):
[Action 1] ───(Causal Link)───> [Action 2]
\ /
└──> [Spliced Step] ┘ (Resolves conflict before finalizing order)
To bring this awareness into state-space search, XuanLong Nguyen et al. developed methods to extract mutual exclusion (mutex) constraints from planning graphs in Extracting Effective and Admissible State Space Heuristics from the Planning Graph. By embedding these mutex constraints directly into state-space heuristics, the planner can mathematically calculate how subgoals interfere with one another, effectively correcting the flaw of the independence assumption.
Embracing Non-Monotonic Progress
Ultimately, overcoming subgoal interference requires a conceptual shift: accepting that progress toward a global goal is not always monotonic. Traditional problem solvers assume that every step must bring the agent closer to the final state. However, highly coupled problems often require the agent to intentionally move away from the goal to unlock a solution path.
David Ruby et al. addressed this in Learning Subgoal Sequences for Planning through the SteppingStone system. When a planner encounters an impasse—a point where satisfying a new objective requires violating a previously achieved one—the system leverages targeted search to discover sequences of intermediate subgoals ("stepping stones"). These sequences temporarily violate global constraints but successfully navigate the system through the negative interaction space, allowing it to reach a state where all conjunctive goals can finally coexist.
Key Foundational Work
The Nonlinear Nature of Plans (1975) — contributed 4 concept elements to this direction.
Interacting Goals And Their Use (1975) — contributed 3 concept elements to this direction.
An Efficient Robot Planner which Generates Its Own Procedures (1973) — contributed 1 concept elements to this direction.