.png){kind=icon}
返回
Multirobot Tree and Graph Exploration
.png){kind=icon}
PRE
AI
DOI：10.1109/TRO.2011.2121170.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
In this paper, we present an algorithm for the exploration of an unknown graph by multiple robots, which is never worse than depth-first search with a single robot. On trees, we prove that the algorithm is optimal for two robots. For k robots, the algorithm has an optimal dependence on the size of the tree but not on its radius. We believe that the algorithm performs well on any tree, and this is substantiated by simulations. For trees with e edges and radius r, the exploration time is less than 2e/k + (1 + (k/r))(k-1) (2/k!)r(k-1) = (2e/k) + O((k + r)(k-1)) (for r > k, <= (2e/k) + 2r(k-1)), thereby improving a recent method with time O((e/log k) + r) [2], and almost reaching the lower bound max((2e/k), 2r). The model underlying undirected-graph exploration is a set of rooms connected by opaque passages; thus, the algorithm is appropriate for scenarios like indoor navigation or cave exploration. In this framework, communication can be realized by bookkeeping devices being dropped by the robots at explored vertices, the states of which are read and changed by further visiting robots. Simulations have been performed in both tree and graph explorations to corroborate the mathematical results.
Keyword:
Distributed robotics
mapping
multirobot exploration
path planning
期刊
IF:
10.5
论文数:
3.3K
被引数:
2.8W
机构
引用论文
Estrogen receptor mediated activity in bankside groundwater, with flood suspended particulate matter and floodplain soil – An approach combining tracer substance, bioassay and target analysis.png)
Chemosphere
ChemosphereIF0
PREAI
分享收藏
查看更多内容