= Solution
Let $G_1=\operatorname{On}(A,B)$ and $G_2=\operatorname{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.
\b[The literal concatenation-only definition in the question is too weak to imply the requested impossibility.] A valid <plan> is
$$
\boxed{\operatorname{MoveToTable}(C,A),\quad\operatorname{Move}(B,\tau,C),\quad\operatorname{Move}(A,\tau,B).}
$$
The 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$.
\Image[/past-exam-of-the-computer-science-course-of-the-university-of-oxford/2019/artificial-intelligence-plan-supports.png]
{title=Support relations along the derived three-action <blocks world> plan}
The green-outlined cells mark achieved goal facts. This original solution timeline makes the distinction explicit: \b[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.
Back to article page
