• Sorted by Date • Classified by Publication Type • Classified by Topic • Grouped by Student (current) • Grouped by Former Students •
Noam Hazon and Gal Kaminka.
On Redundancy, Efficiency, and Robustness in Coverage for Multiple Robots. Robotics and Autonomous Systems,
56(12):1102–1114, 2008.
Motivated by potential efficiency and robustness gains, there is growing interest in the use of multiple robots for coverage. In coverage, robots visit every point in a target area, at least once. Previous investigations of multi-robot coverage focus on completeness of the coverage, and on eliminating redundancy, but do not formally address robustness. Moreover, a common assumption is that elimination of redundancy leads to improved efficiency (coverage time). We address robustness and efficiency in a novel family of multi-robot coverage algorithms, based on spanning-tree coverage of approximate cell decomposition of the work area. 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 robot---thus no performance gain is guaranteed in non-redundant coverage. Surprisingly, however, redundant coverage algorithms lead to guaranteed performance which halves the coverage time even in the worst case. We present a polynomial-time redundant-coverage algorithm, whose coverage time is optimal, and which is able to address robots heterogeneous in speed and fuel. We compare the performance of all algorithms empirically and show that use of the optimal algorithm leads to significant improvements in coverage time.
@Article{ras08,
author = {Noam Hazon and Gal Kaminka},
title = {On Redundancy, Efficiency, and Robustness in Coverage for Multiple Robots},
journal = {Robotics and Autonomous Systems},
year = {2008},
OPTkey = {},
volume = {56},
number = {12},
pages = {1102--1114},
OPTmonth = {December},
OPTnote = {},
wwwnote = {},
abstract = {
Motivated by potential efficiency and robustness gains, there is growing interest in the use of
multiple robots for \emph{coverage}. In coverage, robots visit every point in a target
area, at least once. Previous investigations of multi-robot
coverage focus on completeness of the coverage, and on eliminating redundancy, but do
not formally address robustness. Moreover, a common assumption
is that elimination of redundancy leads to improved efficiency (coverage time). We address
robustness and efficiency in a novel family of multi-robot coverage
algorithms, based on spanning-tree coverage of approximate cell
decomposition of the work area. 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 robot---thus no performance gain is
guaranteed in non-redundant coverage. Surprisingly, however,
redundant coverage algorithms lead to guaranteed performance which
halves the coverage time even in the worst case. We present a polynomial-time
redundant-coverage algorithm, whose coverage time is optimal, and which is
able to address robots heterogeneous in speed and fuel. We compare the performance
of all algorithms empirically and show that use of the optimal algorithm leads
to significant improvements in coverage time.},
OPTannote = {}
}
Generated by bib2html.pl (written by Patrick Riley ) on Fri Aug 30, 2024 17:29:51