Lenguaje de definición de dominio de planificación

Este fue el idioma oficial de la 1.ª y 2.ª IPC en 1998 y 2000 respectivamente. ^{[ 9 ]} Separó el modelo del problema de planificación en dos partes principales:

Esta división del modelo permite una separación intuitiva de los elementos que (1) están 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). De este modo, varias descripciones de problemas pueden estar conectadas a la misma descripción de dominio (al igual que pueden existir varias instancias de una clase en POO (Programación Orientada a Objetos) o en OWL (Lenguaje de Ontología Web), por ejemplo). Así, un dominio y una descripción de problema asociada forman el modelo PDDL de un problema de planificación, que finalmente constituye la entrada de un software de planificación (generalmente un planificador de IA independiente del dominio), cuyo objetivo es resolver el problema de planificación dado mediante un 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). Ahora veamos el contenido de un dominio PDDL1.2 y la descripción del problema en general.

Este fue el lenguaje oficial del 3er IPC en 2002. ^{[ 10 ]} Introdujo variables numéricas (por ejemplo, para modelar recursos no binarios como nivel de combustible, tiempo, energía, distancia, peso, ...), métricas de planificación (para permitir la evaluación cuantitativa de planes, y no solo la planificación orientada a objetivos, sino también la orientada a la utilidad, es decir, optimización, minimización/maximización de métricas) y acciones duraderas/continuas (que podían tener una duración, condiciones y efectos variables y no discretos). 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.

Este fue el lenguaje oficial de la rama determinista de la 4.ª IPC en 2004. ^{[ 11 ]} Introdujo predicados derivados (para modelar la dependencia de hechos dados con respecto a 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 temporizados (para modelar eventos exógenos que ocurren en un momento dado independientemente de la ejecución del plan). Posteriormente, PDDL2.2 extendió el lenguaje con algunos elementos importantes, pero no representó una evolución radical en comparación con PDDL2.1 después de PDDL1.2.

Este fue el lenguaje oficial de la vía determinista del 5.º IPC en 2006. ^{[ 12 ] [ 13 ] [ 14 ]} Introdujo restricciones de trayectoria de estado (restricciones estrictas en forma de expresiones de lógica modal , que deben ser verdaderas para la trayectoria de estado producida durante la ejecución de un plan, que es una solución del problema de planificación dado) y preferencias (restricciones flexibles en forma de expresiones lógicas, similares a las restricciones estrictas, pero su satisfacción no era necesaria, aunque podía incorporarse a la métrica del plan, por ejemplo, para maximizar el número de preferencias satisfechas, o para simplemente medir la calidad de un plan) para permitir la planificación basada en preferencias . Finalmente, PDDL3.0 actualizó la expresividad del lenguaje para poder hacer frente a los desarrollos recientes e importantes en planificación.

Este fue el lenguaje oficial de la vía determinista de la 6.ª y 7.ª IPC en 2008 y 2011 respectivamente. ^{[ 15 ] [ 16 ] [ 17 ]} Introdujo la fluidez de objetos (es decir, el rango de las funciones ahora podía ser no solo numérico ( entero o real), sino también cualquier tipo de objeto). Así, PDDL3.1 adaptó el lenguaje aún más a las expectativas modernas con un cambio en la expresividad que parecía pequeño sintácticamente, pero que era bastante significativo semánticamente.

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 principal de IPC-2011 o la página principal de IPC-2014 .

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 . ^{[ 2 ] [ 18 ]} La clave que proporciona esta extensión es la capacidad de modelar la interacción entre el comportamiento del agente y los cambios que se inician en su entorno. 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 entorno. Esta estructura de 3 partes se conoce como el modelo de inicio-proceso-parada . Se distinguen los 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 dado puede perdurar en el tiempo. Por lo tanto, en PDDL+ las expresiones de actualización continua se restringen a ocurrir solo en los efectos del proceso. Las acciones y los eventos, que son instantáneos, se restringen a la expresión de cambios discretos. Esto introduce el modelado de 3 partes mencionado anteriormente para los períodos de cambio continuo:

Comentario: es posible que los objetivos del plan se alcancen antes de que se detenga un proceso en curso.

NDDL ( New Domain Definition Language ) es ^la respuesta de la NASA a PDDL desde alrededor de 2002. [ 19 ] [ ^{20 ] Su representación difiere} de PDDL en varios aspectos:

En este sentido, los modelos en NDDL se asemejan 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 robustas al usar 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 ( Lenguaje de Planificación Multiagente , pronunciado " maple" ) es una extensión de PDDL2.1 de alrededor de 2003. ^{[ 21 ]} Es una modificación bastante importante del lenguaje original. Introduce variables de estado no proposicionales (que pueden ser n-arias: verdadero, falso, desconocido 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 PDDL original (y es solo una adición opcional). MAPL también introduce acciones cuya duración se determinará en tiempo de ejecución y sincronización explícita de planes que se realiza a través de la comunicación basada en actos de habla entre agentes. Esta suposición puede ser artificial, ya que los agentes que ejecutan planes concurrentes no necesariamente deben comunicarse para poder funcionar en un entorno multiagente. Finalmente, MAPL introduce eventos (endógenos y exógenos) para manejar la concurrencia de acciones. De este modo, los eventos pasan a formar parte de los planes de forma explícita y son asignados a los agentes por una función de control , que también forma parte del plan.

OPT ( Ontología con Tipos Polimórficos ) fue una profunda extensión de PDDL2.1 por Drew McDermott entre 2003 y 2005 (con algunas similitudes con PDDL+). ^{[ 22 ]} 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 las aplicaciones de planificación deben razonar. Su sintaxis se basaba en PDDL, pero tenía un sistema de tipos mucho más elaborado , que permitía a los usuarios utilizar construcciones de orden superior, como expresiones λ explícitas, lo que permitía una 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/fluyentes definidos sobre estos objetos tenían tipos en forma de asignaciones arbitrarias ( tipos de nivel 1 ), que podían ser genéricas, de modo que sus parámetros (el dominio y el rango de la asignación genérica) podían definirse con variables, que podían tener un tipo de nivel aún superior ( tipo de nivel 2 ), sin mencionar que las asignaciones podían ser arbitrarias, es decir, el dominio o el rango de una función (por ejemplo, predicado, fluente numérico) podía ser cualquier tipo de nivel 0/1/2. Por ejemplo, las funciones podían asignar funciones arbitrarias a funciones arbitrarias...). OPT estaba básicamente diseñado para 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 ofreció muchas otras extensiones significativas (por ejemplo, estructuras de datos , fluentes no booleanos , valores de retorno para acciones, enlaces entre acciones, expansión jerárquica de acciones , jerarquía de definiciones de dominio , el uso de espacios de nombres para compatibilidad con la Web Semántica ).

PPDDL ( PDDL probabilístico ) 1.0 fue el lenguaje oficial de la rama probabilística de la 4.ª y 5.ª IPC en 2004 y 2006 respectivamente. ^{[ 23 ]} Extendió PDDL2.1 con efectos probabilísticos (distribuciones de probabilidad discretas y generales sobre los posibles efectos de una acción), fluentes de recompensa (para incrementar o decrementar la recompensa total de un plan en los efectos de las acciones), recompensas de objetivo (para recompensar una trayectoria de estado que incorpore al menos un estado objetivo) y fluentes de objetivo alcanzado (que eran verdaderos si la trayectoria de estado incorporaba al menos un estado objetivo). Finalmente, estos cambios permitieron que PPDDL1.0 implementara la planificación de procesos de decisión de Markov (MDP) , donde puede haber incertidumbre en las transiciones de estado, pero el entorno es completamente observable para el planificador/agente.

APPL ( Abstract Plan Preparation Language ) es una variante más reciente de NDDL de 2006, que es más abstracta que la mayoría de los lenguajes de planificación existentes como PDDL o NDDL. [ 24 ^{] El objetivo} de este lenguaje era simplificar el análisis formal y la especificación de 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 utilizó 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 mantener la robustez y la verificabilidad formal).

RDDL ( Relational Dynamic influence Diagram Language ) fue el lenguaje oficial de la pista de incertidumbre del 7.º IPC en 2011. ^{[ 25 ]} Conceptualmente se basa en PPDDL1.0 y PDDL3.0, pero en la práctica 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 distancia significativamente de PDDL. Grounded RDDL se corresponde con las Redes Bayesianas Dinámicas (DBN) de manera similar a PPDDL1.0, pero RDDL es más expresivo que PPDDL1.0.

MA-PDDL ( Multi - Agent PDDL ) es una extensión modular y minimalista de PDDL3.1 introducida en 2012 (es decir, un nuevo requisito :multi-agent) que permite la planificación por y para múltiples agentes. ^{[ 26 ]} La adición es compatible con todas las características de PDDL3.1 y aborda la mayoría de los problemas de MAPL . Agrega 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 precondiciones 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 se necesitan al menos 2 agentes para ejecutar una liftacción para levantar una mesa pesada en el aire, o de lo contrario la mesa permanecería en el suelo (este es un ejemplo de sinergia constructiva, pero la sinergia destructiva también puede representarse 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 el polimorfismo de acciones, objetivos y métricas:typing (suponiendo que se declare). Dado que PDDL3.1 asume que el entorno es determinista y completamente 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 entorno. Esto se mejoró posteriormente con la adición de observabilidad parcial y efectos probabilísticos (nuevamente, en forma de dos nuevos requisitos modulares, :partial-observabilityy :probabilistic-effects, respectivamente, el último inspirado en PPDDL1.0 , y ambos compatibles con todas las características anteriores del lenguaje, incluyendo :multi-agent). ^{[ 27 ]}