Constructing spanning trees for efficient multi-robot coverage

被引:57
作者
Agmon, Noa [1 ]
Hazon, Noam [1 ]
Kaminka, Gal A. [1 ]
机构
[1] Bar Ilan Univ, MAVERICK Grp, Dept Comp Sci, IL-52100 Ramat Gan, Israel
来源
2006 IEEE INTERNATIONAL CONFERENCE ON ROBOTICS AND AUTOMATION (ICRA), VOLS 1-10 | 2006年
关键词
D O I
10.1109/ROBOT.2006.1641951
中图分类号
TP [自动化技术、计算机技术];
学科分类号
0812 ;
摘要
This paper discusses the problem of building efficient coverage paths for a team of robots. An efficient multirobot coverage algorithm should result in a coverage path for every robot, such that the union of all paths generates a full coverage of the terrain and the total coverage time is minimized. A method, underlying several coverage algorithms, suggests the use of spanning trees as base for creating coverage paths. Current studies assume that the spanning tree is given, and try to make the most out of the given configuration. However, overall performance of the coverage is heavily dependent on the given spanning tree. This paper tackles the open challenge of constructing a coverage spanning tree that minimizes the time to complete coverage. We argue that the choice of the initial spanning tree has far reaching consequences concerning the coverage time, and if the tree is constructed appropriately, it could considerably reduce the coverage time of the terrain. Therefore the problem studied here is finding spanning trees that will decrease the coverage time of the terrain when used as base for multi-robot coverage algorithms. The main contributions of this paper are twofold. First, it provides initial sound discussion and results concerning the construction of the tree as a crucial base for any efficient coverage algorithm. Second, it describes a polynomial-time tree construction algorithm that, as shown in extensive simulations, dramatically improves the coverage time even when used as a basis for a simple, inefficient, coverage algorithm.
引用
收藏
页码:1698 / +
页数:2
相关论文
共 10 条
  • [1] Batalin MA, 2002, DISTRIBUTED AUTONOMOUS ROBOTIC SYSTEMS 5, P373
  • [2] Coverage for robotics - A survey of recent results
    Choset, H
    [J]. ANNALS OF MATHEMATICS AND ARTIFICIAL INTELLIGENCE, 2001, 31 (1-4) : 113 - 126
  • [3] Competitive on-line coverage of grid environments by a mobile robot
    Gabriely, Y
    Rimon, E
    [J]. COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 2003, 24 (03): : 197 - 224
  • [4] Spanning-tree based coverage of continuous areas by a mobile robot
    Gabriely, Y
    Rimon, E
    [J]. ANNALS OF MATHEMATICS AND ARTIFICIAL INTELLIGENCE, 2001, 31 (1-4) : 77 - 98
  • [5] HAZON N, 2005, REDUNDANCY EFFICIENC
  • [6] HAZON N, 2005, P IEEE INT C ROB AUT
  • [7] Limited communication, multi-robot team based coverage
    Rekleitis, I
    Lee-Shue, V
    New, AP
    Choset, H
    [J]. 2004 IEEE INTERNATIONAL CONFERENCE ON ROBOTICS AND AUTOMATION, VOLS 1- 5, PROCEEDINGS, 2004, : 3462 - 3468
  • [8] Multi-robot collaboration for robust exploration
    Rekleitis, I
    Dudek, G
    Milios, E
    [J]. ANNALS OF MATHEMATICS AND ARTIFICIAL INTELLIGENCE, 2001, 31 (1-4) : 7 - 40
  • [9] Wagner I. A., 1997, COMMUN COMPUT PHYS, P289
  • [10] ZHENG X, 2005, P IROS