This thesis addresses the problem of learning in physical heterogeneous multi-agent systems(MAS) and the analysis of the benefits of using heterogeneous MAS with respect tohomogeneous ones. An algorithm is developed for this task; building on a previous work on stability in distributed systems by Tad Hogg and Bernardo Huberman, and combining two phenomena observed in natural systems, task partition and hierarchical dominance. This algorithm is devised for allowing agents to learn which are the best tasks to perform on the basis of each agent's skills and the contribution to the team global performance. Agents learn by interacting with the environment and other teammates, and get rewards from the result of the actions they perform. This algorithm is specially designed for problems where all robots have to co-operate and work simultaneously towards the same goal. One example of such a problem is role distribution in a team of heterogeneous robots that form a soccer team, where all members take decisions and co-operate simultaneously. Soccer offers the possibility of conducting research in MAS, where co-operation plays a very important role in a dynamical and changing environment. For these reasons and the experience of the University of Girona in this domain, soccer has been selected as the test-bed for this research. In the case of soccer, tasks are grouped by means of roles.One of the most interesting features of this algorithm is that it endows MAS with a highadaptability to changes in the environment. It allows the team to perform their tasks, whileadapting to the environment. This is studied in several cases, for changes in the environment and in the robot's body. Other features are also analysed, especially a parameter that defines the fitness (biological concept) of each agent in the system, which contributes to performance and team adaptability.The algorithm is applied later to allow agents to learn in teams of homogeneous andheterogeneous robots which roles they have to select, in order to maximise team performance. The teams are compared and the performance is evaluated in the games against three hand-coded teams and against the different homogeneous and heterogeneous teams built in this thesis. This section focuses on the analysis of performance and task partition, in order to study the benefits of heterogeneity in physical MAS.In order to study heterogeneity from a rigorous point of view, a diversity measure is developed building on the hierarchic social entropy defined by Tucker Balch. This is adapted to quantify physical diversity in robot teams. This tool presents very interesting features, as it can be used in the future to design heterogeneous teams on the basis of the knowledge on other teams.

La coordinació i assignació de tasques en entorns distribuïts ha estat un punt important de la recerca en els últims anys i aquests temes són el cor dels sistemes multi-agent. Els agents en aquests sistemes necessiten cooperar i considerar els altres agents en les seves accions i decisions. A més a més, els agents han de coordinar-se ells mateixos per complir tasques complexes que necessiten més d'un agent per ser complerta. Aquestes tasques poden ser tan complexes que els agents poden no saber la ubicació de les tasques o el temps que resta abans de que les tasques quedin obsoletes. Els agents poden necessitar utilitzar la comunicació amb l'objectiu de conèixer la tasca en l'entorn, en cas contrari, poden perdre molt de temps per trobar la tasca dins de l'escenari. De forma similar, el procés de presa de decisions distribuït pot ser encara més complexa si l'entorn és dinàmic, amb incertesa i en temps real. En aquesta dissertació, considerem entorns amb sistemes multi-agent amb restriccions i cooperatius (dinàmics, amb incertesa i en temps real). En aquest sentit es proposen dues aproximacions que permeten la coordinació dels agents. La primera és un mecanisme semi-centralitzat basat en tècniques de subhastes combinatòries i la idea principal es minimitzar el cost de les tasques assignades des de l'agent central cap als equips d'agents. Aquest algoritme té en compte les preferències dels agents sobre les tasques. Aquestes preferències estan incloses en el bid enviat per l'agent. La segona és un aproximació d'scheduling totalment descentralitzat. Això permet als agents assignar les seves tasques tenint en compte les preferències temporals sobre les tasques dels agents. En aquest cas, el rendiment del sistema no només depèn de la maximització o del criteri d'optimització, sinó que també depèn de la capacitat dels agents per adaptar les seves assignacions eficientment. Addicionalment, en un entorn dinàmic, els errors d'execució poden succeir a qualsevol pla degut a la incertesa i error de accions individuals. A més, una part indispensable d'un sistema de planificació és la capacitat de re-planificar. Aquesta dissertació també proveeix una aproximació amb re-planificació amb l'objectiu de permetre als agent re-coordinar els seus plans quan els problemes en l'entorn no permeti la execució del pla. Totes aquestes aproximacions s'han portat a terme per permetre als agents assignar i coordinar de forma eficient totes les tasques complexes en un entorn multi-agent cooperatiu, dinàmic i amb incertesa. Totes aquestes aproximacions han demostrat la seva eficiència en experiments duts a terme en l'entorn de simulació RoboCup Rescue. / Distributed task allocation and coordination have been the focus of recent research in last years and these topics are the heart of multi-agent systems. Agents in these systems need to cooperate and consider the other agents in their actions and decisions. Moreover, agents may have to coordinate themselves to accomplish complex tasks that need more than one agent to be accomplished. These tasks may be so complicated that the agents may not know the location of them or the time they have before the tasks become obsolete. Agents may need to use communication in order to know the tasks in the environment, otherwise, it may take a long time to find the tasks into the scenario. Similarly, the distributed decisionmaking process may be even more complex if the environment is dynamic, uncertain and real-time. In this dissertation, we consider constrained cooperative multi-agent environments (dynamic, uncertain and real-time). In this regard, we propose two approaches that enable the agents to coordinate themselves. The first one is a semi-centralized mechanism based on combinatorial auction techniques and the main idea is minimizing the cost of assigned tasks from the central agent to the agent teams. This algorithm takes into account the tasks' preferences of the agents. These preferences are included into the bid sent by the agent. The second one is a completely decentralized scheduling approach. It permits agents schedule their tasks taking into account temporal tasks' preferences of the agents. In this case, the system's performance depends not only on the maximization or the optimization criterion, but also on the agents' capacity to adapt their schedule efficiently. Furthermore, in a dynamic environment, execution errors may happen to any plan due to uncertainty and failure of individual actions. Therefore, an indispensable part of a planning system is the capability of replanning. This dissertation is also providing a replanning approach in order to allow agents recoordinate his plans when the environmental problems avoid fulfil them. All these approaches have been carried out to enable the agents to efficiently allocate and coordinate all their complex tasks in a cooperative, dynamic and uncertain multi-agent scenario. All these approaches have demonstrated their effectiveness in experiments performed in the RoboCup Rescue simulation environment.

L'experiència de l'autor en la temàtica d'agents intel·ligents i la seva aplicació als robots que emulen el joc de futbol han donat el bagatge suficient per poder encetar i proposar la temàtica plantejada en aquesta tesi: com fer que un complicat robot pugui treure el màxim suc de l'autoconeixement de l'estructura de control inclosa al seu propi cos físic, i així poder cooperar millor amb d'altres agents per optimitzar el rendiment a l'hora de resoldre problemes de cooperació. Per resoldre aquesta qüestió es proposa incorporar la dinàmica del cos físic en les decisions cooperatives dels agents físics unificant els móns de l'automàtica, la robòtica i la intel·ligència artificial a través de la noció de capacitat: la capacitat vista com a entitat on els enginyers de control dipositen el seu coneixement, i a la vegada la capacitat vista com la utilitat on un agent hi diposita el seu autoconeixement del seu cos físic que ha obtingut per introspecció. En aquesta tesi es presenta l'arquitectura DPAA que s'organitza seguint una jerarquia vertical en tres nivells d'abstracció o mòduls control, supervisor i agent, els quals presenten una estructura interna homogènia que facilita les tasques de disseny de l'agent. Aquests mòduls disposen d'un conjunt específic de capacitats que els permeten avaluar com seran les accions que s'executaran en un futur. En concret, al mòdul de control (baix nivell d'abstracció) les capacitats consisteixen en paràmetres que descriuen el comportament dinàmic i estàtic que resulta d'executar un controlador determinat, és a dir, encapsulen el coneixement de l'enginyer de control. Així, a través dels mecanismes de comunicació entre mòduls aquest coneixement pot anar introduint-se als mecanismes de decisió dels mòduls superiors (supervisor i agent) de forma que quan els paràmetres dinàmics i estàtics indiquin que pot haver-hi problemes a baix nivell, els mòduls superiors es poden responsabilitzar d'inhibir o no l'execució d'algunes accions. Aquest procés top-down intern d'avaluació de la viabilitat d'executar una acció determinada s'anomena procés d'introspecció. Es presenten diversos exemples per tal d'il·lustrar com es pot dissenyar un agent físic amb dinàmica pròpia utilitzant l'arquitectura DPAA com a referent. En concret, es mostra tot el procés a seguir per dissenyar un sistema real format per dos robots en formació de comboi, i es mostra com es pot resoldre el problema de la col·lisió utilitzant les capacitats a partir de les especificacions de disseny de l'arquitectura DPAA. Al cinquè capítol s'hi exposa el procés d'anàlisi i disseny en un domini més complex: un grup de robots que emulen el joc del futbol. Els resultats que s'hi mostren fan referència a l'avaluació de la validesa de l'arquitectura per resoldre el problema de la passada de la pilota. S'hi mostren diversos resultats on es veu que és possible avaluar si una passada de pilota és viable o no. Encara que aquesta possibilitat ja ha estat demostrada en altres treballs, l'aportació d'aquesta tesi està en el fet que és possible avaluar la viabilitat a partir de l'encapsulament de la dinàmica en unes capacitats específiques, és a dir, és possible saber quines seran les característiques de la passada: el temps del xut, la precisió o inclòs la geometria del moviment del robot xutador. Els resultats mostren que la negociació de les condicions de la passada de la pilota és possible a partir de capacitats atòmiques, les quals inclouen informació sobre les característiques de la dinàmica dels controladors. La complexitat del domini proposat fa difícil comparar els resultats amb els altres treballs. Cal tenir present que els resultats mostrats s'han obtingut utilitzant un simulador fet a mida que incorpora les dinàmiques dels motors dels robots i de la pilota. En aquest sentit cal comentar que no existeixen treballs publicats sobre el problema de la passada en què es tingui en compte la dinàmica dels robots.El present treball permet assegurar que la inclusió de paràmetres dinàmics en el conjunt de les capacitats de l'agent físic permet obtenir un millor comportament col·lectiu dels robots, i que aquesta millora es deu al fet que en les etapes de decisió els agents utilitzen informació relativa a la viabilitat sobre les seves accions: aquesta viabilitat es pot calcular a partir del comportament dinàmic dels controladors. De fet, la definició de capacitats a partir de paràmetres dinàmics permet treballar fàcilment amb sistemes autònoms heterogenis: l'agent físic pot ser conscient de les seves capacitats d'actuació a través de mecanismes interns d'introspecció, i això permet que pugui prendre compromisos amb altres agents físics.

In the last decades, significant theoretical advances have been made on the field of distributed mulit-agent control theory. One of the most common systems that can be modelled as multi-agent systems are the so called formation control problems, in which a network of mobile agents is controlled to move towards a desired final formation. These problems additionally pose practical challenges, namely limited access to information about the global state of the system, which justify the use distributed and localized approaches for solving the control problem. The problem is further complicated if partial or no information is known about the dynamic model of the system. A widely used fundamental challenge of this approach in this setting is that the state-action space size scales exponentially with the number of agents, rendering the problem intractable for a large networks. This thesis presents a scalable and localized reinforcement learning approach to a traditional multi-agent formation control problem, with collision avoidance. A scalable reinforcement learning advantage actor critic algorithm is presented, based on previous work in the literature. Sub-optimal bounds are calculated for the accumulated reward and policy gradient localized approximations. The algorithm is tested on a two dimensional setting, with a network of mobile agents following simple integrator dynamics and stochastic localized policies. Neural networks are used to approximate the continuous value functions and policies. The formation control with collisions avoidance formulation and the algorithm presented show good scalability properties, with a polynomial increase in the number of function approximations parameters with number of agents. The reduced number of parameters decreases learning time for bigger networks, although the efficiency of computation is decreased compared to state of the art machine learning implementations. The policies obtained achieve probably safe trajectories although the lack of dynamic model makes it impossible to guarantee safety. / Under de senaste decennierna har betydande framsteg gjorts inom området för distribuerad mulit-agent reglerteori. Ett av de vanligaste systemen som kan modelleras som multiagentsystem är de så kallade formationskontrollproblemen, där ett nätverk av mobila agenter styrs för att röra sig mot en önskad slutlig formation. om systemets globala tillstånd, vilket motiverar användningen av distribuerade och lokaliserade tillvägagångssätt för att lösa det reglertekniska problemet. Problemet kompliceras ytterligare om delvis eller ingen information är känd om systemets dynamiska modell. Ett allmänt använt tillvägagångssätt för modellfri kontroll är reinforcement learning (RL). En grundläggande utmaning med detta tillvägagångssätt i den här miljön är att storleken på state-action utrymmet skalas exponentiellt med antalet agenter, vilket gör problemet svårlöst för ett stort nätverk. Detta examensarbete presenterar en skalbar och lokaliserad reinforcement learning metod på ett traditionellt reglertekniskt problem med flera agenter, med kollisionsundvikande. En reinforcement learning advantage actor critic algoritm presenteras, baserad på tidigare arbete i litteraturen. Suboptimala gränser beräknas för den ackumulerade belönings- och policygradientens lokaliserade approximationer. Algoritmen testas i en tvådimensionell miljö, med ett nätverk av mobila agenter som följer enkel integratordynamik och stokastiska lokaliserade policyer. Neurala nätverk används för att approximera de kontinuerliga värdefunktionerna och policyerna. Den presenterade formationsstyrningen med kollisionsundvikande formulering och algoritmen visar goda skalbarhetsegenskaper, med en polynomisk ökning av antalet funktionsapproximationsparametrar med antalet agenter. Det minskade antalet parametrar minskar inlärningstiden för större nätverk, även om effektiviteten i beräkningen minskar jämfört med avancerade maskininlärningsimplementeringar. De erhållna policyerna uppnår troligen säkra banor även om avsaknaden av dynamisk modell gör det omöjligt att garantera säkerheten. / En las últimas décadas, se han realizado importantes avances teóricos en el campo de la teoría del control multiagente distribuido. Uno de los sistemas más comunes que se pueden modelar como sistemas multiagente son los llamados problemas de control de formación, en los que se controla una red de agentes móviles para alcanzar una formación final deseada. Estos problemas plantean desafíos prácticos como el acceso limitado a la información del estado global del sistema, que justifican el uso de algoritmos distribuidos y locales para resolver el problema de control. El problema se complica aún más si solo se conoce información parcial o nada sobre el modelo dinámico del sistema. Un enfoque ampliamente utilizado para el control sin conocimiento del modelo dinámico es el reinforcement learning (RL). Un desafío fundamental de este método en este entorno es que el tamaño de la acción y el estado aumenta exponencialmente con la cantidad de agentes, lo que hace que el problema sea intratable para una red grande. Esta tesis presenta un algoritmo de RL escalable y local para un problema tradicional de control de formación con múltiples agentes, con prevención de colisiones. Se presenta un algoritmo “advantage actor-”critic, basado en trabajos previos en la literatura. Los límites subóptimos se calculan para las aproximaciones locales de la función Q y gradiente de la política. El algoritmo se prueba en un entorno bidimensional, con una red de agentes móviles que siguen una dinámica de integrador simple y políticas estocásticas localizadas. Redes neuronales se utilizan para aproximar las funciones y políticas de valor continuo. La formulación de del problema de formación con prevención de colisiones y el algoritmo presentado muestran buenas propiedades de escalabilidad, con un aumento polinómico en el número de parámetros con el número de agentes. El número reducido de parámetros disminuye el tiempo de aprendizaje para redes más grandes, aunque la eficiencia de la computación disminuye en comparación con las implementaciones de ML de última generación. Las politicas obtenidas alcanzan trayectorias probablemente seguras, aunque la falta de un modelo dinámico hace imposible garantizar la completa prevención de colisiones. / A les darreres dècades, s'han realitzat importants avenços teòrics en el camp de la teoria del control multiagent distribuït. Un dels sistemes més comuns que es poden modelar com a sistemes multiagent són els anomenats problemes de control de formació, en els què es controla una xarxa d'agents mòbils per assolir una formació final desitjada. Aquests problemes plantegen reptes pràctics com l'accés limitat a la informació de l'estat global del sistema, que justifiquen l'ús d'algorismes distribuïts i locals per resoldre el problema de control. El problema es complica encara més si només es coneix informació parcial sobre el model dinàmic del sistema. Un mètode àmpliament utilitzat per al control sense coneixement del model dinàmic és el reinforcement learning (RL). Un repte fonamental d'aquest mètode en aquest entorn és que la mida de l'acció i l'estat augmenta exponencialment amb la quantitat d'agents, cosa que fa que el problema sigui intractable per a una xarxa gran. Aquesta tesi presenta un algorisme de RL escalable i local per a un problema tradicional de control de formació amb múltiples agents, amb prevenció de col·lisions. Es presenta un algorisme “advantage actor-”critic, basat en treballs previs a la literatura. Els límits subòptims es calculen per a les aproximacions locals de la funció Q i gradient de la política.’ Lalgoritme es prova en un entorn bidimensional, amb una xarxa ’dagents mòbils que segueixen una dinàmica ’dintegrador simple i polítiques estocàstiques localitzades. Xarxes neuronals s'utilitzen per aproximar les funcions i les polítiques de valor continu. La formulació del problema de formació amb prevenció de col·lisions i l'algorisme presentat mostren bones propietats d'escalabilitat, amb un augment polinòmic en el nombre de paràmetres amb el nombre d'agents. El nombre reduït de paràmetres disminueix el temps d'aprenentatge per a les xarxes més grans, encara que l'eficiència de la computació disminueix en comparació amb les implementacions de ML d'última generació. Les polítiques obtingudes aconsegueixen trajectòries probablement segures, tot i que la manca d'un model dinàmic fa impossible garantir la prevenció completa de col·lisions.