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.

L’objectif de ce travail est de permettre à une équipe de robots autonomeshétérogènes d’effectuer une mission complexe dans un environnement réel et sous contraintede communication. Cette thèse a donc consisté à créer et à valider une architecturedistribuée à bord des robots et intégrant planification, supervision de l’exécution du planet réparation de ce plan suite à l’occurrence d’aléas. Ce manuscrit présente la conceptiond’un algorithme de planification hybride, dénommé HiPOP, utilisé pour calculer un planinitial, avant le début de la mission, et pour réparer le plan en cours de mission quandun événement perturbateur survient. Il présente aussi la conception d’un algorithme desupervision, dénommé METAL, utilisé pour suivre l’exécution du plan sur chaque robot et,le cas échéant, faisant appel à HiPOP pour réparer le plan. Ces deux algorithmes ont étéimplémentés et ont permis de réaliser des missions de surveillance allant jusqu’à impliquer12 robots, à la fois en simulation et avec de vrais robots. / The goal of this work is to enable a team of heterogeneous autonomous robotsto perform a complex mission in a real environment with communication constraints. Thisapproach was therefore to create and validate a distributed embedded architecture ableto plan, to monitor the execution of a plan and to repair a plan when an unexpectedevent occurs. This document shows the conception of an hybrid planning algorithm, namedHiPOP, used to compute initial plans before the beginning of the mission and to repair theplan during the mission when something unexpected happens. It also shows the conceptionof a monitoring algorithm, named METAL, used to monitor the execution of the planon each robot and, when needed, which calls HiPOP to repair the plan. Both algorithmswere implemented and used to carry out surveillance missions up to 12 robots, both insimulation and in a real life scenario.

Cette thèse s'inscrit dans le cadre du projet Cart-O-Matic mis en place pour participer au défi CAROTTE (CArtographie par ROboT d'un TErritoire) organisé par l'ANR et la DGA. Le but de ce défi est de construire une carte en deux et trois dimensions et de localiser des objets dans un environnement inconnu statique de type appartement. Dans ce contexte, l'utilisation de plusieurs robots est avantageuse car elle permet d'augmenter l'efficacité en temps de la couverture. Cependant, comme nous le montrons, le gain est conditionné par le niveau de coopération entre les robots. Nous proposons une stratégie de coopération pour une cartographie multirobot efficace. Une difficulté est la construction d'une carte commune, nécessaire, afin que chaque robot puisse connaître les zones de l'environnement encore inexplorées. Pour obtenir une bonne coopération avec un algorithme simple nous proposons une technique de déploiement fondée sur le choix d'une cible par chaque robot. L'algorithme proposé cherche à distribuer les robots vers différentes directions. Il est fondé sur le calcul partiel de champs de potentiels permettant à chaque robot de calculer efficacement son prochain objectif. En complément de ces contributions théoriques, nous décrivons le système robotique complet mis en oeuvre au sein de l'équipe Cart-O-Matic ayant permis de remporter la dernière édition du défi CAROTTE / This thesis is part of Cart-O-Matic project set up to participate in the challenge CARROTE (mapping of a territory) organized by the ANR and the DGA. The purpose of this challenge is to build 2D and 3D maps of a static unknown 'apartment-like' environment. In this context, the use of several robots is advantageous because it increases the time efficiency to discover fully the environment. However, as we show, the gain is determined by the level of cooperation between robots. We propose a cooperation strategy for efficient multirobot mapping. A difficulty is the construction of a common map, necessary so that each robot can know the areas of the environment which remain unexplored.For a good cooperation with a simple algorithm we propose a deployment technique based on the choice of a target by each robot. The proposed algorithm tries to distribute the robots in different directions. It is based on calculation of the partial potential fields allowing each robot to compute efficiently its next target. In addition to these theoretical contributions, we describe the complete robotic system implemented in the Cart-O-Matic team that helped win the last edition of the CARROTE challenge

Ces dernières années, les engins robotisés n’ont cessé d’améliorer leur autonomie dans le domaine de la décision. Désormais, pour ne citer que l’exemple de véhicules aériens, nombre de drones sont largement capables, sans intervention d’un opérateur humain, de décoller, suivre un itinéraire en activant divers capteurs à des moments précis, atterrir en un lieu spécifié, suivre une cible, patrouiller sur une zone... Une des étapes suivantes consiste à faire collaborer une équipe de véhicules autonomes, de nature hétérogène (aériens, terrestres, marins...) afin de leur permettre d’accomplir des missions plus complexes. L’aspect dynamique de l’environnement réel, la non disponibilité à tout instant des moyens de communication, la coordination nécessaire des véhicules,de conceptions parfois différentes, dans l’exécution de certaines parties d’un plan de mission, sont autant d’obstacles à surmonter. Ce travail tente non seulement d’apporter quelques éléments de réponse face à ces difficultés, mais consiste aussi en la mise en place concrète d’un superviseur haut niveau, capable de gérer l’exécution d’une mission par une équipe de véhicules autonomes hétérogènes, où le rôle de l’opérateur humain est volontairement réduit. Nous décrivons dans ce mémoire l’architecture distribuée que nous avons choisi de mettre en œuvre pour répondre à ce problème. Il s’agit d’un superviseur, réparti à bord des véhicules autonomes, interfacé avec leur architecture locale et en charge de l’exécution de la mission d’équipe. Nous nous intéressons également à la formalisation des connaissances nécessaires au déroulement de cette mission, afin d’améliorer l’interopérabilité des véhicules de l’équipe, mais aussi pour expliciter les relations entre modèles décisionnels abstraits et réalité d’exécution concrète. Le superviseur est capable de réagir face aux aléas qui vont se produire dans un environnement dynamique. Nous présentons ainsi dans un second temps les stratégies mises en place pour parvenir à les détecter au mieux, ainsi que la façon dont nous procédons pour réparer partiellement ou totalement le plan de mission initial, afin de remplir les objectifs initiaux. Nous nous basons notamment sur la nature hiérarchique du plan de mission, mais aussi sur celle de la structure de sous-équipes que nous proposons de construire. Enfin, nous présentons quelques résultats obtenus expérimentalement, sur des missions simulées et des scénarios réels, notamment ceux du Programme d’Etudes Amont Action dans lequel s’inscrivent ces travaux de thèse. / Many autonomous robots with specific control oriented architectures have already been developed worldwide.The advance of the work in this field has led researchers wonder for many years to what extent robots would be able to be integrated into a team consisting of autonomous and heterogeneous vehicles with complementary functionalities. However, robot cooperation in a real dynamic environment under unreliable communication conditions remains challenging, especially if these autonomous vehicles have different individual control architectures.In order to address this problem, we have designed a decision software architecture, distributed on each vehicle.This decision layer aims at managing execution and at increasing the fault tolerance of the global system. The mission plan is assumed to be hierarchically structured. ln case of failure detection, the plan repair is done as locally as possible, based on the hierarchical organization.This allows us to restrict message exchange only between the vehicles concerned by the repair process. Knowledge formalisation is also a part of the study permitting the improvement of interoperability between team members. It also provides relevant information all along mission execution, from initial planning computation to plan repair in this multirobot context. The feasibility of the system has been evaluated by simulations and real experiments thanks to the Action project (http://action.onera.fr/welcome/).

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.

This dissertation describes the evolution of the different local magnetic field generating systems for independent actuation of multiple microrobots. A description of the developed hardware, system characterization tests, and experimental results are presented. The system is designed for automated control of multiple microrobots. Finally, sample micromanipulation tasks are demonstrated using the new microrobot design, showcasing its improved manipulation capabilities.<br>First, a mm-scale local magnetic field generating system designed for single layer coils is used to control 3.175 mm size N52 magnets as robots independently in the workspace. The controller used a set of local equilibrium points that were generated from a sequence of coil currents around the robots from one state to the next. The robots moved along paths computed through optimal control synthesis approach to solve complex micromanipulation tasks captured by global LTL formulas. However, the use of local equilibrium points as the states limited the motion of the robot in the workspace to simple tasks. Also, the interaction between the robots limited the robots to stay within far distances with each other. Hence a larger workspace based coil is designed to actuate up to four mm-scale robots in the workspace.<br><br>To improve the resolution of motion of these robots in the workspace, the mm-scale coils are modeled extensively. The forces generated by various coil combinations of the array are modeled and solutions for different actuation force directions are discovered for different locations in the coil. A path planning problem is formulated as a Markov decision process that solves a policy to reach a goal from any location in the workspace. The MDP formulation is also expanded to work when other robots are present in the workspace. The formulation considers the interaction force between the robots and changes the policy to reach the goal location which reduces in the uncertainty of motion of the robot in the presence of interactions from other robots in the workspace.<br><br>The mm-scale coils are difficult to scale down for microrobotic applications and hence a new microscale local magnetic field system was designed. A new microscale local magnetic field system which consisted of two 8 × 8 array of coils aligned in two axes in two layers of a PCB was designed which could actuate robots as small as 1 mm in the plane. The microcoils in the second layer are also able to generate sufficient magnetic field gradients in the workspace, while the traces below it are spaced adequately to eliminate their influence in the workspace. A new microrobot design also enabled the orientation control of the microrobot for performing micromanipulation tasks. However, only two robots could be independently actuated in this workspace due to interaction between the robots.<br><br>In pursuit of actuation smaller and multiple robots in a small workspace, a serpentine coil based local magnetic field generating system was designed to control of the motion of magnets as small as 250 µm. The net size of the robot is 750 µm to enable orientation control and prevent tipping during motion. This system is capable of simultaneous independent closed loop control of up to 4 microrobots. The motion of the robot using the coils resembled that of a stepper motor which enabled the use of sine-cosine functions to specify currents in the coils for smooth motion of the<br>microrobot in the workspace. The experiments demonstrated the capability of the microrobot and platform to simultaneously actuate up to four robots independently and successfully perform manipulation tasks. The ability to control the orientation of the magnet is finally demonstrated that has improved ability to perform manipulation tasks.<br><br>

Understanding machine vision can certainly improve our understanding of artificial intelligence as vision happens to be one of the basic intellectual activities of living beings. Since the notion of computation unifies the concept of a machine, computer vision can be understood as an application of modern approaches for achieving artificial intelligence, like machine learning and cognitive psychology. Computer vision mainly involves processing of different types of sensor data resulting in "perception of machines". Perception of machines plays a very important role in several artificial intelligence applications with sensors. There are numerous practical situations where we acquire sensor data for e.g. from mobile robots, security cameras, service and recreational robots. Making sense of this sensor data is very important so that we have increased automation in using the data. Tools from image processing, shape analysis and probabilistic inferences i.e. learning theory form the artillery for current generation of computer vision researchers. In my thesis I will address some of the most annoying components of two important open problems viz. object recognition and autonomous navigation that remain central in robotic, or in other words computational, intelligence. These problems are concerned with inducing computers, the abilities to recognize and navigate similar to those of humans. Object boundaries are very useful descriptors for recognizing objects. Extracting boundaries from real images has been a notoriously open problem for several decades in the vision community. In the first part I will present novel techniques for extracting object boundaries. The techniques are based on practically successful state-of-the-art Bayesian filtering framework, well founded geometric properties relating boundaries and skeletons and robust high-level shape analyses Acquiring global maps of the environments is crucial for robots to localize and be able to navigate autonomously. Though there has been a lot of progress in achieving autonomous mobility, for e.g. as in DARPA grand-challenges of 2005 and 2007, the mapping problem itself remains to be unsolved which is essential for robust autonomy in hard cases like rescue arenas and collaborative exploration. In the second part I will present techniques for merging maps acquired by multiple and single robots. We developed physics-based energy minimization techniques and also shape based techniques for scalable merging of maps. Our shape based techniques are a product of combining of high-level vision techniques that exploit similarities among maps and strong statistical methods that can handle uncertainties in Bayesian sense. / Computer and Information Science

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 &#61630;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.

Les travaux de cette thèse adressent la problématique de la coopération aéro-terrestre pour la cartographie de l’espace navigable. La nécessité d’une carte pour la navigation et la planification de chemins pour les robots terrestres n’est plus à prouver. L’utilisation d’une coopération aéro-terrestre pour créer une carte navigable à destination du robot terrestre a plusieurs intérêts. Premièrement, le drone peut cartographier rapidement une zone grâce à son champ de vision étendu et ses capacités de déplacement. Deuxièmement, la fusion des cartes créées par ces deux agents permet de tirer le meilleur profit des deux points de vue : la cohérence de la vue aérienne globale et la précision de la vue terrestre locale. Pour répondre à cette problématique, nous proposons une méthode qui s’appuie sur la création de cartes hybrides et leur fusion. Les cartes sont construites en utilisant le squelette de l’espace navigable terrestre comme support d’un graphe contenant également des informations métriques locales de l’environnement. La mise en correspondance des cartes aérienne et terrestre s’effectue à l’aide d’un appariement point à point déterminé grâce à une mesure de dissimilarité appropriée. Cette dernière est définie pour répondre aux critères d’invariance et de discriminance dans ce contexte. La mise en correspondance est ensuite utilisée pour fusionner les cartes entre elles. Les cartes fusionnées peuvent être utilisées par le robot au sol pour effectuer sa mission. Elles permettent également de propager des informations telles que des coordonnées GPS à des robots et dans des lieux où ce dispositif n’est pas disponible. Des expérimentations en environnements virtuels et réels sont réalisées pour valider cette approche et en tracer les perspectives. / This work aims to study the problem of air-ground robotic cooperation for collaborative traversability mapping. The need for a map for navigation and path planning for terrestrial robots is no longer to be proven. The use of air-ground cooperation to create a navigable map for the ground robots has several interests. First, the drone can quickly map an area through its large field of vision and traveling capabilities. Second, the fusion of maps based on these two agents makes it possible to draw the best benefits from both points of views: the coherence of the global aerial view and the accuracy of the local ground view. To answer this problem, we propose a method that relies on the construction of a unified model of hybrid maps and their fusion.The maps are built using the skeleton of the traversability space as a support for graphs also containing local metric and potentialy semantic information of the environment. The maching of aerial and ground maps is done using a point to point correlation based on an appropriate dissimilarity measure. This measure is defined to meet invariance and discriminance criteria. The matching is then used to merge the maps into an augmented traversability map. The merged maps can be used by the ground robot to perform its mission. They also make it possible to deploy information such as GPS coordinates to robots in GPS denied environments. Experiments in virtual and real world environments have been carried out to validate this approach and map out future perspetives.