This project 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 provides 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 navigation, or statistics for a patrolling application.


This paper presents an algorithm to build a triangulation starting from a single point of entry that provides complete coverage of the environment with, a breadth-first search order, and completeness guarantees. The resulting triangulation is a distributed physical data structure, and we show the computational and communication requirements to build and maintain it are small . We implement a navigation algorithm on the dual graph, and show that the resulting path lengths are within a constant factor of the shortest-path distance. Finally, we demonstrate a patrolling application, in which the coverage time for each triangle is stores , and robots can route to less-patrolled ares of the environment. We validate our theoretical results with experiments on triangulating a region with 21 low-cost robots. Their main sensor can only perform coarse angle estimates to neighboring robots, but no distance measurements, and are able to communicate locally, but not globally. Analysis of the resulting quality of the triangulation shows that most of the triangles are of high quality, and cover a large area. how is it still remarkable? The result is remarkable because a limited number of powerful robots cannot achieve any competitive factor for this problem.

Project Type: