Distributed Space Coverage for Exploration, Localization, and Navigation in Unknown Environments
Lee, Seoung Kyou
McLurkin, James D.
Doctor of Philosophy
Many tasks, such as search and rescue, exploration and mapping, security and surveil- lance are suited for mobile robots. These tasks require the population to spread out over a large environment, where the sensing and communicating capacity of an individual robot might be too small to cover the entire environment. This thesis presents approaches for cooperative coverage tasks by large populations of robots to overcome the limitation of a single robot. Not only can a multi-robot system accomplish the coverage task far more efficiently than an individual robot, but also it is more reliable against individual hardware failure. This thesis investigates two different scenarios with respect to distributed multi-robot space coverage in an unknown environment: First, I consider the space coverage in un- bounded environments. This scenario takes care of robots searching or monitoring in an unlimited region, such as a forest or submarine sea floor. For efficient scanning, robots need to spread out sufficiently to cover a large area. At the same time, they have to be close to their neighbors to prevent network disconnection. In order to fulfill both requirements simultaneously, I present a cohesive configuration controller by combining existing flock- ing strategies with a boundary force algorithm and network sensing and mode switching method. By doing so, robots form a convex and cohesive configuration without any dis- connection. Moreover, they maintain this final configuration even while moving. Secondly, I study space coverage problem in bounded environments that pursues to build a robotic sensor network. In this scenario, I present an algorithm to construct a triangulation using multiple low-cost robots. The resulting triangulation approximately maps the geometric characteristics of its surrounding environment and produces a physical data structure that stores triangle information distributively. This physical data structure provides auxiliary data to robots and lets them accomplish the application’s goal using only local communications. In this thesis, I address one simple application for patrolling and one complex application for topological Voronoi tessellation and center computation. This work provides theoretical guarantees about the algorithm performance. I also provide numerous simulation and hardware experiment results using the model of low- cost platforms to validate the feasibility of presented methods. In both scenarios, robots successfully form desired configurations without the aid of centralized infrastructures. In addition, the group of robots maintains the connectivity while running the algorithms.
Multi-Robot System; Coverage Control; Swarm Intelligence; Distributed Algorithm; Computational Geometry