Exploration via structured triangulation by a multi-robot system with bearing-only low-resolution sensors

Abstract

This paper presents a distributed approach for exploring and triangulating an unknown region using a multirobot system. The resulting triangulation is a physical data structure that is a: compact representation of the workspace, contains distributed knowledge of each triangle, builds the dual graph of the triangulation, and supports reads and writes of auxiliary data. Our algorithm builds a triangulation in a closed two-dimensional Euclidean environment, starting from a single location. It provides coverage with a breadth-first search pattern and completeness guarantees. We show that the computational and communication requirements to build and maintain the triangulation and its dual graph are small. We then present a physical navigation algorithm that uses the dual graph, and show that the resulting path lengths are within a constant factor of the shortest-path Euclidean distance. Finally, we validate our theoretical results with experiments on triangulating a region with a system of low-cost robots. Analysis of the resulting triangulation shows that most of the triangles are of high quality, and cover a large area. Implementation of the triangulation, dual graph, and navigation all use communication messages of fixed size, and are a practical solution for large populations of low-cost robots.