En inteligencia artificial , el lenguaje de descripción de acciones ( ADL ) es un sistema automatizado de planificación y programación , en particular para robots. Se considera un avance de STRIPS . Edwin Pednault (un especialista en el campo de la abstracción y 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 un lenguaje de acción .
Orígenes
Pednault observó que el poder expresivo de STRIPS era susceptible de mejora al permitir que los efectos de un operador estuvieran condicionados. Esta es la idea principal de ADL-A, que es básicamente el fragmento proposicional de la ADL propuesto por Pednault, [2] con ADL-B una extensión de -A. En la extensión -B, las acciones pueden describirse 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 se puede clasificar 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 en el entorno y, a partir de ellas, generar automáticamente una cadena de acciones que conducen a un objetivo deseado. Una meta es una determinada condición parcialmente especificada. Antes de que se pueda ejecutar una acción, deben cumplirse sus condiciones previas; después de la ejecución, la acción produce efectos, por los cuales el entorno cambia. El entorno se describe mediante ciertos predicados, que se cumplen o no.
A diferencia de STRIPS, el principio del mundo abierto se aplica con ADL: todo lo que no ocurre en las condiciones es desconocido (en lugar de asumirse como falso). Además, mientras que en STRIPS solo se permiten literales y conjunciones positivas , ADL también permite literales y disyunciones negativas .
Sintaxis de ADL
Un esquema ADL consta de un nombre de acción, una lista de parámetros opcionales y cuatro grupos opcionales de cláusulas etiquetadas Precond, Agregar, Eliminar y Actualizar.
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, el valor "TRUE" se inserta en el grupo y las condiciones previas siempre se evalúan como condiciones de mantenimiento.
Las condiciones Agregar y Eliminar las especifican los grupos Agregar y Eliminar, respectivamente. Cada grupo consta de un conjunto de cláusulas de los formularios que se muestran en la columna de la izquierda de la figura 1:
- La R representa un símbolo de relación
- τ 1 , ..., τ n representa términos
- ψ representa una fórmula
- La secuencia z 1 , ..., z k son símbolos variables que aparecen en los términos τ 1 , ..., τ n , pero no en la lista de parámetros del esquema de acción
- x 1 , ..., x n son símbolos de variable que son diferentes de las variables z 1 , ..., z n y no aparecen en τ 1 , ..., τ n , ψ , o 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 de los formularios que se muestran en la columna izquierda de la figura 2:
Semántica de ADL
La semántica formal de ADL está definida por 4 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 n símbolo de relación 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 ) se da 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 ) fue verdadera de antemano. Tenga en cuenta 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 puede 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 )
Complejidad de la planificación
En términos de eficiencia computacional, ADL se puede ubicar entre STRIPS y el cálculo de situación. [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 de los casos no se puede mejorar si estamos dispuestos a preservar la longitud de los planes polinomialmente, [6] y por lo tanto ADL es estrictamente más breve que STRIPS.
La planificación de ADL sigue siendo un problema completo de PSPACE. La mayoría de los algoritmos espacian polinomios 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 alto 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 de ADL a una que es esencialmente una STRIPS (sin efectos ni objetivos condicionales o cuantificados).
Comparación entre STRIPS y ADL
- El lenguaje STRIPS solo permite literales positivos en los estados, mientras que ADL puede admitir literales tanto positivos como negativos. Por ejemplo, una oración válida en STRIPS podría ser Rica ∧ Hermosa. La misma oración podría expresarse en ADL como ¬Pobre ∧ ¬Ugly
- En STRIPS, los literales no mencionados son falsos. A esto se le llama el supuesto de mundo cerrado . En ADL se desconocen los literales no mencionados. Esto se conoce como el supuesto de mundo abierto.
- En STRIPS solo podemos encontrar literales básicos en las metas. Por ejemplo, Rich ∧ Beautiful. En ADL podemos encontrar variables cuantificadas en metas. 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
- En STRIPS los objetivos son conjunciones, por ejemplo, (Rico ∧ Hermoso). En ADL, los objetivos pueden involucrar conjunciones y disyunciones (Rich ∧ (Beautiful ∨ Smart)).
- 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
- El lenguaje de STRIPS no apoya la igualdad. En ADL, el predicado de igualdad ( x = y ) está integrado.
- STRIPS no tiene soporte para tipos, mientras que en ADL sí lo es (por ejemplo, la variable p : Persona).
La expresividad del lenguaje STRIPS está restringida por los tipos de transformaciones en conjuntos de fórmulas que se pueden describir en el lenguaje. Las transformaciones en conjuntos de fórmulas que utilizan operadores STRIPS se logran eliminando algunas fórmulas del conjunto que se va a transformar y agregando nuevas fórmulas adicionales. Para un operador STRIPS dado, las fórmulas que se agregarán y eliminarán son fijas para todos los conjuntos de fórmulas que se transformarán. En consecuencia, los operadores de STRIPS no pueden modelar adecuadamente acciones cuyos efectos dependen de las situaciones en las que se realizan. Considere un cohete que se va a disparar durante un cierto período de tiempo. La trayectoria puede variar no solo por la duración de la combustión sino también por la velocidad, masa y orientación del cohete. No se puede modelar mediante un operador STRIPS porque las fórmulas que habría que agregar y eliminar dependerían del conjunto de fórmulas a transformar. [8]
Aunque es posible un razonamiento eficiente cuando se usa el lenguaje STRIPS, generalmente se reconoce que la expresividad de STRIPS 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 las AVD se encuentra 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 y, 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 dos veces más grande que los bloques B y C, por lo que la acción xMoveOnto (B, A) solo podría tener el efecto de negar Clear (A) si On (A, C) ya es cierto, o crea el efecto condicional según el tamaño de los bloques. Este tipo de efectos condicionales sería difícil de expresar en notación STRIPS sin los efectos condicionales.
Ejemplo
Considérese el problema del transporte aéreo de mercancías, donde determinadas mercancías deben transportarse en avión desde un aeropuerto a otro aeropuerto y donde los aviones deben cargarse y descargarse.
Las acciones necesarias serían cargar , descargar y volar ; sobre los descriptores uno podía expresar In(c, p)
y At(x, A)
si una carga c está en un avión p y si un objeto x es en un aeropuerto A .
Las acciones podrían definirse entonces de la siguiente manera:
Acción ( Carga ( c : Carga, p: Avión, A: Aeropuerto) Condición previa: En ( c , A) ^ En ( p , A) Efecto: ¬At ( c , A) ^ In ( 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) ^ ¬In ( c , p) )Acción ( Volar ( p : Avión, desde: Aeropuerto, a: Aeropuerto) Precondición: At ( p , from) Efecto: ¬At ( p , from) ^ At ( p , to) )
Ver también
Referencias
- ^ Edwin Pednault. "Sitio web de investigación de IBM: Pednault" . Consultado el 29 de marzo de 2013 .l
- ^ Pednault. Formulación de problemas del mundo dinámico de múltiples agentes en el marco de planificación clásico. En Michael Georgeff y Amy Lansky, editores, Razonamiento sobre acciones y planes, páginas 47-82. Morgan Kaufmann, San Mateo, CA, 1987.
- ^ Michael Gelfond, Vladimir Lifschitz (1998) " Lenguajes de acción archivados el 2 de septiembre de 2011 en la Wayback Machine ", artículos electrónicos de Linköping en informática y ciencias de la información , vol 3 , nr 16 .
- ^ Edwin PD Pednault. ADL. "Explorando el término medio entre STRIPS y el cálculo de situaciones". En Actas de KR -89, 324–332.
- ^ Gazen, BC y Knoblock, CA, "Combinando la expresividad de UCPOP con la eficiencia de Graphplan". En ECP9 7, págs. 221233. Toulouse, Francia. 1997
- ^ Nebel, B., " Sobre la compilabilidad y el poder expresivo de los formalismos de planificación proposicional ". Journal of Artificial Intelligence Research , 12, 271315. 2000
- ^ Jorge A. Baier., "Técnicas de búsqueda efectivas para la planificación no clásica a través de la reformulación". Doctor. tesis, Universidad de Toronto, 2003.
- ^ Edwing PD Pednault. ADL y el modelo de acción de transición de estado
- ^ HJ Levesque y RJ Brachman. Una compensación fundamental en la representación y el razonamiento del conocimiento. En Readings in Knowledge Representation, HJ Levesque y RJ Brachman, eds. 42–70. Morgan Kaufmann, San Mateo, CA, 1985.
- ^ Vladimir Lifschitz y Arkady Rabinov. Milagros en teorías formales de acciones. Inteligencia artificial, 626 (3): 89-116. 1986