No description available.

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.

Robots are increasingly utilized in industry for their capability to perform repetitive,complex tasks in environments unsuitable for humans. This surge in robotic applicationshas spurred research into Multi-Robot Systems (MRS), which aim to tackle complex tasksrequiring collaboration among multiple robots, thereby boosting overall efficiency. However,MRS introduces multifaceted challenges that span various domains, including robot perception,localization, task assignment, communication, and control. This dissertation delves into theintricate aspects of task assignment and path planning within MRS.The first area of focus is on multi-robot navigation, specifically addressing the limitationsinherent in current Multi-Agent Path Finding (MAPF) models. Traditional MAPF solutionstend to oversimplify, treating robots as holonomic units on grid maps. While this approachis impractical in real-world settings where robots have distinct geometries and kinematicrestrictions, it is important to note that even in its simplified form, MAPF is categorized as anNP-hard problem. The complexity inherent in MAPF becomes even more pronounced whenextending these models to non-holonomic robots, underscoring the significant computationalchallenges involved. To address these challenges, this thesis introduces a novel MAPF solverdesigned for non-holonomic, heterogeneous robots. This solver integrates the hybrid A*algorithm, accommodating kinematic constraints, with a conflict-based search (CBS) for efficientconflict resolution. A depth-first search approach in the conflict tree is utilized to accelerate theidentification of viable solutions.The second research direction explores synergizing task assignment with path-finding inMRS. While there is substantial research in both decentralized and centralized task assignmentstrategies, integrating these with path-finding remains underexplored. This dissertation evaluatesdecoupled methods for sequentially resolving task assignment and MAPF challenges. Oneproposed method combines the Hungarian algorithm and a Traveling Salesman Problem (TSP)solver for swift, albeit suboptimal, task allocation. Subsequently, robot paths are generatedindependently, under the assumption of collision-free navigation. During actual navigation, aNonlinear Model Predictive Controller (NMPC) is deployed for dynamic collision avoidance. Analternative approach seeks optimal solutions by conceptualizing task assignment as a MultipleTraveling Salesman Problem (MTSP), solved using a simulated annealing algorithm. In tandem,CBS is iteratively applied to minimize the cumulative path costs of the robots.

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.

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.