This thesis addresses the problem of motion planning for autonomous robots, given a map and an estimate of the robot pose within it. The motion planning problem for a mobile robot can be defined as computing a trajectory in an environment from one pose to another while avoiding obstacles and optimizing some objective such as path length or travel time, subject to constraints like vehicle dynamics limitations. More complex planning problems such as multi-robot planning or complete coverage of an area can also be defined within a similar optimization structure. The computational complexity of path planning presents a considerable challenge for real-time execution with limited resources and various methods of simplifying the problem formulation by discretizing the solution space are grouped under the class of discrete planning methods. The approach suggests representing the environment as a roadmap graph and formulating shortest path problems to compute optimal robot trajectories on it. This thesis presents two main contributions under the framework of discrete planning. The first contribution addresses complete coverage of an unknown environment by a single omnidirectional ground rover. The 2D occupancy grid map of the environment is first converted into a polygonal representation and decomposed into a set of convex sectors. Second, a coverage path is computed through the sectors using a hierarchical inter-sector and intra-sector optimization structure. It should be noted that both convex decomposition and optimal sector ordering are known NP-hard problems, which are solved using a greedy cut approximation algorithm and Travelling Salesman Problem (TSP) heuristics, respectively. The second contribution presents multi-robot path-planning strategies for recharging autonomous robots performing a persistent task. The work considers the case of surveillance missions performed by a team of Unmanned Aerial Vehicles (UAVs). The goal is to plan minimum cost paths for a separate team of dedicated charging robots such that they rendezvous with and recharge all the UAVs as needed. To this end, planar UAV trajectories are discretized into sets of charging locations and a partitioned directed acyclic graph subject to timing constraints is defined over them. Solutions consist of paths through the graph for each of the charging robots. The rendezvous planning problem for a single recharge cycle is formulated as a Mixed Integer Linear Program (MILP), and an algorithmic approach, using a transformation to the TSP, is presented as a scalable heuristic alternative to the MILP. The solution is then extended to longer planning horizons using both a receding horizon and an optimal fixed horizon strategy. Simulation results are presented for both contributions, which demonstrate solution quality and performance of the presented algorithms.

Agents in most types of societies use information about potential partners to determine whether to form mutually beneficial partnerships. We can say that when this information is used to decide to form a partnership that one agent trusts another, and when agents work together for mutual benefit in a partnership, we refer to this as a form of cooperation. Current multi-robot teams typically have the team's goals either explicitly or implicitly encoded into each robot's utility function and are expected to cooperate and perform as designed. However, there are many situations in which robots may not be interested in full cooperation, or may not be capable of performing as expected. In addition, the control strategy for robots may be fixed with no mechanism for modifying the team structure if teammate performance deteriorates. This dissertation investigates the application of trust to multi-robot teams. This research also addresses the problem of how cooperation can be enabled through the use of incentive mechanisms. We posit a framework wherein robot teams may be formed dynamically, using models of trust. These models are used to improve performance on the team, through evolution of the team dynamics. In this context, robots learn online which of their peers are capable and trustworthy to dynamically adjust their teaming strategy. We apply this framework to multi-robot task allocation and patrolling domains and show that performance is improved when this approach is used on teams that may have poorly performing or untrustworthy members. The contributions of this dissertation include algorithms for applying performance characteristics of individual robots to task allocation, methods for monitoring performance of robot team members, and a framework for modeling trust of robot team members. This work also includes experimental results gathered using simulations and on a team of indoor mobile robots to show that the use of a trust model can improve performance on multi-robot teams in the patrolling task.

This thesis examines the use of multiple robots in cooperative simultaneous localization and mapping (SLAM), where each robot must estimate the poses of all robots in the team, along with the positions of all known landmarks. The robot team must operate under the condition that the communication network between robots is never guaranteed to be fully connected. Under this condition, a novel algorithm is derived that allows each robot to obtain the centralized-equivalent estimate in a decentralized manner, whenever possible. The algorithm is then extended to a decentralized and distributed approach where robots share the computational burden in considering different data association hypotheses in generating the centralized-equivalent consensus estimate.

This thesis examines the use of multiple robots in cooperative simultaneous localization and mapping (SLAM), where each robot must estimate the poses of all robots in the team, along with the positions of all known landmarks. The robot team must operate under the condition that the communication network between robots is never guaranteed to be fully connected. Under this condition, a novel algorithm is derived that allows each robot to obtain the centralized-equivalent estimate in a decentralized manner, whenever possible. The algorithm is then extended to a decentralized and distributed approach where robots share the computational burden in considering different data association hypotheses in generating the centralized-equivalent consensus estimate.

Mobile sensor networks have been shown to be a powerful tool for enabling a number of activities that require recording of environmental parameters at various spatial and temporal distributions. These mobile sensor networks could be implemented using a team of robots, usually called robotic sensor networks. This type of sensor network involves the coordinated control of multiple robots to achieve specific measurements separated by varied distances. In most formation measurement applications, initialization involves identifying a number of interesting sites to which mobility platforms, instrumented with a variety of sensors, are tasked. This process of determining which instrumented robot should be tasked to which location can be viewed as solving the task allocation problem. Unfortunately, a centralized approach does not fit in this type of application due to the fault tolerance requirements. Moreover, as the size of the network grows, limitations in bandwidth severely limits the possibility of conveying and using global information. As such, the utilization of decentralized techniques for forming new sensor topologies and configurations is a highly desired quality of robotic sensor networks. In this thesis, several distributed task allocation algorithms will be explained and compared in different scenarios. They are based on a market approach since our interest is not only to obtain a feasible solution, but also an efficient one. Also, an analysis of the efficiency of those algorithms using probabilistic techniques will be explained. Finally, the task allocation algorithms will be implemented on a real system consisted of a team of six robots and integrated in a complete robotic system that considers obstacle avoidance and path planning. The results will be validated in both simulations and real experiments.

Multi-robot systems are an established research area with a growing number of applications. Efficient coordination in such systems usually requires knowledge of robot positions and the global map. This work presents a novel map-merging algorithm for merging 3D point cloud maps in multi-robot systems, which produces the global map and estimates robot positions. The algorithm is based on feature- matching transformation estimation with a novel descriptor matching scheme and works solely on point cloud maps without any additional auxiliary information. The algorithm can work with different SLAM approaches and sensor types and it is applicable in heterogeneous multi-robot systems. The map-merging algorithm has been evaluated on real-world datasets captured by both aerial and ground-based robots with a variety of stereo rig cameras and active RGB-D cameras. It has been evaluated in both indoor and outdoor environments. The proposed algorithm was implemented as a ROS package and it is currently distributed in the ROS distribution. To the best of my knowledge, it is the first ROS package for map-merging of 3D maps.

abstract: Robotic technology is advancing to the point where it will soon be feasible to deploy massive populations, or swarms, of low-cost autonomous robots to collectively perform tasks over large domains and time scales. Many of these tasks will require the robots to allocate themselves around the boundaries of regions or features of interest and achieve target objectives that derive from their resulting spatial configurations, such as forming a connected communication network or acquiring sensor data around the entire boundary. We refer to this spatial allocation problem as boundary coverage. Possible swarm tasks that will involve boundary coverage include cooperative load manipulation for applications in construction, manufacturing, and disaster response. In this work, I address the challenges of controlling a swarm of resource-constrained robots to achieve boundary coverage, which I refer to as the problem of stochastic boundary coverage. I first examined an instance of this behavior in the biological phenomenon of group food retrieval by desert ants, and developed a hybrid dynamical system model of this process from experimental data. Subsequently, with the aid of collaborators, I used a continuum abstraction of swarm population dynamics, adapted from a modeling framework used in chemical kinetics, to derive stochastic robot control policies that drive a swarm to target steady-state allocations around multiple boundaries in a way that is robust to environmental variations. Next, I determined the statistical properties of the random graph that is formed by a group of robots, each with the same capabilities, that have attached to a boundary at random locations. I also computed the probability density functions (pdfs) of the robot positions and inter-robot distances for this case. I then extended this analysis to cases in which the robots have heterogeneous communication/sensing radii and attach to a boundary according to non-uniform, non-identical pdfs. I proved that these more general coverage strategies generate random graphs whose probability of connectivity is Sharp-P Hard to compute. Finally, I investigated possible approaches to validating our boundary coverage strategies in multi-robot simulations with realistic Wi-fi communication. / Dissertation/Thesis / Doctoral Dissertation Computer Science 2016

Neste trabalho foi desenvolvido um estudo comparativo entre duas estratégias básicas para a combinação de mapas parciais baseados em marcos para sistemas multirobô: a estratégia por associação de marcos e a estratégia por distância relativa entre os robôs (também conhecida por rendez-vous). O ambiente simulado corresponde a um entorno plano povoado de árvores que são mapeadas por uma equipe de dois robôs móveis equipados com sensores laser para medir a largura e localização de cada _arvore (marco). Os mapas parciais são estimados usando o algoritmo FastSLAM. Além do estudo comparativo propõe-se também um algoritmo alternativo de localização e mapeamento simultâneos para multirrobôs cooperativos, utilizando as observações entre os robôs não só para o cálculo da transformação de coordenadas, mas também no desenvolvimento de um processo seqüencial para atualizar o alinhamento entre os mapas, explorando de forma mais eficiente as observações entre robôs. Os experimentos realizados demonstraram que o algoritmo proposto pode conduzir a resultados significativamente melhores em termos de precisão quando comparado com a abordagem de combinação de mapas tradicional (usando distância relativa entre os robôs). / In this text a comparative survey between the two basic strategies used to combine partial landmark based maps in multi-robot systems, data association and inter-robot observations (known as rendezvous), is presented. The simulated environment is a at place populated by trees, which are going to be mapped by a two-mobile robot team equipped with laser range finders in order to measure every tree (landmark) location and width. Partial maps are estimated using the algorithm FastSLAM. Besides the comparative study it is also proposed an alternative algorithm for Simultaneous Localization and Mapping (SLAM) in multi-robot cooperative systems. It uses observations between robots (detections) not only for calculating the coordinate transformation but also in the development of a sequential process for updating the alignment between maps, exploiting in a more efficient way the inter-robot observations. The experiments showed that the algorithm can lead to significantly better results in terms of accuracy when compared with the traditional approach of combining maps (using the relative distance between robots).

abstract: One potential application of multi-robot systems is collective transport, a task in which multiple mobile robots collaboratively transport a payload that is too large or heavy to be carried by a single robot. Numerous control schemes have been proposed for collective transport in environments where robots can localize themselves (e.g., using GPS) and communicate with one another, have information about the payload's geometric and dynamical properties, and follow predefined robot and/or payload trajectories. However, these approaches cannot be applied in uncertain environments where robots do not have reliable communication and GPS and lack information about the payload. These conditions characterize a variety of applications, including construction, mining, assembly in space and underwater, search-and-rescue, and disaster response. Toward this end, this thesis presents decentralized control strategies for collective transport by robots that regulate their actions using only their local sensor measurements and minimal prior information. These strategies can be implemented on robots that have limited or absent localization capabilities, do not explicitly exchange information, and are not assigned predefined trajectories. The controllers are developed for collective transport over planar surfaces, but can be extended to three-dimensional environments. This thesis addresses the above problem for two control objectives. First, decentralized controllers are proposed for velocity control of collective transport, in which the robots must transport a payload at a constant velocity through an unbounded domain that may contain strictly convex obstacles. The robots are provided only with the target transport velocity, and they do not have global localization or prior information about any obstacles in the environment. Second, decentralized controllers are proposed for position control of collective transport, in which the robots must transport a payload to a target position through a bounded or unbounded domain that may contain convex obstacles. The robots are subject to the same constraints as in the velocity control scenario, except that they are assumed to have global localization. Theoretical guarantees for successful execution of the task are derived using techniques from nonlinear control theory, and it is shown through simulations and physical robot experiments that the transport objectives are achieved with the proposed controllers. / Dissertation/Thesis / Doctoral Dissertation Mechanical Engineering 2020

abstract: The need for incorporating game engines into robotics tools becomes increasingly crucial as their graphics continue to become more photorealistic. This thesis presents a simulation framework, referred to as OpenUAV, that addresses cloud simulation and photorealism challenges in academic and research goals. In this work, OpenUAV is used to create a simulation of an autonomous underwater vehicle (AUV) closely following a moving autonomous surface vehicle (ASV) in an underwater coral reef environment. It incorporates the Unity3D game engine and the robotics software Gazebo to take advantage of Unity3D's perception and Gazebo's physics simulation. The software is developed as a containerized solution that is deployable on cloud and on-premise systems. This method of utilizing Gazebo's physics and Unity3D perception is evaluated for a team of marine vehicles (an AUV and an ASV) in a coral reef environment. A coordinated navigation and localization module is presented that allows the AUV to follow the path of the ASV. A fiducial marker underneath the ASV facilitates pose estimation of the AUV, and the pose estimates are filtered using the known dynamical system model of both vehicles for better localization. This thesis also investigates different fiducial markers and their detection rates in this Unity3D underwater environment. The limitations and capabilities of this Unity3D perception and Gazebo physics approach are examined. / Dissertation/Thesis / Masters Thesis Computer Science 2020