Project 1: STRIPS


One of the oldest algorithms in robotics is STRIPS. Originally intended
as the control algorithm for Shakey the robot, it is now best known as the
grand-daddy of modern planners. At its core, STRIPS uses a state-space
representation of the robot's environment, and forms plans by searching
within that state-space for a path from the current world-state to the goal.

Your task is to implement STRIPS in Scheme or Common Lisp, according
to the specification below.

States

STRIPS uses a logic-based representation for states. Each state is a
conjuntion of zero or more positive literals. Each literal represents a
part of the world: for example, to describe my office, STRIPS might
use the following state:

messy( desk )
in( prof, deskchair )
on( computer )
off( radio )

A Blocks-world state (a simple problem involving stacking blocks
in certain orders on a table) might be specified as follows:

on( blockA, table )
on( blockB, table )
on( blockC, blockB )
clear( blockA )
clear( blockC )
clear( table )
handempty

Any allowable literal from first-order logic can be used, so long as it
is ground (in other words, contains no variables), and function-free
(in other words, has no unevaluated functions like Father(Prof)). Any
literal not explicitly included in the state is assumed to be false: for
example, in( fred, guestchair ) is false in the above example.

Operators

Operators in STRIPS transform the database according to ADD
and DELETE lists. The ADD lists specify what new literals become
true in the new state. The DELETE lists specify which of the old
state's literals become false. Each operator also has a list of
preconditions, which are the literals that must be true in states
where the action is to be performed.

For example, the blocks-world operator pickup, which picks up a
block from the table, can be defined as follows:

PRECOND: on( X, Y ), clear( X ), handempty
ADD: holding( X ), clear( Y )
DELETE: clear( X ), on( X, Y ), handempty

Algorithm

The basic operation of STRIPS is stack-based. Initially, the stack consists
only of the goal state. At each step: check if the node on top of the stack
is satisfied. If so, pop it and continue. If not, see if any operator has an ADD
list that matches (unifies with -- see your book section 9.2!) the top node. If
so, push that operator onto the stack, followed by its preconditions. These
will be your new subgoals. If at any point the top of the stack contains an
action, pop it, and execute it.

Format of the input

For the input, we need a start state, a goal state, and a set of operators. The start
state is simply a list of ground literals:

'((on blockA table) (on blockB table) (on blockC blockB)
  (clear blockA) (clear blockC) (handempty)
  (clear table))

The goal state is likewise a list of ground literals:

'((on blockC table) (on blockB blockC) (on blockA blockB)
  (clear blockA) (handempty) (clear table))

Finally, the operators have the following format. Each has an operator name,
a list of preconditions, an add list, and a delete list. The pickup example from
above is written below, along with the three other operators necessary to get
from the start state to the goal state.

'((pickup X Y) ((on X Y) (clear X) (handempty))
               ((holding X) (clear Y))
               ((clear X) (handempty) (on X Y)))

'((putdown X Y) ((holding X) (clear Y))
                ((on X Y) (clear X) (handempty) (clear table))
                ((holding X) (clear Y)))


There are a couple of things to notice here. First, we only have two operators,
pickup and putdown -- this is a change made to simplify the example and prevent the
possibility of infinite recursion. Second, notice that the table is now an object, exactly
like the blocks are objects. The issue here is that the table must always remain clear
(this is why STRIPS examples traditionally have separate operators for manipulating
blocks that are directly on the table). In our case, we add an explicit (clear table) to
the add-list of putdown, -- which of course means we need to take care that we aren't
adding to the same fact to the world-state twice!

Putting it all together, the whole input would be:

'(((on blockA table) (on blockB table) (on blockC blockB)     ; START state
  (clear blockA) (clear blockC) (handempty)
  (clear table))

 ((on blockC table) (on blockB blockC) (on blockA blockB)    ; GOAL state
  (clear blockA) (handempty) (clear table))

 ((pickup X Y) ((on X Y) (clear X) (handempty))   ; operators
               ((holding X) (clear Y))
               ((clear X) (handempty) (on X Y)))

 ((putdown X Y) ((holding X) (clear Y))
                ((on X Y) (clear X) (handempty) (clear table))
                ((holding X) (clear Y))))
            
Note the extra set of parentheses around the operator list! Also, note
the single-quote char (') preceeding the whole expression. This prevents
Lisp from trying to evaulate the whole expression as a function. 
Finally, note that this is not a complete set of operators, and therefore
STRIPS will not be able to find a solution.

The start, goal, and operator lists can get pretty long. I recommend
you set variables to hold them, and then build your program arguments
out of the variables.

Format of the output

The output will be a list of the operators to be executed, in order from
first to last, and with variables replaced by the relevant bindings. An
example output might be:

((pickup blockA) (putdown blockA blockB))

which says to pick up block a and put it down on block b. If the program
fails to find a plan that satisfies the goal, output nil.


Unification


In order to get STRIPS to run properly, you will need to be able to unify the
world-state with your operators. When you  do so, make sure the add-list,
delete-list, and preconditions get unified as well -- you don't want to get mixed
up about which block you're putting your block on later!