Diseño e implementación de un sistema de planificación distribuido

UNIVERSIDAD POLITÉCNICA DE VALENCIA Escuela Técnica Superior de Ingeniería Informática Ingeniería Técnica en Informática de Gestión PROYECTO DE FIN DE CARRERA Diseño e implementación de un sistema de planificación distribuido Autor: Alejandro Torreño Lerma Dirigido por: Dr. Óscar Sapena Vercher Grupo de Tecnología Informática - Inteligencia Artificial Group of Reasoning on Planning and Scheduling (GRPS-AI) Departamento de Sistemas Informáticos y Computación Universidad Politécnica de Valencia Camino de Vera, s/n 46022 Valencia, Spain 12 de Febrero de 2012 A todos los integrantes pasados y presentes del laboratorio 2L08 del DSIC. AC6H2(NO2)3CH3. i ii Índice 1 Introducción 3 2 Antecedentes 5 2.1 Planificación clásica centralizada . . . . . . . . . . . . . . . . . 5 2.2 Planificación Multi-Agente . . . . . . . . . . . . . . . . . . . . 7 2.3 Planificación de Orden Parcial . . . . . . . . . . . . . . . . . . 8 2.4 Lenguajes de planificación . . . . . . . . . . . . . . . . . . . . 10 2.4.1 STRIPS .......................... 11 2.4.2 ADL............................ 11 2.4.3 PDDL........................... 12 2.4.4 Extensiones de PDDL . . . . . . . . . . . . . . . . . . 12 3 Modelo de Planificación Multi-Agente 15 3.1 Especificación de una tarea de PMA . . . . . . . . . . . . . . 15 3.2 Planificación basada en refinamientos . . . . . . . . . . . . . . 18 3.2.1 Planificación de Orden Parcial centralizada . . . . . . . 18 3.2.2 Planificación de Orden Parcial distribuida . . . . . . . 19 4 Diseño del sistema de planificación distribuido 23 4.1 Lenguaje de planificación . . . . . . . . . . . . . . . . . . . . . 24 4.1.1 Información compartida . . . . . . . . . . . . . . . . . 25 4.1.2 Metas privadas y globales . . . . . . . . . . . . . . . . 25 4.1.3 Multi-funciones . . . . . . . . . . . . . . . . . . . . . . 26 4.2 Algoritmo de planificación distribuido . . . . . . . . . . . . . . 27 4.2.1 Intercambio inicial de información . . . . . . . . . . . . 27 4.2.2 Proceso de planificación distribuido . . . . . . . . . . . 29 4.3 Planificador de Orden Parcial . . . . . . . . . . . . . . . . . . 31 4.3.1 Extensiones del POP . . . . . . . . . . . . . . . . . . . 31 4.3.2 Funciones heurísticas . . . . . . . . . . . . . . . . . . . 32 iii 5 Implementación del sistema de planificación distribuido 35 5.1 Análisis de la implementación . . . . . . . . . . . . . . . . . . 35 5.2 Desarrollo del proyecto . . . . . . . . . . . . . . . . . . . . . . 39 5.3 Resultados experimentales . . . . . . . . . . . . . . . . . . . . 40 5.3.1 Dominios de PMA . . . . . . . . . . . . . . . . . . . . 41 5.3.2 Pruebas y resultados . . . . . . . . . . . . . . . . . . . 43 6 Conclusiones y trabajo futuro 49 6.1 Resumen de contribuciones . . . . . . . . . . . . . . . . . . . . 49 6.2 Trabajofuturo .......................... 50 6.3 Publicaciones relacionadas . . . . . . . . . . . . . . . . . . . . 51 iv Agradecimientos This work has been partly supported by the Spanish MICINN under projects TIN2011-27652-C03-01 and Consolider Ingenio 2010 CSD2007-00022, and the Valencian Prometeo project 2008/051. 1 2 Capítulo 1 Introducción El término planificación se refiere al arte de construir algoritmos de control para la síntesis de cursos de acción que permitan obtener un conjunto deseado de metas a partir de una situación inicial. En la práctica, la planificación se sustenta en el uso de funciones de utilidad, también conocidas como heurísticas, que permiten evaluar la selección de acciones o estados de acuerdo a la utilidad que ofrecen al agente de planificación [GNT04]. La Planificación Multi-Agente (en adelante PMA) generaliza el problema de planificación en dominios donde diversos agentes planifican y actúan conjuntamente. Cuando los agentes de planificación son completamente cooperativos, el ámbito de estudio se centra en cómo extender la planificación a un entorno distribuido. Tradicionalmente, la investigación en PMA se ha centrado en el diseño de arquitecturas de planificación distribuidas, mecanismos para la coordinación de planes y soluciones para combinar los planes locales de los diferentes agentes dando lugar a un plan global [Dur99, CDB05, dWtMW05]. A diferencia de estos modelos, que enfatizan el problema de controlar y coordinar soluciones locales de agentes independientes a posteriori, el presente proyecto propone un sistema de planificación distribuido que permite a los agentes participantes desarrollar un plan global conjuntamente. Nuestra propuesta se sustenta en el paradigma de Planificación de Orden Parcial (POP) [BW94]. Consideramos que PMA se refiere a la construcción de un curso de acción o plan entre un conjunto de agentes heterogéneos con diferentes capacidades y visiones del mundo. El sistema de planificación desarrollado esta orientado a la formación de un plan global a través de la composición de los planes individuales propuestos por los agentes participantes. Para ello, hemos adoptado un enfoque de planificación basada en refinamientos, por el cual los agentes proponen una serie de refinamientos sobre un plan base inicialmente vacío, hasta que se alcanza un plan solución. Este objetivo se consigue manteniendo 3 10 CAPÍTULO 2. ANTECEDENTES Algoritmo 1 Algoritmo POP Nodos_abiertos ←{Plan vacío} repetir Seleccionar Π∈Nodos_abiertos Inconsistencias_pendientes ←metas_abiertas(Π) ∪amenazas(Π) si Inconsistencias_pendientes =∅entonces devolver Π fin si Seleccionar y extraer Φ∈Inconsistencias_pendientes Sucesores ← {Πr},∀Πrque resuelve Φ si Sucesores 6=∅entonces Nodos_abiertos ←Nodos_abiertos ∪Sucesores fin si hasta que Nodos_abiertos =∅ devolver fallo el proceso POP termina con éxito. En caso de que la lista de Nodos_abiertos quede vacía antes de encontrar una solución, habremos explorado completamente el espacio de búsqueda sin encontrar solución, por lo que el proceso terminará sin éxito. La investigación en planificación se centró en POP durante la década de los ’90. Sin embargo, en los últimos años, POP ha sido abandonado progresivamente en favor de otros paradigmas más eficientes y escalables. La dificultad de diseñar heurísticas eficientes para POP condiciona el rendimiento de los planificadores basados en este paradigma. Ni siquiera los trabajos más recientes orientados a mejorar el rendimiento del paradigma POP [NK01] resultan suficientemente eficientes para competir con los enfoques de planificación basada en estados. Sin embargo, en los últimos años POP ha ganado relevancia, dado que su flexibilidad lo convierte en una buena alternativa para el desarrollo de planificadores multi-agente. 2.4 Lenguajes de planificación Uno de los principales problemas a los que se ha enfrentado la comunidad de planificación es el problema de la representación. El uso de un buen lenguaje de planificación es básico para el desarrollo de herramientas de planificación. Desde los años ’70, la mayoría de propuestas de planificación han sido influenciadas por el lenguaje STRIPS [FN71], que resuelve de forma efectiva el problema marco [MH69], y da soporte a estrategias de tipo divide y vencerás LENGUAJES DE PLANIFICACIÓN 11 [Gef00]. Esta sección describe brevemente las características de este lenguaje y sus extensiones más relevantes: ADL [Ped89] y PDDL [McD00]. 2.4.1 STRIPS El lenguaje STRIPS (STanford Research Institute Problem Solver [FN71]) fue desarrollado a principios de los ’70, como parte del sistema de planificación para el robot Shakey.STRIPS propone un modelo simple y compacto para la especificación de dominios de planificación. La representación propuesta por STRIPS incluye diversas limitaciones que complican la descripción de problemas reales [RN03], por lo que a lo largo de los años se han introducido un conjunto de extensiones que enriquecen la expresividad del lenguaje y simplifican la definición de dominios de planificación. Las limitaciones del lenguaje incluyen la posibilidad de utilizar únicamente literales positivos para describir las precondiciones de las acciones y el estado inicial, de modo que la información no mencionada se considera falsa (negación por fallo). Asimismo, las precondiciones, efectos y metas sólo se pueden describir mediante conjunción de literales, por lo que no pueden utilizarse disyunciones. Por último, destaca la ausencia de soporte de tipos y restricciones de igualdad de tipo (a=b). Además de corregir estas limitaciones, las extensiones de STRIPS mejoran el lenguaje introduciendo nuevas características, como gestión del tiempo y expresiones numéricas. 2.4.2 ADL Una de las extensiones más populares de STRIPS es ADL (Action Description Language.ADL usa un modelo algebraico para describir los estados del mundo, lo que lo hace más expresivo que STRIPS. Las mejoras que introduce ADL sobre STRIPS incluyen la incorporación de tipos en los objetos del problema, la introducción de metas y precondiciones negadas, precondiciones disyuntivas y restricciones de igualdad. Del mismo modo, se introducen los efectos condicionales, que sólo son efectivos si se cumple una determinada condición en el estado en el que se aplica la acción. Las extensiones introducidas por ADL mejoran notablemente la expresividad de STRIPS. Estas nuevas características permiten también mejorar la eficiencia de los sistemas de planificación [KNHD97]. 12 CAPÍTULO 2. ANTECEDENTES 2.4.3 PDDL Además de ADL se han desarrollado otras muchas extensiones de STRIPS, como FStrips (Functional STRIPS [Gef00]. Sin embargo, la extensión de STRIPS de mayor repercusión es PDDL (Planning Domain Definition Language) [GHK+98]) PDDL fue desarrollado para la Competición Internacional de Planning de 1998 [McD00], con el objetivo de proporcionar una notación común para el modelado de problemas de planificación. Desde su introducción, PDDL se ha convertido en el lenguaje de referencia para la mayoría de sistemas de planificación. Además de STRIPS yADL,PDDL ha recibido la influencia de otros muchos formalismos: SIPE-2 [Wil88], Prodigy 4.0 [BEG+92], UCMP [EHN94], Unpop [McD96] y UCPOP [BCF+95]. Las características más relevantes de PDDL incluyen la definición de efectos condicionales, cuantificación universal, acciones jerárquicas, axiomas de dominio, y restricciones de seguridad. La mayor parte de planificadores manejan únicamente un subconjunto de las características de PDDL. Por simplicidad, las funcionalidades de PDDL se agrupan en conjuntos de requerimientos, de modo que los planificadores pueden comprobar fácilmente si soportan las características de un determinado dominio de planificación. 2.4.4 Extensiones de PDDL La Competición Internacional de Planning (IPC ) [DKS+00] se ha convertido en una importante referencia para la investigación en planificación. Uno de los resultados más importantes de su primera edición fue la adopción de PDDL como el lenguaje común de definición de dominios de planificación [MGH+98]. Las siguientes ediciones de la competición sirvieron para introducir nuevas extensiones del lenguaje. Esta sección presenta las características principales de dichas extensiones. La primera revisión de PDDL se introdujo en la IPC de 2002 (IPC-3) [FL03]. Esta extensión añade capacidades numéricas y de manejo de tiempo aPDDL. La cuarta IPC (IPC-4), celebrada en 2004, introdujo una nueva revisión de PDDL,PDDL2.2 [Ede03]. Esta extensión introduce cambios relativamente moderados, entre los que destacan los axiomas derivados (reglas de la forma sif(x)entoncesP(x)) y literales que pasan a ser verdaderos o falsos en instantes de tiempo establecidos. PDDL3.0 [GL05] se desarrolló para la IPC de 2006 (IPC-6). PDDL3.0 enfatiza la importancia de la calidad del plan, a diferencia de las extensiones anteriores. Para ello, se introducen características como las restricciones de LENGUAJES DE PLANIFICACIÓN 13 trayectoria de estado, las restricciones débiles y las preferencias. Finalmente, PDDL3.1 [Kov11], la extensión más reciente de PDDL se introdujo en la IPC de 2008. El objetivo de esta extensión era enriquecer el lenguaje con una representación de problemas al estilo de SAS+ [BN95]. Sin embargo, SAS+ permite usar variables de modo muy limitado al no permitir el anidamiento (sólo se permiten comparaciones y asignaciones con constantes). Por ello, PDDL3.1 introduce variables objeto, que son variables que toman un dominio finito de valores, una solución flexible inspirada por el formalismo Functional Strips [Gef00]. Además, PDDL3.1 permite especificar costes numéricos a las acciones del dominio, de modo que los costes de las acciones adquieren importancia para determinar la calidad del plan. 14 CAPÍTULO 2. ANTECEDENTES Capítulo 3 Modelo de Planificación Multi-Agente Esta sección presenta el modelo de Planificación Multi-Agente (PMA) en el que se basa el sistema de planificación distribuido implementado. Del mismo modo, se describe el procedimiento seguido por los agentes para construir e intercambiar planes. 3.1 Especificación de una tarea de PMA Definición 1. (Tarea de PMA) Una tarea de PMA es una tupla T= hAG,O,V,A,I,G,i.AG ={1, . . . , n}es un conjunto finito no vacío de agentes de planificación. Oes un conjunto finito de objetos, que modelan los elementos del dominio de planificación sobre los que actúan las acciones de planificación. Ves un conjunto finito de variables de estado que modelan los estados del mundo. Cada variable de estado v∈ V está asociada a un dominio finito de valores mutuamente exclusivos Dv. Cada valor en el dominio de una variable corresponde a un objeto del dominio de planificación, esto es, ∀v∈ V,Dv⊆ O. Cuando un valor es asignado a una variable de estado, el par variable-valor actúa como un átomo instanciado en planificación proposicional. Aes el conjunto de acciones deterministas de los agentes. I es el conjunto de valores asignado a las variables de estado en Vy representa el estado inicial de la tarea de PMA T.Ges el conjunto de metas de la tarea de PMA que los agentes deben satisfacer; Grepresenta los valores que las variables de estado deben adquirir en el estado final. La información sobre los estados del mundo que poseen los agentes se modela mediante un conjunto de variables instanciadas. Esto incluye el estado inicial, I, y las metas, G. A diferencia de los modelos basados en 15 16 CAPÍTULO 3. MODELO DE PLANIFICACIÓN MULTI-AGENTE STRIPS [FN71], que aplican negación por fallo, nuestro modelo permite la representación explícita de la información verdadera y falsa. Por tanto, nuestro modelo adopta la asunción de mundo abierto, considerando que la información que no está explícitamente almacenada en el modelo interno de los agentes es desconocida para ellos. Esto se refiere a la información relativa al estado inicial Iy a las metas G. Definición 2. (Variable instanciada) Una variable instanciada del problema es una tupla de la formahv, di, donde v∈ V yd∈ Dv. Una variable instanciada negativa toma la forma hv, ¬di. Una variable instanciada positiva hv, diindica que la variable vtoma el valor d, mientras que una variable instanciada negativa hv, ¬diindica que la variable vno toma el valor d. Los agentes en nuestro modelo son heterogéneos, dado que pueden tener diferentes conocimientos y habilidades de planificación. Además, pueden tener información incompleta acerca de la tarea de PMA, dado que ésta está distribuida entre los agentes. En dicho caso, los agentes deben cooperar para resolver la tarea de PMA. Aunque la información esté distribuida entre los agentes, debe haber un subconjunto de variables de estado susceptible de ser compartido entre los agentes, de modo que éstos puedan interactuar adecuadamente. Para denotar las acciones, metas, etc, de un agente i∈ AG usaremos la notación de superíndice xipara cada aspecto x. Del conjunto de variables Vde la tarea de PMA, Vies el conjunto de variables gestionadas por el agente i, lo que incluye las variables privada que sólo iconoce, y las variables públicas compartidas con otros agentes. Por tanto, V={Vi}n i=1.Di v⊆Dves el conjunto de valores de una variable v∈ Vique son visibles para el agente i. La información del estado inicial de la tarea de PMA, I,se modela mediante un conjunto de variables instanciadas positivas y negativas. Esta información está distribuida entre los agentes bajo la asunción de que el conocimiento parcial de los agentes sobre Ies consistente, es decir, no hay información contradictoria entre los agentes. Por tanto, Ipuede definirse como I=S∀i∈AG Ii. Es posible definir tareas de PMA en las que todos los agentes tienen una visión completa del estado inicial I, es decir, ∀i∈ AG,Ii=I. Cada agente i∈ AG tiene un conjunto asociado de acciones Ai, de modo que el conjunto de acciones de una tarea de PMA se define como A=S∀i∈AG Ai. Una acción αes pública si dos o más agentes la comparten, esto es, α∈Ai∧α∈Aj,i6=j.α∈ Aies privada para una agente isi y sólo si α6∈ Aj,∀j6=i. Una acción α∈ Aidenota que el agente iposee la capacidad expresada en α. Si αforma parte del plan final, el agente ies también responsable de ejecutar α. CAPÍTULO 3. MODELO DE PLANIFICACIÓN MULTI-AGENTE 17 Definición 3. (Acción) Una acción α∈ A es una tupla hPRE(α),EFF(α)i. PRE(α) = {p1, . . . , pn}es un conjunto de variables instanciadas que representan las precondiciones de α, mientras que EFF(α) = {e1, . . . , em}es un conjunto de operaciones de la forma (v=d)o(v6=d),v∈ V,d∈ Dv, que representan las consecuencias de ejecutar α. Una acción αpuede pertenecer a diferentes agentes, es decir, α∈ Aiy α∈ Aj,i6=j. El resultado de ejecutar αen Ses un nuevo estado del mundo S0que surge de la revisión de Spor EFF(α), es decir, S0se genera actualizando las variables instanciadas en Sde acuerdo a los efectos de α: •Una operación (v=d)∈EFF(α)implica la adición de una variable instanciada hv, diy un conjunto de variables instanciadas hv, ¬d0i,∀d0∈ Dv|d06=dal estado S0. Si hv, d0i ∈ So bien hv, ¬di ∈ S,d06= d, la operación (v=d)implica también el borrado de las variables instanciadas hv, ¬diyhv, d0ide S0. •Una operación (v6=d)∈EFF(α)implica la adición de una variable instanciada hv, ¬dial estado S0. Si hv, di ∈ S, la operación (v6=d) implica también el borrado de la variable instanciada hv, difrom S0. Nótese que la sola existencia de una variable instanciada hv, ¬dien un estado Sindica que el valor de la variable ves desconocido en S, y en consecuencia, el resto de los valores de Dv, a excepción de d, son valores desconocidos. El conjunto de precondiciones de una acción α,PRE(α), indica qué variables instanciadas deben figurar en un estado Spara que αsea aplicable en ese estado. Una precondición positiva de la forma hv, diindica que la variable instanciada hv, didebe aparecer en S, mientras que una precondición negativa hv, ¬diindica que la variable instanciada hv, ¬didebe figurar en S. Nótese que la existencia de una variable instanciada positiva hv, diimplica también la existencia de una variable instanciada negativa hv, ¬d0ipara el resto de valores en el dominio de la variable, es decir, (∃hv, di ∈ S)⇒(∀d0∈ Dv, d06=d,∃hv, ¬d0i ∈ S). Cada agente iposee una función de utilidad Fipara evaluar la calidad de los planes propuestos. Fiasigna un coste costei(α)∈R+ 0a cada acción α de un plan de acuerdo con la visión de la tarea de PMA que tiene el agente i. Por último, las metas privadas de un agente i,PGi, son variables instanciadas que el agente iestá interesado en conseguir. Las metas privadas se codifican como restricciones débiles [GL06], dado que no es obligatorio que los agentes las consigan. 18 CAPÍTULO 3. MODELO DE PLANIFICACIÓN MULTI-AGENTE 3.2 Planificación basada en refinamientos Nuestro modelo de PMA es un enfoque de planificación basada en refinamientos, un método consistente en el refinamiento del conjunto de posibles planes [Kam97]. Un agente propone un plan Πque típicamente resuelve un conjunto de metas abiertas; a continuación, el resto de agentes cooperan para refinar Π, resolviendo algunas de sus metas abiertas. De este modo, los agentes resuelven cooperativamente la tarea de PMA mediante consecutivos refinamientos de un plan inicialmente vacío. En este contexto, la Planificación de Orden Parcial (POP) [BW94] aparece como un enfoque adecuado para plantear la planificación basada en refinamientos, dado que este paradigma está orientado a resolver las metas abiertas de forma progresiva. De este modo, los agentes en nuestro modelo planifican mediante la adopción del paradigma POP. A continuación, se proporcionan las definiciones básicas de POP y su adaptación al contexto de PMA. 3.2.1 Planificación de Orden Parcial centralizada Definición 4. (Plan de orden parcial) Un plan de orden parcial o plan parcial es una tupla Π = h∆,OR,CLi.∆⊆ A es el conjunto de acciones en Π.OR es un conjunto de restricciones de orden (≺) en ∆. CL es un conjunto de enlaces causales sobre ∆. Un enlace causal toma la forma αhv,di →βo bien αhv,¬di →β, donde α∈ A yβ∈ A son acciones en ∆.αhv,di →βindica que hay una operación (v=d)tal que v∈ V,d∈ Dv, (v=d)∈EFF(α)y una variable instanciada hv, di ∈ PRE(β).αhv,¬di →β indica que hay una variable instanciada hv, ¬dital que v∈ V,d∈ Dv, hv, ¬di ∈ PRE(β)soportada por una operación (v6=d)∈EFF(α)o una operación (v=d0)∈EFF(α),d0∈ Dv,d06=d. Esta definición de plan parcial muestra que un plan puede verse como un grafo dirigido acíclico, donde ∆representa los nodos del grafo(acciones) y OR yCL son conjuntos de aristas dirigidas que representan las precedencias y enlaces causales entre acciones, respectivamente. Un plan parcial vacío se define como Π0=h∆0,OR0,CL0i, donde ∆0 contiene α0yαf, las acciones inicial y final del plan, respectivamente. α0 yαfson acciones ficticias que no pertenecen al conjunto de acciones de ningún agente. OR0contiene la restricción de orden α0≺αfyCL0es un conjunto vacío. De este modo, un plan Πpara una tarea de PMA T contendrá siempre las dos acciones ficticias, de modo que PRE(α0) = ∅, EFF(α0) = I,PRE(αf) = G, y EFF(αf) = ∅; es decir, α0representa la CAPÍTULO 3. MODELO DE PLANIFICACIÓN MULTI-AGENTE 19 situación inicial de la tarea de PMA T, y αfrepresenta las metas globales de T. Asumiendo que G 6=∅, un plan vacío es incompleto si las precondiciones de αfno están soportadas aún por un enlace causal. El proceso de búsqueda POP se centra en introducir enlaces causales para soportar estas precondiciones, también llamadas metas abiertas. Definición 5. (Meta abierta) Una meta abierta en un plan parcial Π = h∆,OR,CLi es una variable instanciada og de la forma hv, dio bien hv, ¬di, tal que v∈ V,d∈ Dv,og ∈PRE(β),β∈∆, y @α∈∆/α og →β∈ CL. metasAbiertas(Π) denota el conjunto de metas abiertas en Π. Un plan es incompleto si tiene metas abiertas. En caso contrario, se trata de un plan completo. A medida que el proceso de búsqueda POP progresa, los enlaces causales en un plan de orden parcial pueden quedar desprotegidos como resultado de la introducción de una nueva acción que no está ordenada con respecto al enlace causal. Estos conflictos son conocidos como amenazas. Definición 6. (Amenazas) Una amenaza en un plan parcial Π = h∆,OR, CLi representa un conflicto entre una acción del plan y un enlace causal. Una acción γcausa una amenaza sobre un enlace causal αhv,di →βsi ((v=d0)∈ EFF(γ)∨(v6=d)∈EFF(γ)), donde v∈ V,d∈ Dv,d0∈ Dvyd6=d0, y no existe una restricción de orden γ≺αoβ≺γ. La acción γcausará una amenaza sobre un enlace causal de la forma αhv,¬di →βsi (v=d)∈EFF(γ), donde v∈ V,d∈ Dv, y no existe una restricción de orden γ≺αoβ≺γ. Threats(Π) denota el conjunto de amenazas en Π. Una amenaza t∈Threats(Π) se puede resolver promocionando odemocionando la acción amenazante γcon respecto al enlace causal amenazado αhv,di →βoαhv,¬di →β, esto es, introduciendo una restricción de orden γ≺αo β≺γ. 3.2.2 Planificación de Orden Parcial distribuida Los agentes en nuestro modelo de PMA cooperan para refinar un plan base Πinicialmente vacío proponiendo una serie de pasos de refinamiento que resuelven algunas de las metas abiertas en Π. Definición 7. (Paso de refinamiento) Un paso de refinamiento Πidesarrollado por un agente isobre un plan base Πg, donde g∈metasAbiertas(Πg), es una tripla Πi=h∆i, ORi, CLii, donde ∆i⊆ A es un conjunto de acciones 26 CAPÍTULO 4. DISEÑO DEL SISTEMA DE PMA <predicates -def > ::= (or <atom -form -def > <atom -form -def >+) <atom -form -def > ::= (< predicate > <typed - list ( element ) >) <atom -form -def > ::= (= <object -fluent -def > <object >) <predicate > ::= <name > <object -fluent -def > ::= (<name > <object >*) <object > ::= <name > <element > ::= <variable > | <constant > <variable > ::= ?<name > <constant > ::= <name > <typed -list(x)> ::= x* Como muestra la sintaxis BNF, ambos conjuntos de metas globales y privadas pueden describirse mediante conjunción o disyunción de predicados o variables instanciadas. 4.1.3 Multi-funciones Como se ha visto en la sección 3, nuestro modelo permite la representación explícita de información postiva y negativa, lo que dificulta el proceso de codificación, dao que se incrementa el volumen de datos a codificar. Para simplificar este proceso, se ha añadido una estructura multi-functions que permite codificar parte de la información del problema mediante una notación más compacta y simplificada. Las multi-funciones se declaran en el fichero de dominio, dentro de la sección :multi-functions. Dicha sección sigue la sintaxis BNF que se muestra a continuación: <multi -func -sec -def > ::= (: multi - functions <multi -func -def >) <multi -func -def > ::= (<name > <typed - list (typed -v)>) <type > <typed -v> ::= <variable > - <type > <type > ::= <name > <type > ::= ( either <name > <name >+) <variable > ::= ?<name > <typed -list(x)> ::= x* En la sección :init del fichero de problema se emplean las multi-funciones para definir información concreta del estado inicial. La especificación de multi-funciones en la sección :init utiliza la siguiente sintaxis BNF: <multi -func -def > ::= (= <multi -func > <value -def >) <multi - func > ::= (<name > <typed - list (inst -v ) >*) <inst -v >+ <inst -v> ::= <name > <variable > ::= ?<name > <typed -list(x)> ::= x* ALGORITMO DE PLANIFICACIÓN DISTRIBUIDO 27 4.2 Algoritmo de planificación distribuido Esta sección detalla el algoritmo de planificación cooperativa basada en refinamientos que se ha diseñado. Los agentes siguen un protocolo que combina planificación y coordinación. Uno de los agentes lidera el proceso de selección del siguiente plan base a partir de los planes refinamiento generados por el grupo de agentes. El algoritmo de planificación se divide en las siguientes fases: •Intercambio inicial de información: En esta fase inicial, los agentes intercambian información de planificación para generar estructuras de datos que serán de utilidad en las siguientes fases del proceso. •Proceso de planificación basada en refinamientos: Este proceso combinan dos fases, una fase de planificación individual en la cual los agentes refinan un plan base centralizado, y un proceso de coordinación en el que los agentes intercambian sus propuestas y escogen el siguiente plan base: – Proceso de refinamiento individual: Cada agente tiene un planificador POP embebido con el que refinan de forma individual el plan base actual. El algoritmo POP clásico se ha adaptado al contexto de PMA, tal como se describe en la sección 3.2.2. – Proceso de coordinación: Los agentes intercambian los nuevos planes refinamiento desarrollados sobre el plan base actual y seleccionan el refinamiento más prometedor como el nuevo plan base. 4.2.1 Intercambio inicial de información Antes de comenzar el proceso de planificación, los agentes llevan a cabo una fase preliminar para intercambiar la información pública de planificación. Esta fase inicial se centra en la construcción de un grafo de planificación relajado distribuido (dis-RPG) basado en el trabajo de [ZNK07]. El disRPG proporciona a los agentes información de planificación valiosa para el resto del proceso: •Los agentes intercambian la información definida como compartible en la sección :shared-data de los ficheros de definición. Cada variable instanciada se etiqueta con la lista de agentes que pueden conseguirla, lo que proporciona a cada agente una visión de las posibles interacciones que pueden surgir con el resto de agentes en tiempo de planificación. 28 CAPÍTULO 4. DISEÑO DEL SISTEMA DE PMA •Se calcula una estimación del mejor coste para conseguir cada variable instanciada. Esta información es útil para definir heurísticas que guíen el proceso de planificación. Algoritmo 2 Construcción del dis-RPG para un agente i Construir RPGiinicial repetir ∀j6=i,ienvía a jlas nuevas variables instanciadas SFi→j∈RPGide la forma hv, dio bien hv, ¬di, donde v∈ Vi∩ Vjyd∈ Di v∩ Dj v ∀j6=i,irecibe de jlas nuevas variables instanciadas SF j→i∈RPGj de la forma hv, dio bien hv, ¬di, donde v∈ Vi∩ Vjyd∈ Di v∩ Dj v RFi← ∅ ∀j6=i, RFi←RFi∪SFj→i para todo variable instanciada recibida f∈RFihacer si f6∈ RPGientonces Insertar fen RPGi costeRP Gi(f)←coste(f) fin si si (f∈RPGi)∧(costeRP Gi(f)> coste(f)) entonces costeRP Gi(f)←coste(f) fin si fin para Expandir RPGi hasta que RFi=∅ Nótese que ninguno de los agentes maneja una representación completa del dis-RPG. Por el contrario, cada agente mantiene un grafo de planificación distinto internamente, de modo que su información privada no se revela al resto de agentes. El algoritmo 2 resume el proceso de construcción del dis-RPG. En primer lugar, cada agente construye un grafo de planificación inicial teniendo en cuenta únicamente sus propias acciones y variables instanciadas. Para la construcción de este grafo inicial se ha seguido el algoritmo descrito en [HN01]. El grafo de planificación contiene un conjunto de niveles de acciones y variables instanciadas intercalados. El primer nivel de variables instanciadas contiene las variables instanciadas que forman parte del estado inicial, y el primer nivel de acciones contiene todas aquellas acciones aplicables en el estado inicial (acciones cuyas precondiciones figuran en el estado inicial). Los efectos de estas acciones se sitúan en el segundo nivel de variables instan- ALGORITMO DE PLANIFICACIÓN DISTRIBUIDO 29 ciadas, y de este modo el grafo se expande hasta que no aparecen nuevas variables instanciadas. Una vez todos los agentes han construido el grafo inicial, el proceso de composición del dis-RPG se inicia. Este proceso constructivo consta de las siguientes etapas: •Intercambio de variables instanciadas. Los agentes intercambian las variables instanciadas incluidas en sus grafos de planificación de acuerdo a lo especificado en la sección shared-data de sus ficheros de definición. De este modo, dos agentes iyjintercambiarán solo variables instanciadas de la forma hv, dio bien hv, ¬di, donde v∈ Vi∩ Vjyd∈ Di v∩ Dj v. •Expansión del grafo de planificación. Cada agente iactualiza su grafo RPGicon las nuevas variables instanciadas recibidas. Si una variable instanciada fno está aún en RPGi, se almacena de acuerdo a coste(f). Si festá ya en RPGi, su coste se actualiza si costeRP Gi(f)> coste(f). De este modo, los agentes sólo almacenan el mejor coste estimado para conseguir cada variable instanciada. Una vez actualizado RPGi, el agente ilo expande comprobando si las nuevas variables instanciadas añadidas provocan la aparición de nuevas acciones en RPGi. Las nuevas variables instanciadas producidas como efectos de estas nuevas acciones serán intercambiadas en la siguiente etapa de intercambio de variables. 4.2.2 Proceso de planificación distribuido Tras el intercambio inicial de información, los agentes inicial el proceso de planificación distribuido (ver algoritmo 3). El proceso comprende dos fases intercaladas: un proceso de refinamiento individual y una fase de coordinación. En la primera fase, los agentes construyen individualmente refinamientos sobre un plan base centralizado utilizando el POP que tienen integrado. En la segunda fase, los agentes siguen un proceso de coordinación mediante el que intercambian los refinamientos obtenidos y seleccionan el más prometedor como el siguiente plan base. 4.2.2.1 Fase de refinamiento individual Cada agente participante ejecuta un proceso POP individualmente para refinar el plan base actual Π, de modo que se obtiene un conjunto de refinamientos válidos sobre Π. De acuerdo a nuestra definición de plan refinamiento (ver sección 3.2.2), un plan refinamiento Πide un agente isobre un plan 30 CAPÍTULO 4. DISEÑO DEL SISTEMA DE PMA Algoritmo 3 Proceso de planificación distribuido para un agente i Π←Π0 R=∅ repetir Seleccionar meta abierta g∈metasAbiertas(Π) Refinar plan base Πgindividualmente ∀j6=i, enviar Refinamientosi(Πg)al agente j ∀j6=i, recibir Refinamientosj(Πg) Refinamientos(Πg)←Refinamientosi(Πg) ∀j6=i,Refinamientos(Πg)← Refinamientos(Πg)∪Refinamientosj(Πg) Evaluar Refinamientos(Πg) R←R∪Refinamientos(Πg) Seleccionar mejor plan Πi∈R Π←Πi si metasAbiertas(Π) = ∅entonces devolver Π fin si hasta que R=∅ base Πresolverá una de sus metas abiertas g∈metasAbiertas(Π), además de todas las metas abiertas privadas gide la forma hv, dio bien hv, ¬dique surjan de dicha resolución, donde v∈ Vi∧d∈ Di v∧((∀j6=i, v 6∈ Vj)∨(∀j6= i, d 6∈ Dj v)) ∧(gi6∈ metasAbiertas(Π)). 4.2.2.2 Proceso de coordinación El proceso de coordinación está basado en un liderazgo democrático, por el cual, un testigo, que designa al agente líder, es intercambiado entre los agentes siguiendo una estrategia round-robin. El algoritmo intercala la fase de coordinación con el refinamiento individual de planes. Cada iteración de la fase de coordinación es liderada por el agente que tiene el testigo en ese momento (agente líder). Una vez la fase de coordinación termina, el agente líder pasa el testigo al siguiente agente, que pasa a liderar la siguiente iteración. En primer lugar, los agentes intercambian los planes refinamiento que han desarrollado para proceder a su evaluación. Dicha evaluación se realiza mediante una función heurística que puntúa la calidad del plan (ver sección 4.3). Así, el agente líder selecciona el plan refinamiento con mejor puntuación. El plan seleccionado pasa a ser adoptado por los agentes como el nuevo PLANIFICADOR DE ORDEN PARCIAL 31 plan base Π. Si metasAbiertas(Π) = ∅, se devuelve el plan solución y el proceso termina. Dado que algunas de las metas abiertas pueden no ser visibles para algunos agentes, todos deben confirmar que Πes un plan solución de acuerdo con su visión de Π. Si el plan no es solución, el agente líder selecciona la siguiente meta a resolver g∈metasAbiertas(Π), lo que da comienzo a una nueva iteración del proceso de refinamiento individual. El algoritmo de planificación puede verse como una exploración conjunta del espacio de refinamientos llevada a cabo por los agentes. Los nodos del árbol de búsqueda representan los planes refinamiento y cada iteración del algoritmo expande un nodo diferente. 4.3 Planificador de Orden Parcial Como se ha mencionado anteriormente, el elemento clave de nuestro sistema de planificación distribuido es el sistema POP integrado en todos los agentes. Se han introducido algunos cambios y extensiones al algoritmo clásico POP en el diseño de este componente para extenderlo a un contexto de PMA. Las siguientes secciones analizan estas extensiones, y describen las heurísticas de planificación desarrolladas para guiar el proceso de búsqueda POP. 4.3.1 Extensiones del POP Nuestro modelo de PMA, construido a partir del método de planificación basada en refinamientos, introduce una serie de nuevos requisitos que fuerzan la introducción de una serie de cambios en el algoritmo clásico de POP. Hemos diseñado una versión modificada del algoritmo clásico de POP que satisface estos requisitos. Los cambios más relevantes introducidos en el algoritmo pueden resumirse como sigue: 1. Plan inicial: El algoritmo POP clásico comienza con un plan vacío. Nuestro diseño permite escoger cualquier plan como plan inicial. De este modo, los agentes pueden comenzar a buscar refinamientos tomando un plan base cualquiera como plan inicial del proceso POP. 2. Resolución de metas abiertas. El POP diseñado resuelve únicamente la meta abierta seleccionada por los agentes como meta actual. El resto de metas abiertas en el plan inicial son ignoradas. Una vez la meta abierta inicial es resuelta, el planificador tratará de resolver en cascada todas las metas abiertas surgidas de esa primera resolución y que sólo puedan ser resueltas por el agente que está llevando a 32 CAPÍTULO 4. DISEÑO DEL SISTEMA DE PMA cabo el proceso de búsqueda (nótese que el dis-RPG proporciona esta información). 3. Comprobación de solución. Los sistemas POP clásicos devuelven únicamente planes solución, es decir, planes libres de amenazas y de metas abiertas. Nuestro sistema de planificación devuelve refinamientos, por lo que hemos redefinido la fase de comprobación de solución del algoritmo POP. Para que un plan sea devuelto por el POP como un plan refinamiento válido, debe cumplir las siguientes condiciones: •Debe estar libre de amenazas. •Debe incluir un enlace causal que soporte la meta abierta actual. •Si el plan ha añadido nuevas metas abiertas a consecuencia de la resolución de la meta actual, todas aquellas que sólo sean resolubles por el agente actual deben estar resueltas. 4. Relanzamiento del proceso de planificación. Habitualmente, el proceso POP termina una vez se ha encontrado un plan solución. Sin embargo, el POP diseñado permite relanzar el proceso una vez se ha hallado un plan refinamiento para obtener más refinamientos del plan base. 4.3.2 Funciones heurísticas Nuestro POP aplica un enfoque de búsqueda informada, es decir, selecciona el siguiente plan parcial a refinar de acuerdo a una función heurística [RN03], que estima la calidad del plan. El valor heurístico para un plan parcial dado Πse expresa como f(Π) = g(Π) + h(Π), donde g(Π) representa el coste de alcanzar el plan actual desde el plan inicial, y h(Π) estima el coste de alcanzar un plan solución desde Π. La eficiencia del proceso de búsqueda está íntimamente relacionada a la calidad de la función heurística. Una de las limitaciones del paradigma POP, como se describe en la sección 2.3, estriba en la ausencia de heurísticas competitivas. Por ello, hemos tomado en consideración los intentos más recientes para definir una heurística competitiva para POP [NK01]. En concreto, se han adaptado dos heurísticas recientes (en adelante las heurísticas SUM y MAX), que estiman la calidad del plan en base a la información disponible en un grafo de planificación relajado, como es el caso de nuestro dis-RPG. Como trabajo en progreso, se está desarrollando en paralelo una tercera heurística para estimar la calidad de los planes parciales (ver capítulo 6). PLANIFICADOR DE ORDEN PARCIAL 33 La heurística SUM estima el coste de alcanzar una solución desde un plan dado calculando la suma de los costes de las metas abiertas del plan en el grafo de planificación relajado. Aunque no es una heurística admisibe (puede sobrestimar el coste de alcanzar una solución), esta heurística consigue buenos resultados, por lo que se ha utilizado en las pruebas experimentales desarrolladas (ver sección 5.3). La función heurística SUM, f(Π) = g(Π) + h(Π), se calcula como sigue: •g(Π) es el número de acciones del plan refinamiento actual Π(exceptuando las acciones ficticias). •h(Π) se define como la suma de los costes de las precondiciones abiertas del plan actual OC(Π) en el grafo de planificación relajado. La heurística MAX, por su parte, evalúa el plan actual considerando también los costes de las metas abiertas del plan. Sin embargo, para reducir al máximo la sobrestimación, se computa dicha estimación como el coste de la precondición más costosa en el grafo relajado. Por tanto, la función heurística MAX, f(Π) = g(Π) + h(Π), se calcula como sigue: •g(Π) es el número de acciones del plan refinamiento actual Π(exceptuando las acciones ficticias). •h(Π) se define como el coste en el grafo de planificación relajado de la precondición pmás costosa del plan, p∈ OC(Π). 34 CAPÍTULO 4. DISEÑO DEL SISTEMA DE PMA Capítulo 5 Implementación del sistema de planificación distribuido Este capítulo analiza el proceso de implementación del sistema de planificación distribuido llevado a cabo y sus principales componentes, así como las tecnologías empleadas para su desarrollo. Además, se muestran los resultados experimentales obtenidos en las pruebas realizadas. El capítulo se estructura como sigue: la sección 5.1 analiza la implementación desarrollada e introduce los principales módulos del sistema; la sección 5.2 documenta las fases de que ha constado el desarrollo del proyecto; y por último, la sección 5.3 muestra los resultados experimentales obtenidos. 5.1 Análisis de la implementación Nuestro sistema de planificación distribuido, desarrollado en el lenguaje Java [Gos00], se estructura en cinco módulos diferentes: el agente de planificación, la interfaz gráfica de usuario, el analizador, el instanciador y el planificador. Los diferentes módulos han sido desarrollados como bundles, siguiendo el estándar OSGi [All03], de modo que cada módulo se subdivide en dos paquetes Java: un paquete común, que proporciona una interfaz bien definida para utilizar el módulo sin entrar en detalles de implementación, y un paquete de servicio, que incluye la implementación completa del módulo. El uso de la tecnología OSGi permite que cada uno de los módulos pueda utilizarse independientemente del resto en futuros proyectos, lo que facilita la reutilización del código implementado. La figura 5.1 muestra el diagrama de clases del paquete común correspondiente al planificador. Se puede observar en la figura que todas las clases de los paquetes comunes son en realidad interfaces Java, lo que permite al 35 42 CAPÍTULO 5. IMPLEMENTACIÓN DEL SISTEMA DE PMA camión deben estar situados en la misma ciudad dentro del área del agente. •descargar: Descarga un paquete de un camión situado en una ciudad dentro del área del agente. •conducir: Conduce un camión de una ciudad a otra. Ambas ciudades deben estar localizadas dentro del área del agente. El dominio del almacén es similar al dominio clásico del mundo de bloques, donde los paquetes pueden ser apilados o desapilados de una mesa o de otros paquetes. En este caso, la mesa tiene espacio para una única pila de paquetes, y hay dos tipos de paquetes, materias primas y productos terminados. El agente almacén puede entregar productos terminados en la ciudad adyacente al almacén (la ciudad de intercambio), y almacenar materias primas procedentes de los camiones. Los almacenes pueden realizar las siguientes acciones: •obtener: Obtiene una materia-prima de la ciudad-de-intercambio. •entregar: Entrga un producto-terminado en la ciudad-de-intercambio. •apilar: Apila un paquete sobre otro paquete, o lo deja encima de la mesa, si esta está libre. •desapilar: Desapila un paquete de otro paquete, o lo levanta de la mesa, si no tenía nada debajo. 5.3.1.2 Dominio del cuadro Este dominio, adaptado del caso de estudio presentado en [PSJ98], describe una situación en la que un conjunto de trabajadores debe colgar una serie de cuadros en muros, para lo cual deben recoger una serie de herramientas distribuidas por diferentes habitaciones. Por tanto, los agentes deben moverse a través de las habitaciones para recoger las herramientas y colgar los cuadros. El dominio establece una serie de enlaces bidireccionales que indican las conexiones entre habitaciones. La figura 5.7 muestra un ejemplo de este dominio de PMA. A diferencia del dominio de transporte, los agentes en el dominio del cuadro no están especializados, es decir, todos comparten las mismas capacidades, que pueden describirse como sigue: •recoger: Obtiene una herramienta de una habitación. El agente y la herramienta deben estar situados en la misma habitación. RESULTADOS EXPERIMENTALES 43 Figura 5.7: Ejemplo de tarea del cuadro •dejar: Deja una herramienta herramienta en una habitación. El agente debe tener la herramienta para poder dejarla. •pasar: Pasa la herramienta a otro agente. Ambos agentes deben estar en la misma habitación, y el primer agente debe llevar la herramienta para poder pasársela al segundo. •caminar: Camina de una habitación a otra. Ambas habitaciones deben estar enlazadas para que el agente pueda caminar de una a otra. •colgar: Cuelga un cuadro en una habitación con una herramienta. Tanto el agente como el cuadro deben estar en la misma habitación, y el agente debe llevar la herramienta herramienta para poder colgar el cuadro. 5.3.2 Pruebas y resultados Los siguientes apartados muestran los resultados experimentales obtenidos. Hemos llevado a cabo dos pruebas diferentes1. La primera prueba compara la calidad de los planes solución obtenidos mediante planificación centralizada (con un sólo agente) y mediante nuestro planificador distribuido (con varios 1Todas las pruebas se han realizado en una única máquina con un procesador Intel Core 2 Quad a 2.83 GHz y 8 GB de memoria RAM. 44 CAPÍTULO 5. IMPLEMENTACIÓN DEL SISTEMA DE PMA Figura 5.8: Plan solución para la tarea distribuida Cuadro2 agentes trabajando conjuntamente). Para ello, se ha definido un conjunto de tareas de PMA y una versión centralizada equivalente. Por último, hemos realizado una prueba adicional para medir la escalabilidad y la robustez de nuestro sistema de planificación distribuido. El experimento consiste en lanzar varias veces la misma tarea de PMA, añadiendo un agente más en cada ejecución, de modo que podamos estudiar el impacto en el tiempo de ejecución y los mensajes intercambiados que supone la adición de un agente a la tarea. 5.3.2.1 Planificación distribuida contra planificación centralizada Este primer conjunto de pruebas compara la calidad de los planes solución obtenidos mediante nuestro planificador distribuido con otros generados por un sólo agente planificando de forma centralizada. El conjunto de pruebas contiene 20 tareas, 10 por cada dominio de PMA, de dificultad creciente. Como se ha indicado en la sección 5.3.1, los agentes en las tareas de transporte están especializados, mientras que en el dominio del cuadro todos comparten las mismas habilidades. Esto provoca que los agentes de transporte se vean obligados a colaborar unos con otros para resolver las tareas, mientras que cualquier obrero en el dominio del cuadro puede resolver la tarea completa por sí mismo. La tabla 5.1 muestra los resultados obtenidos. #Ag indica el número de agentes que lleva a cabo la tarea de PMA en las pruebas distribuidas. #Acciones y #PT se refieren al número de acciones y pasos de tiempo del plan solución, respectivamente (nótese que no contamos las acciones ficticias de los planes). Por último, Paralelismo indica el número máximo de ramas en paralelo en los planes solución. Los pasos de tiempo son las unidades de tiempo necesarias para ejecutar el plan, es decir, hacen referencia a la duración del plan. Por ejemplo, la figura 5.8 muestra el plan solución para la tarea de PMA Cuadro2. Aunque el plan tiene 12 acciones (sin tener en cuenta las ficticias), puede ser ejecutado en RESULTADOS EXPERIMENTALES 45 Problema Pl. distribuida Pl. centralizada #Ag #Acciones #PT Paralelismo #Acciones #PT Transporte1 2 14 11 2 14 11 Transporte2 2 11 9 2 11 9 Transporte3 3 9 5 2 9 5 Transporte4 3 11 6 2 11 6 Transporte5 4 13 6 3 13 6 Transporte6 4 11 5 3 11 5 Transporte7 5 10 8 2 10 8 Transporte8 5 15 9 3 15 9 Transporte9 6 11 5 3 11 5 Transporte10 6 17 10 3 17 10 Cuadro1 2 11 6 2 14 14 Cuadro2 2 12 8 2 11 11 Cuadro3 3 6 2 3 8 8 Cuadro4 3 11 7 2 11 11 Cuadro5 4 8 2 4 11 11 Cuadro6 4 10 6 2 10 10 Cuadro7 5 8 5 2 8 8 Cuadro8 5 10 2 5 14 14 Cuadro9 6 9 5 2 9 9 Cuadro10 6 12 2 6 17 17 Tabla 5.1: Comparación entre planificación centralizada y distribuida 46 CAPÍTULO 5. IMPLEMENTACIÓN DEL SISTEMA DE PMA sólo ocho pasos de tiempo, dado que la mayoría de sus acciones se ejecutan en dos ramas paralelas. Por tanto, la duración del plan de la figura 5.8 es de 8 unidades de tiempo. Como puede observarse en la tabla 5.1 la aproximación distribuida obtiene los mismos resultados en términos del número de acciones y pasos de tiempo en las pruebas de transporte. Aunque los agentes participantes en las pruebas distribuidas tienen una visión parcial del dominio y diferentes capacidades, el sistema de planificación distribuido es capaz de obtener planes de la misma calidad que un sistema centralizado. Por tanto, la calidad de los planes obtenidos por nuestro planificador distribuido no se ve afectada por la visión limitada del dominio que tiene cada agente ni por la existencia de información privada. Los resultados del dominio del cuadro presentan más diferencias entre las dos aproximaciones. El planificador centralizado genera soluciones completamente lineales, dado que el único agente planificador es también el único agente ejecutor del plan. Sin embargo, el planificador distribuido toma ventaja del hecho de disponer de varios agentes de planificación y ejecución cooperando, por lo que se consiguen planes en los que los agentes trabajan colectivamente, alcanzando distintos objetivos en paralelo o bien colaborando para resolver un mismo objetivo. Por ejemplo, la figura 5.8 muestra a un agente recogiendo una herramienta y pasándola a otro agente, de modo que cada uno de ellos puede colgar un cuadro en paralelo. Este paralelismo, como se aprecia en la tabla 5.1, permite reducir el número de acciones del plan y la duración del mismo. En conclusión, aunque el planificador distribuido es un enfoque más costoso en cuanto a tiempo de ejecución (véase la siguiente sección para un análisis de escalabilidad), consigue planes solución de igual o mejor calidad en términos de acciones y duración. El enfoque distribuido promueve la colaboración entre agentes y es efectivo paralelizando acciones, lo que reduce la duración de los planes. 5.3.2.2 Análisis de escalabilidad Esta sección muestra las pruebas realizadas para evaluar la escalabilidad de nuestro sistema de planificación distribuido, esto es, cómo afecta el incremento del número de agentes a la eficiencia del sistema. Para ello, se han generado ocho pruebas para los dominios de transporte y del cuadro. Cada prueba incremente el número de agentes en uno, manteniendo el resto de parámetros de la tarea sin modificar. Todas las pruebas de transporte incluyen diez ciudades, un camión, una mesa vacía en el almacén y un paquete de materia prima. Todos los problemas RESULTADOS EXPERIMENTALES 47 Figura 5.9: Resultados de escalabilidad para el dominio de transporte Figura 5.10: Resultados de escalabilidad para el dominio del cuadro incluyen un único agente almacén, y cada problema incrementa el número de agencias de transporte en una. La meta para todas las pruebas es entregar el paquete en el almacén, que debe depositarlo sobre la mesa vacía. La solución óptima para todas las pruebas incluye diez acciones, y obliga a participar en ella al menos a una agencia de transporte y al almacén. Respecto al dominio del cuadro, todos los problemas incluyen dos herramientas y doce habitaciones distintas. El objetivo de todas las tareas es colgar dos cuadros distintos. La solución óptima tiene ocho acciones e involucra a dos agentes distintos, cada uno de los cuales coge una herramienta y cuelga uno de los cuadros. Las figuras 5.9 y 5.10 muestran los resultados para cada dominio. Como se puede observar, el número de mensajes intercambiados experimenta un notable incremento con cada nuevo agente introducido en la tarea. Lo mismo ocurre con el tiempo de ejecución, que está condicionado por el número de mensajes intercambiados por los agentes. Estos resultados se deben al creciente número de planes refinamiento 48 CAPÍTULO 5. IMPLEMENTACIÓN DEL SISTEMA DE PMA propuestos por los agentes. Estos planes son comunicados a todos los agentes, por lo que la adición de un agente sobrecarga el número de mensajes intercambiados. Además, cada nuevo agente puede proponer nuevos refinamientos, y estos refinamientos pueden a su vez ser escogidos como plan base, lo que aumenta la complejidad del árbol de búsqueda. Nótese que el número de mensajes es mucho mayor en las tareas del cuadro, pese a que ambas tareas tienen un tamaño y complejidad similares. Esto se debe a que los agentes del cuadro comparten las mismas habilidades, y por tanto cualquier agente puede proponer un refinamiento para cualquier meta. En el dominio de transporte, sin embargo, los agentes son especializados, lo que provoca que no todos los agentes puedan resolver cualquier meta, reduciéndose de este modo los planes propuestos, y en consecuencia los mensajes intercambiados. En conclusión, el número de agentes en el planificador distribuido que hemos desarrollado tiene una influencia importante en su eficiencia, dado que el número de mensajes intercambiados constituye uno de los cuellos de botella del sistema. Un mayor número de agentes conlleva un mayor número de propuestas de plan, lo que redunda en una mayor complejidad del árbol de búsqueda, que es el otro factor que afecta al rendimiento del sistema de planificación distribuido implementado. Capítulo 6 Conclusiones y trabajo futuro Este último capítulo resume las contribuciones principales presentadas en este trabajo, y resume las futuras líneas de trabajo a desarrollar y lista las publicaciones relacionadas con el presente trabajo. 6.1 Resumen de contribuciones En el presente trabajo se ha descrito el diseño e implementación de un sistema de planificación distribuido basado en un modelo que combina planificación basada en refinamientos y Planificación de Orden parcial (POP). El sistema de planificación distribuido se compone de un grupo de agentes con capacidades de planificación, que generan planes individualmente y se coordinan a través de un protocolo en el cual los agentes desempeñan por turnos el rol de líder del proceso. El algoritmo incluye un intercambio inicial de información por el que los agentes construyen un grafo de planificación relajado distribuido. La fase de resolución de problemas combina la planificación individual de refinamientos con un proceso de coordinación mediante el cual se selecciona el refinamiento más prometedor como el siguiente plan base. El algoritmo POP se ha modificado para tratar con los requisitos adicionales que surgen en un contexto de PMA. Del mismo modo, se ha diseñado un lenguaje de planificación que incluye un conjunto de estructuras para soportar estos requisitos. El sistema de planificación implementado está basado en el lenguaje Java. El desarrollo ha involucrado diferentes tecnologías, como la plataforma Magentix2 [FAS+10] un sistema multi-agente que implementa los protocolos de comunicación FIPA [ON98], y que constituye el componente multi-agente del sistema, que permite a los agentes comunicarse e intercambiar mensajes. El 49 50 CAPÍTULO 6. CONCLUSIONES Y TRABAJO FUTURO componente POP desarrollado presenta una implementación modular, flexible y extendible que permite al usuario integrar nuevas heurísticas y métodos de búsqueda. Todos los componentes del sistema se han construido siguiendo los estándares OSGi [All03], lo que facilita su integración en una plataforma orientada a servicios. Por último, los resultados experimentales muestran que el enfoque distribuido del sistema implementado permite obtener planes de igual o superior calidad que un enfoque de planificación centralizado, tanto en número de acciones como en duración del plan. 6.2 Trabajo futuro El trabajo futuro a realizar sigue dos direcciones distintas: por un lado, proseguiremos con el desarrollo de una nueva heurística para POP que mejore el rendimiento del planificador; y por otro lado, probaremos métodos de coordinación alternativos para mejorar el proceso de selección de plan base. La heurística que está en desarrollo se base en el trabajo de [Hel04], que introduce el formalismo de Grafos de Transición de Dominio (DTGs). Estos grafos dirigidos representan las formas en que una variable de estado puede cambiar su valor de acuerdo a las acciones de planificación. Nuestra heurística en desarrollo utiliza los DTGs para generar una estructura de datos intermedia que aproxima la estructura de un plan solución para la tarea de planificación, el Grafo de Transición de Plan (PTG). El trabajo en esta heurística se enfoca por tanto en mejorar la construcción del PTG, de modo que esté lo más cerca posible de los planes solución, lo que redundará en una mayor calidad de la heurística. El segundo punto a desarrollar como trabajo futuro se centra en la implementación de métodos de coordinación alternativos para mejorar la evaluación y selección de planes refinamiento. En este sentido, se ha desarrollado un modelo de argumentación que permite afrontar la evaluación y selección de planes desde un punto de vista social. Nuestro modelo de argumentación adapta la instanciación de un esquema argumentativo y las cuestiones críticas asociadas siguiendo la representación computacional de argumentación práctica presentada en [ABCM06, ABC07]. Este enfoque es particularmente adecuado para representar planes multiagente concurrentes. Además del modelo de argumentación, el trabajo futuro es probar otros métodos de coordinación entre agentes para reemplazar la actual función heurística ad-hoc, de modo que mejoremos la eficiencia del sistema de planificación distribuido implementado. PUBLICACIONES RELACIONADAS 51 6.3 Publicaciones relacionadas Los siguientes artículos de investigación están directamente relacionados con el presente trabajo, y han sido publicados durante su desarrollo: •O. Sapena, A. Torreño, E. Onaindia. On the Construction of Joint Plans through Argumentation Schemes. 10th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2011). •O. Sapena, E. Onaindia, A. Torreño. On the use of Argumentation in Multi-Agent Planning. 19th European Conference on Artificial Intelligence (ECAI 2010). •E. Onaindia, O. Sapena, A. Torreño. Argumentation-based Planning in multi-agent systems. Negotiation and argumentation in Multiagent Systems. Bentham eBooks. In press (2011). •E. Onaindia, O. Sapena, A. Torreño. Cooperative Distributed Planning through Argumentation. International Journal of Artificial Intelligence. ISSN: 0974-0635. In Press (2010). •A. Torreño, E. Onaindia, O. Sapena. Reaching a common agreement discourse universe on Multi-Agent Planning. 5th International Conference on Hybrid Artificial Intelligence Systems (HAIS 2010). •S. Pajares, E. Onaindia, A. Torreño. An architecture for DefeasibleReasoning-based Cooperative Distributed Planning. 9th International Conference on Cooperative Information Systems (CoopIS 2011). [Sap05] O. Sapena. Planificación Independiente del Dominio en Entornos Dinámicos de Tiempo Restringido. PhD thesis, Universidad Politécnica de Valencia, 2005. [TBdWW02] Hans Tonino, André Bos, Mathijs de Weerdt, and Cees Witteveen. Plan coordination by revision in collective agent based systems. Artificial Intelligence, 142(2):121–145, 2002. [TNP10] Y. Tang, T. Norman, and S. Parsons. A model for integrating dialogue and the execution of joint plans. Argumentation in Multi-Agent Systems, pages 60–78, 2010. [VDKDW05] R. Van Der Krogt and M. De Weerdt. Plan repair as an extension of planning. In Proceedings of the 15th International Conference on Automated Planning and Scheduling, pages 161– 170, 2005. [Wel94] D.S. Weld. An introduction to least commitment planning. AI magazine, 15(4):27, 1994. [Wel99] D.S. Weld. Recent advances in AI planning. AI Magazine, 20(2):93–123, 1999. [Wil88] D.E. Wilkins. Practical Planning: Extending the Classical AI Planning Paradigm. Morgan Kaufmann, 1988. [ZNK07] J.F. Zhang, X.T. Nguyen, and R. Kowalczyk. Graph-based multi-agent replanning algorithm. In Proceedings of the 6th Conference on Autonomous Agents and Multiagent Systems, 2007.