Action description language

In artificial intelligence, Action description language (ADL) is an automated planning and scheduling system in particular for robots. It is considered an advancement of STRIPS. Pednault proposed this language in 1987.

Pednault observed that the expressive power of STRIPS was susceptible of being improved by allowing the effects of an operator to be conditional. This is the main idea of ADL-A, which is basically the propositional fragment of the ADL proposed by Pednault . ADL-B is an extension of A. In this extension, actions can be described with indirect effects by the introduction of a new kind of propositions, ”static laws. A third variation of ADL is ADL-C. This last one is similar to B, in the sense that its propositions can be classified into static and dynamic laws. But there are some more particularities

The sense of a planning language is to represent certain conditions in the environment, and, based on these, automatically generate a chain of actions which lead to a desired goal. A goal is a certain partially specified condition. Before an action can be executed, its preconditions must be fulfilled; after the execution, the action yields effects, by which the environment changes. The environment is described by means of certain predicates, which are either fulfilled or not.

Contrary to STRIPS, the principle of the open world applies with ADL: everything not occurring in the conditions is unknown (Instead of being assumed false). In addition, while in STRIPS only positive literals and conjunctions are permitted, ADL allows negative literals and disjunctions as well.

Syntax of ADL

An ADL schema consists of an action name, an optional parameter list and four optional groups of clauses labeled Precond, Add, Delete and Update. The Precond group is a list of formulas that define the preconditions for the execution of an action. If the set is empty, the value TRUE is thus inserted into the group, and the preconditions are always evaluated as holding conditions. The Add and Delete conditions are specified by the Add and Delete groups, respectively. Each group consists of a set of clauses of the forms shown in the left-hand column of the figure 1:

File:ADLSyntax-Pednault.png

Figure 1

1. The R represents a relation symbol
2. τ₁,...,τ_n represents terms
3. ψ represents a formula
4. The sequence z₁,...,z_k are variable symbols that appear in the terms τ₁,...,τ_n, but not in the parameter list of the action schema
5. x₁,...,x_n are variable symbols that are different from the variables z₁,...,z_n and do not appear in τ₁,...,τ_n, ψ , or the parameter list of the action schema

The Update groups are used to specify the update conditions to change the values of function symbols. An Update group consists of a set of clauses of the forms shown in the left column of the figure 2:

File:ADLSyntax-UpdateClauses-Pednault.png

Figure 2

Semantics of ADL

The formal semantic of ADL is defined by 4 constraints. The first constraint is that actions may not change the set of objects that exist in the world; that means that for every action α and every current-state/next-state pair (s, t) ∈ a, it must be the case that the domain of t should be equal to the domain of s.

The second constraint is that actions in ADL must be deterministic. If (s, t1) and (s, t2) are current-state/next-state pairs of action ∃, then it must be the case that t1 = t2.

The third constraint incorporated into ADL is that the functions introduced above must be representable as first-order formulas. For every n-ary relation symbol R, there must exist a formula Φ^a_R x₁,... ,x_n) with free variables x₂,...,x_n such that f^a_R(s) is given by:

t(R) = f^a_R(s) = (d₁,... , d_n) ∈ Dom(s)ⁿ | s[d₁/x₁,...,d_n/x_n ⊧ Φ^a_R(x₁,x_n)]

Consequently, F(n₁,...,x_n) = y will be true after performing action |= if and only if �Φ^a_R (x₁,... ,x_n,y) was true beforehand. Note that this representability requirement relies on the first constraint ( Domain of f should be equal to domain of s).

The fourth and final constraint incorporated into ADL is that set of states in which an action is executable must also be representable as a formula. For every action � that can be represented in ADL, there must exist a formula Π�^a with the property that s | = �Π�_a if and only if there is some state t for which (s, t ) ∈ α � (i.e. action �α is executable in state s)

Complexity of planning

In terms of computational efficiency, ADL can be located between STRIPS and the situation calculus . Any ADL problem can be translated into a STRIPS instance. However, existing compilation techniques are worst-case exponential . This wort case cannot be improved if we are willing to preserve the length of plans polynomially , and thus ADL is strictly more brief than STRIPS.

ADL planning, however, is still a PSPACE-complete problem.Most of the algorithms polynomial space even if the preconditions and effects are complex formulae .

Interestingly, most of the top-performing approaches to classical planning internally utilize a STRIPS like representation. In fact, most of the planners (FF, LPG, Fast-Downward, SGPLAN5 , LAMA) first translate the ADL instance into one that is essentially a STRIPS one (without conditional or quantified effects or goals).

Example

Consider the problem of air freight transport, where certain goods must be transported from an airport to another airport by plane and where airplanes need to be loaded and unloaded.

The necessary actions would be loading, unloading and flying; over the descriptors one could express In(c, p) and At(x, a) whether a freight C is in an airplane p and whether an object x is at an airport A.

The actions could be defined then as follows:

Action (
  Load (c: Freight, p: Airplane, A: Airport)
  Precondition: At(c, A) ^ At(p, A)
  Effect: ¬At(c, A) ^ In(c, p)
)

Action (
  Unload (c: Freight, p: Airplane, A: Airport)
  Precondition: In(c, p) ^ At(p, A) 
  Effect: At(c, A) ^ ¬In(c, p)
)

Action (
  Fly (p: Airplane, from: Airport, to: Airport)
  Precondition: At(p, from)
  Effect: ¬At(p, from) ^ At(p, to)
)

See also

• Automated planning
• Hierarchical task network
• Planning Domain Definition Language (PDDL)
• STRIPS