Planning    Next: Building plans from actions
Up: How PopBeast creates plans and actions
Previous: Filling in referents
Back: to main list of student notes

## 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)`
and makes these facts false:
`square(X,S), empty`
Here, `have(X)` means ``I am holding X'', and `empty` means ``I am holding nothing''.

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)`
become true, and the facts
`have(K), square(D,S)`
become false. (Remember that after using a key on a door, the door disappears from its square, and the key from PopBeast's hand.) This way of describing actions is called the add-list/delete-list representation.

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)`
which literally translated from the logic, means ``X is in S, and PopBeast is in S, and PopBeast's hand is empty''.

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

`have(K), square(D,S), square(me,S)`
which means ``I am holding K, D is in square S, and I am also in square 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) ]
).```    Next: Building plans from actions
Up: How PopBeast creates plans and actions
Previous: Filling in referents
Back: to main list of student notes

Jocelyn Ireson-Paine
Thu Feb 15 00:09:05 GMT 1996