The Sussman Anomaly

MIT computer scientist Gerald Sussman offered this example to show the importance of sophisticated planning algorithms in artificial intelligence. Suppose an agent is told to stack these three blocks into a tower, with A at the top and C at the bottom, moving one block at a time:

https://commons.wikimedia.org/wiki/File:Sussman-anomaly-1.svg
Image: Wikimedia Commons

It might proceed by separating the goal into two subgoals:

  1. Get A onto B.
  2. Get B onto C.

But this leads immediately to trouble. If the agent starts with subgoal 1, it will move C off of A and then put A onto B:

https://commons.wikimedia.org/wiki/File:Sussman-anomaly-2.svg
Image: Wikimedia Commons

But that’s a dead end. Because it can move only one block at a time, the agent can’t now undertake subgoal 2 without first undoing subgoal 1.

If the agent starts with subgoal 2, it will move B onto C, which is another dead end:

https://commons.wikimedia.org/wiki/File:Sussman-anomaly-3.svg
Image: Wikimedia Commons

Now we have a tower, but the blocks are in the wrong order. Again, we’ll have to undo one subgoal before we can undertake the other.

Modern algorithms can handle this challenge, but still it illustrates why planning is not a trivial undertaking. Sussman discussed it as part of his 1973 doctoral dissertation, A Computational Model of Skill Acquisition.