A Visibility-Based Algorithm for Multi-Robot Boundary Coverage

Abstract

Cell decomposition is often used in autonomous area coverage. We propose a visibility-based decomposition algorithm for single robot boundary coverage and a corresponding multi-robot algorithm in unknown environment. A graph data structure is exploited for completeness of coverage and incremental description of partially observed world. Visibility-based decomposition facilitates the construction of graph and algorithms operated on it. In the context of multi-robot, a dynamically selected highest priority robot is in charge of information share and synchrony through communication, polygon set operations provide tools for environmental information mergence, a distributed algorithm for multi-robot boundary coverage is proposed based on those technologies. Finally the experimental results show the relationships between robot number and traversable gate number, some future subjects of researches are introduced.