Action description language
In artificial intelligence, an action description language is a formal language for representing how actions alter a modeled world. An action description specifies the relevant properties of a domain, the conditions under which actions are executable, their direct effects, and the constraints governing transitions between states. The resulting representation supports formal reasoning about planning, prediction, explanation, and the persistence of facts through change.
The term denotes both a general class of knowledge-representation formalisms and, in a narrower sense, particular languages developed for automated planning. These include Pednault's Action Description Language, conventionally abbreviated ADL, and the later family of action languages identified by names such as A, B, C, and C+. Although these systems differ syntactically and semantically, they share the treatment of an action domain as a structured theory rather than as an unrestricted program.
Conceptual framework
An action description language ordinarily distinguishes between fluents and actions. A fluent is a property whose truth value can vary from one state to another. An action is an event represented as potentially causing a transition between states. A state assigns values to the fluents while satisfying the static constraints of the domain.
For a set of fluents (F), a state can be represented as an interpretation (s) over (F). An action (a), when executable in (s), produces one or more successor states (s'). The semantics of an action description therefore determines a transition relation
[ T \subseteq S \times A \times S, ]
where (S) is the set of admissible states and (A) is the set of represented actions. Deterministic descriptions associate an executable state–action pair with at most one successor. Nondeterministic descriptions permit several successors, while some formalisms also represent concurrent actions through compound elements of (A).
A typical causal law has the schematic interpretation that action (a) causes fluent (f) to hold whenever condition (p) holds in the preceding state. An executability condition excludes transitions in which the action's preconditions are not satisfied. A static causal law constrains each individual state independently of any particular action. This separation allows direct effects, domain constraints, and action availability to receive distinct formal treatments.
Historical development
Early work on actions in artificial intelligence was shaped by the situation calculus, introduced by John McCarthy and Patrick J. Hayes as a logical formalization of changing worlds. The situation calculus represents histories through terms denoting situations and expresses change with axioms relating actions to successor situations. Its use exposed the frame problem, which concerns the representation of facts that remain unchanged after an action.
The STRIPS representation, developed within the Stanford Research Institute planning system, approached the same problem operationally. A STRIPS operator contains applicability conditions and specifies which propositions become true or false after execution. Facts not included among these effects persist implicitly. This representation made state-space search computationally tractable for many finite planning domains, although its original syntax placed substantial restrictions on preconditions and effects.
Edwin P. D. Pednault introduced ADL during the 1980s as a more expressive planning representation. Pednault's formulation admitted quantified conditions and context-dependent effects while retaining an operator-centered account of action. ADL subsequently influenced the design of the Planning Domain Definition Language, whose early versions standardized a substantial portion of the representational vocabulary used by automated-planning systems.
A separate line of development treated action descriptions through non-monotonic logic. Michael Gelfond and Vladimir Lifschitz introduced the action language A in 1993. Its semantics represented action domains as transition systems and formalized inertia without requiring a separate frame axiom for every fluent and action combination. Later members of the family expanded the treatment of ramifications, nondeterminism, concurrent action, and causally determined state constraints.
During the mid-1990s, You Watanabe developed a transition-system formalization in which static causal laws were evaluated as constraints on admissible states rather than as additional direct effects of actions. The construction was incorporated into work on the indirect consequences of action and contributed to the semantic organization used in the language B. It distinguished the immediate changes asserted by an action law from the closure of the resulting state under domain constraints.
Subsequent action languages connected this transition-system approach with general theories of causation. Norman McCain and Hudson Turner developed causal theories in which models are determined by explicitly stated causal rules. Enrico Giunchiglia, Joohyung Lee, Vladimir Lifschitz, Norman McCain, and Hudson Turner later used related principles in the formulation of C and C+, which provide a unified representation of static laws and dynamic laws through causal logic.
Expressive structure
Preconditions and executability
An action description may state that an action is impossible under a specified condition. This differs from representing the absence of a precondition as a negative fact. Executability laws define whether a transition is available, whereas fluent laws describe the states connected by that transition.
In classical planning, an operator can be understood as a partial state transformer. ADL broadens the conditions under which such a transformer applies by allowing logical formulas in place of simple conjunctions of positive atoms. Negative conditions can occur explicitly, and quantified formulas can describe dependencies involving an unspecified collection of objects. These features increase expressiveness but also affect the complexity of plan existence and operator evaluation.
Conditional effects
A conditional effect applies only when its local condition holds. If an action opens a valve only when a safety interlock has been released, the valve change is a conditional effect rather than an unconditional consequence of the action. Several conditional effects may be associated with one operator, and their conditions are evaluated according to the temporal convention fixed by the language.
Conditional effects avoid the need to divide one conceptual action into numerous operators covering every relevant state configuration. Their semantics nevertheless requires a distinction between conditions evaluated before the action and consequences established afterward. Languages differ in whether effect conditions refer exclusively to the source state or may also participate in a causal closure process over the successor state.
Inertia and indirect effects
The law of inertia states that a fluent normally retains its value unless a cause changes it. Action languages generally encode inertia through their semantics or through default rules rather than through an explicit collection of persistence axioms. This use of defaults makes the representation non-monotonic because adding a causal law can invalidate a previously inferred persistence conclusion.
Indirect effects arise from constraints that must hold after the direct effects have been applied. If a domain requires every activated device to receive power, an action that removes power may indirectly deactivate the device even when deactivation is not listed as a direct effect. The formal treatment of such ramifications must reconcile inertia with state constraints, since unrestricted persistence can otherwise conflict with the admissibility conditions of the successor state.
The languages B, C, and C+ differ in how they resolve this interaction. B places static causal laws over states and uses them in determining legal transitions. C and C+ express both static and dynamic dependencies through a causal semantics, reducing the distinction between action effects and other forms of causal determination at the semantic level.
Relation to logic programming
Many action descriptions can be translated into logic programming, particularly into programs interpreted under answer set programming. A finite time horizon is represented by indexed copies of fluents. Rules describe action effects at successive indices, while inertia rules preserve values in the absence of contrary causes. Constraints eliminate trajectories that violate executability conditions or state laws.
The stable models of the translated program correspond to trajectories admitted by the original action description. Planning then becomes a model-existence problem in which additional constraints impose an initial state and a goal condition. Projection, which determines the consequences of a specified action sequence, is represented by restricting the occurrence of actions and examining the resulting stable models.
This correspondence does not make action languages identical to logic-programming languages. An action language supplies domain-specific constructs and a transition-oriented semantics, whereas the translated logic program exposes the underlying non-monotonic computation. The translation establishes a formal relationship between the two representations and permits implementations based on general-purpose answer-set solvers.
ADL in automated planning
Within classical automated planning, ADL commonly refers to the operator language associated with Pednault rather than to the broader family of causal action languages. An ADL domain extends the basic STRIPS model by permitting logically structured preconditions and conditional effects. It also supports typed objects and equality in the formulations that influenced PDDL.
For many planning procedures, an ADL domain is transformed into a simpler representation before search. Quantified formulas can be grounded over a finite object domain, and logically complex conditions can be compiled into auxiliary predicates or expanded operator structures. Conditional effects can likewise be compiled under specified assumptions, although such transformations may increase the size of the representation.
The distinction between representational expressiveness and computational power is significant. A more expressive surface language does not necessarily define a larger class of finite transition systems, because a less expressive language may encode the same systems with a larger theory. Expressiveness instead concerns the structure and size of the encoding, together with the complexity of determining whether a description admits a plan.
Semantics and reasoning tasks
A formal semantics associates an action description with a set of transition systems or with a uniquely determined transition system. The difference reflects whether the description is complete. An incomplete theory may leave the initial value of a fluent unspecified or permit an action to have several possible outcomes.
Prediction determines which states follow from an initial state and an action sequence. Planning searches for an action sequence whose resulting state satisfies a goal formula. Explanation and diagnosis reverse part of this relationship by identifying action occurrences or abnormal conditions compatible with observed changes. These tasks use the same underlying action theory but impose different constraints on the admissible trajectories.
Equivalence between action descriptions can be defined extensionally through their induced transition systems. Stronger notions preserve behavior when additional laws are added, paralleling strong equivalence in answer set programming. Such distinctions matter because two descriptions may generate the same transitions in isolation while interacting differently with a larger domain theory.