Lenguaje de definición de dominio de planificación
De Wikipedia, la enciclopedia libre
Saltar a navegación Saltar a búsqueda

El lenguaje de definición de dominio de planificación ( PDDL ) es un intento de estandarizar los lenguajes de planificación de inteligencia artificial (IA) . Fue desarrollado por primera vez por Drew McDermott y sus colegas en 1998 (inspirado en STRIPS y ADL, entre otros) principalmente para hacer posible la Competencia Internacional de Planificación (IPC) 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 costa de cierto poder expresivo, en comparación con los sistemas específicos de dominio. [1]

Versiones oficiales de facto de PDDL

PDDL1.2

Este fue el idioma oficial del 1º y 2º IPC en 1998 y 2000 respectivamente. [2] Separa el modelo del problema de planificación en dos partes principales: (1) descripción del dominio y (2) 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)determinar el problema de planificación específico (estos elementos están contenidos en la descripción del problema). Así, 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 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 de problema de conexión forman el modelo PDDL de un problema de planificación y, finalmente, esta es la entrada de un software planificador (generalmente planificador de IA independiente del dominio), que tiene como objetivo resolver el problema de planificación dado a través de algún software apropiado. algoritmo de planificación. La salida del planificador no se especifica por PDDL, pero por lo general es un plan de total o parcialmente ordenado(una secuencia de acciones, algunas de las cuales pueden ejecutarse incluso en paralelo a veces). 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 consistió en una definición de nombre de dominio , una definición de requisitos (para declarar los elementos del modelo al planificador que el modelo PDDL que está usando), definición de jerarquía de tipo de objeto (como una jerarquía de clases en OOP ), definición de objetos constantes (que están presentes en cada problema en el 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 estar conectados a tierra / instanciados 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 pueden ser condicionales (efectos cuando) .
(2) La descripción del problema consistió en una definición del nombre del problema , la definición del nombre de dominio relacionado , la definición de todos los objetos posibles (átomos en el universo lógico), condiciones iniciales (el estado inicial del entorno de planificación, un conjunción de hechos verdaderos / falsos), y la definición de estados-objetivo(una expresión lógica sobre hechos que deberían ser verdaderos / falsos en un estado-objetivo del entorno de planificación). Así, finalmente, PDDL1.2 capturó la "física" de un entorno de planificación determinista, discreto y totalmente accesible, de agente único.

PDDL2.1

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

PDDL2.2

Este fue el lenguaje oficial de la vía determinista de la 4ta IPC en 2004. [4] 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 literales iniciales cronometrados (para modelar eventos exógenos que ocurren en un momento 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 vía determinista del quinto IPC en 2006. [5] [6] [7] Introdujo restricciones de trayectoria de estado ( restricciones duras en forma de expresiones de lógica modal , que deberían ser verdaderas para el estado -trayectoria 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 restricciones duras, pero su satisfacción no fue necesaria, aunque podría ser incorporado en la métrica del 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. Eventualmente, PDDL3.0 actualizó la expresividad del lenguaje para poder hacer frente a importantes desarrollos 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. [8] [9] [10] Introdujo fluidos de objeto (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). Por lo tanto, PDDL3.1 adaptó el lenguaje aún más a las expectativas modernas con un cambio sintáctico aparentemente pequeño, pero semánticamente bastante significativo en la expresividad.

Situación actual

La última versión del idioma 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 IPC-2011 o la página de inicio de IPC-2014 .

Sucesores / variantes / extensiones de PDDL

PDDL +

Esta extensión de PDDL2.1 alrededor de 2002–2006 proporciona un modelo más flexible de cambio continuo mediante el uso de procesos y eventos autónomos . [1] [11] 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 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 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 dado puede perdurar en el tiempo. Por lo tanto, en PDDL + las expresiones de actualización continua están restringidas para ocurrir solo en efectos de proceso. Las acciones y eventos, que son instantáneos, están restringidos a la expresión de cambios discretos. Esto introduce el modelo de tres partes antes mencionado 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 por medio de un proceso; (2) el proceso se da cuenta del 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 pueden lograrse antes de que se detenga un proceso activo.

NDDL

NDDL ( N ew D omain D efinición L anguage) es NASA respuesta 's para PDDL de alrededor de 2002. [12] [13] Sus Difiere de representación de PDDL en varios aspectos: 1) que utiliza una representación de la variable / valor (líneas de tiempo / actividades ) en lugar de una lógica proposicional / de primer orden , y 2) no hay un concepto de estados o acciones, solo de intervalos (actividades) y restricciones entre esas actividades . En este sentido, los modelos en NDDL se parecen más a esquemas para SATcodificaciones de problemas de planificación en lugar de 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 cuando se utiliza NDDL, pero la correspondencia con representaciones de problemas de planificación estándar distintas de PDDL puede ser mucho menos intuitiva que en el caso de PDDL.

MAPL

MAPL ( M en última A gent P Lanning L anguage, pronunciado "arce") es una extensión de PDDL2.1 desde alrededor de 2003. [14] Es una modificación bastante grave de la lengua original. Introduce variables de estado no proposicionales (que pueden ser n-arias: verdaderas, falsas, desconocidas 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 ysincronización explícita del plan 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 simultáneos no necesariamente deben comunicarse para poder funcionar en un entorno de múltiples agentes. Finalmente, MAPL introduce eventos (endógenos y exógenos) con el fin de manejar la concurrencia de acciones. Así, 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.

OPTAR

OPT ( O ntology con P olymorphic T ipos) fue una profunda extensión de PDDL2.1 por Drew McDermott desde alrededor de 2003 hasta 2005 (con algunas similitudes con PDDL +). [15] Fue un intento de crear una notación de propósito general para crear ontologías , definidas como marcos conceptuales formalizados para los 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 hacer uso de construcciones de orden superior como expresiones λ explícitas que permitían una inferencia de tipos eficiente (es decir, no solo los objetos de dominio tenían tipos (tipos de nivel 0 ), pero también las funciones / fluidos definidos anteriormente, estos objetos tenían tipos en forma de mapeos arbitrarios ( tipos de nivel 1 ), que podrían ser genéricos, 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 más alto (tipo de nivel 2 ) sin mencionar 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 nivel 0/1 / 2 tipo. Por ejemplo, las funciones podrían correlacionarse de funciones arbitrarias a funciones arbitrarias ...). OPT estaba destinado básicamente a ser (casi) compatible con PDDL2.1. La notación para procesos y acciones duraderas.se tomó prestado principalmente de PDDL + y PDDL2.1, pero más allá de eso, OPT ofreció muchas otras extensiones significativas (por ejemplo , estructuras de datos , fluidos no booleanos , valores de retorno para acciones, vínculos entre acciones, expansión de acciones jerárquicas , jerarquía de definiciones de dominio , uso de espacios de nombres para compatibilidad con la web semántica ).

PPDDL

PPDDL ( P robabilistic PDDL ) 1.0 fue el idioma oficial de la vía probabilística del 4º y 5º IPC en 2004 y 2006 respectivamente. [16] Extendió PDDL2.1 con efectos probabilísticos (distribuciones discretas de probabilidad general sobre los posibles efectos de una acción), fluidos de recompensa (por incrementar o disminuir la recompensa total de un plan en los efectos de las acciones), recompensas de metas (por recompensando una trayectoria de estado, que incorpora al menos un estado de meta), y fluidez de meta alcanzada(lo cual era cierto, 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 completamente observable para el planificador / agente.

APPL

APPL ( A bstract P lan P reparation L anguage) 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. [17] 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 las reuniones automatizadas 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 ( R elational D ynamic influencia D iagram L anguage) era el idioma oficial de la pista de la incertidumbre de la séptima IPC en 2011. [18] Conceptualmente se basa en PPDDL1.0 y PDDL3.0, pero en la práctica se trata de un completamente diferente lenguaje 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)representando todo (estado-fluidez, observaciones, acciones, ...) con variables. De esta manera RDDL se aparta significativamente de PDDL. El RDDL conectado a tierra corresponde a las redes dinámicas bayesianas (DBN) de manera similar a PPDDL1.0, pero el RDDL es más expresivo que el PPDDL1.0.

MA-PDDL

MA-PDDL ( M ulti A gent PDDL ) es una extensión modular minimalista de PDDL3.1 introducida en 2012 (es decir, un nuevo :multi-agentrequisito) que permite la planificación por y para múltiples agentes. [19] 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 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 se pueden representar de una manera general y flexible (por ejemplo, suponga 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 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, metas y métricas (suponiendo que :typingse declare). Desde PDDL3.1asume que el entorno es determinista y completamente observable, lo mismo vale para MA-PDDL, es decir, cada agente puede acceder al valor de cada estado con fluidez en cada instante de tiempo y observar cada acción previamente ejecutada de cada agente, y también las acciones concurrentes de los agentes determinan sin ambigüedades el siguiente estado del medio ambiente. Esto se mejoró más tarde mediante la adición de efectos probabilísticos y de observabilidad parcial (nuevamente, en forma de dos nuevos requisitos modulares :partial-observabilityy :probabilistic-effects, respectivamente, este último se inspiró en PPDDL1.0 , y ambos son compatibles con todas las características anteriores del lenguaje , incluido :multi-agent). [20]

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. [21]

( definir ( dominio  tiras de agarre )  ( : predicados  ( sala  ? r )  ( bola  ? b )  ( agarrador  ? g )  ( en-robby  ? r )  ( en  ? b  ? r )  ( libre  ? g )  ( llevar  ? o  ? g ))  ( :  movimiento de  acción : parámetros  ( ? desde  ? hasta )  : condición previa  ( y ( habitación  ? desde ) ( room  ? to )  ( at-robby  ? from ))  : efecto  ( y ( at-robby  ? to )  ( not ( at-robby  ? from ))))  ( : action  pick  : parameters  ( ? obj  ? room  ? gripper )  : condición previa  ( y ( bola  ? obj )  ( habitación  ? habitación )  ( pinza  ? pinza )  ( en la habitación  ? obj  ? )  (at-robby  ? room )  ( free  ? gripper ))  : efecto  ( y ( carry  ? obj  ? gripper )  ( not ( at  ? obj  ? room ))  ( not ( free  ? gripper ))))  ( : action  drop  : parameters  ( ? obj  ? habitación  ? pinza )  : condición previa  ( y ( bola  ? obj )  ( habitación  ? habitación )  ( pinza ? pinza )  ( llevar  ? obj  ? pinza )  ( en-robby  ? habitación ))  : efecto  ( y ( en  ? obj  ? habitación )  ( libre  ? pinza )  ( no ( llevar  ? obj  ? pinza )))))

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

( Definir ( problemas  tiras-gripper2 )  ( : dominio  de agarre-Strips )  ( : objetos  rooma  roomb  ball1  ball2  dejó  derecha )  ( : init  ( habitación  rooma )  ( habitación  roomb )  ( balón  ball1 )  ( balón  ball2 )  ( pinza  izquierda )  ( pinza  derecha )  ( a-Robby  rooma )  ( gratuita izquierda )  ( libre  derecha )  ( en la  sala de la  pelota 1 )  ( en la  sala de la  pelota 2 ))  ( : gol  ( en la  sala de la  pelota 1 )))

Referencias

  1. ^ a b Fox, M .; Long, D. (2002). "PDDL +: Modelado de efectos dependientes del tiempo continuo". Actas del 3er Taller Internacional de la NASA sobre Planificación y Programación para el Espacio . CiteSeerX  10.1.1.15.5965 .
  2. ^ McDermott, Drew; Ghallab, Malik; Howe, Adele; Knoblock, Craig; Ram, Ashwin; Veloso, Manuela; Weld, Daniel; Wilkins, David (1998). "PDDL --- El lenguaje de definición de dominio de planificación" (PDF) . Informe técnico CVC TR98003 / DCS TR1165 . New Haven, CT: Yale Center for Computational Vision and Control. CiteSeerX 10.1.1.51.9941 .  
  3. ^ Fox, M .; Long, D. (2003). "PDDL2.1: una extensión de PDDL para expresar dominios de planificación temporal" (PDF) . Revista de Investigación en Inteligencia Artificial . 20 : 61-124. doi : 10.1613 / jair.1129 .
  4. ↑ Edelkamp, ​​S .; Hoffmann, J. (2003). "PDDL2.2: El lenguaje para la parte clásica del IV Concurso Internacional de planificación" (PDF) . Informe técnico No. 195 . Institut für Informatik .
  5. ↑ Gerevini, A .; Long, D. (2006). "Preferencias y restricciones suaves en PDDL3" (PDF) . Actas del taller ICAPS-2006 sobre preferencias y restricciones blandas en la planificación . págs. 46–54.
  6. ↑ Gerevini, A .; Long, D. (2005). "Plan de restricciones y preferencias en PDDL3" (PDF) . Informe técnico RT 2005-08-47 . Dipartimento di Elettronica per l'Automazione, Università degli Studi di Brescia.
  7. ↑ Gerevini, A .; Long, D. (2005). "Descripción BNF de PDDL3.0" (PDF) . Manuscrito inédito vinculado desde el sitio web de IPC-5 .
  8. ^ Helmert, M. (2008). "Cambios en PDDL 3.1" . Resumen inédito del sitio web de IPC-2008 .
  9. ^ Kovacs, DL (2011). "Definición BNF de PDDL3.1: completamente corregida, sin comentarios" (PDF) . Manuscrito inédito del sitio web de IPC-2011 .
  10. ^ Kovacs, DL (2011). "Definición BNF de PDDL3.1: parcialmente corregida, con comentarios / explicaciones" (PDF) . Manuscrito inédito del sitio web de IPC-2011 .
  11. ^ Fox, M .; Long, D. (2006). "Modelado de dominios mixtos discretos y continuos para la planificación" (PDF) . Revista de Investigación en Inteligencia Artificial . 27 : 235-297. arXiv : 1110.2200 . CiteSeerX 10.1.1.75.6792 . doi : 10.1613 / jair.2044 .  
  12. ^ Frank, J .; Jonsson, A. (2002). "Planificación de intervalos y atributos basada en restricciones" (PDF) . Informe técnico . Moffett Field, CA: Centro de Investigación Ames de la NASA.
  13. ^ Bernardini, S .; Smith, DE (2007). "Desarrollo del control de búsqueda independiente del dominio para EUROPA2" (PDF) . Actas del taller sobre heurística para la planificación independiente del dominio: avances, ideas, limitaciones, desafíos . XVII Congreso Internacional de Planificación y Programación Automatizados (ICAPS-2007). Rhode Island, Estados Unidos.
  14. ^ Brenner, M. (2003). "Un lenguaje de planificación de agentes múltiples" (PDF) . Actas del Taller sobre PDDL . XIII Congreso Internacional de Planificación y Programación Automatizados (ICAPS-2003). Trento, Italia.
  15. ^ McDermott, D. (2005). "OPT Manual Versión 1.7.3 (Refleja Opt Versión 1.6.11) * BORRADOR **" (PDF) . Manuscrito inédito del sitio web de Drew McDermott .
  16. ^ Younes, HLS; Littman, ML (2004). "PPDDL 1.0: una extensión de PDDL para expresar dominios de planificación con efectos probabilísticos" (PDF) . Informe técnico CMU-CS-04-167 . Pittsburgh: Universidad Carnegie Mellon.
  17. ^ Mayordomo, R .; Muñoz, C. (2006). "Un lenguaje de preparación del plan de resumen" (PDF) . Informe técnico de la NASA NASA / TM-2006-214518 .
  18. ^ Sanner, S. (2010). "Lenguaje de diagrama de influencia dinámica relacional (RDDL): descripción del lenguaje" (PDF) . Manuscrito inédito del sitio web de IPC-2011 .
  19. ^ Kovacs, DL (2012). "Una extensión de múltiples agentes de PDDL3.1" (PDF) . Actas del 3er Taller sobre el Concurso Internacional de Planificación (IPC) . 22º Congreso Internacional de Planificación y Programación Automatizados (ICAPS-2012). Atibaia, São Paulo, Brasil. págs. 19-27.
  20. ^ Kovacs, DL; Dobrowiecki, TP (2013). Conversión de MA-PDDL en juegos de formato extenso (PDF) . Acta Polytechnica Hungarica . 10 (8). págs. 27–47. doi : 10.12700 / APH.10.08.2013.8.2 .
  21. ^ Veloso, Manuela. "PDDL por ejemplo" (PDF) . Universidad Carnegie Mellon . Consultado el 28 de noviembre de 2015 .
Obtenido de " https://en.wikipedia.org/w/index.php?title=Planning_Domain_Definition_Language&oldid=1026662262#MAPL "
Contribute a better translation