Planning

The verb table above has told PopBeast that opening something is equivalent to making it disappear from the square in which it was. With the referents of D and S filled in, this implies that opening door(2) is equivalent to making it disappear from square [8,4]. How can PopBeast find a sequence of actions that will achieve this - a plan? This is called planning, and the program that does it is called a planner.

Remember that in each turn, PopBeast can perform one of eight primitive actions: left, right, forward, back, drop, grab, use, and wait. To reason about what sequence of actions will achieve a goal such as clear([8,4]), PopBeast needs to represent the effect of each of these actions. There are various ways to do this; the one I have chosen is based on that used in an early planner called STRIPS.

The idea is that we represent the state of the world at any time by a set of propositions, as PopBeast does in its propositional world-model. We then represent each action by a table showing how, if it were carried out, it would change the state. In particular: what does it make false that used to be true; and what does it make true that used to be false?

Let's look at ``grab'' as an example. Before PopBeast grabs an object, its hand must be empty, and the object must be in the same square as PopBeast. After grabbing, the hand will contain the object, and the square will be empty. We can represent this by saying that when grabbing X in square S, PopBeast makes this fact true:

have(X)

square(X,S), empty

Other actions can be specified in the same fashion. When using a key K on a door D in square S, the facts

empty, clear(S)

have(K), square(D,S)

We need one further piece of information for each action: under what conditions it can be performed. You can only open a door if you are in the same square as it and you have a key; you can only grab an object if your hand is empty and you are in the same square as it. These necessary conditions are called the action's preconditions. We represent these in the same way as the add- and delete-lists: as sequences of propositions. Thus the precondition for grabbing X in square S is

square(X,S), empty, square(me,S)

Similarly, the precondition for opening door D with key K in square S is that

have(K), square(D,S), square(me,S)

The add-lists, delete-lists and preconditions are collected together for each primitive action, in a table rather like the verb table. As an example, here are the descriptions of the primitive actions grab and use:

action( grab(X,S),
        [ square(X,S), empty, square(me,S) ],
        [ square(X,S), empty ],
        [ have(X) ]
      ).

action( use(K),
        [ have(K), square(D,S), square(me,S) ],
        [ have(K), square(D,S) ],
        [ empty, clear(S) ]
      ).