The situation calculus is a logic formalism designed for representing and reasoning about dynamical domains. It was first introduced by John McCarthy in 1963. The main version of the situational calculus that is presented in this article is based on that introduced by Ray Reiter in 1991. It is followed by sections about McCarthy's 1986 version and a logic programming formulation.
Contents
Overview
The situation calculus represents changing scenarios as a set of first-order logic formulae. The basic elements of the calculus are:
A domain is formalized by a number of formulae, namely:
A simple robot world will be modeled as a running example. In this world there is a single robot and several inanimate objects. The world is laid out according to a grid so that locations can be specified in terms of
Elements
The main elements of the situation calculus are the actions, fluents and the situations. A number of objects are also typically involved in the description of the world. The situation calculus is based on a sorted domain with three sorts: actions, situations, and objects, where the objects include everything that is not an action or a situation. Variables of each sort can be used. While actions, situations, and objects are elements of the domain, the fluents are modeled as either predicates or functions.
Actions
The actions form a sort of the domain. Variables of sort action can be used. Actions can be quantified. A special predicate
In the example robot world, possible action terms would be
Situations
In the situation calculus, a dynamic world is modeled as progressing through a series of situations as a result of various actions being performed within the world. A situation represents a history of action occurrences. In the Reiter version of the situation calculus described here, a situation does not represent a state, contrarily to the literal meaning of the term and contrarily to the original definition by McCarthy and Hayes. This point has been summarized by Reiter as follows:
A situation is a finite sequence of actions. Period. It's not a state, it's not a snapshot, it's a history [1].The situation before any actions have been performed is typically denoted
The fact that situations are sequences of actions and not states is enforced by an axiom stating that
In the example robot world, if the robot's first action is to move to location
Fluents
Statements whose truth value may change are modeled by relational fluents, predicates which take a situation as their final argument. Also possible are functional fluents, functions which take a situation as their final argument and return a situation-dependent value. Fluents may be thought of as "properties of the world"'.
In the example, the fluent
Formulae
The description of a dynamic world is encoded in second order logics using three kinds of formulae: formulae about actions (preconditions and effects), formulae about the state of the world, and foundational axioms.
Action preconditions
Some actions may not be executable in a given situation. For example, it is impossible to put down an object unless one is in fact carrying it. The restrictions on the performance of actions are modeled by literals of the form
As a more complex example, the following models that the robot can carry only one object at a time, and that some objects are too heavy for the robot to lift (indicated by the predicate
Action effects
Given that an action is possible in a situation, one must specify the effects of that action on the fluents. This is done by the effect axioms. For example, the fact that picking up an object causes the robot to be carrying it can be modeled as:
It is also possible to specify conditional effects, which are effects that depend on the current state. The following models that some objects are fragile (indicated by the predicate
While this formula correctly describes the effect of the actions, it is not sufficient to correctly describe the action in logic, because of the frame problem.
The frame problem
While the above formulae seem suitable for reasoning about the effects of actions, they have a critical weakness - they cannot be used to derive the non-effects of actions. For example, it is not possible to deduce that after picking up an object, the robot's location remains unchanged. This requires a so-called frame axiom, a formula like:
The need to specify frame axioms has long been recognised as a problem in axiomatizing dynamic worlds, and is known as the frame problem. As there are generally a very large number of such axioms, it is very easy for the designer to leave out a necessary frame axiom, or to forget to modify all appropriate axioms when a change to the world description is made.
The successor state axioms
The successor state axioms "solve" the frame problem in the situation calculus. According to this solution, the designer must enumerate as effect axioms all the ways in which the value of a particular fluent can be changed. The effect axioms affecting the value of fluent
The formula
If this pair of axioms describe all the ways in which fluent
In words, this formula states: "given that it is possible to perform action
By way of example, the value of the fluent
States
The properties of the initial or any other situation can be specified by simply stating them as formulae. For example, a fact about the initial state is formalized by making assertions about
Foundational axioms
The foundational axioms of the situation calculus formalize the idea that situations are histories by having
Regression
Regression is a mechanism for proving consequences in the situation calculus. It is based on expressing a formula containing the situation
GOLOG
GOLOG is a logic programming language based on the situation calculus.
The original version of the situation calculus
The main difference between the original situation calculus by McCarthy and Hayes and the one in use today is the interpretation of situations. In the modern version of the situational calculus, a situation is a sequence of actions. Originally, situations were defined as “the complete state of the universe at an instant of time”. It was clear from the beginning that such situations could not be completely described; the idea was simply to give some statements about situations, and derive consequences from them. This is also different from the approach that is taken by the fluent calculus, where a state can be a collection of known facts, that is, a possibly incomplete description of the universe.
In the original version of the situation calculus, fluents are not reified. In other words, conditions that can change are represented by predicates and not by functions. Actually, McCarthy and Hayes defined a fluent as a function that depends on the situation, but they then proceeded always using predicates to represent fluents. For example, the fact that it is raining at place
The execution of actions is represented by the function
The predicates
These formulae are not sufficient to derive everything that is considered plausible. Indeed, fluents at different situations are only related if they are preconditions and effects of actions; if a fluent is not affected by an action, there is no way to deduce it did not change. For example, the formula above does not imply that
In the original formulation of the situation calculus, the initial situation, later denoted by
The version of the situation calculus introduced by McCarthy in 1986 differs to the original one for the use of functional fluents (e.g.,
The situation calculus as a logic program
It is also possible (e.g. Kowalski 1979, Apt and Bezem 1990, Shanahan 1997) to write the situation calculus as a logic program:
Here