situation calculus
In plain wordsA logical language for describing how the world changes as actions happen, so that a program can work out what will be true after any sequence of actions.
A logical formalism, essentially first-order logicfirst-order logic, n.: A precise formal language for statements about objects and their relations, using 'for all' and 'there exists', such as 'every person has a mother'. It is the standard logic of mathematics and of classic AI. plus a few second-order devices, in which one can describe how actions alter the world and deduce what holds after any sequence of them. Situations are terms denoting histories of actions — the initial situation S0, and do(a, s), the situation that results from performing action a in situation s — and fluents are relations whose truth varies from situation to situation, such as Holding(x, s). Action preconditions and effects are stated as axioms, and planning becomes deduction: proving that some sequence of actions leads to a situation satisfying the goal. Its central difficulty, the frame problemframe problem, n.: The difficulty of getting an AI to work out what does and does not change when something happens, without spelling out every one of the countless things that stay the same. of stating what an action leaves unchanged, received a widely adopted solution in Ray Reiter's successor state axioms (1991), which gather all the ways a fluent can change into a single formula. The GOLOG family of agent programming languages builds on it; the event calculus is a related formalism based on time points.
Origin
Introduced by John McCarthy in the 1963 Stanford AI memo 'Situations, Actions and Causal Laws' and developed with Patrick Hayes in their 1969 paper, which also identified the frame problem. Ray Reiter's group at Toronto reformulated it in the 1990s, culminating in his book Knowledge in Action (2001).
Related
- frame problemframe problem, n.: The difficulty of getting an AI to work out what does and does not change when something happens, without spelling out every one of the countless things that stay the same.
- automated planningautomated planning, n.: The branch of AI that works out a sequence of actions to reach a goal, such as the steps a robot must take to assemble a part, from descriptions of what each action needs and what it changes.
- first-order logicfirst-order logic, n.: A precise formal language for statements about objects and their relations, using 'for all' and 'there exists', such as 'every person has a mother'. It is the standard logic of mathematics and of classic AI.
- knowledge representationknowledge representation, n.: The study of how to record knowledge about objects, categories, rules and events in a precise format, so that a program can reason with it and reach conclusions nobody typed in.
- non-monotonic reasoningnon-monotonic reasoning, n.: Reasoning in which new information can overturn earlier conclusions — you assume a bird can fly until you learn it is a penguin — as people do constantly but classical logic does not allow.
- STRIPSSTRIPS, prop. n.: An early AI planning program, and the simple action language it introduced, in which each action lists what must be true beforehand, what becomes true and what stops being true.
Sources
- McCarthy, J. & Hayes, P. J. (1969). Some Philosophical Problems from the Standpoint of Artificial Intelligence. Machine Intelligence 4, 463–502.
- Reiter, R. (2001). Knowledge in Action: Logical Foundations for Specifying and Implementing Dynamical Systems. MIT Press.
Mentioned in
automated planningautomated planning, n.: The branch of AI that works out a sequence of actions to reach a goal, such as the steps a robot must take to assemble a part, from descriptions of what each action needs and what it changes., commonsense reasoningcommonsense reasoning, n.: The everyday background knowledge and reasoning people take for granted — dropped glasses break, hungry people eat, nobody is in two places at once — which machines long struggled to match., knowledge representationknowledge representation, n.: The study of how to record knowledge about objects, categories, rules and events in a precise format, so that a program can reason with it and reach conclusions nobody typed in., non-monotonic reasoningnon-monotonic reasoning, n.: Reasoning in which new information can overturn earlier conclusions — you assume a bird can fly until you learn it is a penguin — as people do constantly but classical logic does not allow., STRIPSSTRIPS, prop. n.: An early AI planning program, and the simple action language it introduced, in which each action lists what must be true beforehand, what becomes true and what stops being true., temporal logictemporal logic, n.: A logic for statements about time — 'eventually the light turns green', 'the door is never open while the train moves' — used to specify and check how systems must behave over time.