Exploration via Structured Triangulation by a Multi-Robot System with Bearing-Only Low-Resolution Sensors
It provides a practical solution for large populations of low-cost robots in applications like environmental monitoring or search and rescue, though it is incremental as it builds on existing triangulation methods.
The paper tackles the problem of exploring and triangulating an unknown region with a multi-robot system using bearing-only low-resolution sensors, resulting in a triangulation that covers a large area with high-quality triangles and path lengths within a constant factor of the shortest Euclidean distance.
This paper presents a distributed approach for exploring and triangulating an unknown region using a multi- robot system. The objective is to produce a covering of an unknown workspace by a fixed number of robots such that the covered region is maximized, solving the Maximum Area Triangulation Problem (MATP). The resulting triangulation is a physical data structure that is a compact representation of the workspace; it contains distributed knowledge of each triangle, adjacent triangles, and the dual graph of the workspace. Algorithms can store information in this physical data structure, such as a routing table for robot navigation Our algorithm builds a triangulation in a closed environment, starting from a single location. It provides coverage with a breadth-first search pattern and completeness guarantees. We show the computational and communication requirements to build and maintain the triangulation and its dual graph are small. Finally, we 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. We validate our theoretical results with experiments on triangulating a region with a system of low-cost robots. Analysis of the resulting quality of the 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.