In recent years, we have seen the applications of distributed autonomous mobile robots (DAMRs) in a broad spectrum of areas like search and rescue, disaster management, warehouse, and delivery systems. Although each type of systems employing DAMRs has its specific challenges, they are all limited by energy since the robots are powered by batteries which have not advanced in decades. This motivates the development of energy efficiency for such systems. Although there has been research on optimizing energy for robotic systems, their approaches are from low-level (e.g., mechanic, system control, or avionic) perspectives. They, therefore, are limited to a specific type of robots and not easily adjusted to apply for different types of robots. Moreover, there is a lack of work studying the problem from a software perspective and abstraction. In this thesis, we tackle the problem from a software perspective and are particularly interested in DAMR systems in which a team of networked robots navigating in a physical environment and acting in concert to accomplish a common goal. Also, the primary focus of our work is to design schedules (or plans) for the robots so that they can achieve their goal while spending as little energy as possible. To this end, we study the problem in three different contexts: - Managing reliability and energy consumption tradeoff. That is, we propose that robots verify computational results of one another to increase the corroboration of outputs of our DAMR systems. However, this new feature requires robots to do additional tasks and consume more energy. Thus, we propose approaches to reach a balance between energy consumption and the reliability of results obtained by our DAMR systems. - Extending the operational time of robots. We first propose that our DAMR systems should employ charging stations where robots can come to recharge their batteries. Then, we aim to design schedules for the robots so that they can finish all their tasks while consuming as little energy and time (including the time spent for recharging) as possible. Moreover, we model the working space by a connected (possibly incomplete) graph to make the problem more practical. - Coping with environmental changes. This path planning problem takes into account not only energy limits but also changes in the physical environment, which may result in overheads (i.e., additional time and energy) that robots incur while doing their tasks. To tackle the problem from a software perspective, we first utilize Gaussian Process and Polynomial Regression to model disturbances and energy consumption, respectively, then proposed techniques to generate plans and adjust them when robots detect environmental changes. For each problem, we give a formal description, a transformation to integer (linear) programming, online algorithms, and an online algorithm. Moreover, we also rigorously analyze the proposed techniques by conducting simulations and experiments in a real network of unmanned aerial vehicles (UAVs). / Thesis / Candidate in Philosophy

Multi-robot systems (MRS) offer many performance benefits over single robots for tasks that can be completed by one robot. They offer potential redundancies to the system to improve robustness and allow tasks to be completed in parallel. These benefits, however, can be quickly offset by losses in productivity from diminishing returns caused by interference between robots and communication problems. This dissertation developed and evaluated MRS control architectures to solve the dynamic multi-robot autonomous routing problem. Dynamic multi-robot autonomous routing requires robots to complete a trip from their initial location at the time of task allocation to an assigned destination. The primary concern for the control architectures was how well the communication requirements and overall system performance scaled as the number of robots in the MRS got larger. The primary metrics for evaluation of the controller were the effective robot usage rate and the bandwidth usage. This dissertation evaluated several different approaches to solving dynamic multi-robot autonomous routing. The first three methods were based off of common MRS coordination approaches from previous research. These three control architectures with distributed control without communication (a swarm-like method), distributed control with communication, and centralized control. An additional architecture was developed to solve the problem in a way that scales better as the number of robots increase. This architecture, mixed mode autonomy, combines the strengths of distributed control with communication and centralized control. Like distributed control with communication, mixed mode autonomy's performance degrades gracefully with communication failures and is not dependent on a single controller. Like centralized control, there is oversight from a central controller to ensure repeatable high performance of the system. Each of the controllers other than distributed control without communication is based on building world models to facilitate coordination of the routes. A second variant of mixed mode autonomy was developed to allow robots to share parts of their world models with their peers when their models were incomplete or outdated. The system performance was evaluated for three example applications that represent different cases of dynamic multi-robot autonomous routing. These example applications were the automation of open pit mines, container terminals, and warehouses. The effective robot usage rates for mixed mode autonomy were generally significantly higher than the other controllers with a higher numbers of robots. The bandwidth usage was also much lower. These performance trends were also observed across a wide range of operating conditions for dynamic multi-robot autonomous routing. The original contributions from this work were the development of a new MRS control architecture, development of system model for the dynamic multi-robot autonomous routing problem, and identification of the tradeoffs for MRS design for the dynamic multi-robot autonomous routing problem. / Ph. D.

The task assignment problem is one of the fundamental combinatorial optimization problems. It has been extensively studied in operation research, management science, computer science and robotics. Task assignment problems arise in various applications of multi-robot systems (MRS), such as environmental monitoring, disaster response, extraterrestrial exploration, sensing data collection and collaborative autonomous manufacturing. In these MRS applications, there are realistic constraints on robots and tasks that must be taken into account both from the modeling perspective and the algorithmic perspective. From the modeling aspect, such constraints include (a) Task group constraints: where tasks form disjoint groups and each robot can be assigned to at most one task in each group. One example of the group constraints comes from tightly-coupled tasks, where multiple micro tasks form one tightly-coupled macro task and need multiple robots to perform each simultaneously. (b) Task deadline constraints: where tasks must be assigned to meet their deadlines. (c) Dynamically-arising tasks: where tasks arrive dynamically and the payoffs of future tasks are unknown. Such tasks arise in scenarios like searchrescue, where new victims are found dynamically. (d) Robot budget constraints: where the number of tasks each robot can perform is bounded according to the resource it possesses (e.g., energy). From the solution aspect, there is often a need for decentralized solution that are implemented on individual robots, especially when no powerful centralized controller exists or when the system needs to avoid single-point failure or be adaptive to environmental changes. Most existing algorithms either do not consider the above constraints in problem modeling, are centralized or do not provide formal performance guarantees. In this thesis, I propose methods to address these issues for two classes of problems, namely, the constrained linear assignment problem and constrained generalized assignment problem. Constrained linear assignment problem belongs to P, while constrained generalized assignment problem is NP-hard. I develop decomposition-based distributed auction algorithms with performance guarantees for both problem classes. The multi-robot assignment problem is decomposed into an optimization problem for each robot and each robot iteratively solving its own optimization problem leads to a provably good solution to the overall problem. For constrained linear assignment problem, my approaches provides an almost optimal solution. For constrained generalized assignment problem, I present a distributed algorithm that provides a solution within a constant factor of the optimal solution. I also study the online version of the task allocation problem with task group constraints. For the online problem, I prove that a repeated greedy version of my algorithm gives solution with constant factor competitive ratio. I include simulation results to evaluate the average-case performance of the proposed algorithms. I also include results on multi-robot cooperative package transport to illustrate the approach.

La principale difficulté pour la navigation autonome d'un robot dans un environnement partiellement ou totalement inconnu vient naturellement du manque d'informations sur l'environnement : on ne peut assurer que le chemin calculé soit aussi court et aussi sûr que le chemin calculé avec une connaissance parfaite de l'environnement. Les informations sur l'environnement sont obtenues au fur et à mesure de la navigation avec un degré variable de certitude qui dépend de l'environnement lui-même, des capacités de perception et la localisation du véhicule, et c'est l'acquisition des informations pertinentes pour la tâche de navigation qui conditionne sa bonne réalisation. Les travaux proposés sont réalisés dans ce contexte : ils définissent une stratégie de navigation qui est basée sur la détermination des zones où l'information est nécessaire au robot pour atteindre le but. / The main difficulty of autonomous navigation of a mobile robot in a partially comes from the lack of information about the environment. One can not assure the calculated navigation path is as short and as safe as the path calculated if we had all the necessary information on the environment. Information is gathered along the moves of the mobile robot with a varying degree of certainty. This uncertainty come from the environment itself, the perception abilities and the localisation abilities of the robot. Only relevant information acquisitions can help a good execution of the navigation task.The proposed approach is realised in this context : it consists of a navigation strategy based on the determination of zones where information is necessary for the robot to rally its objective.

Multi-agent systems (MAS) have been of interest to many researchers during the last decades. This thesis focuses on multi-robot systems (MRS) and programmable matter as two types of MAS. Regarding MRS, the focus is on the 'mergeable nervous system' (MNS) concept which allows the robots to connect to one another and establish a communication network through self-organization and then use the network to temporarily report sensing events and cede authority to a single robot in the system. Here, in a collective perception scenario, we experimentally evaluate the performance of an MNS-enabled approach and compare it with that of several decentralized benchmark approaches. We show that an MNS-enabled approach is high-performing, fault-tolerant, and scalable, so it is an appropriate approach for MRS. As a goal of the thesis, using an MNS-enabled approach, we present for the first time a comprehensive comparison of control architectures in multi-robot systems, which includes a comparison of accuracy, efficiency, speed, energy consumption, scalability, and fault tolerance. Our comparisons provide designers of multi-robot systems with a better understanding for selecting the best-performing control depending on the system's objectives. Additionally, as a separate goal, we design a high-level leader based programmable matter, which can perform some basic primitive operations in a grid environment, and construct it using lower-level organisms. We design and implement deterministic algorithms for "curl" operation of this high-level matter, an instance of shape formation problem. We prove the correctness of the presented algorithms, analytically determine their complexity, and experimentally evaluate their performance.

Autonomous robots like household service robots, self-driving cars and dronesare emerging as important parts of our daily lives in the near future. They need tocomprehend and fulfill complex tasks specified by the users with minimal humanintervention. Also they should be able to handle un-modeled changes and contingentevents in the workspace. More importantly, they shall communicate and collaboratewith each other in an efficient and correct manner. In this thesis, we address theseissues by focusing on the distributed and hybrid control of multi-robot systemsunder complex individual tasks. We start from the nominal case where a single dynamical robot is deployed in astatic and fully-known workspace. Its local tasks are specified as Linear TemporalLogic (LTL) formulas containing the desired motion. We provide an automatedframework as the nominal solution to construct the hybrid controller that drives therobot such that its resulting trajectory satisfies the given task. Then we expand theproblem by considering a team of networked dynamical robots, where each robot hasa locally-specified individual task also as LTL formulas. In particular, we analyzefour different aspects as described below. When the workspace is only partially known to each robot, the nominal solutionmight be inadequate. Thus we first propose an algorithm for initial plan synthesis tohandle partially infeasible tasks that contain hard and soft constraints. We designan on-line scheme for each robot to verify and improve its local plan during runtime, utilizing its sensory measurements and communications with other robots. Itis ensured that the hard constraints for safety are always fulfilled while the softconstraints for performance are improved gradually. Secondly, we introduce a new approach to construct a full model of both robotmotion and actions. Based on this model, we can specify much broader robotic tasksand it is used to model inter-robot collaborative actions, which are essential for manymulti-robot applications to improve system capability, efficiency and robustness.Accordingly, we devise a distributed strategy where the robots coordinate theirmotion and action plans to fulfill the desired collaboration by their local tasks. Thirdly, continuous relative-motion constraints among the robots, such as collision avoidance and connectivity maintenance, are closely related to the stability,safety and integrity of multi-robot systems. We propose two different hybrid controlapproaches to guarantee the satisfaction of all local tasks and the relative-motionconstraints at all time: the first one is based on potential fields and nonlinear controltechnique; the second uses Embedded Graph Grammars (EGGs) as the main tool. At last, we take into account two common cooperative robotic tasks, namelyservice and formation tasks. These tasks are requested and exchanged among therobots during run time. The proposed hybrid control scheme ensures that the real-time plan execution incorporates not only local tasks of each robot but also thecontingent service and formation tasks it receives. Some of the theoretical results of the thesis have been implemented and demonstrated on various robotic platforms. / Denna avhandling fokuserar på distribuerad och hybridstyrning av multi-robot-system för komplexa, lokala och tidsberoende uppgifter. Dessa uppgifter specificerasav logiska formler rörande robotens rörelser och andra ageranden. Avhandlingenbehandlar ett tvärvetenskapligt område som integrerar reglering av nätverkaderobotsystem och planering baserad på formella metoder. Ett ramverk för hybridstyrning av flera dynamiska robotar med lokalt specificerade uppgifter presenteras.Fyra huvudscenarier betraktas: (1) robot-planering med motstridiga arbetsuppgifterinom ett delvis okänt arbetsområde; (2) beroende uppgifter för en grupp heterogenaoch samverkande robotar; (3) relativa rörelsebegränsningar hos varje robot; samt(4) robotar med uppgifter som begärs och bekräftas under körning. Numeriskasimuleringar och experiment visas för att validera de teoretiska resultaten. / <p>QC 20151204</p> / EU STREP RECONFIG: FP7-ICT-2011-9-600825 / Swedish Research Council (VR)

Certain tasks require multiple robots to cooperate in order to solve them. The main problem with multi-robot systems is that they are inherently complex and usually situated in a dynamic environment. Now, biological immune systems possess a natural distributed control and exhibit real-time adaptivity, properties that are required to solve problems in multi-robot systems. In this thesis, biological immune systems and their response to external elements to maintain an organism's health state are researched. The objective of this research is to propose immune-inspired approaches to cooperation, to establish an adaptive cooperation algorithm, and to determine the refinements that can be applied in relation to cooperation. Two immune-inspired models that are based on the immune network theory are proposed, namely the Immune Network T-cell-regulated---with Memory (INT-M) and the Immune Network T-cell-regulated---Cross-Reactive (INT-X) models. The INT-M model is further studied where the results have suggested that the model is feasible and suitable to be used, especially in the multi-robot cooperative shepherding domain. The Collecting task in the RoboShepherd scenario and the application of the INT-M algorithm for multi-robot cooperation are discussed. This scenario provides a highly dynamic and complex situation that has wide applicability in real-world problems. The underlying 'mechanism of cooperation' in the immune inspired model (INT-M) is verified to be adaptive in this chosen scenario. Several multi-robot cooperative shepherding factors are studied and refinements proposed, notably methods used for Shepherds' Approach, Shepherds' Formation and Steering Points' Distance. This study also recognises the importance of flock identification in relation to cooperative shepherding, and the Connected Components Labelling method to overcome the related problem is presented. Further work is suggested on the proposed INT-X model that was not implemented in this study, since it builds on top of the INT-M algorithm and its refinements. This study can also be extended to include other shepherding behaviours, further investigation of other useful features of biological immune systems, and the application of the proposed models to other cooperative tasks.

The objective of this thesis is to develop a strategy that allows robots to safely execute open-loop motion patterns for pre-computed time durations when facing interruptions in communication. By computing the time horizon in which collisions with other robots are impossible, this method allows the robots to move safely despite having no updated information about the environment. As the complexity of multi-robot systems increase, communication failures in the form of packet losses, saturated network channels and hardware failures are inevitable. This thesis is motivated by the need to increase the robustness of operation in the face of such failures. The advantage of this strategy is that it prevents the jerky and unpredictable motion behaviour which often plague robotic systems experiencing communication issues. To compute the safe time horizon, the first step involves constructing reachable sets around the robots to determine the set of all positions that can be reached by the robot in a given amount of time. In order to avoid complications arising from the non-convexity of these reachable sets, analytical expressions for minimum area ellipses enclosing the reachable sets are obtained. By using a fast gradient descent based technique, intersections are computed between a robot’s trajectory and the reachable sets of other robots. This information is then used to compute the safe time horizon for each robot in real time. To this end, provable safety guarantees are formulated to ensure collision avoidance. This strategy has been verified in simulation as well as on a team of two-wheeled differential drive robots on a multi-robot testbed.

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. 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. 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. 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. 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. 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. 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.

Simultaneous localization and mapping (SLAM) is a challenging and vital problem in robotics. It is important in tasks such as disaster response, deep-sea and cave exploration, in which robots must construct a map of an unknown terrain, and at the same time localize themselves within the map. The issue with single- robot SLAM is the relatively high rate of failure in a realistic application, as well as the time and energy cost. In this work, we propose a new approach to decentralized multi-robot SLAM which uses a robot swarm to map the environment. This system is capable of mapping an environment without human assistance and without the need for any additional infrastructure. We assume that 1) no robot possesses sufficient memory to store the entire map of the environment, 2) the communication range of the robots is limited, and 3)there is no infrastructure present in the environment to assist the robot in communicating with others. To cope with these limitations, the swarm system is designed to work as an independent entity. The swarm can deploy new robots towards the region that is yet to be explored, coordinate the communication between the robots by using itself as the communication network and replace any malfunctioning robots. The proposed method proves to be a reliable and robust exploration algorithm. It is shown to be a self-growing mapping network that is able to coordinate among numerous robots and replace any broken robots hence reducing the chance of system failure.