Goal interaction in planning

Two subgoals interact when actions needed for one can establish, obstruct or delete facts needed for the other. A plan for each subgoal separately need not combine into a plan for their conjunction. Preparing the world before committing to a subgoal, revising an earlier subplan or temporarily undoing an achieved fact can all be necessary. Goal-by-goal planning may therefore be incomplete.

The Sussman anomaly is a blocks world example in which independently constructing the obvious subplans for two stacking goals gives destructive goal interaction in planning. Clearing a block in advance allows a short joint plan, while prematurely achieving either isolated goal can block the other. It demonstrates the inadequacy of restricted goal-by-goal planning, rather than a prohibition on every possible ordering of final goal achievements. Preparatory actions can make such an ordering succeed. For a concrete instance, start with $C$ on $A$ and $A,B$ on the table, and require $A$ on $B$ and $B$ on $C$. Moving $C$ to the table, then $B$ onto $C$, then $A$ onto $B$ succeeds. The first move is preparation that an isolated shortest subplan for the second stacking goal would omit.

A restricted goal-by-goal planning procedure chooses one subgoal, constructs a subplan for it without preparation motivated by other pending subgoals, then moves on while treating the earlier goal as protected. Destructive goal interaction in planning can defeat either ordering. Merely requiring the final plan to be a concatenation of subplans is a weaker condition: a subplan may already contain preparatory work useful to a later goal. A claimed impossibility must specify the stronger restriction rather than infer it from concatenation alone.