Past exam of the computer science course of the University of Oxford / 2019 / Artificial intelligence / 3 / d / Solution

Let $G_1=\mathrm{On}(A,B)$ and $G_2=\mathrm{On}(B,C)$. The familiar obstruction is the Sussman anomaly for restricted goal-by-goal planning.

If one first constructs the obvious isolated plan for $G_1$, it moves $C$ off $A$ and then puts $A$ on $B$. Now $B$ is not clear, so achieving $G_2$ requires taking $A$ off $B$, undoing $G_1$. If one first achieves the isolated $G_2$ directly, it puts $B$ on $C$ while $C$ is still on $A$. To free $A$, it must move $C$, which first requires moving $B$ off $C$, undoing $G_2$. Therefore neither ordering of those independent subplans works while protecting the first achieved goal.

The literal concatenation-only definition in the question is too weak to imply the requested impossibility. A valid plan isThe first two actions constitute a plan for $G_2$ from the original state, and the last action is a plan for $G_1$ from the resulting state, preserving $G_2$. Thus this is itself a concatenation of the stated kind. Its crucial first action prepares for the later subgoal before completing $G_2$.

The green-outlined cells mark achieved goal facts. This original solution timeline makes the distinction explicit: independent goal-directed subplanning fails, but unrestricted concatenation does not. To obtain the intended impossibility claim, “non-interleaved” must also forbid anticipatory preparation or require the isolated subplans described above. No source input is missing; the issue is the breadth of the printed definition.