No description available.

Decision-making is an essential topic for multi-robot coordination and collaboration and is also the main topic of this thesis. Examples can be found in autonomous driving, environmental monitoring, intelligent transportation, etc. To study this problem, we first use multiple applications as motivating examples and then construct the general formulation and solution for those applications. Finally, we extend our investigation from the fundamental problem formulation to resilient and decentralized versions. All those problems are studied in the combinatorial optimization domain with the help of submodular and matroid optimization techniques. As a motivating example, we use a multi-robot environmental monitoring problem to extract the general formulation of a multi-robot decision-making problem. Consider the problem of deploying multi-agent teams for environmental monitoring in a precision farming application. We want to answer the question of when and where to deploy our robots. This is a typical task allocation problem in multi-robot systems. Using the above problem as an example, we first focus on this decision-making problem, e.g., intermittent deployment problem, in a centralized scenario. Given a predictable agriculture environment, we want to make decisions for robots for this monitoring task. The problem is formulated as a combinatorial submodular optimization with matroid constraints. By utilizing the properties of submodularity, we aim to develop a solution with performance guarantees. This motivating example demonstrates how to use a submodular function and matroids to model and solve decision-making problems in multi-robot systems. Based on this framework, we continue to explore the fundamental decision-making problem in several other directions in multi-robot systems, including the robust decision-making problem. All those problems and solutions are formulated and considered in a centralized scenario. In the second part of this thesis, we switch our focus from centralized to decentralized scenarios. We first investigate a case where the robots in a distributed multi-robot system need to work together to guard the system against worst-case attacks while making decisions. By worst-case attacks, we refer to the case where the system may have up to $K$ sensor failures. To increase resilience, we propose a fully distributed algorithm to guide each robot's action selection when the system is attacked. The proposed algorithm guarantees performance in a worst-case scenario where up to a portion of the robots malfunction due to attacks. Based on this specific task allocation problem in robotics, we then create a unified framework for a more general case in a decentralized scenario, e.g., asynchronous decentralized decision-making problems with matroid and knapsack constraints. Finally, several applications in decentralized scenarios are used to validate the theoretical guaranteed performance in robotics. / Doctor of Philosophy / Robots have been widely used as mobile sensing agents nowadays in various applications. Especially with the help of multi-robot systems and artificial intelligence, our lives have changed dramatically in the last decades. One of the most fundamental questions is how to utilize multi-robot systems to finish tasks successfully. To answer this, we need first to formulate the problem from applications and then find theoretically guaranteed answers to those questions. Meanwhile, the robustness and resilience of the solution also need to be taken care of, as cyber-attacks or system failures can happen everywhere. Motivated by those two main goals, this thesis will first use multiple applications to introduce the thesis's topic. We then provide solutions to those problems in centralized and decentralized scenarios. Meanwhile, to increase the system's ability to handle failures, we need to answer how to improve the robustness and resilience of the proposed solutions. Therefore, the topic of this thesis spread from problem formulation to failure-proof solutions. The result of this thesis can be widely used in multi-robot decision-making applications, including autonomous driving, intelligent transportation, and other cyber-physical systems.

Multi-robot systems (MRSs) have gained significant momentum as of late in the robotics community as they find application in tasks such as unknown environment exploration, distributed surveillance, and search and rescue. Operating robot teams in real world environments introduces a notion of uncertainty into the system, especially when it comes to the ability of the MRS to reliably communicate. This poses a significant challenge as a stable communication topology is the backbone of the team's ability to coordinate. Additionally, as these systems continue to evolve and integrate further into our society, a growing threat of adversarial attackers pose the risk of compromising nominal operation. As such, this dissertation aims to model the effects of uncertainty in communication on the topology of the MRS using a probabilistic interaction model. More specifically we are interested in studying a probabilistic perspective to those topologies that pertain to the security and resilience of an MRS against adversarial attacks. Having a model that is capable of capturing how probabilistic topologies may evolve over time is essential for secure and resilient planning under communication uncertainty. As a result, we develop probabilistic models, both exact and approximate, for the topological properties of system left-invertibility and (r, s)-robustness that respectively characterize the security and resilience of an MRS. In our modeling, we use binary decision diagrams, convolutional neural networks, matroid theory and more to tackle the problems related to probabilistic security and resilience where we find exact solutions, calculate bounds, solve optimization problems, and compute informative paths for exploration. / Doctor of Philosophy / When robots coordinate and interact together to achieve a collaborative task as a team, we obtain what is known as a multi-robot system or MRS for short. MRSs have several advantages over single robots. These include reliability through redundancy, where several robots can perform a given task in case one of the robots unexpectedly fails. The ability to work faster and more efficiently by working in parallel and at different locations. And taking on more complex tasks that can be too demanding for a single robot to complete. Unfortunately, the advantages of MRSs come at a cost, they are generally harder to coordinate, the action of one robot often depends on the action of other robots in the system, and they are more vulnerable to being attacked or exploited by malicious attackers who want to disrupt nominal operation. As one would expect, communication plays a very important roles in coordinating a team of robots. Unfortunately, robots operating in real world environments are subject to disturbances such as noise, obstacles, and interference that hinders the team's ability to effectively exchange information. In addition to being crucial in coordination, effective information exchange plays a major role in detecting and avoiding adversarial robots. Whenever misinformation is being spread in the team, the best way to counter such adversarial behavior is to communicate with as much well-behaving robots as possible to identity and isolate inconsistencies. In this dissertation we try to study how uncertainty in communication affects a system's ability to detect adversarial behavior, and how we can model such a phenomenon to help us account for these uncertainties when designing secure and resilient multi-robot systems.

In this dissertation, we study multi-robot coordination in the context of multi-target tracking. Specifically, we are interested in the coordination achieved by means of submodular function optimization. Submodularity encodes the diminishing returns property that arises in multi-robot coordination. For example, the marginal gain of assigning an additional robot to track the same target diminishes as the number of robots assigned increases. The advantage of formulating coordination problems as submodular optimization is that a simple, greedy algorithm is guaranteed to give a good performance. However, often this comes at the expense of unrealistic models and assumptions. For example, the standard formulation does not take into account the fact that robots may fail, either randomly or due to adversarial attacks. When operating in uncertain conditions, we typically seek to optimize the expected performance. However, this does not give any flexibility for a user to seek conservative or aggressive behaviors from the team of robots. Furthermore, most coordination algorithms force robots to communicate at each time step, even though they may not need to. Our goal in this dissertation is to overcome these limitations by devising coordination algorithms that are parsimonious in communication, allow a user to manage the risk of the robot performance, and are resilient to worst-case robot failures and attacks. In the first part of this dissertation, we focus on designing parsimonious communication strategies for target tracking. Specifically, we investigate the problem of determining when to communicate and who to communicate with. When the robots use range sensors, the tracking performance is a function of the relative positions of the robots and the targets. We propose a self-triggered communication strategy in which a robot communicates its own position with its neighbors only when a certain set of conditions are violated. We prove that this strategy converges to the optimal robot positions for tracking a single target and in practice, reduces the number of communication messages by 30%. When tracking multiple targets, we can reduce the communication by forming subsets of robots and assigning one subset to track a target. We investigate a number of measures for tracking quality based on the observability matrix and show which ones are submodular and which ones are not. For non-submodular measures, we show a greedy algorithm gives a 1/(n+1) approximation, if we restrict the subset to n robots. In optimizing submodular functions, a common assumption is that the function value is deterministic, which may not hold in practice. For example, the sensor performance may depend on environmental conditions which are not known exactly. In the second part of the dissertation, we design an algorithm for stochastic submodular optimization. The standard formulation for stochastic optimization optimizes the expected performance. However, the expectation is a risk-neutral measure. Instead, we optimize the Conditional Value-at-Risk (CVaR), which allows the user the flexibility of choosing a risk level. We present an algorithm, based on the greedy algorithm, and prove that its performance has bounded suboptimality and improves with running time. We also present an online version of the algorithm to adapt to real-time scenarios. In the third part of this dissertation, we focus on scenarios where a set of robots may fail naturally or due to adversarial attacks. Our objective is to track as many targets as possible, a submodular measure, assuming worst-case robot failures. We present both centralized and distributed resilient tracking algorithms to cope with centralized and distributed communication settings. We prove these algorithms give a constant-factor approximation of the optimal in polynomial running time. / Doctor of Philosophy / Today, robotics and autonomous systems have been increasingly used in various areas such as manufacturing, military, agriculture, medical sciences, and environmental monitoring. However, most of these systems are fragile and vulnerable to adversarial attacks and uncertain environmental conditions. In most cases, even if a part of the system fails, the entire system performance can be significantly undermined. As robots start to coexist with humans, we need algorithms that can be trusted under real-world, not just ideal conditions. Thus, this dissertation focuses on enabling security, trustworthiness, and long-term autonomy in robotics and autonomous systems. In particular, we devise coordination algorithms that are resilient to attacks, trustworthy in the face of the uncertain conditions, and allow the long-term operation of multi-robot systems. We evaluate our algorithms through extensive simulations and proof-of-concept experiments. Generally speaking, multi-robot systems form the "physical" layer of Cyber-Physical Sytems (CPS), the Internet of Things (IoT), and Smart City. Thus, our research can find applications in the areas of connected and autonomous vehicles, intelligent transportation, communications and sensor networks, and environmental monitoring in smart cities.

We study the problem of planning a tour for an energy-limited Unmanned Aerial Vehicle (UAV) to visit a set of sites in the least amount of time. We envision scenarios where the UAV can be recharged along the way either by landing on stationary recharging stations or on Unmanned Ground Vehicles (UGVs) acting as mobile recharging stations. This leads to a new variant of the Traveling Salesperson Problem (TSP) with mobile recharging stations. We present an algorithm that finds not only the order in which to visit the sites but also when and where to land on the charging stations to recharge. Our algorithm plans tours for the UGVs as well as determines the best locations to place stationary charging stations. While the problems we study are NP-Hard, we present a practical solution using Generalized TSP that finds the optimal solution. If the UGVs are slower, the algorithm also finds the minimum number of UGVs required to support the UAV mission such that the UAV is not required to wait for the UGV. We present a calibration routine to identify parameters that are needed for our algorithm as well as simulation results that show the running time is acceptable for reasonably sized instances in practice. We evaluate the performance of our algorithm through simulations and proof-of-concept experiments with a fully autonomous system of one UAV and UGV. / Master of Science / Commercially available Unmanned Aerial Vehicles (UAVs), especially multi-rotor aircrafts, have a flight time of less than 30 minutes. However many UAV applications, such as surveillance, package delivery, and infrastructure monitoring, require much longer flight times. To address this problem, we present a system in which an Unmanned Ground Vehicle (UGV) can recharge the UAV during deployments. This thesis studies the problem of finding when, where, and how much to recharge the battery. We also allow for the UGV to recharge while moving from one site to another. We present an algorithm that finds the paths for the UAV and UGV to visit a set of points of interest in the least time possible. We also present algorithms for cases when the UGV is slower than the UAV, and more than one UGV may be required. We evaluate our algorithms through simulations and proof-of-concept experiments.

Motion planning for robot operations is concerned with path planning and trajectory generation. In multi-robot systems, i.e. with multiple robots operating simultaneously in a shared workspace, the motion planning also needs to coordinate the robots' motions to avoid collisions between them. The multi-robot coordination decides the cycle-time for the planned paths and trajectories since it determines to which extend the operations can take place simultaneously without colliding. To obtain the quickest cycle-time, there needs to bean optimal balance between, on the one hand short paths and fast trajectories, and on the other hand possibly longer paths and slower trajectories to allow that the operations take place simultaneously in the shared workspace. Due to the inter-dependencies, it becomes necessary to consider the path planning, trajectory generation and multi-robot coordination together as one optimisation problem in order to find this optimal balance.This thesis focusses on optimising the motion planning for multi-robot material handling systems of sheet metal parts. A methodology to model the relevant aspects of this motion planning problem together as one multi-disciplinary optimisation problem for Simulation based Optimisation (SBO) is proposed. The identified relevant aspects include path planning,trajectory generation, multi-robot coordination, collision-avoidance, motion smoothness, end-effectors' holding force, cycle-time, robot wear, energy efficiency, part deformations, induced stresses in the part, and end-effectors' design. The cycle-time is not always the (only) objective since it is sometimes equally/more important to minimise robot wear, energy consumption, and/or part deformations. Different scenarios for these other objectives are therefore also investigated. Specialised single- and multi-objective algorithms are proposed for optimising the motion planning of these multi-robot systems. This thesis also investigates how to optimise the velocity and acceleration profiles of the coordinated trajectories for multi-robot material handling of sheet metal parts. Another modelling methodology is proposed that is based on a novel mathematical model that parametrises the velocity and acceleration profiles of the trajectories, while including the relevant aspects of the motion planning problem excluding the path planning since the paths are now predefined.This enables generating optimised trajectories that have tailored velocity and acceleration profiles for the specific material handling operations in order to minimise the cycle-time,energy consumption, or deformations of the handled parts.The proposed methodologies are evaluated in different scenarios. This is done for real world industrial case studies that consider the multi-robot material handling of a multi-stage tandem sheet metal press line, which is used in the automotive industry to produce the cars' body panels. The optimisation results show that significant improvements can be obtained compared to the current industrial practice.

Multi-robot task assignment (allocation) involves assigning robots to tasks in order to optimize the entire team’s performances. Until now, one of the most useful non-domain-specific ways to coordinate multi-robot systems is through task allocation mechanisms. This dissertation addresses the classic task assignment problems in which robots and tasks are eventually matched by forming a one-to-one mapping, and their overall performances (e.g., cost, utility, and risk) can be linearly summed. At a high level, this research emphasizes two facets of the multi-robot task assignment, including (1) novel extensions from classic assignment algorithms, and (2) completely newly designed task allocation methods with impressive new features. For the former, we first propose a strongly polynomial assignment sensitivity analysis algorithm as well as a means to measure the assignment uncertainties; after that we propose a novel method to address problems of multi-robot routing and formation morphing, the trajectories of which are obtained from projections of augmenting paths that reside in a new three-dimensional interpretation of embedded matching graphs. For the latter, we present two optimal assignment algorithms that are distributable and suitable for multi-robot task allocation problems: the first one is an anytime assignment algorithm that produces non-decreasing assignment solutions along a series of task-swapping operations, each of which updates the assignment configurations and thus can be interrupted at any moment; the second one is a new market-based algorithm with a novel pricing policy: in contrast to the buyers’ “selfish” bidding behaviors in conventional auction/market-based approaches, we employ a virtual merchant to strategically escalate market prices in order to reach a state of equilibrium that satisfies both the merchant and buyers. Both of these newly developed assignment algorithms have a strongly polynomial running time close to the benchmark algorithms but can be easily decentralized in terms of computation and communication.

Submitted by Renata Lopes (renatasil82@gmail.com) on 2017-03-09T12:13:05Z No. of bitstreams: 1 rafaeljosefonsecadesa.pdf: 2699281 bytes, checksum: ca2455c138265324b1a8fcbb6075da41 (MD5) / Approved for entry into archive by Adriana Oliveira (adriana.oliveira@ufjf.edu.br) on 2017-03-10T12:58:01Z (GMT) No. of bitstreams: 1 rafaeljosefonsecadesa.pdf: 2699281 bytes, checksum: ca2455c138265324b1a8fcbb6075da41 (MD5) / Made available in DSpace on 2017-03-10T12:58:01Z (GMT). No. of bitstreams: 1 rafaeljosefonsecadesa.pdf: 2699281 bytes, checksum: ca2455c138265324b1a8fcbb6075da41 (MD5) Previous issue date: 2016-09-09 / Com a evolução da tecnologia, estão aumentando as aplicabilidades dos robôs em nosso meio. Em alguns casos, a utilização de sistemas com múltiplos robôs autônomos trabalhando em cooperação se torna uma ótima alternativa. Há várias pesquisas em andamento na área de robótica com o intuito de aprimorar estas tarefas. Entre estas pesquisas estão os sistemas de patrulhamento. Neste trabalho, o sistema de patrulhamento utilizando múltiplos robôs é implementado considerando a série de chegada de alertas nas estações de monitoramento e o robô pode andar somente em uma única direção. Devido ao número de estações que podem entrar em alerta e ao número de robôs, o controle desse sistema se torna complexo. Como a finalidade de um sistema de patrulhamento é atender possíveis alertas de invasores, é imprescindível que haja uma resposta rápida do controlador responsável para que um robô logo seja encaminhado com o propósito de atender a esse alerta. No caso de sistemas com múltiplos robôs, é necessário que haja uma coordenação do controlador para que os robôs possam atender o máximo de alertas possíveis em um menor instante de tempo. Para resolver esse problema, foi utilizado um controlador composto por uma técnica inteligente de otimização bioinspirada chamada de “Algoritmo Genético” (AG). Este controlador centraliza todas as decisões de controle dos robôs, sendo responsável por orientá-los em relação aos movimentos e captação de informação. As decisões são tomadas com o intuito de maximizar a recompensa do sistema. Esta recompensa é composta pelo ganho de informação do sistema e por uma penalização gerada pela demora em atender aos alertas ativados. Foram feitas simulações com a intenção de verificar a eficácia desse controlador, comparando-o com um controlador utilizando heurísticas pré-definidas. Essas simulações comprovaram a eficiência do controlador via Algoritmo Genético. Devido ao fato do controlador via AG analisar o sistema como um todo enquanto que o controlador heurístico analisa apenas o estágio atual, foi possível observar que a distribuição dos robôs no mapa permitia um atendimento mais ágil às estações com alerta ativados, assim como uma maior aquisição de informações do local. Outro fato importante foi em relação à complexidade do sistema. Foi notado que quanto maior a complexidade do sistema, ou seja, quanto maior o número de robôs e de estações, melhor era a eficiência do controlador via Algoritmo Genético em relação ao controlador heurístico. / New technologies have been considerable advances, and consequently, thus allows the robot appearance as an integral part of our daily lives. In recent years, the design of cooperative multi-robot systems has become a highly active research area within robotics. Cooperative multi-robot systems (MRS) have received significant attention by the robotics community for the past two decades, because their successful deployment have unquestionable social and economical relevance in many application domain. There are several advantages of using multi-robot systems in different application and task. The development and conception of patrolling methods using multi-robot systems is a scientific area which has a growing interest. This work, the patrol system using multiple robots is implemented considering the series of arrival of alerts in the monitoring stations known and the robot was limited to move in one direction. Due to the large number of stations that can assume alert condition and due to the large number of robots, the system control becomes extremely complex. Patrol systems are usually designed for surveillance. An efficient controller permits a patrol in a way that maximizes their chances of detecting an adversary trying to penetrate through the patrol path. The obvious advantage of multi-robot exploration is its concurrency, which can greatly reduce the time needed for the mission. Coordination among multiple robots is necessary to achieve efficiency in robotic explorations. When working in groups, robots need to coordinate their activities. However, a Genetic Algorithm approach was implemented to carryout an optimized control action provided from the controller. In fact the controller determines the robot's behavior. The decision strategies are implemented in order to maximize the system response. The present work deals with a computational study of controller based on Genetic Algorithm and it comparison with another controller based pre-defined heuristics. The simulation results show the efficiency of the proposed controller based on Genetic Algorithm, when compared with the controller based on heuristics. The right decisions from the controller based on Genetic Algorithm allowed a better distribution of the robots on the map leading to fast service stations with active alert, as well as increased acquisition of location information. Another important fact was regarding the complexity of the system. Also, as a result, it was noticed an excellent efficiency of the controller based on Genetic Algorithm when the existence of the large number of robots and stations.

Designing an effective human-robot interaction paradigm is particularly important for complex tasks such as multi-robot manipulation that require the human and robot to work together in a tightly coupled fashion. Although increasing the number of robots can expand the area that the robots can cover within a bounded period of time, a poor human-robot interface will ultimately compromise the performance of the team of robots. However, introducing a human operator to the team of robots, does not automatically improve performance due to the difficulty of teleoperating mobile robots with manipulators. The human operator’s concentration is divided not only among multiple robots but also between controlling each robot’s base and arm. This complexity substantially increases the potential neglect time, since the operator’s inability to effectively attend to each robot during a critical phase of the task leads to a significant degradation in task performance. There are several proven paradigms for increasing the efficacy of human-robot interaction: 1) multimodal interfaces in which the user controls the robots using voice and gesture; 2) configurable interfaces which allow the user to create new commands by demonstrating them; 3) adaptive interfaces which reduce the operator’s workload as necessary through increasing robot autonomy. This dissertation presents an evaluation of the relative benefits of different types of user interfaces for multi-robot systems composed of robots with wheeled bases and three degree of freedom arms. It describes a design for constructing low-cost multi-robot manipulation systems from off the shelf parts. User expertise was measured along three axes (navigation, manipulation, and coordination), and participants who performed above threshold on two out of three dimensions on a calibration task were rated as expert. Our experiments reveal that the relative expertise of the user was the key determinant of the best performing interface paradigm for that user, indicating that good user modiii eling is essential for designing a human-robot interaction system that will be used for an extended period of time. The contributions of the dissertation include: 1) a model for detecting operator distraction from robot motion trajectories; 2) adjustable autonomy paradigms for reducing operator workload; 3) a method for creating coordinated multi-robot behaviors from demonstrations with a single robot; 4) a user modeling approach for identifying expert-novice differences from short teleoperation traces.

Thesis (MScEng)--Stellenbosch University, 2011. / ENGLISH ABSTRACT: RoboCup promotes research in robotics and multi-robot systems (MRS). The RoboCup Small Size League (SSL), in particular, offers an entry level opportunity to take part in this field of study. This thesis presents a starting phase for research in robotics and MRS at Stellenbosch University. It includes the full documentation of the mechanical, electronic and software design of an omni-directional soccer robot for RoboCup SSL. The robot is also meant to operate as a hardware and software development platform for research in MRS. The platform was therefore designed with high-level programming language compatibility, a wide range of connectivity, and modularity in mind. The robot uses a single board computer (SBC) running a Linux operating system to accomplish these objectives. Moreover, a driver class library was written in C++ as a software application interface (API) for future development on the robot platform. The robot was also developed with a particular focus on a distributed control architecture. "Player" was implemented as the middleware, which can be used for communication between multiple robots in a distributed environment. Additionally, three tests were performed to demonstrate the functionality of the prototype: a PI speed control test, a direction accuracy test and a static communication test using the middleware. Recommendations for possible future work are also given. / AFRIKAANSE OPSOMMING: RoboCup bevorder navorsing in robotika en multi-robot-stelsels (MRS). Die RoboCup Klein Liga (KL) bied in die besonder die geleentheid om op intreevlak navorsing te doen in hierdie veld. Hierdie tesis verteenwoordig die eerste fase van navorsing in robotika en MRS by Stellenbosch Universiteit. Dit sluit die volledige dokumentasie van die meganiese, elektroniese en sagteware-ontwerp van ’n omnidireksionele sokker-robot vir die KL in. Die robot is ook veronderstel om te dien as ’n hardeware- en sagteware-ontwikkelingsplatform vir navorsing in MRS. Die platform is dus ontwerp met ’n verskeidenheid van uitbreingsmoontlikhede en modulariteit in gedagte asook die moontlikheid om gebruik te maak van ’n hoë-vlak programmeertaal. Om hierdie doelwitte te bereik, maak die robot gebruik van ’n enkel-bord-rekenaar met ’n Linux bedryfstelsel. Verder was ’n sagteware drywer in C++ geskryf om te dien as ’n sagteware-koppelvlak vir toekomstige ontwikkeling op die robot platform. Die robot is ook ontwikkel met die besondere fokus op ’n gedesentraliseerde beheerstels. Player was geïmplementeer as die middelware, wat gebruik kan word vir kommunikasie tussen verskeie robotte in ’n gedesentralliseerde beheerstelsel. Daar is drie toetse uitgevoer om die funksionaliteit van die prototipe te demonstreer, ’n PI spoed beheer toets, ’n rigting akkuraatheidstoets en ’n statiese kommunikasie toets deur van die middelware gebruik te maak. Aanbevelings vir moontlike toekomstige werk word ook verskaf.