Artificial Intelligence - foundations of computational agents -- 14.1.1 Situation Calculus

Third edition of Artificial Intelligence: foundations of computational agents, Cambridge University Press, 2023 is now available (including the full text).

14.1.1 Situation Calculus

The idea behind situation calculus is that (reachable) states are definable in terms of the actions required to reach them. These reachable states are called situations. What is true in a situation can be defined in terms of relations with the situation as an argument. Situation calculus can be seen as a relational version of the feature-based representation of actions.

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

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 14.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.

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 picks 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 can 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 exists that 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. However, sometimes an agent must reason about such a (potential) situation without knowing if A is possible in state S, or if S is possible.

Example 14.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.

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 14.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. Typically, this is done inductively in terms of the structure of situations.

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.
Static relations are defined without reference to the situation.

Example 14.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(P₁,P₂,S)←
between(Door,P₁,P₂)∧
unlocked(Door,S).

Notice the free S variable; these clauses are true for all situations. We cannot omit the S because which rooms are adjacent depends on whether a door is 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 distinguish whether or not an agent is being carried. If an object is not being carried, we say that the object is sitting at its location. We distinguish this case because an object being carried 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 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 14.5: An agent can always put down an object it is carrying:

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

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

poss(move(Ag,P₁,P₂),S) ←
     autonomous(Ag) ∧
     adjacent(P₁,P₂,S)∧
     sitting_at(Ag,P₁,S) .

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

poss(unlock(Ag,Door),S)←
     autonomous(Ag)∧
     between(Door,P₁,P₂)∧
     at(Ag,P₁,S)∧
     opens(Key,Door)∧
     carrying(Ag,Key,S).

We do not assume that the between relation is symmetric. Some doors can only open one way.

We define what is true in each situation recursively in terms of the previous situation and of 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 14.6: The primitive unlocked relation can be defined by specifying how different actions can affect its being true. The door is unlocked in the situation resulting from an unlock action, as long as the unlock action was possible. This is represented using the following 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)∧
     A≠lock(Door) ∧
     poss(A,S).

This is a frame rule.

Example 14.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)∧
     A ≠putdown(Ag,Obj).

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

sitting_at(Obj,Pos,do(move(Obj,Pos₀,Pos),S)) ←
poss(move(Obj,Pos₀,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 is 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) ∧
     ∀Pos₁    A≠move(Obj,Pos,Pos₁) ∧
     ∀Ag    A≠pickup(Ag,Obj) .

Note that the quantification in the body is not the standard quantification for rules. This can be represented using negation as failure:

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,Pos₁),Obj,Pos).
pickup_action(pickup(Ag,Obj),Obj).

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

Example 14.9: 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 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)∧
     A ≠drop_everything(Ag)∧
     A ≠putdown(Ag,Obj).

The drop_everything action thus affects an unbounded number of objects.

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 14.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 8.