Lenguaje de definición de dominio de planificación

El Lenguaje de definición de dominio de planificación (PDDL) es un intento de estandarizar los lenguajes de planificación de la Inteligencia Artificial (IA). Fue desarrollado por primera vez por Drew McDermott y sus colegas en 1998 principalmente para hacer posible el Concurso Internacional de Planificación (IPC) 1998/2000, y luego evolucionó con cada concurso. La estandarización proporcionada por PDDL tiene el beneficio de hacer que la investigación sea más reutilizable y fácilmente comparable, aunque a costa de cierto poder expresivo, en comparación con los sistemas de dominios específicos.

Descripción general

PDDL es un formato legible por humanos para problemas de planificación automatizada que proporciona una descripción de los posibles estados del mundo, una descripción del conjunto de acciones posibles, un estado inicial específico del mundo y una descripción de las acciones deseadas. objetivos. PDDL separa el modelo del problema de planificación en dos partes principales: (1) una descripción de dominio de aquellos elementos que están presentes en cada problema del dominio del problema, y (2) la descripción del problema que determina el problema de planificación específico. La descripción del problema incluye el estado inicial y los objetivos a alcanzar. El siguiente ejemplo proporciona una definición de dominio y una descripción del problema para la planificación automatizada de un robot con dos brazos de agarre.

PDDL se convierte en la entrada para el software de planificación, que suele ser un planificador de Inteligencia Artificial (IA) independiente del dominio. PDDL no describe el resultado del software planificador, pero el resultado suele ser un plan total o parcialmente ordenado, que es una secuencia de acciones, algunas de las cuales pueden ejecutarse en paralelo.

El lenguaje PDDL se inspiró en el Problem Solver del Stanford Research Institute (STRIPS) y el lenguaje de descripción de acciones (ADL), entre otros. El lenguaje PDDL utiliza principios de lenguajes de representación del conocimiento que se utilizan para crear ontologías; un ejemplo es el lenguaje de ontología web (OWL). Las ontologías son una forma formal de describir taxonomías y redes de clasificación, definiendo esencialmente la estructura del conocimiento para varios dominios: los sustantivos que representan clases de objetos y los verbos que representan relaciones entre los objetos.

La versión más reciente de PDDL se describe en una definición de sintaxis BNF (Backus-Naur Form) de PDDL 3.1.

Versiones oficiales de facto del PDDL

PDDL1.2

Este fue el idioma oficial del 1º y 2º IPC en 1998 y 2000 respectivamente. Separó el modelo del problema de planificación en dos partes principales: (1) descripción del dominio y (2) la descripción del problema relacionado. . Tal división del modelo permite una separación intuitiva de aquellos elementos que están (1) presentes en cada problema específico del dominio del problema (estos elementos están contenidos en la descripción del dominio), y aquellos elementos que (2) determinan el problema de planificación específico (estos elementos están contenidos en la descripción del problema). Por lo tanto, varias descripciones de problemas pueden estar conectadas a la misma descripción de dominio (del mismo modo que pueden existir varias instancias de una clase en OOP (Programación orientada a objetos) o en OWL (Lenguaje de ontología web), por ejemplo). Por lo tanto, un dominio y una descripción del problema que lo conecta forman el modelo PDDL de un problema de planificación y, finalmente, esta es la entrada de un software de planificación (normalmente un planificador de IA independiente del dominio), cuyo objetivo es resolver el problema. problema de planificación dado a través de algún algoritmo de planificación apropiado. La salida del planificador no está especificada por PDDL, pero suele ser un plan total o parcialmente ordenado (una secuencia de acciones, algunas de las cuales pueden ejecutarse incluso en paralelo en ocasiones). Ahora echemos un vistazo al contenido de un dominio PDDL1.2 y la descripción del problema en general...
(1) La descripción del dominio consistía en un nombre de dominio definición, definición de requisitos (para declarar esos elementos del modelo al planificador que el modelo PDDL realmente está usando), definición de jerarquía de tipos de objetos (al igual que una jerarquía de clases en programación orientada a objetos), definición de objetos constantes (que están presentes en todos los problemas del dominio), definición de predicados (plantillas para hechos lógicos) y también la definición de posibles acciones (esquemas de operador con parámetros, que deben fundamentarse/crearse instancias durante la ejecución). Las acciones tenían parámetros (variables que pueden instanciarse con objetos), condiciones previas y efectos. Los efectos de las acciones también podrían ser condicionales (cuando-efectos).
(2) La descripción del problema consistía en un nombre-del-problema definición, la definición del nombre-dominio relacionado, la definición de todos los posibles objetos (átomos en el universo lógico), condiciones iniciales (el estado inicial del entorno de planificación, una conjunción de hechos verdaderos/falso), y la definición de estados-objetivo (una expresión lógica sobre hechos que deberían ser verdaderos/falso en un estado-objetivo de el entorno de planificación). Así, finalmente, PDDL1.2 capturó la "física" de un entorno de planificación determinista, discreto, totalmente accesible y de agente único.

PDDL2.1

Este fue el idioma oficial del 3er IPC en 2002. Introdujo fluidos numéricos (por ejemplo, para modelar recursos no binarios como nivel de combustible, tiempo, energía, distancia, peso,...), plan-metrics (para permitir la evaluación cuantitativa de los planes, y no sólo una planificación basada en objetivos, sino también basada en la utilidad, es decir, optimización, minimización/maximización de métricas) y acciones duraderas/continuas (que podrían tener efectos variables y no discretos). duración, condiciones y efectos). Finalmente, PDDL2.1 permitió la representación y solución de muchos más problemas del mundo real que la versión original del lenguaje.

PDDL2.2

Este fue el idioma oficial de la vía determinista del 4º IPC en 2004. Introdujo predicados derivados (para modelar la dependencia de hechos dados de otros hechos, por ejemplo, si A es alcanzable desde B y B es alcanzable desde C, entonces A es alcanzable desde C (transitividad)), y literales iniciales cronometrados (para modelar eventos exógenos que ocurren en un momento dado independientemente de la ejecución del plan). Finalmente, PDDL2.2 amplió el lenguaje con algunos elementos importantes, pero no fue una evolución radical en comparación con PDDL2.1 después de PDDL1.2.

PDDL3.0

Este fue el idioma oficial de la vía determinista del 5º IPC en 2006. Introdujo restricciones de trayectoria de estado (restricciones estrictas en forma de expresiones de lógica modal, que deberían ser ciertas para la trayectoria de estado producida durante la ejecución de un plan, que es una solución de la planificación dada). problema) y preferencias (restricciones suaves en forma de expresiones lógicas, similares a las restricciones duras, pero su satisfacción no era necesaria, aunque podría incorporarse a la métrica del plan, por ejemplo, para maximizar el número de preferencias satisfechas, o simplemente medir la calidad de un plan) para permitir una planificación basada en preferencias. Finalmente, PDDL3.0 actualizó la expresividad del lenguaje para poder hacer frente a importantes avances recientes en la planificación.

PDDL3.1

Este fue el idioma oficial de la vía determinista del 6º y 7º IPC en 2008 y 2011 respectivamente. Introdujo fluidos de objetos (es decir, el rango de funciones ahora podría ser no solo numérico (entero o real), sino que también podría ser cualquier tipo de objeto). Así, PDDL3.1 adaptó el lenguaje aún más a las expectativas modernas con un cambio en la expresividad sintácticamente aparentemente pequeño, pero semánticamente bastante significativo.

Situación actual

La última versión del lenguaje es PDDL3.1. La definición de sintaxis BNF (Backus-Naur Form) de PDDL3.1 se puede encontrar entre los recursos de la página de inicio de la IPC-2011 o de la página de inicio de la IPC-2014.

Sucesoras / variantes / extensiones de PDDL

PDDL+

Esta extensión de PDDL2.1 de alrededor de 2002-2006 proporciona un modelo más flexible de cambio continuo mediante el uso de procesos y eventos autónomos. La clave que proporciona esta extensión es la capacidad de modelar la interacción entre el comportamiento del agente y los cambios iniciados por el entorno del agente. Los procesos se ejecutan a lo largo del tiempo y tienen un efecto continuo sobre los valores numéricos. Se inician y terminan ya sea por la acción directa del agente o por eventos desencadenados en el ambiente. Esta estructura de tres partes se conoce como modelo de inicio-proceso-detención. Se hacen distinciones entre estados lógicos y numéricos: se supone que las transiciones entre estados lógicos son instantáneas, mientras que la ocupación de un estado lógico determinado puede perdurar en el tiempo. Por lo tanto, en PDDL+ las expresiones de actualización continua están restringidas a ocurrir solo en los efectos del proceso. Las acciones y eventos, que son instantáneos, se restringen a la expresión de cambios discretos. Esto introduce el antes mencionado modelado de 3 partes de períodos de cambio continuo: (1) una acción o evento inicia un período de cambio continuo en una variable numérica expresada mediante un proceso; (2) el proceso realiza el cambio continuo de la variable numérica; (3) una acción o evento finalmente detiene la ejecución del proceso y termina su efecto sobre la variable numérica. Comentario: los objetivos del plan podrían lograrse antes de que se detenga un proceso activo.

NDDL

NDDL (Nuevonuevo Ddominio Ddefinición Lidioma) es La respuesta de la NASA al PDDL alrededor de 2002. Su representación difiere de PDDL en varios aspectos: 1) utiliza una representación de variable/valor (líneas de tiempo/actividades) en lugar de una lógica proposicional/de primer orden, y 2) no existe ningún concepto de estados o acciones, sólo de intervalos (actividades) y restricciones entre esas actividades. En este sentido, los modelos en NDDL se parecen más a esquemas para codificaciones SAT de problemas de planificación que a modelos PDDL. Debido a las diferencias mencionadas, la planificación y ejecución de planes (por ejemplo, durante misiones espaciales críticas) pueden ser más sólidas cuando se utiliza NDDL, pero la correspondencia con representaciones estándar de problemas de planificación distintas de PDDL puede ser mucho menos intuitiva que en el caso de PDDL.

MAPL

MAPL (Multi-Agent Planguaje L, pronunciado "arce") es una extensión de PDDL2.1 de alrededor de 2003. Es una modificación bastante seria del idioma original. Introduce variables de estado no proposicionales (que pueden ser n-arias: verdadera, falsa, desconocida o cualquier otra cosa). Introduce un modelo temporal dado con operadores modales (antes, después, etc.). No obstante, en PDDL3.0 se proporcionó un modelo temporal más completo, que también es compatible con la sintaxis original de PDDL (y es sólo una adición opcional). MAPL también introduce acciones cuya duración se determinará en tiempo de ejecución y sincronización explícita del plan que se realiza a través de comunicación basada en actos de habla entre agentes. Esta suposición puede ser artificial, ya que los agentes que ejecutan planes simultáneos no necesariamente deberían comunicarse para poder funcionar en un entorno de múltiples agentes. Finalmente, MAPL introduce eventos (endógenos y exógenos) para manejar la concurrencia de acciones. Así, los eventos pasan a formar parte explícitamente de los planes y son asignados a los agentes mediante una función de control, que también forma parte del plan.

OPTAR

OPT (Ontología con tipos ppolimórficos) fue una profunda extensión de PDDL2.1 por Drew McDermott alrededor de 2003-2005 (con algunas similitudes con PDDL+). Fue un intento de crear una notación de propósito general para crear ontologías, definidas como marcos conceptuales formalizados para dominios de planificación sobre los cuales deben razonar las aplicaciones de planificación. Su sintaxis se basaba en PDDL, pero tenía un sistema de tipos mucho más elaborado, que permitía a los usuarios hacer uso de construcciones de orden superior, como λ-expresiones explícitas, que permitían inferencia de tipos eficiente (es decir, no solo los objetos de dominio tenían tipos (tipos de nivel 0), sino que también las funciones/fluidos definidos arriba de estos objetos tenían tipos en forma de asignaciones arbitrarias (tipos de nivel 1), que podría ser genérico, por lo que sus parámetros (el dominio y rango del mapeo genérico) podrían definirse con variables, que podrían tener un tipo de nivel aún mayor (tipo de nivel 2) no para hablar de que las asignaciones podrían ser arbitrarias, es decir, el dominio o rango de una función (por ejemplo, predicado, fluidez numérica) podría ser cualquier tipo de nivel 0/1/2. Por ejemplo, las funciones podrían asignarse desde funciones arbitrarias a funciones arbitrarias. .). Básicamente, OPT estaba destinado a ser (casi) compatible con PDDL2.1. La notación para procesos y acciones durativas se tomó prestada principalmente de PDDL+ y PDDL2.1, pero más allá de eso, OPT ofrecía muchas otras extensiones importantes (por ejemplo, estructuras de datos b>, fluidos no booleanos, valores de retorno para acciones, vínculos entre acciones, expansión de acciones jerárquicas, jerarquía de definiciones de dominio, el uso de espacios de nombres para compatibilidad con la web semántica).

PPDDL

PPDDL (Probabilístico PDDL) 1.0 fue el idioma oficial del track probabilístico del 4º y 5º IPC en 2004 y 2006 respectivamente. . Amplió PDDL2.1 con efectos probabilísticos (distribuciones de probabilidad generales y discretas sobre posibles efectos de una acción), fluidos de recompensa (para incrementar o disminuir la recompensa total de un plan en los efectos de las acciones), recompensas por objetivos (para recompensar una trayectoria de estado, que incorpora al menos un estado-objetivo) y fluidos por objetivos alcanzados (que eran verdaderos , si la trayectoria del estado incorporaba al menos un estado objetivo). Finalmente, estos cambios permitieron a PPDDL1.0 realizar la planificación del Proceso de Decisión de Markov (MDP), donde puede haber incertidumbre en las transiciones de estado, pero el entorno es totalmente observable para el planificador/agente.

APLICACIÓN

APPL (Unlenguaje Plan Pde reparación L) es una variante más nueva de NDDL de 2006, que es más abstracta que la mayoría de los lenguajes de planificación existentes, como PDDL o NDDL. El objetivo de este lenguaje era simplificar el análisis formal y la especificación de los problemas de planificación destinados a aplicaciones críticas para la seguridad, como la gestión de energía o el encuentro automatizado en futuras naves espaciales tripuladas. APPL usó los mismos conceptos que NDDL con la extensión de acciones, y también algunos otros conceptos, pero aún así su poder expresivo es mucho menor que el de PDDL (con la esperanza de mantenerse robusto y formalmente verificable) .

RDDL

RDDL (lenguaje diagrama lenguaje dinámico de influencia relacional) fue el idioma oficial de la pista de incertidumbre del 7º IPC en 2011. Conceptualmente está basado en PPDDL1.0 y PDDL3.0, pero prácticamente es un lenguaje completamente diferente tanto sintáctica como semánticamente. La introducción de la observabilidad parcial es uno de los cambios más importantes en RDDL en comparación con PPDDL1.0. Permite una descripción eficiente de los procesos de decisión de Markov (MDP) y los procesos de decisión de Markov parcialmente observables (POMDP) al representar todo (flujos de estado, observaciones, acciones,...) con variables. De esta manera, RDDL se aleja significativamente de PDDL. RDDL conectado a tierra corresponde a redes bayesianas dinámicas (DBN) de manera similar a PPDDL1.0, pero RDDL es más expresivo que PPDDL1.0.

MA-PDDL

MA-PDDL (Multi Agent PDDL) es una extensión modular y minimalista de PDDL3. 1 introducido en 2012 (es decir, un nuevo requisito :multi-agent) que permite la planificación por y para múltiples agentes. La adición es compatible con todas las características de PDDL3.1 y aborda la mayoría de los problemas de MAPL. Añade la posibilidad de distinguir entre las posibles acciones diferentes de diferentes agentes (es decir, diferentes capacidades). De manera similar, diferentes agentes pueden tener diferentes objetivos y/o métricas. Las condiciones previas de las acciones ahora pueden referirse directamente a acciones concurrentes (por ejemplo, las acciones de otros agentes) y, por lo tanto, las acciones con efectos interactivos pueden representarse de una manera general y flexible (por ejemplo, supongamos que al menos 2 agentes están necesario ejecutar una acción lift para levantar una mesa pesada en el aire, de lo contrario la mesa permanecería en el suelo (este es un ejemplo de sinergia constructiva, pero la sinergia destructiva también se puede representar fácilmente en MA -PDDL)). Además, como una especie de azúcar sintáctico, también se introdujo en MA-PDDL un mecanismo simple para la herencia y polimorfismo de acciones, objetivos y métricas (suponiendo que se declare :typing). . Dado que PDDL3.1 supone que el entorno es determinista y totalmente observable, lo mismo se aplica a MA-PDDL, es decir, cada agente puede acceder al valor de cada estado fluido en cada instante de tiempo y observar cada acción ejecutada previamente por cada agente, y también las acciones concurrentes de los agentes determinan inequívocamente el siguiente estado del medio ambiente. Esto se mejoró más tarde mediante la adición de observabilidad parcial y efectos probabilísticos (nuevamente, en forma de dos nuevos requisitos modulares, :partial-observability y :probabilistic-effects, respectivamente , este último inspirado en PPDDL1.0 y ambos compatibles con todas las características anteriores del lenguaje, incluido :multi-agent).

Ejemplo

Esta es la definición de dominio de una instancia STRIPS para la planificación automatizada de un robot con dos brazos de agarre.

()definir ()dominio empuñaduras) ():predicados ()habitación ? r) ()bola ? b) ()agarre ?g) ()a-robby ? r) ()a ? b ? r) ()gratis ?g) ()transporte ? o ?g) ():acción movimiento :parametros ()? desde ? a) :precondición ()y ()habitación ? desde) ()habitación ? a) ()a-robby ? desde) :efecto ()y ()a-robby ? a) ()no ()a-robby ? desde))) ():acción Elige. :parametros ()?obj ¿El cuarto? ? agarre) :precondición ()y ()bola ?obj) ()habitación ¿El cuarto?) ()agarre ? agarre) ()a ?obj ¿El cuarto?) ()a-robby ¿El cuarto?) ()gratis ? agarre) :efecto ()y ()transporte ?obj ? agarre) ()no ()a ?obj ¿El cuarto?) ()no ()gratis ? agarre))) ():acción gota :parametros ()?obj ¿El cuarto? ? agarre) :precondición ()y ()bola ?obj) ()habitación ¿El cuarto?) ()agarre ? agarre) ()transporte ?obj ? agarre) ()a-robby ¿El cuarto?) :efecto ()y ()a ?obj ¿El cuarto?) ()gratis ? agarre) ()no ()transporte ?obj ? agarre)))

Y esta es la definición de problema que instantánea la definición de dominio anterior con un ambiente concreto con dos habitaciones y dos bolas.

()definir ()problema strip-gripper2) ():dominio empuñaduras) ():objetos habitacióna habitaciónb bola1 bola2 izquierda derecho) ():init ()habitación habitacióna) ()habitación habitaciónb) ()bola bola1) ()bola bola2) ()agarre izquierda) ()agarre derecho) ()a-robby habitacióna) ()gratis izquierda) ()gratis derecho) ()a bola1 habitacióna) ()a bola2 habitacióna) ()# Goal ()a bola1 habitaciónb))