**SVRAI** Coordinación en Sistemas Multiagentes. Aplicaciones a la Robótica. **'En la unión está la fuerza'**. Esta frase tan conocida resume la necesidad de la coordinación y cooperación en sistemas multiagentes. En ciertas tareas, la cooperación y coordinación de individuos resulta en una mayor eficacia a la hora de llevar a cabo un fin común. El objetivo de este trabajo es presentar una revisión comprensiva del aspecto de la coordinación en sistemas multiagentes, definir qué es la coordinación y cómo se puede dividir, estudiar los algoritmos propios de este tema y profundizar en las aplicaciones a la robótica que actualmente se están utilizando en nuestra sociedad. Introducción ============================================================== El problema de la coordinación en sistemas multiagentes (MASs) tiene mucha importancia en el ámbito de la IA y la teoría de juegos. Dado un conjunto de agentes que tienen que llevar a cabo una serie de tareas, pueden existir situaciones en las que la acción óptima de un agente dependa de la acción elegida por otro agente. Si ambos agentes no se ***coordinan*** el resultado final puede ser desastroso. !!!Tip:Ejemplo En una planta de almacenaje, el robot **A** y el robot **B**, dos robots transportadores de cajas se encuentran en un pasillo no lo suficientemente grande para que puedan pasar los dos simultáneamente. Si se desea que ambos robots no se choquen, deberán coordinarse para ver cúal de ellos pasa antes y de ese modo gestionar el espacio que comparten. ![](./img/robotsAB.png align="center " width=80%) Los problemas de coordinación suelen surgir en los MASs totalmente cooperativos, en los que cada agente comparte la misma función de utilidad o intereses comunes. Este tipo de sistema es apropiado para modelar un equipo de agentes que actúan en nombre de un solo individuo (cada uno trata de maximizar la utilidad de ese individuo). En el ejemplo anterior, puede ser que a ninguno de los robots le importe si cruza primero, siempre que ambos crucen y alcancen su objetivo. En este caso, los problemas de coordinación generalmente surgen en situaciones en las que hay cierta flexibilidad de los 'roles' de los agentes. Si ambos agentes tienen las mismas capacidades de manera que da igual que el robot **A** persiga el objetivo $O_1$ y el robot **B** el objetivo $O_2$ o viceversa, los agentes corren el riesgo de que ambos persigan el mismo objetivo, con consecuencias que pueden ir desde un simple retraso en la resolución del objetivo a no llegar a alcanzarlo nunca. Para lidiar con este tipo de problema se utiliza la **coordinación**. Algunos de los campos de estudio en los que se ha profundizado son: * a) El diseño de convenciones o leyes sociales que limitan a los agentes a seleccionar acciones coordinadas. [#DKLewis] * b) La comunicación entre los agentes antes de llevar a cabo la decisión de las acciones. [#GWeiß] * c) El uso de métodos de aprendizaje por los cuáles un agente aprenda a coordinarse con los demás agentes debido a la repetición. [#Fudenberg] # Definición de Coordinación Cuando se indaga en el estudio del término de coordinación, se observa que las definiciones asociadas a este término están enmarcadas en el ámbito de la *Teoría de las Organizaciones*, en la que la coordinación es vista como la gestión de dependencias entre actividades organizativas, [#Malone]. En este ámbito se pueden realizar las siguientes: !!![]Def: Definición: Actividad Una **actividad** es un conjunto de acciones potenciales que un **actor** puede llevar a cabo para conseguir un objetivo o una serie de objetivos. !!![]Def: Definición: Actor Un **actor** puede ser un **agente** o un conjunto de agentes. !!![]Def: Definición: Procedimiento Un conjunto de actividades y la ordenación entre ellas es un **procedimiento**. !!![]Def: Definición: Coordinación En el ámbito de los Sistemas Multiagente, la **coordinación** se refiere a la distribución de tareas a fin de alcanzar los objetivos comunes, [#Dignum]. Tal distribución se consigue cuando los agentes pueden seleccionar las acciones apropiadas, el número de veces adecuado y en una secuencia correcta. En este proceso, se evaluan las acciones propias, y también las de los otros agentes, con la finalidad de asegurar que los actos de todos los agentes resulten coherentes. Esta coherencia implica que las acciones de los agentes puedan realizarse sin generar conflictos entre unos y otras, logrando de esta forma que todos los agentes se comporten como la unidad. Con todo ello, la coordinación de actividades entre los agentes comienza a ser neceseria cuando existen interdependencias entre agentes y actividades. Una coordinación efectiva es esencial si diferentes agentes autónomos quieren alcanzar sus objetivos dentro de un Sistema Multiagente (SMA). Dicha coordinación requiere gestionar las diferentes formas de dependencia que se generan entre los agentes cuándo: * Tienen objetivos inter-relacionados. * Comparten un entorno común. * Hay recursos compartidos. !!![]Def: Cooperación vs Coordinación La coordinación de agentes es la capacidad de gestionar las interdependencias de las actividades entre agentes, mientras que la cooperación de agentes es el proceso utilizado para que un agente entre voluntariamente en relación con otro para lograr un objetivo derivado del sistema. ## Dependencias entre actividades y agentes Detectar los tipos de interrelaciones existentes entre las actividades resulta importante dentro de la temática de la coordinación. Los investigadores generalmente se apoyan en la clasificación de interdependencias dadas por Von Martial, [#VonMartial], basándose en dos categorías principales:   **1. Interrelación negativa o conflictual:** Dadas dos acciones $A_1$ y $A_2$, existe entre ellas una interrelación negativa si no pueden efectuarse simultáneamente. Esta imposibilidad puede deberse a la incompatibilidad de objetivos o metas perseguidas por los agentes involucrados, o a la competencia por el uso de recursos limitados.   **2. Interrelación positiva o sinérgicas:** Dadas dos acciones $A_1$ y $A_2$, existe entre ellas una interrelación positiva si alrealizarlas favorecen la realización de las tareas de otros agentes, tendiendo así a aumentar la eficiencia del sistema por no efectuar las actividades independientemente unas de otras. Dentro de esta categorías se pueden diferenciar:     **a) Interrelaciones positivas de igualdad:** Las acciones $A_1$ y $A_2$ no están vinculadas a agentes específicos y por tanto pueden ser efectuadas por cualquiera de ellos.     **b) Interrelaciones positivas de subsunción:** Cuando la acción $A_1$ de un agente determinado forma parte del conjunto de acciones $B$ de otro agente, de tal manera q ue cuando $B$ es llevado a cabo puede afirmarse que el primer agente al mismo tiempo realizó $A_1$.     **c) Interrelaciones positivas de favor:** Cuando simplemente una acción finalizada favorece la realización de otras acciones. Tal como afirma Ferber [#Ferber], coordinar implica articular las acciones individuales realizadas por cada agente a fin de lograr un sistema con operación de alto rendimiento. En otras palabras, analizar las interdependencias permite identificar ciertas acciones particularmente sensibles para el objetivo que se persigue en el sistema, ya sea porque sus ejecuciones simultáneas generan conflictos o porque favorecen a niveles de rendimiento individuales y globales. ## ¿Por qué es importante coordinar? Antes de seguir introduciendo algunos conceptos básicos sobre este tema y ver cuáles son los tipos de coordinación además de los algoritmos propios. Es importante analizar la utilidad y la importancia de coordinar las acciones de los agentes en los sistemas multiagentes. Algunas de ellas son: * Por la naturaleza de algunos problemas, los agentes individualmente no tienen la capacidad de resolver el problema completo y necesitan de los resultados que únicamente otros agentes pueden facilitar. * Existe la necesida de satisfacer restricciones globales para que la solución alcanzada sea exitosa. * En algunos problemas, pueden existir interdependencias negativas y/o positivas entre las acciones a realizarse. * Los recursos son limitados por lo que los agentes deben optimizar sus utilizaciones, para evitar conflictos por su uso. * Existen situaciones en las que una información descubierta por un agente facilita la tarea que debe realizar otro agente. Por lo que juntos resuelven el problema más rápido. * Para evitar que los agentes áctuen de mánera egoísta y tengan objetivos globales o de conjunto. Sin coordinación entre los agentes, los beneficios de la resolución descentralizada de problemas pueden llegar a desaparecer. ## Tipos de Coordinación La coordinación de uno o mas gentes puede clasificación en función de diferentes factores. Algunos de ellos son el modo en que se asignen las tareas o tomen las decisiones y el nivel de comunicación que exista entre los agentes. Si clasificamos la coordinación en función del modo de comunicación entre los agentes, tenemos: **1. Coordinación Explícita:** Los agentes comparten información acerca de las acciones, roles, y asignaciones de tareas entre ellos. **2. Coordinación Implícita:** No existe comunicación directa entre los agentes para llevar a cabo la coordinación. En el caso en se clasificara la coordinación en función de quién asigna las tareas, tendríamos: **1. Coordinación Centralizada:** Las asignación de tareas y las decisiones se realizan por un agente central, el cuál conoce gran parte de la información de los agentes y del entorno, a partir de lo que asignará tareas del modo más óptimas posible. **2. Coordinación Descentralizada:** Los agentes tomarán las decisiones por sí mismos, o en función de estimulos o del resultado de la comunicación entre los agentes. Cabe destacar que éstas clasificaciones no son excluyentes, es decir, se podría dar un tipo de coordinación descentralizada que además sea implicita o explicita. Es por ello que éstas clasificaciones pueden ser complementarias entre sí. # Coordinación Explícita La coordinación basada en la comunicación explícita requiere que los agentes se comuniquen sobre las tareas, las asignaciones de tareas y, potencialmente, sobre las motivaciones para aceptar o rechazar las asignaciones de tareas. En un principio este tipo de coordinación estaba pensada para enfoques de intenciones conjuntas, sin embargo, Wooldridge and Jennings [#Jennings] desarrollaron un abanico de algoritmos de coordinación que involucraba la comunicación explícita. Ellos dividieron el proceso de **Resolución Cooperativa de Problemas o (CPS)** en 4 pasos: **1. Reconocimiento del problema:** El proceso CPS empieza cuando algún actor identifica un problema en el que la cooperación es necesaria. Esta identifiación puede ser provocada porque el agente no puede llevar a cabo la tarea solo, o por que es más eficaz si la realiza con ayuda de otros agentes. **2. Formación de equipo:** Durante esta etapa, el agente que ha reconocido el problema en la etapa 1 solicita ayuda. Si esta etapa se logra satisfactoriamente, acabará con un grupo de agentes que tienen un objetivo común. **3. Formación del plan:** Durante esta etapa, los agentes intentan negociar un plan común para intentar llevar a cabo el objetivo. **4. Ejecución del plan:** Durante esta etapa, el plan es ejecutado por los agentes, que mantienen una estrecha relación definidica por una convención social que todos los agentes siguen. La mayoría de los problemas de coordinación siguen estas etapas que pueden simplificarse si sólo existe un objetivo para todos los agentes, o si sólo existen 2 agentes. ## Intenciones Conjuntas Las intenciones conjuntas como medio para modelar la coordinación sustentan gran parte de los trabajos sobre coordinación multiagente. El termino 'intención' fue acuñado por John Searle [#Searle], y se define por un estado mental que puede ser considerado como un compromiso de actuar para lograr un determinado estado de las cosas. Estas intenciones pueden ser: * **Realistas:** El agente debe creer que el estado de cosas que desea es alcanzable o, al menos, no ser consciente de que es ciertamente inalcanzable. * **Temporalmente estables:** Las intenciones deben ser persistentes en algún sentido. Sin embargo, no deben ser completamente inflexibles. El primero asegura que las intenciones deben traducirse en acciones en algún momento y el segundo sugiere que corresponden a objetivos a medio y largo plazo que, aunque pueden cambiar si se dispone de nueva información, por ejemplo, pueden servir para orientar las acciones de los agentes. Las intenciones conjuntas extienden la idea de una sola intención de un agente a un estado mental compartido entre dos o más agentes, los cuales que tienen la misma intención. Las teorias basadas en intenciones conjuntas remarcan que: * Los objetivos conjuntos son necesarios para la actuación conjunta. * Todos los agentes en el grupo deben acordar que deben cooperar para conseguir el objetivo conjunto. Jennings [#Jennings2] ademas introduce el término de responsabilidad de intención, la cual remarca que los agentes están comprometidos a: * Un objetivo común. * Un plan para conseguir ese objetivo común. Se considera que el efecto de la invalidación del plan es diferente al de la invalidación del objetivo común. En el primer caso, el objetivo común permanece y los agentes pueden buscar otro plan. En el segundo caso, toda la acción conjunta se abandona. Las intenciones conjuntas se han convertido, por tanto, en una de las herramientas más útiles para describir la actividad coordinada de los agentes. Entre las críticas más conocidas que discuten los límites de los enfoques basados en las intenciones conjuntas son: * **No se tiene en cuenta la estructura social:** Las relaciones entre los agentes generan implícitamente estructuras sociales que son fundamentales para determinar si los agentes optan por los objetivos de otros agentes o no. * **Se centra en la representanción interna:** Las acciones coherentes tienen mas peso que la acción coordinada. Es decir que el sistema alcanzará su objetivo independientemente del estado de los agentes. * **Aplicación limitada:** No se puede aplicar esta teoría para todos los tipos de coordinación. ## Trabajo en equipo Sin embargo, algunos autores defienden que no es necesario que la lógica que subyace detras de la teoría de las intenciones conjuntas tengan que implementarse para construir sistemas de coordinación. Sino que puede implementarse como una serie de reglas de coordinación. La teoría de las intenciones conjuntas se ha aplicado de maneras diferentes para crear mecanismos de coordinación. Algunas de ellas son: * 1. **STEAM [#Tambe]: ** Basado en el modelo de intención común de Cohen y Levesque [#Cohen] que permite a los agentes modelar el proceso de coordinación. Los ámbitos de uso incluyen escenarios militares con helicópteros y fútbol con robots. !!!Tip:Ejemplo (Attack) Uno de los escenarios que se planteó para resolver con el modelo **STEAM** se conoce como **Attack**. En este escenario existe una compañía de más de 8 helicópteros de ataque. La compañía despega de una estación base, donde el comandante indica instruciones y ordenes al resto. La compañía despega y empieza a volar hacia la posición de batalla, es decir dónde la compañía quiere atacar al enemigo. Mientras que se dirigen a esa posición, dependiendo de las órdenes, los miembros de la compañía deberán volar juntos o dividirse dinámicamente en varios equipos. Una vez que la compañía llega a la posición de ataque espera a que uno de los helicópteros exploradores vuelen primero y exploren la zona. Dependiendo de las comunicaciones con los helicópteros exploradores, los demás helicópteros empiezan a sobrevolar la posición de batalla y a disparar misíles contra los vehículos enemigos. Una vez que el ataque es completado, la compañía se reagrupa y vuelve a la posición base. Si durante la vuelta alguno de los helicópteros detecta algún enemigo, alerta a los demás helicópteros para que eviten el ataque. Cuando la compañía llegue segura a la posición base, puede rearmarse y repostar para estar lista para la siguiente misión. ![](./img/attack.png align="center" width=80%) * 2. **GRATE y GRATE* [#Jennings3]:** Basado en el modelo de responsabilidad de intención de Jennings comentado en la sección anterior y que ha sido aplicado a problemas de distribución de electricidad. * 3. **Kinnet et. al: [#Kinney]** Describe un planificador/programador multiagente que intercala planes de acción previamente planificados para realizar acciones coherentes. En cada caso, la importante ventaja que aportan estos sistemas es que permiten a los agentes modelar explícitamente el proceso de coordinación y reaccionar adecuadamente a los cambios del entorno. Este trabajo está intrínsecamente relacionado con: * **Detección de interacciones:** Detectar interacciones positivas y negativas entre los sub planes llevados a cabo por los diferentes agentes. * **Monitorización del plan y el progreso del equipo:** A medida que se llevan a cabo las acciones conjuntas, es vital que los agentes implicados supervisen el progreso para garantizar que los objetivos y los planes planes sigan siendo válidos. * **Planificación y resolución de conflictos:** al acordar el plan que seguirán para alcanzar un objetivo conjunto, los agentes necesitarán inevitablemente utilizar mecanismos de coordinación y resolución de conflictos más precisos para garantizar que los planes sean compatibles con las capacidades y los objetivos de cada agente. ## Planificación La elección de secuencias de acciones que se tienen que llevar a cabo para conseguir un objetivo ha sido el punto de enfoque en el que se ha centrado el trabajo de la IA desde que nació. Aunque gran parte del trabajo realizado por la comunidad de planificación de la IA se refiere a un único agente planificador que suele actuar solo en el mundo existe un trabajo considerable sobre los sistemas de planificación que se ocupan de múltiples agentes: * **Planificación Contigente:** Se ocupa de desarrollar planes que sean flexibles con respecto a las posibles modificaciones que se puedan llevar a cabo durante la ejecución del plan. Uno de los principales usos es en entornos en los que el agente que ejecuta el plan no está solo y otros agentes pueden actuar en el mismo mundo. * **Planificación Adversaria:** es una subcategoría de la planificación de la IA que se ocupa específicamente de de situaciones en las que los agentes hostiles del entorno pueden intentar bloquear la consecución de los objetivos de un plan. * **Reconocimiento de planes:** abarca el problema de la identificación de los planes que están siendo ejecutados por otros agentes y usar esa información para decidir sobre las propias acciones que debe tomar el agente que percibe esta información. Estos sistemas de planificación desglosan los planes en tareas para los actores y razonan sobre la sincronización de los planes. Los planes también se reconocen como una poderosa herramienta de comunicación explícita sobre la coordinación. Pueden utilizarse como una expresión de propuestas de acciones futuras acciones que los agentes pueden compartir entre sí. 1. **sharedPlans [#Kraus]:** funciona de forma similar al marco basado en las intenciones conjuntas, combinando un agente que pretende que algo sea cierto con el axioma de que los agentes con intenciones actuarán tarde o temprano para hacer realidad sus intenciones. 2. **Planificación Parcial Global (PGP) [#Durfee]: ** PGP es un marco en el que los agentes son capaces de intercambiar información sobre sus propias acciones planificadas, su orden, el tiempo de resultado previsto, etc., y las de los demás. Esta difusión de conocimientos es utilizada por los agentes del sistema para optimizar el trabajo realizado por toda la comunidad. 3. **Concencus [#Concensus]:** similar a PGP, el consenso permite a los agentes intercambiar información del plan a través de una *'arquitectura de pizarra'*. Se aplicó originalmente a los sistemas expertos cooperativos. !!!Tip: *Blackboard architecture* La arquitectura software en pizarra es un modelo habitualmente utilizado en sistemas multiagente. Ésta arquitectura consta de múltiples elementos funcionales, agentes, y un instrumento de control denominado pizarra. Todos ellos cooperan para alcanzar una meta común, sin embargo, sus objetivos individuales no están aparentemente coordinados. El comportamiento básico de cualquier agente consiste en examinar la pizarra, realizar su tarea y escribir sus resultados en la misma pizarra. De este modo, otro agente puede trabajar sobre los resultados generados por otro. La computación termina cuando se alcanza alguna condición deseada entre los resultados escritos en la pizarra. La pizarra tiene un doble papel. Por una parte, coordina a los distintos agentes y, por otra, facilita su intercomunicación. El estado inicial de la pizarra es una descripción del problema que resolver y el estado final será la solución del problema. La planificación ha sido usada por autores como Decker, [#Decker], y Durfee, [#Durfee2], para intentar guiar la coordinación en sistemas multiagentes. ## Negociación La negociación es un proceso mediante el cual los agentes pueden actuar para resolver puntos de vista inconsistentes y llegar a un acuerdo. La negociación puede aplicarse tanto en dominios cooperativos para resolver conflictos de recursos entre agentes que trabajan hacia el mismo objetivo, por ejemplo, como en entornos competitivos en los que cada agente pretende maximizar su beneficio por razones puramente personales. Muchos de los enfoques de negociación para ambos propósitos pueden considerarse como coordinación explícita, ya que: * Los agentes se ponen de acuerdo de una serie de reglas que se impone por el propio proceso de negociación. * Los agentes tienen un objetivo común de llegar a un acuerdo. * La información intercambiada implica detalles de las tareas a realizar, los bienes que se intercambian e información acerca de los pagos por esos bienes. Aunque no entraremos en detalle, algunas técnicas de negociación incluyen: teoría de juegos, negociación multi-etapa o el algoritmo propuesto por Smith and Davies conocido como '*Contract Net Based*'. ## Mercados, Subastas e Instituciones Como la negociación, el objetivo de un '*mercado*' es asegurar el acuerdo entre el precio y la venta de un bien o servicio. Un mercado generalmente esteá compuesto por: * **Infraestructura de comunicación:** Los agentes puedan conectarse al mercado, reciben información sobre los precios y envien ofertas conociendo los resultados. * **Reglas:** un conjunto de reglas que rigen las interacciones en el mercado. * **Protocolos:** un conjunto de protocolos o procedimientos a seguir para iniciar la venta, y envío/respuesta de ofertas así como el cálculo del ganador de la oferta. Las reglas de un mercado son aplicadas por la institución o entorno en el que los agentes interactúan. En este contexto, los agentes utilizan mensajes de señales explícitas para indicar sus compromisos de compra de bienes o de realización de tareas que constituyen una coordinación explícita. Algunos de los trabajos basados en sistemas de mercados son: * **Mercados Eléctricos:** Frederic Ygge [#Ygge] junto a otros autores describen el mecanismo para regular los precios de la electricidad en los mercados eléctricos. * **Optimización de potencia:** Malone y Chavez describen como usar los mecanismos de marcado para compartir potencia de computacion de estaciones de trabajo en '*intranets*'. # Coordinación Implícita Aunque la coordinación explícita proporciona modelos muy útiles en algunos dominios no es posible o no es deseable proporcionar a los agentes los mecanismos para comunicarse con fines de coordinación. Las razones para ello son, entre otras, las siguientes: * **Velocidad:** aunque se han llevado a cabo metodogías para tener en cuenta el tiempo durante los mecanismos de coordinación, la comunicación explícita para la coordinación de tareas conlleva retrasos notables. * **Seguridad:** en entornos no cooperativos y abiertos puede ser indeseable permitir que los agentes interactúen con otros a menos que se puedan resolver los problemas de autenticación y confianza. En algunos casos, la interacción directa también puede estar prohibida por razones de igualdad (para evitar la colaboración de los pujadores en las subastas, por ejemplo). * **Complejidad:** La coordinacion explícita requiere normalmente bastante computación a la hora de comunicarte y puede sobrecargar los sistemas que utilizan los agentes para llevar a cabo sus tareas básicas. * **Información Limitada:** Los agentes pueden interactuar entre sí en el entorno (por ejemplo, jugando una partida de ajedrez o participando en una subasta a puja cerrada) pero no tienen un canal de comunicación directo entre ellos. En estas condiciones, es necesario emplear mecanismos que no requieran una comunicación explícita o, en algunos casos, una representación de la coordinación para que los agentes puedan trabajar eficazmente entre sí. ## Modelado del agente En algunos ámbitos, la falta de comunicación sobre los objetivos de los agentes puede compensarse con un razonamiento sobre sus acciones probables basado en el conocimiento del entorno del agente o teniendo en cuenta las acciones observables. Existen algunos técnicas que intentan llevar a cabo este enfoque: * **Métodos de modelado recursivo (RMM):** este enfoque está basado en el conocimiento (o suposición) de la utilidad (recompensa) de ciertas acciones de los agentes en el entorno. El conocimiento de las utilidades permite a un agente $A$ a construir un árbol que represente las vistas diferentes que otro agente $B$ pueda tener acerca de una elección particular. En estas vistas el agente $A$ puede añadir que es lo que el agente $B$ está considerando cómo la vista de A, por eso es un proceso recursivo. El árbol representa la acción más rentable que $A$ puede hacer conociendo la información sobre $B$. * **Reconocimiento de planes:** En el reconocimiento de planes, un agente observa las acciones de otros agentes en el entorno e intenta hacerlas coincidir con los planes de acción conocidos. Esto sirve para discernir los objetivos de los agentes o hacer un seguimiento del progreso. * **Teoría de juegos:** Los problemas de teorías de juegos han planteado a la investigación de la Inteligencia Artificial muchos de sus mayores retos y han llevado al desarrollo de muchos sistemas que se basan en algún tipo de modelo de oponentes. Aunque estas técnicas suelen aplicarse en dominios adversarios o, al menos, no cooperativos, también pueden ser utilizadas por agentes que deseen cooperar, además pueden ser utilizadas por agentes que desean cooperar pero que no pueden comunicarse de forma directa. ## Estructuras Sociales En muchos ejemplos de sistemas de agentes, éstos son capaces de interactuar y producir resultados coherentes porque operan en un marco de reglas implícitas en el diseño o en el diseño del sistema en el que trabajan. Por tanto, el comportamiento de los agentes está preprogramado para mantenerse dentro de unos límites de aplicación predeterminados. Algunos de los mejores ejemplos de esto son: * **Leyes Sociales:** un gran número de trabajos sobre las leyes sociales se ocupa del uso de las relaciones de las normas sociales o de los patrones de control para gobernar las acciones de los agentes. Las leyes pueden ser aplicadas explícitamente por un sistema externo o simplemente utilizadas como directrices para los desarrolladores. También ha habido un amplio trabajo sobre el aprendizaje o la adquisición de leyes sociales. * **Relaciones Sociales de Poder:** Algunos autores defienden que las interacciones de los agentes están guiadas por '*relaciones de dependencia*' que los agentes pueden o no conocer (es decir, un agente tiene que utilizar recursos vitales que otros agentes también necesita). Estas dependencias provocan una estructura social implícita. * **Estructuras Sociales:** mientras que las nociones de trabajo sobre el poder social se refieren a la percepción internos de los agentes de las dependencias y la posterior adopción de objetivos, algunos autores sostienen que las estructuras inducidas también pueden ser vistas como puramente externas. Esto da lugar a un entorno limitado por las normas sin referencia particular a los modelos internos de los agentes. Cada uno de estos enfoques, muy relacionados entre sí, puede considerarse una coordinación implícita, ya que los agentes implicados pueden no ser conscientes de las restricciones que se les imponen. Sin embargo, en cada caso, la coordinación explícita puede seguir siendo apropiada en el contexto de la sociedad. ## Coordinación Emergente Un grupo de agentes pueden tomar acciones coherentes incluso si: * No hay comunicación directa entre los agentes. * No hay apriori mecanismos para asignar o obligar a los agentes a basarse en leyes sociales. * Cada agente tiene una serie de objetivos que no tienen ninguna relación entre los objetivos de los otros agentes. Es decir, que no existe intención de coordinarse. En estos casos, los agentes interactúan eficazmente a través del entorno. Las acciones de cada agente cambian el entorno de alguna manera y esto, a su vez, estimula a otros agentes a actuar de determinadas maneras. Esto se aplica sobre todo a los agentes puramente reactivos, que por definición no tienen capacidad de predicción ni de planificación. De ello se deduce que cualquier coordinación observable es emergente y no puede ser el resultado de una intención. Algunos de los trabajos más conocidos sobre la aplicación de la coordinación emergente son: * **Tidy Robots [#Becker]:** En este trabajo se muestra como equipos de robots autónomos pueden transportar objetos distribuidos aleatoriamente y apilarlas de manera ordenada sin tener programados ningún algoritmo de coordinación. Los robots llevan a cabo tareas simples basadas en simples reglas de comportamiento e interaccionan con los demás agentes indirectamente modificando el entorno común a todos los agentes. !!!Tip:Ejemplo (Tidy Robots) ![](./img/tidy_robot.png align="center " width=50%) En un entorno controlado en forma de cuadrado de 250x250cm se colocaron 81 piezas de basura distribuidas en una red. El objetivo consistía en apilar todas ellas en un cuadrado de la red, para ello se hicieron experimentos con unos robots equipados con 2 sensores IR para poder detectar los obstáculos (en este caso sólo las paredes) así como una garra que le permitía empujar las piezas de basura. El comportamiento de los robots era muy básico, cada uno de ellos seguía una simple regla, debía de apilar las piezas de basura una cerca de otra. Para ello cada robot tenía tres comportamientos. Si los sensores de proximidad no estaban activados el robot se movía en linea recta hasta que se activaran o hasta que se activara la garra (se activaba cuando tres piezas de basura eran detectadas en la garra). Si se detectaba un obstáculo se llevaba a cabo una rutina de evitación de obstáculos muy simple (girando un ángulo aleatorio). Si cuando se detectara el obstáculo, había alguna pieza de basura en la garra, se mantenía la pieza durante el giro. Si la garra detectaba más de tres piezas de basura, el comportamiento del robot cambiaba a dejar las piezas de basura en el sitio, retrocedía hacia atrás y giraba y seguía en el comportamiento normal en línea recta. Los robots operaban completamente autónomos, todos los sensores, control y actuadores estaban embarcados y no existía ninguna comunicación explícita entre ellos o con un ordenador central. Los robots sólo reaccionaban a la configuración del entorno. Al comienzo de cada experimento, los robots se colocan en el centro de la arena, cada uno apuntando en una dirección diferente. Cada 10 minutos de funcionamiento, los robots se detienen manualmente, se registran los tamaños y las posiciones de los grupos de discos y se vuelven a poner en marcha. Una agrupación se define como un grupo de discos separados por no más de un diámetro de disco. El experimento continúa hasta que los 81 discos están en un solo grupo. ![](./img/tidy_robots.png align="center" width=70%) Esta figura muestra el estado inicial (a) y la evolución típica de un experimento con un grupo de 5 robots. La primera fase (b) que se daba a cabo tras 10 minutos de experimento se caracterizaba por un gran numero de pequeños grupos de 1-10 piezas. En la fase 2 (c), los grupos de piezas empiezan a crecer rápidamente y el entorno empieza a ser más heterogéneo. Por último, la fase 3 (d), está caracterizada por una competición entre pocos grandes grupos de piezas que acaba convergiendo a un grupo con todas las piezas en una pila. * **Swarm Intelligence:** Éstos sistemas se inspiran en el comportamiento de las colonias de insectos, tales como hormigas o abejas. Se trata de sistemas auto-organizados (self organized systems) definidos en la literatura del siguiente modo: *"[...] systems of non-intelligent robots exhibiting collectively intelligent behavior"*. Algunos ejemplos de ello son: Las optimizaciones basadas en hormigas para la resolución del problema del viajero, en los que cada una de las hormigas explora una parte de su entorno y de manera distribuida añade calidad a la solución y la optimiza. Otro ejemplo de aplicación, es la rutina de rastreo de redes basadas en colonias de hormigas. Los agentes tipo hormiga pueden aplicarse a los problemas de direccionamiento de llamadas telefónicas. Las hormigas exploran aleatoriamente la red dejando rastros de feromonas químicas artificiales mientras se mueven. Otras hormigas siguen estos rastros reforzando lentamente el camino más rápido y eficiente. Aunque presenta un gran número de ventanjas, el principal problema de éstos sistemas es la falta de conocimiento global, que limita o impide totalmente que un robot pueda saber cuáles son las decisiones tomadas por los otros miembros de la colonia. Además, las tareas que se llevan a cabo suelen ser muy simples y débilmente acopladas, tales como, la recogida de objetos, o la cobertura de una superficie usando robots homogéneos. # Coordinación centralizada-descentralizada Si en lugar de clasificar los sistemas multiagente en función del medio de comunicación se hace en función de quién tome las decisiones se tendrían dos subcategorías: Coordinación centralizada, dónde un agente central será el encargado de recibir toda la información de los agentes y del entorno y con ello, tomar las decisiones apropiadas. Y, la coordinación descentralizada, dónde cada agente tomará las decisiones por sí mismo. ## Coordinación Centralizada Generalmente, en éstos sistemas se emplean en mecanismos basados en programación lineal o en búsquedas basadas en alguna heurística con el objetivo de obtener la solución más óptima o la más próxima posible a la óptima. En éste ámbito de los multi-agentes, destacan trabajos los trabajos realizados por Shehory y Kraus, [#MA-Coallition]. Dónde se propone un algoritmo de creación de coaliciones de agentes basado en las deficiones SPP *(Set Partitioning Problem)* y SCP *(Set Covering Problem)*, dónde se fija el número máximo de elementos, *k*, para formar una coalición. La complejidad del algoritmo es $O(n^k m)$, dónde *n* es el número de agentes y *m* es el número de tareas a realizar. En [#MR-Coallition], Vig propone un algoritmo con la misma complejidad, es decir, $O(n^k m)$, que extiende los conceptos propuestos anteriormente a sistemas multi-robot. Uno de los mecanismos de coordinador más común basado en éste principio, es el mecanismo de las subastas. Un mecanismo de subasta clásico está compuesto por un grupo de agentes: dónde uno de los agentes cumple el rol de subastador y los agentes restantes son los ofertantes, dicho mecanismo ha sido utilizado en muchas aplicaciones prácticas de ciencias computacionales que involucran la asignación de bienes, tareas y recursos. La razón por la cual la subasta se ha tornado tan popular es que es un escenario fácil de automatizar; esto la hace una buena primera opción a considerar como vía para que los agentes alcancen acuerdos entre sí, sin necesidad de comunicación directa entre ellos. El elevado tiempo de ejecución que, en general, requieren los algoritmos centralizados, junto con los problemas de punto único de fallo y saturación en las comunicaciones, hacen inviable estos mecanismos en entornos dinámicos o con un elevado número de robots. ## Coordinación Descentralizada En la coordinación a nivel descentralizado los agentes explícitamente inician una comunicación y acuerdan un protocolo de comunicación. El intercambio de conocimiento se efectúa sobre la base de la comunicación directa entre los agentes. Este tipo de coordinación requiere saber con certeza quiénes son los interlocutores, dónde se encuentran y cuándo se dará tal interacción. Se han desarrollado diversas investigaciones para alcanzar la coordinación en SMA, que cumpla con ideología de toma de decisiones a nivel distribuido. Cualquiera de ellos implementa y utiliza mecanismos, compuestos por una variedad de protocolos y estructuras, que posibilitan administrar las distintas formas de dependencias que naturalmente se dan cuando los agentes poseen objetivos interconectados, cuando comparten un ambiente común, o cuando existen recursos compartidos [#Agents]. # Aplicaciones a la Robótica En el ámbito de la robótica los sistemas multi-robot, análogos a los sistemas multi-agente, son empleados en un gran número de aplicaciones y de gran interés, ya que permiten optimizar los proceso y los objetivos a realizar. Los dos problemas fundamentales de los sistemas multi-robot son la planificación de tareas y la planificación de movimiento. Éstos dos problemas son fundamentales para resolver de manera satisfactoria cualquier problema en un MRS (*Multi-Robot System*). En la siguiente imagen, se observa cómo, considerando el dominio de las aplicaciones de los MRS, para casi todas las aplicaciones de los sistemas multirobot, es necesario la planificación de tareas y de movimiento. ![](./img/application_domains.png align="center" width=50%) A continuación, se expondrá el funcionamiento de algunos algoritmos concretos para la resolución de éstos problemas para sistemas multi-robot. ## Coordinación de movimientos La coordinación de movimientos juega un papel crucial en las aplicaciones reales a la robótica, cómo se ha mostrado en el diagrama de dominios de aplicación de los sistemas multi-robot. Además de ser una tarea transversal y necesaria por otras, es de las que presenta mayor complejidad realizarla del modo mas óptimo posible. Un claro ejemplo de ello, es que a día de hoy, gran parte de los almacenes de las grandes empresas se encuentran automatizados, de tal modo que existe una 'flota' de robots terrestres que se encargan de la gestión del inventario. Es crucial que el movimiento de éstos robots se encuentren coordinados para alcanzar su objetivo de la manera más óptima posible y no interfieran entre ellos. Ya que de lo contrario entorpecerían el proceso de producción. Es por ello que se deben tener en cuenta en los procesos de planificación los obstaculos dinámicos, por ello se debe añadir la dimensión del tiempo a la resolución de los problemas. La resolución de éste problema puede ser afrontada desde distintos puntos de vista. En los ejemplos expuestos en éste apartado, se verán los sistemas centralizados, dónde se tiene un agente central que tiene toda la información de los agentes y el entorno y le asignará la tarea a realizar, en éste caso, el camino a seguir a cada agente. Y los sistemas descentralizados, dónde cada agente debe buscar de manera independiente el camino a seguir en función de los estimulos que perciba del entorno para resolver la tarea asignada. Para mostrar ejemplos realistas de la coordinación de movimientos entre robots, se hará uso de una [ librería en Python para la sistemas multiagente](https://atb033.github.io/multi_agent_path_planning/). ### Soluciones centralizada Cómo se ha expuesto anteriormente, en éste tipo de soluciones a los sistemas multiagente, se tiene un agente central que tiene toda la información de los agentes y el entorno y le asignará la tarea a realizar, en éste caso, el camino a seguir a cada agente. #### Prioritized Safe-Interval Path Planning (SIPP) El algoritmo SIPP(Prioritized Safe-Interval Path Planning) [#SIPP] es un planificador local que permite generar una trayectoria libre de colisiones, teniendo en cuenta tanto los obstaculos estáticos cómo los dinámicos del entorno. En el caso de que haya multiples robots, es decir, en el caso de que el sistema sea multiagente, cada agente será visto por los otros cómo un obstáculo dinámico. El planificador implementado en SIPP se basa en la siguiente observación: Mientras que el número de pasos de tiempo seguros en cualquier configuración es ilimitado, el número de intervalos de tiempo seguros en una configuración concreta es finito y, generalmente, pequeño. Se define un intervalo seguro cómo un periodo de tiempo para una configuración concreta que no presenta colisiones y, si se avanzara un paso de tiempo en cualquier dirección, entonces encontraría una colisión. El planificador de SIPP aprovecha ésta observación y construye un espacio de busqueda con estados definidos a partir de su configuración y su intervalo seguro, lo que dará lugar a un grafo que generalmente presentará un pequeño número de estados por configuración. Además de ello, en el plano teórico, éste planificador será igual de óptimo y exhaustivo que uno en el que se tenga en cuenta el tiempo cómo dimensión adiccional. A continuación, se expondrá una pequeña explicación conceptual de la algoritmo extraida del artículo: !!!Tip:Ejemplo (Algoritmo SIPP) ![](./img/sipp_paper.png align="right" width=30%) En ésta imagen se muestra el estado inicial del entorno y las tres primeras acciones del plan óptimo obtenido. En la esquina superior izquierda, **(a)**, tenemos el entorno inicial. En él los dos circulos grises son dos obstaculos móviles que se desplazarán hacia la izquierda y arriba, respectivamente, y, el robot está representado por la letra **R** y su objetivo será alcanzar la posición marcada por la letra **G**. En cuánto al movimiento, se supondrá que se mueven cada paso de tiempo una casilla. A partir de la imagen **(a)**, se observa que el robot no podrá generar un camino seguro hasta que el obstaculo movil no pase. Por lo que la primera acción a realizar será esperar y luego moverse. En la imagen **(b)** podemos ver éste estado. La única celda que presenta un lugar seguro será la que se encuentra a la izquierda, ya que éste algoritmo únicamente almacena un estado por cada par configuración-intervalo seguro y éste será el que se alcance en el menor tiempo posible. Por lo que la única acción considerada será moverse inmediatamente a la izquierda. En la imagen **(c)** tenemos el estado del robot tras realizar la segunda acción. En éste caso, observa que el intervalo seguro más cercano es esperar a que pase el obstáculo y moverse hacia la izquierda. Ésta situación se observa en la imagen **(d)**. Por último, el camino que nos queda hasta llegar al objetivo será seguro. #### Conflict Based Search (CBS) Un problema MAPF (*Multi Agent Path Finding*) se basa en la busqueda de un camino libre de colisiones para varios robots que comienzan en diferentes lugares y tienen diferentes destinos en el mismo entorno. En muchas ocasiones se han empleado busquedas globales basadas en A*. El algoritmo CBS, [#CBS], resuelve el problema de MAPF descomponiendolo en un gran número de subproblemas de busqueda de trayectoria para un único agente. Su idea básica es crear una serie de restricciones para cada uno de los agentes y buscar trayectorias que sean consistentes con ellas. Si dos trayectorias presentasen conflictos, y ambas fueran inválidas, se resolverían esos conflictos añadiendo nuevas restricciones. Éste algoritmo trabaja en dos niveles de abstración, a alto nivel se realiza una busqueda en árbol empleando los conflictos (Constraint Tree) entre los agentes para generar nuevas restricciones y, a bajo nivel, que se realizará una actualización o busqueda de la trayectoria de cada agente uno por uno adaptandose a las nuevas restricciones. Ésta busqueda de la trayectoria para cada agente a partir de las restricciones definidas se realiza mediante el algoritmo A*. !!!Tip: Algoritmo A* (CBS a bajo nivel) ![](./img/Astar_progress_animation.gif align="right" width=30%) Este algoritmo de busqueda es ampliamente empleado en el ámbito de la robótica. Se puede clasificar dentro de los algoritmos de busqueda de grafos de tipo heurístico. Si existe una solución, A* encontrará el camino de menor coste entre el nodo origen y el objetivo. Éste algoritmo, emplea una función de evaluación $f(n) = g(n) + h(n)$, dónde $h(n)$ representa la heurística de calcular el coste estimado del camino desde el nodo actual hasta el nodo objetivo y $g(n)$ el coste real del camino recorrido para llegar a dicho nodo, $n$, desde el nodo inicial. A* mantiene dos estructuras de datos auxiliares, que podemos denominar *abiertos*, implementado como una cola de prioridad (ordenada por el valor $f(n)$ de cada nodo), y *cerrados*, donde se guarda la información de los nodos que ya han sido visitados. En cada paso del algoritmo, se expande el nodo que esté primero en abiertos, y en caso de que no sea un nodo objetivo, calcula la $f(n)$ de todos sus hijos, los inserta en abiertos, y pasa el nodo evaluado a cerrados. El algoritmo es una combinación entre dos tipos de busquedas de grafos: *Primero en anchura*, $g(n)$ y *Primero en profundidad*, $h(n)$. Es por ello que cambia el camino de busqueda cada vez que existen nodos más prometedores. El algoritmo que presentaremos aqui, en muchos casos resulta en menos estados que el A*, pero manteniendose óptimo, de tal modo que se puede ejecutar en un mejor número de pasos. ### Soluciones descentralizadas En éste tipo de problemas, cada robot deberá estimar su trayectoria a partir de los estimulos que reciba del entorno o la comunicación con otros robots. El resto de agentes se entenderán cómo obstaculos dinámicos y habrá que evitar colisionar con ellos. #### Hybrid Reciprocal Velocity Obstacle Éste primer enfoque, se expondrá el trabajo realizado en HRVO (*'The Hybrid Reciprocal Velocity Obstacle'*), [#HRVO]. Éste algoritmo permite la navegación de multiples robots sin colisiones ni oscilación. Cada robot únicamente toma información de su entorno y actúa de manera independiente, sin una coordinación central ni comunicación con los otros robots. Éste algoritmo es de código abierto y se puede encontrar tanto información sobre él cómo su código en C++ en el siguiente [enlace](https://gamma.cs.unc.edu/HRVO/). En él, se empleará tanto la posición cómo la velocidad actual del robot y la velocidad de los obstaculos dinámicos, otros robots, para calcular las futuras trayectorias con el fín de evitar colisiones. Además de ello, éste algoritmo se considera reciproco y evita las oscilaciones al tener encuenta explicitamente que los otros robots también perciben el entorno y cambian sus trayectorias en consecuencia. !!!Tip: Construcción del HRVO para un robot En la siguiente imagen, se muestra el modo en el que se construye éste HRVO para cada robot. Dados dos robots con forma de disco cuyo radio $r_i$, posición $p_i$, velocidad $v_i$ son conocidos, **(a)**. En la figura **(b)**, se observa el grafo del Velocity Obstacle($VO_{A|B}$) que induce el robot B en el A, lo cual se define cómo el conjunto de todas las posibles velocidades tomadas por el robot A que resultarían en una colisión entre él y el obstáculo móvil, B, en cualquier momento de tiempo y asumiento que el obstáculo dinámico B mantiene su velocidad constante. ![](./img/HRVO-build.png align="center" width=90%) En la figura **(c)**, se observa el conjunto de velocidades de Reciprocal Velocity Obstacle($RVO_{A|B}$) que induce el robot A en el B, el cuál es una mejora sobre el anterior el problema de las oscilaciones en los sistemas de robots reactivos. Para ello, a diferencia del anterior, en lugar de que cada robot asuma toda la responsabilidad de evitar la colisión, únicamente se tendrá en cuenta la mitad de la responsabilidad, asumiento que el otro agente implicado se encargará de la otra mitad. En otras palabras, cuándo se elige una velocidad para un agente, se tomará la media de su velocidad actual, $v_a$ y la velocidad de $VO_{A|B}$. Por último, en **(d)** se observa el Hybrid Reciprocal Velocity Obstacle ($HRVO_{A|B}$) que induce el robot A en el B. Destacar que la velocidad, $v_a$ se encuentra a la derecha de la línea central del resultado de ($RVO_{A|B}$), por lo que el vértice HRVO es el punto de intersección del lado derecho de ($RVO_{A|B}$) y el lado izquierdo de ($VO_{A|B}$). En el caso de que $v_a$ se encuentre a la izquierda el análisis será análogo. Ésto tiene cómo consecuencia que si el robot A intenta pasar por el lado equivocado del robot B, entonces tiene que dar total prioridad al robot B, cómo en el caso de VO. Sin embargo, si elige el lado correcto, entonces puede asumir una cooperación del robot B y, por tanto, se pueden repartir las responsabilidades de la evutación de la colisión, cómo en RVO. ![](./img/HRVO.png align="right" width=25%) En la imagen se muestra la HRVO del robot oscuro, A. Su HRVO será la resultante de la unión de todos los HRVO inducido por los otros robots de manera individual. Los puntos marcados en gris, representan la proyección de la velocidad preferida en las lineas que no están dentro de la combinación de los HRVO, y por tanto, son las que se emplearán por el algoritmo *ClearPath* para definir nuevas velocidades de cada robot. En el siguiente [enlace](https://www.youtube.com/watch?v=u9I-SqLznYw), se puede observar el funcionamiento de éste algoritmo aplicado sobre robots reales. #### Nonlinear Model-Predictive Control Un último ejemplo que veremos, será el uso de un MPC no lineal, [#MPC], el cuál ha sido desarrollado para evitar colisiones de manera reactiva empleando microdrones (MAVs). Se empleará un controlador basado en el modelo para conocer de manera simultanea tanto la trayectoria de referencia a seguir cómo la evitación de colisiones. Además, se tendrá en cuentra la incretidumbre del estimador de estados y la incretidumbre de la posición y velocidad de cada uno de los otros agentes para lograr un mayor nivel de robustez. ![](./img/forces_mav.png align="right" width=40%) Para la formulación del modelo en el que se basa el controlador MPC, se empleará el modelado ya conocido de un dron empleando las fuerzas y los momentos del sistema. A partir de éstas fuerzas y la dinámica de la aeronave, se definirán las ecuaciones de movimiento del vehículo. En cuánto a la definición del problema de control, se hará cómo un problema de optimización con restricciones (COP). La función de coste del problema de optimización, incluye un término del tipo campo potencial que penaliza las colisiones entre los agentes. Cabe destacar que aunque los métodos de campos potenciales no proporcionan garantías y son sensibles al ajuste de ciertos parámetros, se han fijado unas fuertes restricciones para garantizar que no se produzcan colisiones. Cómo se ha dicho ántes, para aumentar la robustez de la evitación de obstaculos, se empleará la incertidumbre del estimador de estados para dar forma al término de colisión en la función de costes y restricciones de optimización. El funcionamiento de éste MPC con multiples drones se puede observar en el siguiente [enlace](https://www.youtube.com/watch?v=Ot76i9p2ZZo). ## Enjambres de drones (swarm) para observación de objetivos Un ejemplo de ello, podría ser el rastreo de un área y detección de objetivos empleando múltiples drones. Todos ellos se comunican con una estación de tierra, la cuál será la encargada de tomar las decisiones y enviar las premisas de control a cada aeronave. En el momento que en la cámara de alguna de las aeronaves se detecte un objetivo, se pasará a una formación de observación del objetivo desde todas las aeronaves. La formación empleada se denomina *Virtual Structure*, dónde se colocará cada aeronave en un punto y se emulará que éstas forman un sólido rígido, por lo que todas se moverán siguiendo las ecuaciones de movimiento de un sólido rígido. ![](./img/virtual_structure_formation.png align="center" width=40%) Aunque en éste caso de aplicación se ha expuesto un sistema centralizado, no es lo más conveniente debido a que se tiene un único punto de error. En la literatura aparecen implementaciones similares a la realizada aquí pero de un modo descentralizado. ## Enjambres de drones (swarm) para rescate o vigilancia Cómo hemos visto en el inicio del apartado, otro de los dominios de aplicación en la coordinación de sistemas multi-robot, es el de rescate o vigilancia. Dónde un conjunto de robots deben explorar una zona en el mejor tiempo posible. Es por ello, que aquí es necesario tener en cuenta tánto la planificación de movimientos cómo de tareas ya que ésto será crucial para alcanzar el objetivo de manera óptima. Por último, veremos el más complejo y completo de los ejemplos vistos. En éste apartado se expondrá el funcionamiento de un algoritmo realista para la coordinación y exploración de un terreno desconocido empleando múltiples aeronaves o drones: [Framework para coordinación de drones en entornos desconocidos](https://github.com/VIS4ROB-lab/multi_robot_coordination). ![](./img/iros_coordination_arq.png align="right" width=40%) Al igual que en gran parte de los ejemplos expuestos, en éste proyecto plantearán una arquitectura centralizada, dónde todos los agentes se comunicarán y enviarán información a un servidor central. El objetivo es que mediante la coordinación de éstos agentes se logre explorar el área de interes. Cada agente estimará su posición mediante la utilización de algún algoritmo de Odometría Visual-Inercial. Para la planificación de trayectorias local y la evitación de pequeños obstáculos se emplea el algoritmo propuesto por V. Usenko en [#TrajMAV]. En el servidor, se realizarán las tareas computacionalmente más costosas cómo la optimización se la fusión sensorial, el mapeo y el planificador de trayectorias global. Las posiciones y orientaciones estimadas se fusionarán con la información GPS para corregir la posible deriva que surja en la estimación de la posición realizada por cada agente y se convierte a un marco global, en lugar del local de cada agente. Empleando las posiciones correjidas y las nubes de puntos de cada agente, se creará un mapa denso del entorno. A partir de éste mapa, se emplea una estrategia de planificación de trayectorias jerarquica para coordinar la misión, de tal modo que cada agente alcance tu posición objetivo en una zona que no esté previamente mapeada. Por lo tanto, la información sobre el entorno recibida por cada agente es empleada por el planificador global, para coordinar los movimientos de cada robot. Para definir las prioridades del planificador jerarquico, al inicio de la misión a todos los agentes se le asigna una zona desconocida a mapear mediante waypoints GPS, los cuales deben ser alcanzamos lo más rápido posible. El planificador calcula la trayectoria a seguir por cada agente y se lo comunica a cada uno. Si a partir del mapa que se va creando, algún waypoint queda dentro de un obstáculo, éste será eliminado por el planificador global y se enviará la trayectoria modificada al agente. Además de una trayectoria, al inicio a cada agente se le asignará un nivel de prioridad de tal modo que en un equipo de busqueda no pueda haber dos robots con un mismo nivel de prioridad. El planificador jerarquico conlleva que, el espacio de vuelo de cada agente estará restrigido por el mapa obtenido y la trayectoria de los agentes con prioridad superior. En el caso en alguna trayectoria no sea consistente con el orden jerarquico, el planificador global recomputará una nueva trayectoria válida y la comunicará. ![](./img/mrs_topview.png align="left" width=90%) ![](./img/mrs_3dview.png align="right" width=90%) El funcionamiento en simulación de éste framework se puede observar en el siguiente [video](https://www.youtube.com/watch?v=BlFbiuV-d10). Tras haber expuesto el funcionamiento de un sistema de coordinación de robots en entornos desconocidos reales, se mostrarán los resultados y el funcionamiento de éste último algoritmo. Con ello, podremos concluir en los beneficios que conlleva la coordinación de sistemas multirobot de tal modo que se logren resolver tareas del modo más óptimo posible. Cabe destacar que, aunque gran parte de los ejemplos realistas expuestos en éste documento sean centralizados, existen soluciones mucho mas complejas en la literatura con un enfoque descentralizado, que permite evitar las desventajas que supone la implementación de un sistema centralizado. # Referencias [#Agents]: Excelente-Toledo C. y Jennings N. The dynamic selection of coordination mechanisms. Autonomous Agents and Multi-Agent Systems, 9, Kluwer:55-85, 2004. [#DKLewis]: D. K. Lewis. *[Conventions, A Philosophical Study.](https://philpapers.org/rec/LEWCAP-4)*. Harvard University Press, Cambridge, 1969. [#GWeiß]: G. Weiß. *[Learning to coordinate actions in multi-agent system](https://courses.cs.duke.edu/cps296.3/spring07/multiagentlearning.pdf)*. Proc. 13th International Joint Conf. on Artif. Intel., pages 311-316, Chambery, FR, 1993. [#Fudenberg]: D. Fudenberg and D. K. Levine. *[Steady state learning and Nash equilibrium](https://www.jstor.org/stable/2951717)*. Econometrica, 61(3):547-573, 1993. [#Malone]: Malone T. y Crowston K. *[The Interdisciplinary Study of Coordination](https://dl.acm.org/doi/10.1145/174666.174668)*. In ACM Computing Surveys, Vol. 26 (1), pp. 87-119 , 1994. [#Dignum]: Dignum V. y Dignum F. *[Task ad Social Coordination in Agent Organizatios](https://dl.acm.org/doi/10.1145/1082473.1082684)*. In Proc. ACM AAMAS, pp. 1183-1184. 2005. [#VonMartial]: Von Martial F. *[Coordinating Plans of Autonomous Agents](https://dl.acm.org/doi/10.5555/531540)*. Springer-Verlag. 1992. [#Ferber]: Ferber J. *[Multi Agent Systems. An Introduction to Distributed Artificial Intelligence.](https://www.jasss.org/4/2/reviews/rouchier.html)*. Addison-Wesley. 1999. [#Jennings]: Nicholas R. Jennings y Michael Wooldridge *[Agent-Oriented Software Engineering](https://www.cs.upc.edu/~jvazquez/teaching/sma-upc/docs/jennings00agentoriented.pdf)*. University of London. 1999. [#Searle]: J. Searle *[Collective Intentions and Actions](https://web.media.mit.edu/~cynthiab/Readings/searle-90.pdf)*. MIT, 1999. [#Jennings2]: Nicholas R. Jennings *[Joint Intentions as a Model of Multi-Agent Cooperation in Complex Dynamic Environments](https://eprints.soton.ac.uk/256596/1/nrj_thesis.pdf)*. University of London. 1992. [#Cohen]: Philip R. Cohen y Hector J. Levesque *[On Acting Together](https://web.media.mit.edu/~cynthiab/Readings/Levesque-AAAI90.pdf)*. University of Toronto. 1992. [#Tambe]: Milind Tambe *[Towards Flexible Teamwork](https://arxiv.org/pdf/cs/9709101.pdf)*. University of Southern California. 1997. [#Jennings3]: Nicholas R. Jennings y E. Mamandi *[GRATE : A General Framework for Cooperative Problem Solving 1 GRATE : A GENERAL FRAMEWORK FOR COOPERA TIVE PROBLEM](https://www.semanticscholar.org/paper/GRATE-%3A-A-General-Framework-for-Cooperative-Problem-Jennings-Mamdani/25d3eb953213b9854126dbd9d9a68c7010f3acea)*. University of London. 1992. [#Kinney]: Michael Kinney *[Learning Communication Strategies in Multiagent Systems](https://www.researchgate.net/publication/226224587_Learning_Communication_Strategies_in_Multiagent_Systems)*. University of Missouri. 1997. [#Kraus]: Barbara J. Grosz y Sarit Kraus *[The evolution of SharedPlans](https://www.researchgate.net/publication/2643842_The_Evolution_of_SharedPlans)*. Harvard University. 1970. [#Concensus]: R. Clark, C. Grossner, and T. Radhakrishnan. Concensus and compromise: Planning in cooperative agents (Computer Science, Concordia University, 1455 DeMaisonneuve, Montreal, Quebec, H3G 1M8, Canada) International Journal of Cooperative Information Systems 1996 05:01, 27-72 [#Durfee]: Durfee, Edmund y Victor Lesser *[Partial Global Planning: A coordination framework for distributed hypothesis formation Systems](https://www.researchgate.net/publication/264565845_Partial_global_planning_A_coordination_framework_for_distributed_hypothesis_formation)*. University of Michigan. 1990. [#Durfee2]: Piotr J. Gmytrasiewicz, Edmund H. Durfee, and David K. Wehe. 1991. (The utility of communication in coordinating intelligent agents)[https://www.aaai.org/Papers/AAAI/1991/AAAI91-027.pdf) In Proceedings of the ninth National conference on Artificial intelligence - Volume 1 (AAAI'91). AAAI Press, 166-172. [#Decker]: Keith Decker and Victor Lesser. 1993. (An approach to analyzing the need for meta-level communication)[http://mas.cs.umass.edu/Documents/lesser/decker-93-22.pdf]. In Proceedings of the 13th international joint conference on Artifical intelligence - Volume 1 (IJCAI'93). Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 360-366. [#Ygge]: Per Carlsson y Frederic Ygge *[Algortihms for electronic power markets](https://www.diva-portal.org/smash/get/diva2:165438/FULLTEXT01.pdf)*. University of Uppsala. 2004. [#Becker]: Bernd Becker Y Wolfram Burgard *[Techniques for Multi-Robot Coordination and Navigation](http://www2.informatik.uni-freiburg.de/~wurm/papers/wurm12phd.pdf)*. MIT. 2012. [#Pengi]: Philip E. Agre and David Chapman *[Pengi: implementation of a Theory of Activity](https://aaai.org/Papers/AAAI/1987/AAAI87-048.pdf)*. 2012. [#SIPP]: Phillips, M., & Likhachev, M. (2011). [SIPP: Safe interval path planning for dynamic environments](https://www.cs.cmu.edu/~maxim/files/sipp_icra11.pdf). 2011 IEEE International Conference on Robotics and Automation, 5628-5635. [#CBS]: Sharon, Guni & Stern, Roni & Felner, Ariel & Sturtevant, Nathan. (2015). [Conflict-based search for optimal multi-agent pathfinding.](https://www.aaai.org/ocs/index.php/AAAI/AAAI12/paper/viewFile/5062/5239) Artificial Intelligence. 219. 40-66. 10.1016/j.artint.2014.11.006. [#HRVO]: Jamie Snape, Jur van den Ber, Stephen J. Guy, and Dinesh Manocha [The Hybrid Reciprocal Velocity Obstacle](https://gamma.cs.unc.edu/HRVO/HRVO-T-RO.pdf) [#MPC]: Kamel, Mina Samir & Alonso-Mora, Javier & Siegwart, Roland & Nieto, Juan. (2017). [Nonlinear Model Predictive Control for Multi-Micro Aerial Vehicle Robust Collision Avoidance](https://arxiv.org/pdf/1703.01164.pdf) [#MR-Coallition]: L. Vig, “Multi-robot coalition formation,” Tesis doctoral, Gratuate School of Vanderbilt University, Nashville, EUA, Diciembre 2006. [#MA-Coallition]: O. Shehory y S. Kraus, “Methods for task allocation via agent coalition formation,” Artificial Intelligence, no. 1-2, pp. 165-200, Mayo 1998 [#trajMAV]: V. Usenko, L. von Stumberg, A. Pangercic, and D. Cremers, “Real-time trajectory replanning for MAVs using uniform B-Splines and a 3D circular buffer,” in IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), 2017. [#MRS_IROS]: Bartolomei, Luca and Karrer, Marco and Chli, Margarita. [Multi-robot Coordination with Agent-Server Architecture for Autonomous Navigation in Partially Unknown Environment](https://doi.org/10.3929/ethz-b-000441280) --- Borrego Villa, Joaquín and Montes Grova, Marco A. Síntesis, Verificación y Razonamiento sobre Agentes Inteligentes. 2022.