With the promise to shape the future of industry, multi-agent robotic technologies have the potential to change many aspects of daily life. Over the coming decade, they are expected to impact transportation systems, military applications such as reconnaissance and surveillance, search-and-rescue operations, or space missions, as well as provide support to emergency first responders. Motivated by the latest developments in the field of robotics, this thesis contributes to the evolution of the future generation of multi-agent robotic systems as they become smarter, more accurate, and diversified in terms of applications. But in order to achieve these goals, the individual agents forming cooperative robotic systems need to be specialized in what they can accomplish, while ensuring accuracy and preserving the ability to perform diverse tasks. This thesis addresses the problem of task allocation in swarm robotics in the specific context where specialized capabilities of the individual agents are considered. Based on the assumption that each individual agent possesses specialized functional capabilities and that the expected tasks, which are distributed in the surrounding environment, impose specific requirements, the proposed task allocation mechanisms are formulated in two different spaces. First, a rudimentary form of the team members’ specialization is formulated as a cooperative control problem embedded in the agents’ dynamics control space. Second, an advanced formulation of agents’ specialization is defined to estimate the individual agents’ task allocation probabilities in a dedicated specialization space, which represents the core contribution of this thesis to the advancement and practice in the area of swarm robotics. The original task allocation process formulated in the specialization space evolves through four stages of development. First, a task features recognition stage is conceptually introduced to leverage the output of a sensing layer embedded in robotic agents to drive the proposed task allocation scheme. Second, a matching scheme is developed to best match each agent’s specialized capabilities with the corresponding detected tasks. At this stage, a general binary definition of agents’ specialization serves as the basis for task-agent association. Third, the task-agent matching scheme is expanded to an innovative probabilistic specialty-based task-agent allocation framework to generalize the concept and exploit the potential of agents’ specialization consideration. Fourth, the general framework is further refined with a modulated definition of the agents’ specialization based on their mechanical, physical structure, and embedded resources. The original framework is extended and a prioritization layer is also introduced to improve the system’s response to complex tasks that are characterized based on the recognition of multiple classes. Experimental validation of the proposed specialty-based task allocation approach is conducted in simulation and on real-world experiments, and the results are presented and discussed in light of potential applications to demonstrate the effectiveness and efficiency of the proposed framework.

The security of multi-robot systems is critical in various applications such as patrol, transportation, and search and rescue operations, where they face threats from adversaries attempting to gain control of the robots. These compromised robots are significant threats as they allow attackers to steer robots towards forbidden areas without being detected, potentially causing harm or compromising the mission. To address this problem, we propose a resilient planning, task assignment, and control framework. The proposed framework builds a multi-robot plan where robots are designed to get close enough to other robots according to a co-observation schedule, in order to mutually check for abnormal behaviors. For the first part of the thesis, we propose an optimal trajectory solver based on the alternating direction method of multipliers (ADMM) to generate multi-agent trajectories that satisfy spatio-temporal requirements introduced by the co-observation schedules. As part of the formulation, we provide a new reachability constraint to guarantee that, despite adversarial movement by the attacker, a compromised robot cannot reach forbidden areas between co-observations without being detected. In the second part of the thesis, to further enhance the system's performance, reliability, and robustness, we propose to deploy multiple robots on each route to form sub-teams. A new cross-trajectory co-observation scheme between sub-teams is introduced that preserves the optimal unsecured trajectories. The new planner ensures that at least one robot in each sub-team sticks to the planned trajectories, while sub-teams can constantly exchange robots during the task introducing additional co-observations that can secure originally unsecured routes. We show that the planning of cross-trajectory co-observations can be transformed into a network flow problem and solved using traditional linear program technique. In the final part of the thesis, we show that the introduction of sub-teams also improves the multi-robot system's robustness to unplanned situations, allowing servicing unplanned online events without breaking the security requirements. This is achieved by a distributed task assignment algorithm based on consensus ADMM which can handle tasks with different priorities. The assignment result and security requirements are formulated as spatio-temporal schedules and guaranteed through control barrier function (CBF) based controls.

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

<p>This thesis consists of four independent papers concerningthe control of mobile robots in the context of obstacleavoidance and formation keeping.</p><p>The first paper describes a new theoreticallyv erifiableapproach to obstacle avoidance. It merges the ideas of twoprevious methods, with complementaryprop erties, byusing acombined control Lyapunov function (CLF) and model predictivecontrol (MPC) framework.</p><p>The second paper investigates the problem of moving a fixedformation of vehicles through a partiallykno wn environmentwith obstacles. Using an input to state (ISS) formulation theconcept of configuration space obstacles is generalized toleader follower formations. This generalization then makes itpossible to convert the problem into a standard single vehicleobstacle avoidance problem, such as the one considered in thefirst paper. The properties of goal convergence and safetyth uscarries over to the formation obstacle avoidance case.</p><p>In the third paper, coordination along trajectories of anonhomogenuos set of vehicles is considered. Byusing a controlLyapunov function approach, properties such as boundedformation error and finite completion time is shown.</p><p>Finally, the fourth paper applies a generalized version ofthe control in the third paper to translate,rotate and expanda formation. It is furthermore shown how a partial decouplingof formation keeping and formation mission can be achieved. Theapproach is then applied to a scenario of underwater vehiclesclimbing gradients in search for specific thermal/biologicalregions of interest. The sensor data fusion problem fordifferent formation configurations is investigated and anoptimal formation geometryis proposed.</p><p><b>Keywords:</b>Mobile Robots, Robot Control, ObstacleAvoidance, Multirobot System, Formation Control, NavigationFunction, Lyapunov Function, Model Predictive Control, RecedingHorizon Control, Gradient Climbing, Gradient Estimation.</p>

This thesis consists of four independent papers concerningthe control of mobile robots in the context of obstacleavoidance and formation keeping. The first paper describes a new theoreticallyv erifiableapproach to obstacle avoidance. It merges the ideas of twoprevious methods, with complementaryprop erties, byusing acombined control Lyapunov function (CLF) and model predictivecontrol (MPC) framework. The second paper investigates the problem of moving a fixedformation of vehicles through a partiallykno wn environmentwith obstacles. Using an input to state (ISS) formulation theconcept of configuration space obstacles is generalized toleader follower formations. This generalization then makes itpossible to convert the problem into a standard single vehicleobstacle avoidance problem, such as the one considered in thefirst paper. The properties of goal convergence and safetyth uscarries over to the formation obstacle avoidance case. In the third paper, coordination along trajectories of anonhomogenuos set of vehicles is considered. Byusing a controlLyapunov function approach, properties such as boundedformation error and finite completion time is shown. Finally, the fourth paper applies a generalized version ofthe control in the third paper to translate,rotate and expanda formation. It is furthermore shown how a partial decouplingof formation keeping and formation mission can be achieved. Theapproach is then applied to a scenario of underwater vehiclesclimbing gradients in search for specific thermal/biologicalregions of interest. The sensor data fusion problem fordifferent formation configurations is investigated and anoptimal formation geometryis proposed. Keywords:Mobile Robots, Robot Control, ObstacleAvoidance, Multirobot System, Formation Control, NavigationFunction, Lyapunov Function, Model Predictive Control, RecedingHorizon Control, Gradient Climbing, Gradient Estimation. / QC 20111121

In this thesis, we examine algorithms for the division of labour in a group of robot. The algorithms make no use of direct communication. Instead, they are based only on the interactions among the robots and between the group and the environment.<p><p>Division of labour is the mechanism that decides how many robots shall be used to perform a task. The efficiency of the group of robots depends in fact on the number of robots involved in a task. If too few robots are used to achieve a task, they might not be successful or might perform poorly. If too many robots are used, it might be a waste of resources. The number of robots to use might be decided a priori by the system designer. More interestingly, the group of robots might autonomously select how many and which robots to use. In this thesis, we study algorithms of the latter type.<p><p>The robotic literature offers already some solutions, but most of them use a form of direct communication between agents. Direct, or explicit, communication between the robots is usually considered a necessary condition for co-ordination. Recent studies have questioned this assumption. The claim is based on observations of animal colonies, e.g. ants and termites. They can effectively co-operate without directly communicating, but using indirect forms of communication like stigmergy. Because they do not rely on communication, such colonies show robust behaviours at group level, a condition that one wishes also for groups of robots. Algorithms for robot co-ordination without direct communication have been proposed in the last few years. They are interesting not only because they are a stimulating intellectual challenge, but also because they address a situation that might likely occur when using robots for real-world out-door applications. Unfortunately, they are still poorly studied.<p><p>This thesis helps the understanding and the development of such algorithms. We start from a specific case to learn its characteristics. Then we improve our understandings through comparisons with other solutions, and finally we port everything into another domain.<p><p>We first study an algorithm for division of labour that was inspired by ants' foraging. We test the algorithm in an application similar to ants' foraging: prey retrieval. We prove that the model used for ants' foraging can be effective also in real conditions. Our analysis allows us to understand the underlying mechanisms of the division of labour and to define some way of measuring it.<p><p>Using this knowledge, we continue by comparing the ant-inspired algorithm with similar solutions that can be found in the literature and by assessing their differences. In performing these comparisons, we take care of using a formal methodology that allows us to spare resources. Namely, we use concepts of experiment design to reduce the number of experiments with real robots, without losing significance in the results.<p><p>Finally, we apply and port what we previously learnt into another application: Sensor/Actor Networks (SANETs). We develop an architecture for division of labour that is based on the same mechanisms as the ants' foraging model. Although the individuals in the SANET can communicate, the communication channel might be overloaded. Therefore, the agents of a SANET shall be able to co-ordinate without accessing the communication channel. / Doctorat en sciences appliquées / info:eu-repo/semantics/nonPublished

Malgré de nombreuses années de travail en robotique, il existe toujours un manque d’architecture logicielle et de middleware stables pour les systèmes multi-robot. Un intergiciel robotique devrait être conçu pour faire abstraction de l’architecture matérielle de bas niveau, faciliter la communication et l’intégration de nouveaux logiciels. Cette thèse se concentre sur le middleware pour systèmes multi-robot et sur la façon dont nous pouvons améliorer les frameworks existantes dans un contexte multi-robot en ajoutant des services de coordination multi-robot, des outils de développement et de déploiement massif. Nous nous attendons à ce que les robots soient de plus en plus utiles car ils peuvent tirer profit des données provenant d’autres périphériques externes dans leur prise de décision au lieu de simplement réagir à leur environnement local (capteurs, robots coopérant dans une flotte, etc.). Cette thèse évalue d’abord l’un des intergiciels les plus récents pour robot(s) mobile(s), Robot operating system (ROS), suivi par la suite d’un état de l’art sur les middlewares couramment utilisés en robotique. Basé sur les conclusions, nous proposons une contribution originale dans le contexte multi-robots, appelé SDfR (Service discovery for Robots), un mécanisme de découverte des services pour les robots. L’objectif principal est de proposer un mécanisme permettant aux robots de garder une trace des pairs accessibles à l’intérieur d’une flotte tout en utilisant une infrastructure ad-hoc. A cause de la mobilité des robots, les techniques classiques de configuration de réseau pair à pair ne conviennent pas. SDfR est un protocole hautement dynamique, adaptatif et évolutif adapté du protocole SSDP (Simple Service Discovery Protocol). Nous conduisons un ensemble d’expériences, en utilisant une flotte de robots Turtlebot, pour mesurer et montrer que le surdébit de SDfR est limité. La dernière partie de la thèse se concentre sur un modèle de programmation basé sur un automate temporisé. Ce type de programmation a l’avantage d’avoir un modèle qui peut être vérifié et simulé avant de déployer l’application sur de vrais robots. Afin d’enrichir et de faciliter le développement d’applications robotiques, un nouveau modèle de programmation basé sur des automates à états temporisés est proposé, appelé ROSMDB (Robot Operating system Model Driven Behaviour). Il fournit une vérification de modèle lors de la phase de développement et lors de l’exécution. Cette contribution est composée de plusieurs composants : une interface graphique pour créer des modèles basés sur un automate temporisé, un vérificateur de modèle intégré basé sur UPPAAL et un générateur de squelette de code. Enfin, nous avons effectué deux expériences : une avec une flotte de drones Parrot et l’autre avec des Turtlebots afin d’illustre le modèle proposé et sa capacité à vérifier les propriétés. / Despite many years of work in robotics, there is still a lack of established software architecture and middleware for multi-robot systems. A robotic middleware should be designed to abstract the low-level hardware architecture, facilitate communication and integration of new software. This PhD thesis is focusing on middleware for multi-robot system and how we can improve existing frameworks for fleet purposes by adding multi-robot coordination services, development and massive deployment tools. We expect robots to be increasingly useful as they can take advantage of data pushed from other external devices in their decision making instead of just reacting to their local environment (sensors, cooperating robots in a fleet, etc). This thesis first evaluates one of the most recent middleware for mobile robot(s), Robot operating system (ROS) and continues with a state of the art about the commonly used middlewares in robotics. Based on the conclusions, we propose an original contribution in the multi-robot context, called SDfR (Service discovery for Robots), a service discovery mechanism for Robots. The main goal is to propose a mechanism that allows highly mobile robots to keep track of the reachable peers inside a fleet while using an ad-hoc infrastructure. Another objective is to propose a network configuration negotiation protocol. Due to the mobility of robots, classical peer to peer network configuration techniques are not suitable. SDfR is a highly dynamic, adaptive and scalable protocol adapted from Simple Service Discovery Protocol (SSDP). We conduced a set of experiments, using a fleet of Turtlebot robots, to measure and show that the overhead of SDfR is limited. The last part of the thesis focuses on programming model based on timed automata. This type of programming has the benefits of having a model that can be verified and simulated before deploying the application on real robots. In order to enrich and facilitate the development of robotic applications, a new programming model based on timed automata state machines is proposed, called ROSMDB (Robot Operating system Model Driven Behaviour). It provides model checking at development phase and at runtime. This contribution is composed of several components: a graphical interface to create models based on timed automata, an integrated model checker based on UPPAAL and a code skeleton generator. Moreover, a ROS specific framework is proposed to verify the correctness of the execution of the models and to trigger alerts. Finally, we conduct two experiments: one with a fleet of Parrot drones and second with Turtlebots in order to illustrates the proposed model and its ability to check properties.

The purpose of information acquisition for data and information fusion is to provide relevant and timely information. The acquired information is integrated (or fused) to estimate the state of some environment. The success of information acquisition can be measured in the quality of the environment state estimates generated by the data and information fusion process. In this thesis, we introduce and set out to characterise the concept of large-scale information acquisition. Our interest in this subject is justified both by the identified lack of research on a holistic view on data and information fusion, and the proliferation of networked sensors which promises to enable handy access to a multitude of information sources. We identify a number of properties that could be considered in the context of large-scale information acquisition. The sensors used could be large in number, heterogeneous, complex, and distributed. Also, algorithms for large-scale information acquisition may have to deal with decentralised control and multiple and varying objectives. In the literature, a process that realises information acquisition is frequently denoted sensor management. We, however, introduce the term perception management instead, which encourages an agent perspective on information acquisition. Apart from explictly inviting the wealth of agent theory research into the data and information fusion research, it also highlights that the resource usage of perception management is constrained by the overall control of a system that uses data and information fusion. To address the challenges posed by the concept of large-scale information acquisition, we present a framework which highlights some of its pertinent aspects. We have implemented some important parts of the framework. What becomes evident in our study is the innate complexity of information acquisition for data and information fusion, which suggests approximative solutions. We, furthermore, study one of the possibly most important properties of large-scale information acquisition, decentralised control, in more detail. We propose a recurrent negotiation protocol for (decentralised) multi-agent coordination. Our approach to the negotiations is from an axiomatic bargaining theory perspective; an economics discipline. We identify shortcomings of the most commonly applied bargaining solution and demonstrate in simulations a problem instance where it is inferior to an alternative solution. However, we can not conclude that one of the solutions dominates the other in general. They are both preferable in different situations. We have also implemented the recurrent negotiation protocol on a group of mobile robots. We note some subtle difficulties with transferring bargaining solutions from economics to our computational problem. For instance, the characterising axioms of solutions in bargaining theory are useful to qualitatively compare different solutions, but care has to be taken when translating the solution to algorithms in computer science as some properties might be undesirable, unimportant or risk being lost in the translation. / QC 20100903

This thesis presents a novel approach to several problems in intelligent transportation systems using collaborative driving coordination. With inter-vehicle communication and intelligent vehicle cooperation, important tasks in transportation such as lane position determination, lane assignment and platoon formation can be solved. Several topics in regard to inter-vehicle communication, lane positioning, lane assignment and platoon formation are explored in this thesis: First, the design and experimental results of low-cost lane-level positioning system that can support a large number of transportation applications are discussed. Using a Markov-based approach based on sharing information among a group of vehicles that are traveling within the communication range of each other, the lane positions of vehicles can be determined. The robustness effectiveness of the system is shown in both simulations and real road tests. Second, a decentralized approach to lane scheduling for vehicles with an aim to increase traffic throughput while ensuring the vehicles exit successfully at their destinations is presented. Most of current traffic management systems do not consider lane organization of vehicles and only regulate traffic flows by controlling traffic signals or ramp meters. However, traffic throughput and efficient use of highways can be increased by coordinating driver behaviors intelligently. The lane optimization problem is formulated as a linear programming problem that can be solved using the Simplex method. Finally, a direction for cooperative vehicle platoon formation is proposed. To enhance traffic safety, increase lane capacities and reduce fuel consumption, vehicles can be organized into platoons with the objective of maximizing the travel distance that platoons stay intact. Toward this end, this work evaluates a proposed strategy which assigns vehicles to platoons by solving an optimization problem. A linear model for assigning vehicles to appropriate platoons when they enter the highway is formulated. Simulation results demonstrate that lane capacity can be increased effectively when platooning operation is used.

This thesis presents a novel approach to several problems in intelligent transportation systems using collaborative driving coordination. With inter-vehicle communication and intelligent vehicle cooperation, important tasks in transportation such as lane position determination, lane assignment and platoon formation can be solved. Several topics in regard to inter-vehicle communication, lane positioning, lane assignment and platoon formation are explored in this thesis: First, the design and experimental results of low-cost lane-level positioning system that can support a large number of transportation applications are discussed. Using a Markov-based approach based on sharing information among a group of vehicles that are traveling within the communication range of each other, the lane positions of vehicles can be determined. The robustness effectiveness of the system is shown in both simulations and real road tests. Second, a decentralized approach to lane scheduling for vehicles with an aim to increase traffic throughput while ensuring the vehicles exit successfully at their destinations is presented. Most of current traffic management systems do not consider lane organization of vehicles and only regulate traffic flows by controlling traffic signals or ramp meters. However, traffic throughput and efficient use of highways can be increased by coordinating driver behaviors intelligently. The lane optimization problem is formulated as a linear programming problem that can be solved using the Simplex method. Finally, a direction for cooperative vehicle platoon formation is proposed. To enhance traffic safety, increase lane capacities and reduce fuel consumption, vehicles can be organized into platoons with the objective of maximizing the travel distance that platoons stay intact. Toward this end, this work evaluates a proposed strategy which assigns vehicles to platoons by solving an optimization problem. A linear model for assigning vehicles to appropriate platoons when they enter the highway is formulated. Simulation results demonstrate that lane capacity can be increased effectively when platooning operation is used.