15.1 Planning with Individuals and Relations 15.1 Planning with Individuals and Relations 15.1.2 Event Calculus

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

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

•

$i n i t$ , 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, $i n i t$ , the robot, Rob, is at location $o109$ and there is a key $k1$ at the mail room and a package at $s t o r a g e$ . Suppose $move(Ag,L_{0},L_{1})$ is the action of agent $A g$ moving from location $L_{0}$ to location $L_{1}$ .

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

is the situation resulting from Rob moving from position $o109$ in situation $i n i t$ to position $o103$ . In this situation, Rob is at $o103$ , the key $k1$ is still at $m a i l$ , and the package is at $s t o r a g e$ .

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 $m a i l$ 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 $m a i l$ 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:

	$\displaystyle init$
	$\displaystyle do(move(rob,o103,o109),do(move(rob,o103,o109),init))$
	$\displaystyle 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 $i n i t$ 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, $a t$ is a fluent.

The atom

at(rob,o109,init)

is true if the robot $r o b$ is at position $o109$ in the initial situation. The atom

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

is true if robot $r o b$ is at position $o103$ in the situation resulting from $r o b$ 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 $m a i l$ 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 $i n i t$ 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:

	$\displaystyle{at(rob,o109,init).}$
	$\displaystyle{at(parcel,storage,init).}$
	$\displaystyle{at(k1,mail,init).}$

The $a d j a c e n t$ relation is a dynamic, derived relation defined as follows:

	$\displaystyle{adjacent(o109,o103,S).}$
	$\displaystyle{adjacent(o103,o109,S).}$
	$\displaystyle{adjacent(o109,storage,S).}$
	$\displaystyle{adjacent(storage,o109,S).}$
	$\displaystyle{adjacent(o109,o111,S).}$
	$\displaystyle{adjacent(o111,o109,S).}$
	$\displaystyle{adjacent(o103,mail,S).}$
	$\displaystyle{adjacent(mail,o103,S).}$
	$\displaystyle{adjacent(lab2,o109,S).}$
	$\displaystyle{adjacent(P_{1},P_{2},S)\leftarrow}$
	$\displaystyle\ \ \ \ {between(Door,P_{1},P_{2})\wedge\mbox{}}$
	$\displaystyle\ \ \ \ {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 $b e t w e e n$ relation is static and does not require a situation variable:

\displaystyle{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:

	$\displaystyle{at(Ob,P,S)\leftarrow\mbox{}}$
	$\displaystyle\ \ \ \ {sitting\_at(Ob,P,S).}$
	$\displaystyle{at(Ob,P,S)\leftarrow\mbox{}}$
	$\displaystyle\ \ \ \ {carrying(Ob1,Ob,S)\wedge\mbox{}}$
	$\displaystyle\ \ \ \ {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:

	$\displaystyle{poss(putdown(Ag,Obj),S)\leftarrow}$
	$\displaystyle\ \ \ \ {autonomous(Ag)\wedge\mbox{}}$
	$\displaystyle\ \ \ \ {carrying(Ag,Obj,S).}$

For the $m o v e$ action, an autonomous agent can move from its current position to an adjacent position:

	$\displaystyle{poss(move(Ag,P_{1},P_{2}),S)\leftarrow}$
	$\displaystyle\ \ \ \ {autonomous(Ag)\wedge\mbox{}}$
	$\displaystyle\ \ \ \ {adjacent(P_{1},P_{2},S)\wedge\mbox{}}$
	$\displaystyle\ \ \ \ {sitting\_at(Ag,P_{1},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:

	$\displaystyle{poss(unlock(Ag,Door),S)\leftarrow}$
	$\displaystyle\ \ \ \ {autonomous(Ag)\wedge\mbox{}}$
	$\displaystyle\ \ \ \ {between(Door,P_{1},P_{2})\wedge\mbox{}}$
	$\displaystyle\ \ \ \ {at(Ag,P_{1},S)\wedge\mbox{}}$
	$\displaystyle\ \ \ \ {opens(Key,Door)\wedge\mbox{}}$
	$\displaystyle\ \ \ \ {carrying(Ag,Key,S).}$

The $b e t w e e n$ 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 $u n l o c k e d$ 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:

	$\displaystyle{unlocked(Door,do(unlock(Ag,Door),S))\leftarrow}$
	$\displaystyle\ \ \ \ {poss(unlock(Ag,Door),S).}$

Suppose the only action to make the door locked is to lock the door. Thus, $u n l o c k e d$ 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:

	$\displaystyle{unlocked(Door,do(A,S))\leftarrow}$
	$\displaystyle\ \ \ \ {unlocked(Door,S)\wedge\mbox{}}$
	$\displaystyle\ \ \ \ {A\neq lock(Door)\wedge\mbox{}}$
	$\displaystyle\ \ \ \ {poss(A,S).}$

This is a frame rule.

Example 15.7.

The $c a r r y i n g$ predicate can be defined as follows.

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

	$\displaystyle{carrying(Ag,Obj,do(pickup(Ag,Obj),S))\leftarrow}$
	$\displaystyle\ \ \ \ {poss(pickup(Ag,Obj),S).}$

The only action that undoes the $c a r r y i n g$ predicate is the $p u t d o w n$ action. Thus, $c a r r y i n g$ 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:

	$\displaystyle{carrying(Ag,Obj,do(A,S))\leftarrow}$
	$\displaystyle\ \ \ \ {carrying(Ag,Obj,S)\wedge\mbox{}}$
	$\displaystyle\ \ \ \ {poss(A,S)\wedge\mbox{}}$
	$\displaystyle\ \ \ \ {A\neq putdown(Ag,Obj).}$

Example 15.8.

The atom $sitting\_at(Obj,Pos,S_{1})$ is true in a situation $S_{1}$ resulting from object $O b j$ moving to $P o s$ , as long as the action was possible:

	$\displaystyle{sitting\_at(Obj,Pos,do(move(Obj,Pos_{0},Pos),S))\leftarrow}$
	$\displaystyle\ \ \ \ {poss(move(Obj,Pos_{0},Pos),S).}$

The other action that makes $sitting\_at$ true is the $p u t d o w n$ action. An object is sitting at the location where the agent who put it down was located:

	$\displaystyle{sitting\_at(Obj,Pos,do(putdown(Ag,Obj),S))\leftarrow}$
	$\displaystyle\ \ \ \ {poss(putdown(Ag,Obj),S)\wedge\mbox{}}$
	$\displaystyle\ \ \ \ {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 $m o v e$ action or a $p i c k u p$ action. This can be specified by the following frame axiom:

	$\displaystyle{sitting\_at(Obj,Pos,do(A,S))\leftarrow}$
	$\displaystyle\ \ \ \ {poss(A,S)\wedge\mbox{}}$
	$\displaystyle\ \ \ \ {sitting\_at(Obj,Pos,S)\wedge\mbox{}}$
	$\displaystyle\ \ \ \ {\forall Pos_{1}~{}~{}A\neq move(Obj,Pos,Pos_{1})\wedge% \mbox{}}$
	$\displaystyle\ \ \ \ {\forall Ag~{}~{}A\neq pickup(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:

	$\displaystyle{sitting\_at(Obj,Pos,do(A,S))\leftarrow}$
	$\displaystyle\ \ \ \ {poss(A,S)\wedge\mbox{}}$
	$\displaystyle\ \ \ \ {sitting\_at(Obj,Pos,S)\wedge\mbox{}}$
	$\displaystyle\ \ \ \ {\mbox{$\sim$}move\_action(A,Obj,Pos)\wedge\mbox{}}$
	$\displaystyle\ \ \ \ {\mbox{$\sim$}pickup\_action(A,Obj).}$
	$\displaystyle{move\_action(move(Obj,Pos,Pos_{1}),Obj,Pos).}$
	$\displaystyle{pickup\_action(pickup(Ag,Obj),Obj).}$

where $\sim$ 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:

	$\displaystyle{sitting\_at(Obj,Pos,do(drop\_everything(Ag),S))\leftarrow}$
	$\displaystyle\ \ \ \ {poss(drop\_everything(Ag),S)\wedge\mbox{}}$
	$\displaystyle\ \ \ \ {at(Ag,Pos,S)\wedge\mbox{}}$
	$\displaystyle\ \ \ \ {carrying(Ag,Obj,S).}$

A frame axiom for $c a r r y i n g$ specifies that an agent is not carrying an object after a $drop\_everything$ action.

	$\displaystyle{carrying(Ag,Obj,do(A,S))\leftarrow}$
	$\displaystyle\ \ \ \ {poss(A,S)\wedge\mbox{}}$
	$\displaystyle\ \ \ \ {carrying(Ag,Obj,S)\wedge\mbox{}}$
	$\displaystyle\ \ \ \ {A\neq drop\_everything(Ag)\wedge\mbox{}}$
	$\displaystyle\ \ \ \ {A\neq putdown(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:

\mbox{{ask}~{}}{}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 $m a i l$ , where it picks up the key.

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

\mbox{{ask}~{}}{}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.

Artificial Intelligence 2E