15.1 Planning with Individuals and Relations

15.1.1 Situation Calculus

The situation calculus represents states in terms of the actions required to reach them. The situation calculus can be seen as a relational version of the feature-based representation of actions.

Here we consider only a single agent, a fully observable environment, and deterministic actions.

The situation calculus is defined in terms of situations. A situation is either

  • init, the initial situation, or

  • do(A,S), the situation resulting from doing action A in situation S, if it is possible to do action A in situation S.

Example 15.1.

Consider the domain of Figure 3.1. Suppose in the initial situation, init, the robot, Rob, is at location o109 and there is a key k1 at the mail room and a package at storage. Suppose move(Ag,L0,L1) is the action of agent Ag moving from location L0 to location L1.

do(move(rob,o109,o103),init)

is the situation resulting from Rob moving from position o109 in situation init to position o103. In this situation, Rob is at o103, the key k1 is still at mail, and the package is at storage.

The situation do(move(rob,o103,mail), do(move(rob,o109,o103), init)) is one in which the robot has moved from position o109 to o103 to mail and is currently at mail. Suppose Rob then carries out the action pickup(rob,k1), which is to pick up the key k1. The resulting situation is do(pickup(rob,k1), do(move(rob,o103,mail), do(move(rob,o109,o103), init))). In this situation, Rob is at position mail carrying the key k1.

A situation may be associated with a state. There are two main differences between situations and states:

  • Multiple situations may refer to the same state if multiple sequences of actions lead to the same state. That is, equality between situations is not the same as equality between states.

  • Not all states have corresponding situations. A state is reachable if a sequence of actions can reach that state from the initial state. States that are not reachable do not have a corresponding situation.

Some do(A,S) terms do not correspond to any state. Sometimes an agent must reason about such a (potential) situation without knowing whether A is possible in state S, or whether S is possible.

Example 15.2.

The term do(unlock(rob,door1),init) does not denote a state at all, because it is not possible for Rob to unlock the door when Rob is not at the door and does not have the key.

The situations:

init
do(move(rob,o103,o109),do(move(rob,o103,o109),init))
do(move(rob,o103,ts),do(move(rob,o103,ts),init))

all represent the same state, with the robot at location o103, and everything else that is true in the initial state. In the last two situations, the robot has moved away from o103 and back again. This assumes that the resources used by the robot are not being modeled; if the resources were modeled, the last two situations may represent different states from init as the battery level may be less.

A static relation is a relation for which the truth value does not depend on the situation; that is, its truth value is unchanging through time. A dynamic relation is a relation for which the truth value depends on the situation. To represent what is true in a situation, predicate symbols denoting dynamic relations have a situation argument so that the truth can depend on the situation. A predicate symbol with a situation argument is called a fluent.

Example 15.3.

The relation at(O,L,S) is true when object O is at location L in situation S. Thus, at is a fluent.

The atom

at(rob,o109,init)

is true if the robot rob is at position o109 in the initial situation. The atom

at(rob,o103,do(move(rob,o109,o103),init))

is true if robot rob is at position o103 in the situation resulting from rob moving from position o109 to position o103 from the initial situation. The atom

at(k1,mail,do(move(rob,o109,o103),init))

is true if k1 is at position mail in the situation resulting from Rob moving from position o109 to position o103 from the initial situation.

A dynamic relation is axiomatized by specifying the situations in which it is true. This is done inductively in terms of the structure of situations, as follows:

  • Axioms with init as the situation parameter are used to specify what is true in the initial situation.

  • A primitive relation is defined by specifying when it is true in situations of the form do(A,S) in terms of what is true in situation S. That is, primitive relations are defined in terms of what is true at the previous situation.

  • A derived relation is defined using clauses with a variable in the situation argument. The truth of a derived relation in a situation depends on what else is true in the same situation.

  • A static relation is defined without reference to the situation.

Example 15.4.

Suppose the delivery robot, Rob, is in the domain depicted in Figure 3.1. Rob is at location o109, the parcel is in the storage room, and the key is in the mail room. The following axioms describe this initial situation:

at(rob,o109,init).
at(parcel,storage,init).
at(k1,mail,init).

The adjacent relation is a dynamic, derived relation defined as follows:

adjacent(o109,o103,S).
adjacent(o103,o109,S).
adjacent(o109,storage,S).
adjacent(storage,o109,S).
adjacent(o109,o111,S).
adjacent(o111,o109,S).
adjacent(o103,mail,S).
adjacent(mail,o103,S).
adjacent(lab2,o109,S).
adjacent(P1,P2,S)
    between(Door,P1,P2)
    unlocked(Door,S).

Notice the free S variable; these clauses are true for all situations. The situation term, S, cannot be omitted because which rooms are adjacent depends on which doors are unlocked. This can change from situation to situation.

The between relation is static and does not require a situation variable:

between(door1,o103,lab2).

We also model whether or not an object is being carried. If an object is not being carried, we say that the object is sitting at its location. A carried object moves with the object carrying it. An object is at a location if it is sitting at that location or is being carried by an object at that location. Thus, at(Object,Location,Situation) is a derived relation:

at(Ob,P,S)
    sitting_at(Ob,P,S).
at(Ob,P,S)
    carrying(Ob1,Ob,S)
    at(Ob1,P,S).

Note that this definition allows for Rob to be carrying a bag, which, in turn, is carrying a book.

The precondition of an action specifies when it is possible to carry out the action. The relation poss(A,S) is true when action A is possible in situation S. This is typically a derived relation.

Example 15.5.

An autonomous agent can put down an object it is carrying:

poss(putdown(Ag,Obj),S)
    autonomous(Ag)
    carrying(Ag,Obj,S).

For the move action, an autonomous agent can move from its current position to an adjacent position:

poss(move(Ag,P1,P2),S)
    autonomous(Ag)
    adjacent(P1,P2,S)
    sitting_at(Ag,P1,S).

The precondition for the unlock action is more complicated. The agent must be on the correct side of the door and carrying the appropriate key:

poss(unlock(Ag,Door),S)
    autonomous(Ag)
    between(Door,P1,P2)
    at(Ag,P1,S)
    opens(Key,Door)
    carrying(Ag,Key,S).

The between relation is not symmetric; some doors can only be opened with a key from one side.

What is true in each situation is defined recursively in terms of the previous situation and what action occurred between the situations. As in the feature-based representation of actions, causal rules specify when a relation becomes true and frame rules specify when a relation remains true.

Example 15.6.

The primitive relation unlocked can be defined by specifying how different actions can affect its being true. A door is unlocked in the situation resulting from an unlock action, as long as the unlock action was possible. This is represented using the causal rule:

unlocked(Door,do(unlock(Ag,Door),S))
    poss(unlock(Ag,Door),S).

Suppose the only action to make the door locked is to lock the door. Thus, unlocked is true in a situation following an action if it was true before, if the action was not to lock the door, and if the action was possible:

unlocked(Door,do(A,S))
    unlocked(Door,S)
    Alock(Door)
    poss(A,S).

This is a frame rule.

Example 15.7.

The carrying predicate can be defined as follows.

An agent is carrying an object after picking up the object:

carrying(Ag,Obj,do(pickup(Ag,Obj),S))
    poss(pickup(Ag,Obj),S).

The only action that undoes the carrying predicate is the putdown action. Thus, carrying is true after an action if it was true before the action, and the action was not to put down the object. This is represented in the frame rule:

carrying(Ag,Obj,do(A,S))
    carrying(Ag,Obj,S)
    poss(A,S)
    Aputdown(Ag,Obj).
Example 15.8.

The atom sitting_at(Obj,Pos,S1) is true in a situation S1 resulting from object Obj moving to Pos, as long as the action was possible:

sitting_at(Obj,Pos,do(move(Obj,Pos0,Pos),S))
    poss(move(Obj,Pos0,Pos),S).

The other action that makes sitting_at true is the putdown action. An object is sitting at the location where the agent who put it down was located:

sitting_at(Obj,Pos,do(putdown(Ag,Obj),S))
    poss(putdown(Ag,Obj),S)
    at(Ag,Pos,S).

The only other time that sitting_at is true in a (non-initial) situation is when it was true in the previous situation and it was not undone by an action. The only actions that undo sitting_at are a move action or a pickup action. This can be specified by the following frame axiom:

sitting_at(Obj,Pos,do(A,S))
    poss(A,S)
    sitting_at(Obj,Pos,S)
    Pos1Amove(Obj,Pos,Pos1)
    AgApickup(Ag,Obj).

Note that the quantification in the body is not the standard quantification for rules. This can be represented in a standard manner as:

sitting_at(Obj,Pos,do(A,S))
    poss(A,S)
    sitting_at(Obj,Pos,S)
    move_action(A,Obj,Pos)
    pickup_action(A,Obj).
move_action(move(Obj,Pos,Pos1),Obj,Pos).
pickup_action(pickup(Ag,Obj),Obj).

where is negation as failure. These clauses are designed not to have a free variable in the scope of the negation.

Example 15.9.

The situation calculus can represent more complicated actions than can be represented with simple addition and deletion of propositions in the state description.

Consider the drop_everything action in which an agent drops everything it is carrying. In the situation calculus, the following axiom can be added to the definition of sitting_at to say that everything the agent was carrying is now on the ground:

sitting_at(Obj,Pos,do(drop_everything(Ag),S))
    poss(drop_everything(Ag),S)
    at(Ag,Pos,S)
    carrying(Ag,Obj,S).

A frame axiom for carrying specifies that an agent is not carrying an object after a drop_everything action.

carrying(Ag,Obj,do(A,S))
    poss(A,S)
    carrying(Ag,Obj,S)
    Adrop_everything(Ag)
    Aputdown(Ag,Obj).

The drop_everything action thus affects an unbounded number of objects.

The situation calculus is used for planning by asking for a situation in which a goal is true. Answer extraction is used to find a situation in which the goal is true. This situation can be interpreted as a sequence of actions for the agent to perform.

Example 15.10.

Suppose the goal is for the robot to have the key k1. The following query asks for a situation where this is true:

𝘢𝘴𝘬 carrying(rob,k1,S).

This query has the following answer: S=do(pickup(rob,k1), do(move(rob,o103,mail), do(move(rob,o109,o103), init))). The preceding answer can be interpreted as a way for Rob to get the key: it moves from o109 to o103, then to mail, where it picks up the key.

The goal of delivering the parcel (which is, initially, in the lounge, lng) to o111 can be asked with the query

𝘢𝘴𝘬 at(parcel,o111,S).

This query has the following answer: S=do(move(rob,o109,o111), do(move(rob,lng,o109), do(pickup(rob,parcel), do(move(rob,o109,lng),init)))). Therefore, Rob should go to the lounge, pick up the parcel, go back to o109, and then go to o111.

Using the top-down proof procedure on the situation calculus definitions is very inefficient, because a frame axiom is almost always applicable. A complete proof procedure, such as iterative deepening, searches through all permutations of actions even if they are not relevant to the goal. The use of answer extraction does not negate the necessity for efficient planners, such as the ones in Chapter 6.