Planning Domain Definition Language - Enciclopedia

El Lenguaje de Definición de Dominio de Planificación (PDDL) es un intento por 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 la Competencia Internacional de Planificación (IPC) de 1998/2000, y luego evolucionó con cada competencia. La estandarización proporcionada por PDDL tiene la ventaja de hacer que la investigación sea más reutilizable y fácilmente comparable, aunque a cambio de cierta capacidad expresiva, en comparación con los sistemas específicos del dominio.

Resumen
PDDL es un formato legible por humanos para problemas de planificación automática que proporciona una descripción de los posibles estados del mundo, una descripción del conjunto de posibles acciones, un estado inicial específico del mundo y un conjunto específico de objetivos deseados. Las descripciones de acciones incluyen los requisitos de la acción y los efectos de la acción. PDDL separa el modelo del problema de planificación en dos partes principales: La descripción del problema incluye el estado inicial y los objetivos a cumplir. El ejemplo siguiente proporciona una definición de dominio y una instancia de descripción de problema para la planificación automatizada de un robot con dos brazos de agarre.
PDDL se convierte en la entrada para el software de planificador, que suele ser un planificador de IA (Inteligencia Artificial) independiente del dominio. PDDL no describe la salida del software de planificador, pero la salida suele ser un plan ordenado total o parcialmente, que es una secuencia de acciones, algunas de las cuales pueden ejecutarse en paralelo.
El lenguaje PDDL se inspira en el Solucionador de Problemas del Instituto de Investigación de Stanford (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 manera formal de describir taxonomías y redes de clasificación, esencialmente definiendo la estructura del conocimiento para varios dominios: los sustantivos representan clases de objetos y los verbos representan relaciones entre los objetos. El lenguaje PDDL también utiliza principios de programación orientada a objetos (OOP), en el sentido de que la descripción del dominio tiene una jerarquía de tipos de objetos que es relativamente fija, como la jerarquía de clases en OOP, y la descripción del problema varía de un problema de planificación a otro, como los datos en instancias de un objeto.
La última versión del PDDL se describe en una definición de sintaxis en forma BNF (Backus-Naur Form) del PDDL 3.1. Hay varios recursos en línea sobre cómo usar PDDL, y también un libro.

Versiones oficiales de facto de PDDL


= PDDL1.2 =
Este fue el lenguaje oficial de la 1ª y 2ª IPC en 1998 y 2000, respectivamente. Separó el modelo del problema de planificación en dos partes principales: Such a division of the model allows for an intuitive separation of those elements, which are (1) present in every specific problem of the problem-domain (these elements are contained in the domain-description), and those elements, which (2) determine the specific planning-problem (these elements are contained in the problem-description). Thus several problem-descriptions may be connected to the same domain-description (just as several instances may exist of a class in OOP (Object Oriented Programming) or in OWL (Web Ontology Language) for example). Thus a domain and a connecting problem description forms the PDDL-model of a planning-problem, and eventually this is the input of a planner (usually domain-independent AI planner) software, which aims to solve the given planning-problem via some appropriate planning algorithm. The output of the planner is not specified by PDDL, but it is usually a totally or partially ordered plan (a sequence of actions, some of which may be executed even in parallel sometimes). Now lets take a look at the contents of a PDDL1.2 domain and problem description in general.


= PDDL2.1 =
Este fue el lenguaje oficial de la 3ª IPC en 2002. Introdujo flujos numéricos (por ejemplo, para modelar recursos no binarios como el nivel de combustible, el tiempo, la energía, la distancia, el peso, ...), métricas de plan (para permitir una evaluación cuantitativa de los planes, y no solo planificación impulsada por objetivos, sino también planificación impulsada por utilidad, es decir, optimización, minimización/maximización métrica), y acciones durativas/continuas (que podrían tener una longitud variable, no discreta, 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 lenguaje oficial de la pista determinista de la 4ª IPC en 2004. Introdujo predicados derivados (para modelar la dependencia de hechos dados de otros hechos, por ejemplo, si A es accesible desde B, y B es accesible desde C, entonces A es accesible desde C (transitividad)), y literals iniciales con tiempo (para modelar eventos exógenos que ocurren en un tiempo dado independientemente de la ejecución del plan). Finalmente, PDDL2.2 extendió 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 lenguaje oficial de la pista determinista de la 5ª IPC en 2006. Introdujo restricciones de trayectoria de estado (restricciones duras 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 suaves en forma de expresiones lógicas, similares a las restricciones duras, pero su satisfacción no es necesaria, aunque podría ser incorporada en el métrica de plan, por ejemplo, para maximizar el número de preferencias satisfechas o simplemente para medir la calidad de un plan) para permitir la planificación basada en preferencias. Finalmente, PDDL3.0 actualizó la expresividad del lenguaje para poder manejar los últimos y importantes desarrollos en la planificación.


= PDDL3.1 =
Este fue el lenguaje oficial de la pista determinista de la 6ª y 7ª IPC en 2008 y 2011, respectivamente. Introdujo flujos de objetos (es decir, el rango de las funciones ahora podría no ser 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 sintácticamente aparentemente pequeño, pero semánticamente bastante significativo en la expresividad.


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


Sucesores/variantes/extensiones de PDDL


= PDDL+ =
Esta extensión de PDDL2.1 de aproximadamente 2002-2006 proporciona un modelo más flexible de cambio continuo a través del uso de procesos autónomos y eventos. La clave que esta extensión proporciona 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 en los valores numéricos. Se inician y terminan por 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-cierre. Se hacen distinciones entre estados lógicos y numéricos: las transiciones entre estados lógicos se asumen que son instantáneas mientras que la ocupación de un estado lógico dado puede durar sobre el tiempo. Por lo tanto, las expresiones de actualización continua se restringen a ocurrir solo en los efectos de los procesos. Las acciones y los eventos, que son instantáneos, se restringen a la expresión de cambios discretos. Esto introduce el mencionado modelo de 3 partes de períodos de cambio continuo: Comentario: los objetivos del plan pueden alcanzarse antes de que se detenga un proceso activo.


= NDDL =
NDDL (New Domain Definition Language) es la respuesta de la NASA a PDDL de aproximadamente 2002. Su representación difiere de PDDL en varios aspectos: En este sentido, los modelos en NDDL se parecen más a esquemas para la codificación SAT de problemas de planificación en lugar de modelos PDDL. Debido a las diferencias mencionadas, la planificación y la ejecución de planes (por ejemplo, durante misiones espaciales críticas) pueden ser más robustas cuando se utiliza NDDL, pero la correspondencia con las representaciones estándar de problemas de planificación diferentes de PDDL puede ser mucho menos intuitiva que en el caso de PDDL.


= MAPL =
MAPL (Multi-Agent Planning Language, pronunciado "maple") es una extensión de PDDL2.1 de aproximadamente 2003. Es una modificación bastante seria 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 exhaustivo, que también es compatible con la sintaxis original de PDDL (y es solo una adición opcional). MAPL también introduce acciones cuyas duraciones se determinarán en tiempo de ejecución y sincronización explícita de planes que se realiza a través de comunicación basada en actos de habla entre los agentes. Esta asunción puede ser artificial, ya que los agentes que ejecutan planes concurrentes no necesariamente deben 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. Por lo tanto, los eventos se convierten en parte explícita de los planes y se asignan a los agentes por una función de control, que también es parte del plan.


= OPT =
OPT (Ontology with Polymorphic Types) fue una extensión profunda de PDDL2.1 de Drew McDermott de aproximadamente 2003-2005 (con algunas similitudes con PDDL+). Fue un intento por crear una notación general-purpose para crear ontologías, definidas como marcos conceptuales formales para dominios de planificación sobre los que 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 estructuras de alto orden como expresiones λ-explícitas que permiten inferencias de tipo eficientes (es decir, no solo los objetos del dominio tenían tipos (tipos de nivel 0), sino también las funciones/fluencias definidas sobre estos objetos tenían tipos en forma de mapeos arbitrarios (tipos de nivel 1), que podían ser genéricos, por lo que sus parámetros (el dominio y el rango del mapeo genérico) podían definirse con variables, que podrían tener un tipo de nivel superior (nivel 2 tipo) no hablando de que los mapeos podrían ser arbitrarios, es decir, el dominio o el rango de una función (por ejemplo, predicado, flujo numérico) podría ser cualquier tipo de nivel 0/1/2. Por ejemplo, las funciones podrían mapear desde funciones arbitrarias a funciones arbitrarias...). OPT estaba básicamente destinado a ser (casi) compatible con PDDL2.1. La notación para procesos y acciones durativas se prestó principalmente de PDDL+ y PDDL2.1, pero más allá de eso OPT ofreció muchas otras extensiones significativas (por ejemplo, estructuras de datos, fluencias no booleanas, valores devueltos para las acciones, enlaces entre acciones, expansión jerárquica de acciones, jerarquía de definiciones de dominio, el uso de nombres de espacio para la compatibilidad con la Web Semántica).


= PPDDL =
PPDDL (Probabilistic PDDL) 1.0 fue el lenguaje oficial de la pista probabilística de la 4ª y 5ª IPC en 2004 y 2006, respectivamente. Extendió PDDL2.1 con efectos probabilísticos (discretos, distribuciones de probabilidad generales sobre los posibles efectos de una acción), fluencias 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 incorpora al menos un estado de objetivo) y fluencias de objetivo alcanzado (que son verdaderas si la trayectoria de estado incorpora al menos un estado de objetivo). Finalmente, estos cambios permitieron que PPDDL1.0 realizara planificación de Procesos de Decisión Markoviana (MDP), donde puede haber incertidumbre en las transiciones de estado, pero el entorno es completamente observable para el planificador/agente.


= APPL =
APPL (Abstract Plan Preparation Language) 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 fue simplificar el análisis y especificación formal de problemas de planificación que se destinan a aplicaciones críticas de seguridad como la gestión de energía o el alineamiento automatizado en futuros vehículos tripulados. APPL utilizó los mismos conceptos que NDDL con la extensión de acciones, y también algunos otros conceptos, pero su capacidad expresiva es mucho menor que la de PDDL (con la esperanza de mantenerse robusto y formalmente verificable).


= RDDL =
RDDL (Relational Dynamic influence Diagram Language) fue el lenguaje oficial de la pista de incertidumbre de la 7ª IPC en 2011.
Conceptualmente se basa en PPDDL1.0 y PDDL3.0, pero prácticamente es un lenguaje completamente diferente tanto en sintaxis como en semántica. La introducción de observabilidad parcial es una de las más importantes cambios en RDDL en comparación con PPDDL1.0. Permite una descripción eficiente de Procesos de Decisión Markoviana (MDP) y Procesos de Decisión Markoviana Parcialmente Observables (POMDP) representando todo (estado-flujo, observaciones, acciones, ...) con variables. De esta manera, RDDL se aleja significativamente de PDDL. RDDL basado en datos (RDDL) 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 minimalista y modular de PDDL3.1 introducida en 2012 (es decir, un nuevo :multi-agent requirement) 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 de diferentes agentes (es decir, diferentes capacidades). Del mismo modo, 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 interactuantes pueden representarse de manera general y flexible (por ejemplo, supongamos que se necesitan al menos 2 agentes para ejecutar una acción de levantamiento 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 también se puede representar fácilmente la sinergia destructiva en MA-PDDL)). Además, como un tipo de azúcar sintáctico, se introdujo un mecanismo simple para la herencia y la polimorfismo de acciones, objetivos y métricas en MA-PDDL (asumiendo :typing se declara). 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 flujo de estado en cada instante de tiempo y observar cada acción ejecutada anteriormente por cada agente, y también las acciones concurrentes de los agentes determinan sin ambigüedad el siguiente estado del entorno. Esto se mejoró más tarde con la adición de observabilidad parcial y efectos probabilísticos (de nuevo, en forma de dos nuevos requisitos modulares, :partial-observability y :probabilistic-effects, respectivamente, el último inspirado en PPDDL1.0, y ambos compatibles con todas las características anteriores del lenguaje, incluyendo :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.

Y esta es la definición de problema que instancia la definición de dominio anterior con un entorno concreto con dos habitaciones y dos bolas.


Referencias