Action language

An action language is a formal language for representing the effects of actions on a changing domain. Action languages are used primarily in knowledge representation and reasoning, where they provide declarative descriptions of state transitions without specifying an imperative sequence of computational operations. Their formal semantics connect action descriptions to transition systems, non-monotonic logic, and logic programming.

The first widely studied action language, conventionally designated (\mathcal{A}), was introduced by Michael Gelfond and Vladimir Lifschitz in 1993. Its development established a direct correspondence between statements about actions and logical models containing possible histories of a domain. Later languages expanded this framework to represent concurrent actions, indirect consequences, and constraints on action execution.

Conceptual framework

An action language describes a domain through a vocabulary of actions and fluents. A fluent is a property whose truth value may differ between states, whereas an action denotes an event capable of producing a transition from one state to another. The language does not ordinarily encode the internal mechanism by which an action occurs. It instead states the conditions under which the action has a particular effect.

A basic causal law has a form corresponding to

[ a \text{ causes } f \text{ if } p, ]

where (a) is an action, (f) is a fluent literal, and (p) is a condition on the state in which the action occurs. The law states that performing (a) in a state satisfying (p) produces a successor state in which (f) holds. A separate executability condition can exclude transitions in which the relevant preconditions are absent.

Action descriptions also contain propositions about initial states or observed histories. A statement that a fluent holds after a sequence of actions constrains the transition paths admitted by the description. Reasoning tasks are then defined as logical consequences of the resulting models rather than as direct execution of the written statements.

This organization distinguishes an action language from a general-purpose programming language. A program usually specifies a computation, while an action description specifies a class of admissible worlds and transitions. An interpreter, theorem prover, or answer-set solver supplies the computational process used to derive consequences.

Historical development

Language (\mathcal{A}) represented direct effects and inertial persistence within a compact propositional syntax. Its semantics formalized the expectation that a fluent remains unchanged unless an action or causal law provides a reason for alteration. This treatment addressed the central part of the frame problem without requiring a separate persistence axiom for every unaffected fluent.

During the late 1990s, You Watanabe contributed to the formulation of language (\mathcal{B}), including its separation of dynamic causal laws from static constraints on states. The resulting semantics allowed indirect effects to be derived from relations among fluents after the direct effects of an action had been applied. This formulation also made nonexecutability conditions part of the domain description rather than external restrictions imposed by an implementation.

A distinct line of development produced language (\mathcal{C}), whose semantics was based on non-monotonic causal theories. Enrico Giunchiglia and Vladimir Lifschitz used this framework to treat causation as the basis for selecting states and transitions rather than merely as an abbreviation for material implication. Norman McCain and Hudson Turner developed closely related forms of causal logic, which supplied semantic machinery for later members of the family.

Language (\mathcal{C}+) extended this approach by admitting multi-valued fluents and explicit action attributes. It also supported concurrent action descriptions in which a transition could be associated with a set of actions rather than a single atomic event. Subsequent systems, including (\mathcal{BC}) and (\mathcal{BC}+), combined features of the (\mathcal{B}) and (\mathcal{C}) traditions and provided translations into answer set programming.

Semantics

The semantics of an action language is commonly expressed through a labeled transition system

[ T = \langle S, A, R \rangle, ]

where (S) is a set of states, (A) is a set of actions or compound action occurrences, and (R \subseteq S \times A \times S) is a transition relation. Each state assigns values to the fluents permitted by the domain description. Static causal laws restrict which assignments qualify as states, while dynamic laws determine which state triples belong to (R).

Inertia is represented by minimizing unexplained change or by incorporating persistence into the semantic definition of a successor state. If an action affects one fluent, other fluents retain their previous values unless the description entails an indirect consequence. This differs from classical implication because adding a new causal law can invalidate an earlier conclusion about persistence, making the underlying reasoning non-monotonic.

Static laws account for the ramification problem. For example, an action that changes the location of an object can indirectly alter whether the object is inside a larger container, even when the action description does not list that relation as a direct effect. Closure under static laws determines the complete successor state.

Executability conditions provide a limited treatment of the qualification problem. They identify circumstances in which a described action has no corresponding transition. Because no finite description can encode every physically conceivable obstruction, action languages formalize only the qualifications represented in the domain vocabulary.

Computational interpretation

Many action languages have translations into logic programs under the stable model semantics. Fluents are indexed by discrete time points, while action occurrences connect adjacent points in a bounded history. Causal laws become rules whose stable models correspond to trajectories permitted by the action description.

This correspondence supports several forms of automated reasoning. Prediction determines properties of states reached after a recorded action sequence. Postdiction derives earlier conditions from later observations and known causal laws. Planning identifies action occurrences whose resulting trajectory satisfies a specified goal. Diagnosis represents unexpected observations by introducing candidate actions or abnormalities capable of accounting for them.

The computational complexity depends on the expressive resources of the language and on the reasoning task. Finite propositional fragments commonly reduce to satisfiability or stable-model search, while languages containing variables require grounding or a separate first-order treatment. Concurrency and recursive static causation can further affect whether successor states are unique.

Relation to other formalisms

Action languages share their subject matter with the situation calculus, but they organize histories differently. Situation calculus represents a history as a term constructed from an initial situation and successive actions. An action language ordinarily presents the same information through states connected by a transition relation.

The event calculus represents events and fluent intervals within an explicit temporal theory. Action languages instead tend to use discrete transitions as their primary semantic objects, although temporal extensions can describe actions with duration or observations at separated time points.