Exploration via structured triangulation by a multi-robot system with bearing-only low-resolution sensors
Exploration via structured triangulation by a multi-robot system with bearing-only low-resolution sensors
复制标题
DOI：
10.1109/icra.2014.6907155
复制
发表时间：
2014-02
期刊：
影响因子：
--
通讯作者：
SeoungKyou Lee;Aaron T. Becker;S. Fekete;A. Kröller;James McLurkin
中科院分区：
文献类型：
--
作者：
SeoungKyou Lee;Aaron T. Becker;S. Fekete;A. Kröller;James McLurkin
本文提出了一种利用多机器人系统对未知区域进行探索和三角测量的分布式方法。得到的三角测量是一个物理数据结构，它是工作空间的紧凑表示，包含每个三角形的分布式知识，构建三角测量的对偶图，并支持辅助数据的读写。我们的算法在一个封闭的二维欧几里得环境中建立一个三角测量，从一个单一的位置开始。它提供了宽度优先搜索模式和完整性保证的覆盖。我们证明了建立和维护三角剖分及其对偶图的计算和通信需求很小。然后，我们提出了一种使用对偶图的物理导航算法，并表明所得到的路径长度在最短路径欧几里得距离的常数因子内。最后，我们用一个低成本机器人系统对一个区域进行三角测量的实验来验证我们的理论结果。分析结果表明，大多数三角形质量高，覆盖面积大。三角测量、对偶图和导航的实现都使用固定大小的通信消息，是大量低成本机器人的实用解决方案。
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.