Structured triangulation in multi-robot systems: Coverage, patrolling, Voronoi partitions, and geodesic centers
| Autor: | Seoung Kyou Lee, James McLurkin, Sándor P. Fekete |
|---|---|
| Rok vydání: | 2016 |
| Předmět: |
0209 industrial biotechnology
Theoretical computer science Applied Mathematics Mechanical Engineering Distributed computing Triangulation (social science) 02 engineering and technology Data structure Computer Science::Robotics Euclidean distance 020901 industrial engineering & automation Artificial Intelligence Dual graph Distributed algorithm Modeling and Simulation Path (graph theory) 0202 electrical engineering electronic engineering information engineering Robot 020201 artificial intelligence & image processing Electrical and Electronic Engineering Voronoi diagram Software Mathematics |
| Zdroj: | The International Journal of Robotics Research. 35:1234-1260 |
| ISSN: | 1741-3176 0278-3649 |
| DOI: | 10.1177/0278364915624974 |
| Popis: | We present a fundamental framework for organizing exploration, coverage, and surveillance by a swarm of robots with limited individual capabilities, based on triangulating an unknown environment with a multi-robot system. Locally, an individual triangle is easy for a single robot to manage and covers a small area; globally, the topology of the triangulation approximately captures the geometry of the entire environment. Combined, a multi-robot system can explore, map, navigate, and patrol. Algorithms can store information in triangles that the robots can read and write as they run their algorithms. This creates a physical data structure (PDS) that is both robust and versatile. We study distributed approaches to triangulating an unknown, two-dimensional Euclidean space using a multi-robot network. The resulting PDS is a compact representation of the workspace, contains distributed knowledge of each triangle, encodes the dual graph of the triangulation, and supports reads and writes of auxiliary data. The ability to store and process this auxiliary information enables the simple robots to solve complex problems. We develop distributed algorithms for dual-graph navigation, patrolling, construction of a topological Voronoi tessellation, and location of the geodesic centers in non-convex regions. We provide theoretical performance guarantees for the quality of constructed triangulation and the connectivity of a dual graph in the triangulation. In addition, we show that the path lengths of the physical navigation are within a constant factor of the shortest-path Euclidean distance. We validate these theoretical results with simulations and experiments with a dozen or more robots. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|