Situation calculation

The situation calculus is a concept of artificial intelligence . Effects of actions on situations in a model world are described using predicate logic . The situation calculus is used, for example, in the GOLOG language , which is used in robotics for action planning , among other things .

It goes back to John McCarthy and Pat Hayes in the 1960s. It was further developed by Ray Reiter in the 1990s.

Description of the model world

Carrying out an action a leads to a follow-up situation that depends on the previous situation and the action carried out. This can be formally represented by a binary function expressed: . Not every action can be carried out in every situation. The feasibility can be defined with the help of the predicate , which is true in all situations in which the action is allowed. Situation-dependent predicates are often necessary for this definition. Relations that change their truth value over time are called fluents. ${\displaystyle s_{i+1}}$ ${\displaystyle s_{i}}$ ${\displaystyle do(a,s)}$ ${\displaystyle s_{i+1}=do(a,s_{i})}$ ${\displaystyle Poss(a,s)}$

example

A cabinet with several drawers is used as an example. Objects can be taken out of the drawers, the drawers can be opened and closed. This fact can be described as follows:

• Closed drawers can be opened! → The drawer x can be opened precisely in the situations s in which it is closed.

${\displaystyle {\textrm {Poss}}({\mathit {oeffneSchublade}}(x),s)\equiv {\mathit {istGeschlossen}}(x,s)}$

• If you open a drawer, then it's open afterwards! → If the drawer x is opened in a situation s , it follows that it is no longer closed in the following situation.

${\displaystyle {\textrm {Poss}}({\mathit {oeffneSchublade}}(x),s)\rightarrow \neg {\mathit {istGeschlossen}}(x,{\textrm {do}}({\mathit {oeffneSchublade}}(x),s))}$

• Objects that are in an open drawer can be removed! → The object y can be taken out of the drawer x in precisely those situations s in which the drawer is not closed and the object is in the drawer.

${\displaystyle {\textrm {Poss}}({\mathit {nimmAusSchublade}}(x,y),s)\equiv \neg {\mathit {istGeschlossen}}(x,s)\wedge {\mathit {istInSchublade}}(x,y,s)}$

• If you take out an object, it is no longer in the drawer! → If the object y is taken from the drawer x in a situation s , the object is no longer in the drawer in the following situation.

${\displaystyle {\textrm {Poss}}({\mathit {nimmAusSchublade}}(x,y),s)\rightarrow \neg {\mathit {istInSchublade}}(x,y,{\textrm {do}}({\mathit {nimmAusSchublade}}(x,y),s))}$

• Opened drawers can be closed! → The drawer x can be closed precisely in situations s in which it is not closed.

${\displaystyle {\textrm {Poss}}({\mathit {schliesseSchublade}}(x),s)\equiv \neg {\mathit {istGeschlossen}}(x,s)}$

• When you close a drawer, it is closed afterwards! → If the drawer x is closed in a situation s , it follows that it is closed in the following situation.

${\displaystyle {\textrm {Poss}}({\mathit {schliesseSchublade}}(x),s)\rightarrow {\mathit {istGeschlossen}}(x,{\textrm {do}}({\mathit {schliesseSchublade}}(x),s))}$

Frame problem

→ Main article : Framework problem

The previous example leads directly to the framework problem , since the clauses are not yet sufficient to describe the world. There are still no trivial clauses that only state that all other things will not be changed by the actions. Even with small worlds, these clauses become extremely numerous: With 100 different actions with 50 fluents, around 10,000 clauses are necessary for the description. Raymond Reiter found a solution to this problem in 1991 that only needs one clause to represent a fluent:

• If it is possible to carry out an action a in a situation s , then it follows that the drawer is closed in the subsequent situation if either action a was the closing of the drawer or if the drawer was already closed before, and it The action was not about opening the drawer.

${\displaystyle {\textrm {Poss}}(a,s)\rightarrow [{\mathit {istGeschlossen}}(x,{\textrm {do}}(a,s))\equiv [\,\,a={\mathit {schliesseSchublade}}(x)\,\,\vee \,\,{\mathit {istGeschlossen}}(x,s)\,\wedge \,a\neq {\mathit {oeffneSchublade}}(x)\,\,]]}$

This approach is known as the Successor State Axiom .

Axioms of the situational calculus

The axioms are the following clauses that apply in every world:

There is exactly one initial situation, no situation is before the initial situation ${\displaystyle S_{0}}$ ${\displaystyle s}$

${\displaystyle \neg (s\sqsubset S_{0})}$

Every situation is unique. If two situations are the same, created by the action in the situation and the action in the situation , then both the situations and are the same, as are the actions and . ${\displaystyle a_{1}}$ ${\displaystyle s_{1}}$ ${\displaystyle a_{2}}$ ${\displaystyle s_{2}}$ ${\displaystyle s_{1}}$ ${\displaystyle s_{2}}$ ${\displaystyle a_{1}}$ ${\displaystyle a_{2}}$

${\displaystyle {\textrm {do}}(a_{1},s_{1})\!=\!{\textrm {do}}(a_{2},s_{2})\;\rightarrow \;a_{1}\!=\!a_{2}\,\wedge \,s_{1}\!=\!s_{2}}$

A statement is true in all situations if it is true in the initial situation and the statement remains true in any situation even after taking any action.

${\displaystyle \forall {\textrm {P}}.\quad {\textrm {P}}(S_{0})\,\wedge \,\forall a\,\forall s\left[{\textrm {P}}(s)\!\rightarrow \!{\textrm {P}}({\textrm {do}}(a,s))\right]\;\rightarrow \;\forall s\,{\textrm {P}}(s)}$

Some of the situations can be sorted. The comparison operator is defined recursively: a situation that precedes a situation that results from executing the action in the situation is either the situation or a situation that precedes it. ${\displaystyle \sqsubset }$ ${\displaystyle s_{1}}$ ${\displaystyle {\textrm {do}}(a,s_{2})}$ ${\displaystyle a}$ ${\displaystyle s_{2}}$ ${\displaystyle s_{2}}$ ${\displaystyle s_{2}}$

${\displaystyle s_{1}\sqsubset {\textrm {do}}(a,s_{2})\,\,\equiv \,\,s_{1}\!=\!s_{2}\,\vee \,s_{1}\sqsubset s_{2}\,\,\equiv \,\,s_{1}\sqsubseteq s_{2}}$

comment

If the initial condition is that there is a ball in the closed left drawer and the goal is that the ball should no longer be there, a plan can be calculated, taking into account all clauses, which opens the left drawer and removes the ball the drawer takes.

See also

• Logic calculus

literature

• Hermann Scheffler : The situation calculation. Attempt of an arithmetic representation of the lower and higher geometry on the basis of an abstract conception of the spatial sizes, shapes and movements . Braunschweig, Friedrich Vieweg, 1851.
• Christoph Beierle, Gabriele Kern-Isberner: Methods of knowledge-based systems: fundamentals, algorithms, applications. Teubner-Verlag, 2008, p. 304.
• Raymond Reiter: Knowledge in Action. Logical Foundations for Specifying and Implementing Dynamical Systems . 2001, ISBN 0-262-18218-1 .
• Raymond Reiter: The frame problem in the situation calculus: a simple solution (sometimes) and a completeness result for goal regression. In: Vladimir Lifschitz (Ed.): Artificial Intelligence and Mathematical Theory of Computation: Papers in Honor of John McCarthy , pp. 359-380. Academic Press, New York, 1991. ISBN 0-124-50010-2 .

Individual evidence

1. ↑ http://prism.cs.umd.edu/papers/Min02:reiter_memoriam/Min02:reiter_memoriam.html