Planning optimal paths for large numbers of robots is computationally expensive. In this thesis, we present a new framework for multirobot path planning called subdimensional expansion, which initially plans for each robot individually, and then coordinates motion among the robots as needed. More specifically subdimensional expansion initially creates a one-dimensional search space embedded in the joint configuration space of the multirobot system. When the search space is found to be blocked during planning by a robot-robot collision, the dimensionality of the search space is locally increased to ensure that an alternative path can be found. As a result, robots are only coordinated when necessary, which reduces the computational cost of finding a path. Subdimensional expansion is a exible framework that can be used with multiple planning algorithms. For discrete planning problems, subdimensional expansion can be combined with A* to produce the M* algorithm, a complete and optimal multirobot path planning problem. When the configuration space of individual robots is too large to be explored effectively with A*, subdimensional expansion can be combined with probabilistic planning algorithms to produce sRRT and sPRM. M* is then extended to solve variants of the multirobot path planning algorithm. We present the Constraint Manifold Subsearch (CMS) algorithm to solve problems where robots must dynamically form and dissolve teams with other robots to perform cooperative tasks. Uncertainty M* (UM*) is a variant of M* that handles systems with probabilistic dynamics. Finally, we apply M* to multirobot sequential composition. Results are validated with extensive simulations and experiments on multiple physical robots.

International Telemetering Conference Proceedings / October 18-21, 2004 / Town & Country Resort, San Diego, California / In this paper we propose an open multi-robot architecture that dramatically reduces the time to deployment and increases the utility value to the mainstream non-technical user. We describe a multi-robot behavior-based coordination architecture and argue its suitability in the context of general-purpose robot teams operating in dynamic and unpredictable environments. We then formalize and describe a command fusion module for the coordination of high-level behaviors of the system. The command fusion module is interfaced to our middle-ware/compiler that generates behavior selection tips from a user specified abstract description of a scenario. Finally, we utilize an example search and rescue scenario to illustrate the overall process and give preliminary results of the experiments performed on actual robots.

A novel methodology is presented for organizing swarms of robots into a formation utilizing artificial potential fields generated from normal and sigmoid functions. These functions construct the surface which swarm members travel on, controlling the overall swarm geometry and the individual member spacing. Nonlinear limiting functions are defined to provide tighter swarm control by modifying and adjusting a set of control variables forcing the swarm to behave according to set constraints, formation and member spacing. The swarm function and limiting functions are combined to control swarm formation, orientation, and swarm movement as a whole. Parameters are chosen based on desired formation as well as user defined constraints. This approach compared to others, is simple, computationally efficient, scales well to different swarm sizes, to heterogeneous systems, and to both centralized and decentralized swarm models. Simulation results are presented for a swarm of four and ten particles following circle, ellipse and wedge formations. Experimental results are also included with a swarm of four unmanned ground vehicles (UGV) as well as UGV swarm and unmanned aerial vehicle (UAV) coordination.

Distributed Mobile Robotics (DMR) is a multidisciplinary research area with many open research questions. This is a survey of the state of the art in Distributed Mobile Robotics research. DMR is sometimes referred to as cooperative robotics or multi-robotic systems. DMR is about how multiple robots can cooperate to achieve goals and complete tasks better than single robot systems. It covers architectures, communication, learning, exploration and many other areas presented in this master thesis. / Uppsatsen är en brett spektrum på vilken forskning som pågår rörande distribuerad mobil robotik, dvs hur många robotar kan samverka för att lösa uppgifter. / Adress: Victor Adolfsson Folkparksvägen 12:24 372 38 Ronneby Telefon: 0457-171 42 Mobil: 0709-441389

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.