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
causes	—	Effect	Action causes fluent
if	—	Condition	When
after	—	After	Post-sequence
initially	—	Initially	At start
impossible	—	Impossible	Precondition
;	—	Sequence	Action sequence

Metatheory. Translation to logic programs (ASP). Reasoning tasks: prediction, postdiction, planning. Complexity: varies by language. Answer Set Programming connection. Complete for transition system semantics.

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

Limitations. Many competing languages. Concurrency needs extensions. Continuous change not native. Duration not built-in. Probabilistic extensions separate. Learning actions challenging.