Multirobot Tree and Graph Exploration

被引:69
作者
Brass, Peter [1 ,2 ]
Cabrera-Mora, Flavio [3 ,4 ]
Gasparri, Andrea [5 ]
Xiao, Jizhong [1 ,2 ]
机构
[1] CUNY City Coll, Dept Comp Sci, New York, NY 10031 USA
[2] CUNY City Coll, Dept Elect Engn, New York, NY 10031 USA
[3] CUNY, Grad Ctr, New York, NY 10016 USA
[4] CUNY City Coll, Dept Elect Engn, New York, NY 10016 USA
[5] Univ Rome Roma Tre, Dept Comp Sci, I-00146 Rome, Italy
基金
美国国家科学基金会;
关键词
Distributed robotics; mapping; multirobot exploration; path planning; COVERAGE;
D O I
10.1109/TRO.2011.2121170
中图分类号
TP24 [机器人技术];
学科分类号
080202 ; 1405 ;
摘要
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.
引用
收藏
页码:707 / 717
页数:11
相关论文
共 33 条
  • [1] Exploring unknown environments
    Albers, S
    Henzinger, MR
    [J]. SIAM JOURNAL ON COMPUTING, 2000, 29 (04) : 1164 - 1188
  • [2] Awerbuch B., 1995, Proceedings of the Eighth Annual Conference on Computational Learning Theory, P321, DOI 10.1145/225298.225337
  • [3] Awerbuch B., 1998, Proceedings of the Eleventh Annual Conference on Computational Learning Theory, P280, DOI 10.1145/279943.279998
  • [4] Coverage, exploration and deployment by a mobile robot and communication network
    Batalin, MA
    Sukhatme, GS
    [J]. TELECOMMUNICATION SYSTEMS, 2004, 26 (2-4) : 181 - 196
  • [5] The design and analysis of an efficient local algorithm for coverage and exploration based on sensor network deployment
    Batalin, Maxim A.
    Sukhatme, Gaurav S.
    [J]. IEEE TRANSACTIONS ON ROBOTICS, 2007, 23 (04) : 661 - 675
  • [6] Bender M. A., 1998, Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing, P269, DOI 10.1145/276698.276759
  • [7] BLUM A, 1991, P 23 ANN ACM S THEOR, P494
  • [8] Brass P, 2009, IEEE INT CONF ROBOT, P495
  • [9] Budach L., 1975, Elektronische Informationsverarbeitung und Kybernetik (EIK), V11, P661
  • [10] CHIN W, 1986, P 2 ANN S COMP GEOM, P24, DOI DOI 10.1145/10515.10518