Multi-Robot Adversarial Coverage

被引:5
作者
Yehoshua, Roi [1 ]
Agmon, Noa [1 ]
机构
[1] Bar Ilan Univ, Ramat Gan, Israel
来源
ECAI 2016: 22ND EUROPEAN CONFERENCE ON ARTIFICIAL INTELLIGENCE | 2016年 / 285卷
关键词
D O I
10.3233/978-1-61499-672-9-1493
中图分类号
TP18 [人工智能理论];
学科分类号
081104 ; 0812 ; 0835 ; 1405 ;
摘要
This work discusses the problem of adversarial coverage, in which one or more robots are required to visit every point of a given area, which contains threats that might stop the robots. The objective of the robots is to cover the target area as quickly as possible, while maximizing the percentage of covered area before they are stopped. This problem has many real-world applications, from performing coverage missions in hazardous fields such as nuclear power plants, to surveillance of enemy forces in the battlefield and field demining. Previous studies of the problem dealt with single-robot coverage. Using a multi-robot team for the coverage has clear advantages in terms of both coverage time and robustness: even if one robot is totally damaged, others may take over its coverage subtask. Hence, in this paper we describe a multi-robot coverage algorithm for adversarial environments that tries to maximize the percentage of covered area before the team is stopped, while minimizing the coverage time. We analytically show that the algorithm is robust, in that as long as a single robot is able to move, the coverage will be completed. We also establish theoretical bounds on the minimum covered area guaranteed by the algorithm and on the coverage time. Lastly, we evaluate the effectiveness of the algorithm in an extensive set of environments and settings.
引用
收藏
页码:1493 / 1501
页数:9
相关论文
共 22 条
[1]   Constructing spanning trees for efficient multi-robot coverage [J].
Agmon, Noa ;
Hazon, Noam ;
Kaminka, Gal A. .
2006 IEEE INTERNATIONAL CONFERENCE ON ROBOTICS AND AUTOMATION (ICRA), VOLS 1-10, 2006, :1698-+
[2]  
[Anonymous], IEEE RSJ INT C INT R
[3]  
Colegrave J., 1994, AIAANASA CIRFFSS, P107
[4]   Multi-robot area patrol under frequency constraints [J].
Elmaliach, Yehuda ;
Agmon, Noa ;
Kaminka, Gal A. .
ANNALS OF MATHEMATICS AND ARTIFICIAL INTELLIGENCE, 2009, 57 (3-4) :293-320
[5]  
Endres H, 1998, IEEE INT CONF ROBOT, P1779, DOI 10.1109/ROBOT.1998.677424
[6]   Competitive on-line coverage of grid environments by a mobile robot [J].
Gabriely, Y ;
Rimon, E .
COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 2003, 24 (03) :197-224
[7]   A survey on coverage path planning for robotics [J].
Galceran, Enric ;
Carreras, Marc .
ROBOTICS AND AUTONOMOUS SYSTEMS, 2013, 61 (12) :1258-1276
[8]   Border patrol and surveillance missions using multiple Unmanned Air Vehicles [J].
Girard, AR ;
Howell, AS ;
Hedrick, JK .
2004 43RD IEEE CONFERENCE ON DECISION AND CONTROL (CDC), VOLS 1-5, 2004, :620-625
[9]   On redundancy, efficiency, and robustness in coverage for multiple robots [J].
Hazon, Noam ;
Kaminka, Gal A. .
ROBOTICS AND AUTONOMOUS SYSTEMS, 2008, 56 (12) :1102-1114
[10]   Multilevel k-way partitioning scheme for irregular graphs [J].
Karypis, G ;
Kumar, V .
JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING, 1998, 48 (01) :96-129