TY - GEN
T1 - Redundancy, efficiency and robustness in multi-robot coverage
AU - Hazon, Noam
AU - Kaminka, Gal A.
PY - 2005
Y1 - 2005
N2 - Area coverage is an important task for mobile robots, with many real-world applications. Motivated by potential efficiency and robustness improvements, there is growing interest in the use of multiple robots in coverage. Previous investigations of multi-robot coverage focuses on completeness and eliminating redundancy, but does not formally address robustness, nor examine the impact of the initial positions of robots on the coverage time. Indeed, a common assumption is that non-redundancy leads to improved coverage time. We address robustness and efficiency in a family of multi-robot coverage algorithms, based on spanning-tree coverage of approximate cell decomposition. We analytically show that the algorithms are robust, in that as long as a single robot is able to move, the coverage will be completed. We also show that non-redundant (non-backtracking) versions of the algorithms have a worst-case coverage time virtually identical to that of a single robotthus no performance gain is guaranteed in non-redundant coverage. Moreover, this worst-case is in fact common in real-world applications. Surprisingly, however, redundant coverage algorithms lead to guaranteed performance which halves the coverage time even in the worst case.
AB - Area coverage is an important task for mobile robots, with many real-world applications. Motivated by potential efficiency and robustness improvements, there is growing interest in the use of multiple robots in coverage. Previous investigations of multi-robot coverage focuses on completeness and eliminating redundancy, but does not formally address robustness, nor examine the impact of the initial positions of robots on the coverage time. Indeed, a common assumption is that non-redundancy leads to improved coverage time. We address robustness and efficiency in a family of multi-robot coverage algorithms, based on spanning-tree coverage of approximate cell decomposition. We analytically show that the algorithms are robust, in that as long as a single robot is able to move, the coverage will be completed. We also show that non-redundant (non-backtracking) versions of the algorithms have a worst-case coverage time virtually identical to that of a single robotthus no performance gain is guaranteed in non-redundant coverage. Moreover, this worst-case is in fact common in real-world applications. Surprisingly, however, redundant coverage algorithms lead to guaranteed performance which halves the coverage time even in the worst case.
UR - http://www.scopus.com/inward/record.url?scp=33846121632&partnerID=8YFLogxK
U2 - 10.1109/ROBOT.2005.1570205
DO - 10.1109/ROBOT.2005.1570205
M3 - ???researchoutput.researchoutputtypes.contributiontobookanthology.conference???
AN - SCOPUS:33846121632
SN - 078038914X
SN - 9780780389144
T3 - Proceedings - IEEE International Conference on Robotics and Automation
SP - 735
EP - 741
BT - Proceedings of the 2005 IEEE International Conference on Robotics and Automation
T2 - 2005 IEEE International Conference on Robotics and Automation
Y2 - 18 April 2005 through 22 April 2005
ER -