Action Languages

Origin. Gelfond and Lifschitz introduced action language A (1993). Subsequent: B, C, AL, and others. Formalisms for describing action effects. Connects to situation calculus and event calculus. Foundation for planning and reasoning about change.

Models. Describing action domains. Actions have preconditions and effects. Fluents: properties that change. Domain description: what actions do. Query: what holds after actions?

Formalism.

Action language A: Statements:

a causes f if p₁,...,pₙ (effect)
f if p₁,...,pₙ (static law — in extensions)

Value propositions:

initially f: f holds initially
f after a₁;...;aₙ: f holds after action sequence

Language B: Adds static laws (constraints). a causes f if p₁,...,pₙ (dynamic law) f if g₁,...,gₙ (static law/ramification)

Language C: Causal laws: caused f if p₁,...,pₙ (after a) Separates causation from effect.

Action language AL: Action description + logic programming. Nonmonotonic: defaults and exceptions.

Transition systems: Semantics: state transition system. State: truth assignment to fluents. Action: state transformer (partial function).

Example (blocks world): move(X,Y) causes on(X,Y) move(X,Y) causes ¬on(X,Z) if on(X,Z) impossible move(X,Y) if on(Z,X)

Symbols.

Symbol	Unicode	Name	Meaning
¬	U+00AC	Negation	Negative effect of an action
;	U+003B	Semicolon	Concatenation of actions in a sequence
,	U+002C	Comma	Conjunction of conditions in a law
causes	—	Dynamic law	Performing the action makes the fluent hold
caused	—	Causal law	The fluent is caused, not merely true; primitive of C
if	—	Condition	Guard on a dynamic or static law
after	—	After	Evaluates a fluent following an action sequence
initially	—	Initially	Holds in the initial state
impossible	—	Impossibility law	Rules out a transition; states a precondition
a	—	Action	Label on a transition
f	—	Fluent	Component of a state
p	—	Precondition literal	Condition under which a law applies

Metatheory. The meaning of an action description is a transition system whose nodes are complete interpretations of the fluents and whose edges are labelled by actions, so prediction, postdiction and planning are all questions about paths in one graph, and a completeness claim is the claim that some translation preserves that graph. Gelfond and Lifschitz (1993) gave such a translation of A into extended logic programs under the answer set semantics. Where the languages part company is indirect effects: B adds static laws and closes the direct effects under them by minimization, whereas C, built on McCain and Turner's (1997) logic of universal causation, requires that everything true in a successor state be caused. Their fixpoint definition — an interpretation I is a causal model of T when I is the unique classical model of the reduct T^I — makes ramification come out right in cases where minimization does not, which is the reason C exists. Complexity separates the levels: plan existence for propositional STRIPS is PSPACE-complete (Bylander 1994), while Turner (2002) showed bounded-length planning with nondeterminism and static laws to be Σ₂ᵖ-complete.

Applies to. Planning systems. Robotics. Agent programming. Diagnosis. Natural language action semantics. Game design. Business process modeling.

Limitations. This is a family rather than a formalism: A, B and C assign different transition systems to the same domain description, and nothing above them adjudicates — they diverge precisely on the ramification cases the static laws were introduced to handle. States are complete interpretations of a fixed finite set of fluents, so partial or uncertain knowledge cannot be represented inside a state at all; that requires an epistemic layer with its own semantics. Actions are instantaneous and, in the base languages, sequential, so duration, overlap and true concurrency demand extensions that alter the transition system rather than being definable over it. There is no continuous change and no numeric fluent in A, B or C; multi-valued and additive fluents arrived only with C+. Preconditions are expressed by impossibility laws, which delete transitions without saying why they fail, so the qualification problem is pushed onto the person writing the description.