En inteligencia artificial , el lenguaje de descripción de acciones ( ADL ) es un sistema de planificación y programación automatizado , en particular para robots. Se considera un avance de STRIPS . Edwin Pednault (un especialista en el campo de la abstracción y el modelado de datos que ha sido miembro del personal de investigación de IBM en el grupo de investigación de abstracción de datos desde 1996 [1] ) propuso este lenguaje en 1987. Es un ejemplo de lenguaje de acción .
Pednault observó que el poder expresivo de STRIPS era susceptible de ser mejorado al permitir que los efectos de un operador fueran condicionales. Esta es la idea principal de ADL-A, que es aproximadamente el fragmento proposicional del ADL propuesto por Pednault, [2] siendo ADL-B una extensión de -A. En la extensión -B, las acciones pueden ser descritas con efectos indirectos mediante la introducción de un nuevo tipo de proposiciones: "leyes estáticas". Una tercera variación de ADL es ADL-C que es similar a -B, en el sentido de que sus proposiciones pueden ser clasificadas en leyes estáticas y dinámicas, pero con algunas particularidades más. [3]
El sentido de un lenguaje de planificación es representar ciertas condiciones del entorno y, en base a ellas, generar automáticamente una cadena de acciones que conduzcan a un objetivo deseado. Un objetivo es una condición parcialmente especificada. Antes de que una acción pueda ejecutarse, sus precondiciones deben cumplirse; después de la ejecución, la acción produce efectos que modifican el entorno. El entorno se describe por medio de ciertos predicados, que se cumplen o no.
A diferencia de STRIPS, en ADL se aplica el principio del mundo abierto : todo lo que no se cumple en las condiciones es desconocido (en lugar de asumirse falso). Además, mientras que en STRIPS solo se permiten literales positivos y conjunciones , en ADL también se permiten literales negativos y disyunciones .
Un esquema ADL consta de un nombre de acción, una lista de parámetros opcionales y cuatro grupos opcionales de cláusulas denominadas Precond, Add, Delete y Update.
El grupo Precond es una lista de fórmulas que definen las condiciones previas para la ejecución de una acción. Si el conjunto está vacío, se inserta el valor "TRUE" en el grupo y las condiciones previas siempre se evalúan como condiciones de cumplimiento.
Las condiciones de Agregar y Eliminar se especifican mediante los grupos Agregar y Eliminar, respectivamente. Cada grupo consta de un conjunto de cláusulas con las formas que se muestran en la columna de la izquierda de la figura 1:
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 de las formas que se muestran en la columna izquierda de la figura 2:
La semántica formal de ADL está definida por cuatro restricciones. La primera restricción es que las acciones no pueden cambiar el conjunto de objetos que existen en el mundo; esto significa que para cada acción α y cada par de estado actual/estado siguiente ( s , t ) ∈ a , debe darse el caso de que el dominio de t sea igual al dominio de s .
La segunda restricción es que las acciones en ADL deben ser deterministas. Si ( s , t 1 ) y ( s , t 2 ) son pares de acción ∃ de estado actual/estado siguiente, entonces debe darse el caso de que t 1 = t 2 .
La tercera restricción incorporada en ADL es que las funciones introducidas anteriormente deben ser representables como fórmulas de primer orden. Para cada símbolo de relación n -ario R , debe existir una fórmula Φ a R ( x 1 ,... , x n ) con variables libres x 2 , ..., x n tal que f a R ( s ) está dada por:
En consecuencia, F ( n 1 , ..., x n ) = y será verdadera después de realizar la acción |= si y solo si Φ a R ( x 1 , ..., x n , y ) era verdadera de antemano. 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 ).
La cuarta y última restricción incorporada en ADL es que el conjunto de estados en los que una acción es ejecutable también debe ser representable como una fórmula. Para cada acción α que se pueda representar en ADL, debe existir una fórmula Π a con la propiedad de que s |= Π a si y solo si hay 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 puede ubicarse entre STRIPS y el Cálculo de Situaciones. [4] Cualquier problema de ADL puede traducirse en 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 manera polinomial, [6] y, por lo tanto, ADL es estrictamente más breve que STRIPS.
La planificación ADL sigue siendo un problema completo de PSPACE. La mayoría de los algoritmos son de espacio polinómico, incluso si las condiciones previas y los efectos son fórmulas complejas. [7]
La mayoría de los enfoques de planificación clásica de mayor rendimiento utilizan internamente una representación similar a STRIPS. De hecho, la mayoría de los planificadores (FF, LPG, Fast-Downward, SGPLAN5 y LAMA) primero traducen la instancia ADL a una que es esencialmente una STRIPS (sin efectos ni objetivos condicionales o cuantificados).
La expresividad del lenguaje STRIPS está limitada por los tipos de transformaciones sobre conjuntos de fórmulas que se pueden describir en el lenguaje. Las transformaciones sobre conjuntos de fórmulas utilizando operadores STRIPS se logran eliminando algunas fórmulas del conjunto a transformar y agregando nuevas fórmulas adicionales. Para un operador STRIPS dado, las fórmulas a agregar y eliminar 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 va a ser lanzado durante una cierta cantidad de tiempo. La trayectoria puede variar no solo debido a la duración de la combustión sino también debido a la velocidad, masa y orientación del cohete. No se puede modelar por medio de un operador STRIPS porque las fórmulas que tendrían que agregarse y eliminarse dependerían del conjunto de fórmulas a transformar. [8]
Aunque es posible un razonamiento eficiente cuando se utiliza el lenguaje STRIPS, se reconoce generalmente que la expresividad de STRIPS no es adecuada para modelar acciones en muchas aplicaciones del mundo real. Esta inadecuación motivó el desarrollo del lenguaje ADL. [9] [10] La expresividad y complejidad del ADL se encuentran entre el lenguaje STRIPS y el cálculo de situaciones. Su poder expresivo es suficiente para permitir que se represente el ejemplo del cohete descrito anteriormente, pero, al mismo tiempo, es lo suficientemente restrictivo como para permitir que se desarrollen algoritmos de razonamiento eficientes.
Como ejemplo de 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) podría tener solo 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 notación STRIPS sin los efectos condicionales.
Pensemos en el problema del transporte aéreo de mercancías, en el que determinadas mercancías deben transportarse de un aeropuerto a otro en avión y es necesario cargar y descargar 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:
![{\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})]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/32b785abbd5a0182e6ec56950a5ec83e2b082aed)
Acción ( Carga ( c : Carga, p: Avión, A: Aeropuerto) Condición previa: En ( c , A) ^ En ( p , A) Efecto: ¬En ( c , A) ^ En ( c , p) ) Acción ( Descargar ( c : Carga, p: Avión, A: Aeropuerto) Condición previa: En ( c , p) ^ En ( p , A) Efecto: En ( c , A) ^ ¬En ( c , p) ) Acción ( Volar ( p : Avión, desde: Aeropuerto, hasta: Aeropuerto) Condición previa: En ( p , desde) Efecto: ¬En ( p , desde) ^ En ( p , hasta) )