foundations of computational agents
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
, the initial situation, or
, the situation resulting from doing action in situation , if it is possible to do action in situation .
Consider the domain of Figure 3.1. Suppose in the initial situation, , the robot, Rob, is at location and there is a key at the mail room and a package at . Suppose is the action of agent moving from location to location .
is the situation resulting from Rob moving from position in situation to position . In this situation, Rob is at , the key is still at , and the package is at .
The situation is one in which the robot has moved from position to to and is currently at mail. Suppose Rob then carries out the action , which is to pick up the key . The resulting situation is . In this situation, Rob is at position carrying the key .
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 terms do not correspond to any state. Sometimes an agent must reason about such a (potential) situation without knowing whether is possible in state , or whether is possible.
The term 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.
all represent the same state, with the robot at location , and everything else that is true in the initial state. In the last two situations, the robot has moved away from 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 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.
The relation is true when object is at location in situation . Thus, is a fluent.
is true if the robot is at position in the initial situation. The atom
is true if robot is at position in the situation resulting from moving from position to position from the initial situation. The atom
is true if is at position in the situation resulting from Rob moving from position to position 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 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 in terms of what is true in situation . 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.
Suppose the delivery robot, Rob, is in the domain depicted in Figure 3.1. Rob is at location , the parcel is in the storage room, and the key is in the mail room. The following axioms describe this initial situation:
The relation is a dynamic, derived relation defined as follows:
Notice the free variable; these clauses are true for all situations. The situation term, , cannot be omitted because which rooms are adjacent depends on which doors are unlocked. This can change from situation to situation.
The relation is static and does not require a situation variable:
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, is a derived relation:
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 is true when action is possible in situation . This is typically a derived relation.
An autonomous agent can put down an object it is carrying:
For the action, an autonomous agent can move from its current position to an adjacent position:
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:
The 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.
The primitive relation 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:
Suppose the only action to make the door locked is to lock the door. Thus, 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:
This is a frame rule.
The predicate can be defined as follows.
An agent is carrying an object after picking up the object:
The only action that undoes the predicate is the action. Thus, 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:
The atom is true in a situation resulting from object moving to , as long as the action was possible:
The other action that makes true is the action. An object is sitting at the location where the agent who put it down was located:
The only other time that 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 are a action or a action. This can be specified by the following frame axiom:
Note that the quantification in the body is not the standard quantification for rules. This can be represented in a standard manner as:
where is negation as failure. These clauses are designed not to have a free variable in the scope of the negation.
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 action in which an agent drops everything it is carrying. In the situation calculus, the following axiom can be added to the definition of to say that everything the agent was carrying is now on the ground:
A frame axiom for specifies that an agent is not carrying an object after a action.
The 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.
Suppose the goal is for the robot to have the key . The following query asks for a situation where this is true:
This query has the following answer: . The preceding answer can be interpreted as a way for Rob to get the key: it moves from to , then to , where it picks up the key.
The goal of delivering the parcel (which is, initially, in the lounge, ) to can be asked with the query
This query has the following answer: . Therefore, Rob should go to the lounge, pick up the parcel, go back to , and then go to .
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.