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. Edwin Pednault (a specialist in the field of data abstraction and modelling who has been an IBM Research Staff Member in the Data Abstraction Research Group since 1996^[1]) proposed this language in 1987. It is an example of an action language.

Pednault observed that the expressive power of STRIPS was susceptible to being improved by allowing the effects of an operator to be conditional. This is the main idea of ADL-A, which is roughly the propositional fragment of the ADL proposed by Pednault,^[2] with ADL-B an extension of -A. In the -B 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 which is similar to -B, in the sense that its propositions can be classified into static and dynamic laws, but with some more particularities.^[3]

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, whereas in STRIPS only positive literals and conjunctions are permitted, ADL allows negative literals and disjunctions as well.

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 formulae that define the preconditions for the execution of an action. If the set is empty the value "TRUE" is 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:

1. The R represents a relation symbol
2. τ₁, ..., τ_n represents terms
3. ψ representa una fórmula
4. La secuencia z ₁ , ..., z _k son símbolos variables que aparecen en los términos τ ₁ , ..., τ _n , pero no en la lista de parámetros del esquema de acción.
5. x ₁ , ..., x _n son símbolos de variables que son diferentes de las variables z ₁ , ..., z _n y no aparecen en τ ₁ , ..., τ _n , ψ , ni en la lista de parámetros del esquema de acción.

Los grupos de actualización se utilizan para especificar las condiciones de actualización para cambiar los valores de los símbolos de función. Un grupo de actualización consta de un conjunto de cláusulas con las formas que se muestran en la columna izquierda de la figura 2:

La semántica formal de ADL se define mediante cuatro restricciones.

⇒ Las acciones no pueden cambiar el conjunto de objetos que existen en el mundo; esto significa que para cada acción α y cada par estado actual/estado siguiente ( s , t ) ∈ a , debe ser cierto que el dominio de t debe ser igual al dominio de s .

⇒ Las acciones en ADL deben ser deterministas. Si ( s , t ₁ ) y ( s , t ₂ ) son pares de estado actual/estado siguiente de la acción ∃, entonces debe ser cierto que t ₁ = t ₂ .

⇒ Las funciones introducidas anteriormente deben poder representarse como fórmulas de primer orden. Para cada símbolo de relación n -aria R , debe existir una fórmula Φ ^a _R ( x ₁ , ... , x _n ) con variables libres x ₂ , ..., x _n tal que f ^a _R ( s ) esté dada por:

${\displaystyle t(R)=f_{R}^{a}(s)=(d_{1},\ldots ,d_{n})\in \operatorname {Dom} (s)^{n}\mid s[d_{1}/x_{1},\ldots ,d_{n}/x_{n}\models \Phi _{R}^{a}(x_{1},\ldots ,x_{n})]}$

En consecuencia, F ( n ₁ , ..., x _n ) = y será verdadero después de realizar la acción |= si y solo si Φ ^a _R ( x ₁ , ..., x _n , y ) era verdadero previamente. Nótese que este requisito de representabilidad se basa en la primera restricción (el dominio de f debe ser igual al dominio de s ).

⇒ El conjunto de estados en los que una acción es ejecutable también debe poder representarse como una fórmula. Para cada acción α que pueda representarse en ADL, debe existir una fórmula Π ^a con la propiedad de que s |= Π _a si y solo si existe algún estado t para el cual ( s , t ) ∈ α (es decir, la acción α es ejecutable en el estado s ).

En términos de eficiencia computacional, ADL se puede ubicar entre STRIPS y el Cálculo de Situaciones . ^{[ 4 ]} Cualquier problema de ADL se puede traducir a una instancia de STRIPS; sin embargo, las técnicas de compilación existentes son exponenciales en el peor de los casos. ^{[ 5 ]} Este peor caso no se puede mejorar si estamos dispuestos a preservar la longitud de los planes de forma polinómica, ^{[ 6 ]} y por lo tanto ADL es estrictamente más breve que STRIPS.

La planificación de ADL sigue siendo un problema PSPACE-completo. La mayoría de los algoritmos tienen espacio polinomial, incluso si las precondiciones y los efectos son fórmulas complejas. ^{[ 7 ]}

La mayoría de los enfoques de planificación clásica de alto rendimiento utilizan internamente una representación tipo STRIPS. De hecho, la mayoría de los planificadores (FF, LPG, Fast-Downward, SGPLAN5 y LAMA) primero traducen la instancia de ADL a una que es esencialmente una instancia STRIPS (sin efectos ni objetivos condicionales o cuantificados).

1. El lenguaje STRIPS solo permite literales positivos en los estados, mientras que ADL admite literales tanto positivos como negativos. Por ejemplo, una oración válida en STRIPS podría ser Rich  ∧  Beautiful. La misma oración podría expresarse en ADL como ¬Poor  ∧  ¬Ugly.
2. En STRIPS, los literales no mencionados son falsos. Esto se conoce como la suposición de mundo cerrado . En ADL, los literales no mencionados son desconocidos. Esto se conoce como la suposición de mundo abierto.
3. En STRIPS solo podemos encontrar literales básicos en los objetivos. Por ejemplo, Rich ∧ Beautiful. En ADL podemos encontrar variables cuantificadas en los objetivos. Por ejemplo, ∃ x At (P1, x ) ∧ At(P2, x ) es el objetivo de tener P1 y P2 en el mismo lugar en el ejemplo de los bloques.
4. En STRIPS, los objetivos son conjunciones, por ejemplo, (Rico ∧ Hermoso). En ADL, los objetivos pueden implicar conjunciones y disyunciones (Rico ∧ (Hermoso ∨ Inteligente)).
5. En STRIPS los efectos son conjunciones, pero en ADL se permiten efectos condicionales: cuando P : E significa que E es un efecto solo si P se satisface.
6. El lenguaje STRIPS no admite la igualdad. En ADL, el predicado de igualdad ( x = y ) está incorporado.
7. STRIPS no admite tipos, mientras que en ADL sí los admite (por ejemplo, la variable p  : Person).

La expresividad del lenguaje STRIPS está limitada por los tipos de transformaciones en conjuntos de fórmulas que se pueden describir en dicho lenguaje. Las transformaciones en conjuntos de fórmulas mediante operadores STRIPS se realizan eliminando algunas fórmulas del conjunto a transformar y añadiendo otras nuevas. Para un operador STRIPS dado, las fórmulas que se añaden y eliminan son fijas para todos los conjuntos de fórmulas a transformar. En consecuencia, los operadores STRIPS no pueden modelar adecuadamente acciones cuyos efectos dependen de las situaciones en las que se realizan. Consideremos un cohete que se va a disparar durante un tiempo determinado. La trayectoria puede variar no solo por la duración de la combustión, sino también por la velocidad, la masa y la orientación del cohete. No se puede modelar mediante un operador STRIPS porque las fórmulas que habría que añadir y eliminar dependerían del conjunto de fórmulas a transformar. ^{[ 8 ]}

Aunque es posible un razonamiento eficiente al usar el lenguaje STRIPS, generalmente se reconoce que su expresividad no es adecuada para modelar acciones en muchas aplicaciones del mundo real. Esta insuficiencia motivó el desarrollo del lenguaje ADL. ^{[ 9 ] [ 10 ]} La expresividad y complejidad de ADL se sitúan entre el lenguaje STRIPS y el cálculo de situaciones. Su poder expresivo es suficiente para permitir la representación del ejemplo del cohete descrito anteriormente, pero, al mismo tiempo, es lo suficientemente restrictivo como para permitir el desarrollo de algoritmos de razonamiento eficientes.

Como ejemplo en una versión más compleja del mundo de los bloques : podría ser que el bloque A sea el doble de grande que los bloques B y C, por lo que la acción xMoveOnto(B,A) solo tendría el efecto de negar Clear(A) si On(A,C) ya es verdadero, o crear el efecto condicional dependiendo del tamaño de los bloques. Este tipo de efectos condicionales serían difíciles de expresar en la notación STRIPS sin los efectos condicionales.

Consideremos el problema del transporte aéreo de mercancías, donde ciertos productos deben transportarse de un aeropuerto a otro en avión y donde es necesario cargar y descargar los aviones.

Las acciones necesarias serían cargar , descargar y volar ; sobre los descriptores se podría expresar In(c, p)si At(x, A)una carga c está en un avión p y si un objeto x está en un aeropuerto A.

Las acciones podrían definirse entonces de la siguiente manera:

Acción (  Carga ( c : Carga, p: Avión, A: Aeropuerto)  Precondición: En ( c , A) ^ En ( p , A)  Efecto: ¬En ( c , A) ^ En ( c , p) )Acción (  Descargar ( c : Carga, p: Avión, A: Aeropuerto)  Precondición: En ( c , p) ^ En ( p , A)  Efecto: En ( c , A) ^ ¬En ( c , p) )Acción (  Volar ( p : Avión, desde: Aeropuerto, a: Aeropuerto)  Precondición: En ( p , desde)  Efecto: ¬En ( p , desde) ^ En ( p , a) )

• Lenguaje de acción
• Selección de acciones
• Red de tareas jerárquica
• Lenguaje de definición de dominio de planificación (PDDL)