EECS 391/491: SUSSMAN ANOMALY

According to Nilsson, the anomaly is that when using recursive STRIPS (achieving one conjunct at a time), neither option results in a minimal plan. According to R&N (see Exercise 11.11 on page 414), it is an anomaly because a non-interleaved planner cannot solve the problem. Both of these facts are demonstrated explicitly.

The notation CA, B is shorthand for denoting the start state:

 C
_A_B_

Goal: On(A,B) ^ On(B,C)
Goal state: ABC


Option I: Achieve On(A,B) first and then On(B,C)
------------------------------------------------

Achieve On(A,B) first:
  I1. move(C,A,Fl)    C, A, B
  I2. move(A,Fl,B)    C, AB

On(A,B) has been achieved.  Now achieve On(B,C):
  I3. move(A,B,Fl)    C, A, B  <-- undoes On(A,B), which must be re-achieved
  I4. move(B,Fl,C)    BC, A

On(B,C) has been achieved, but now we must re-achieve On(A,B)
  I5. move(A,Fl,B)    ABC

This is now a complete, but non-minimal plan.
A minimal plan would remove I2 and I3.
A non-interleaved planner would stop at I4, without solving the problem.


Option II: Achieve On(B,C) first and then On(A,B)
-------------------------------------------------

Achieve On(B,C)
  II1. move(B,Fl,C)   BCA
  
On(B,C) has been achieved.  Now achieve On(A,B):
  II2. move(B,C,Fl)   CA, B    <-- undoes On(B,C), which must be re-achieved
  II3. move(C,A,Fl)   C, A, B
  II4. move(A,Fl,B)   C, AB

On(A,B) has been achieved, but On(B,C) must be re-achieved:
  II5. move(A,B,Fl)   C, A, B  <-- undoes On(A,B), which must be re-achieved
  II6. move(B,Fl,C)   BC, A

On(B,C) has been achieved, but now we must re-achieve On(A,B):
  II7. move(A,Fl,B)   ABC

This is now a complete, but, again, non-minimal plan.
A minimal plan would remove II1, II2, II4, and II5.
A non-interleaved planner would stop at II4, without solving the problem.

Note: An infinite loop behavior can result if one "prefers the floor," but that is a red herring which defeats any goal requiring a stack of three or more.

Author: M.S. Branicky