• Sorted by Date • Classified by Publication Type • Classified by Topic • Grouped by Student (current) • Grouped by Former Students •
Noa Agmon, Noam Hazon, and
Gal A. Kaminka. The Giving Tree: Constructing Trees for Efficient Offline
and Online Multi-Robot Coverage. Annals of Math and Artificial Intelligence, 52(2--4):143–168, 2008.
This paper discusses the problem of building efficient coverage paths for a team of robots. An efficient multi-robot 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. However, overall performanceof the coverage is heavily dependent on the given spanning tree. This paper focuses on the challenge of constructing a coverage spanning tree forboth online and offline coverage that minimizes the time to complete coverage. Our general approach involves building a spanning tree by growingsub-trees from the initial location of the robots. This paper first describes apolynomial time tree-construction algorithm for offline coverage. The useof this algorithm is shown by extensive simulations to significantly improvethe coverage time of the terrain even when used as a basis for a simple, inefficient, coverage algorithm. Second, this paper provides an algorithm foronline coverage of a finite terrain based on spanning-trees, that is completeand guarantees linear time coverage with no redundancy in the coverage. Inaddition, the solutions proposed by this paper guarantee robustness to failing robots: the offline trees are used as base for robust multi-robot coveragealgorithms, and the online algorithm is proven to be robust.
The article's official web page is at: .
@Article{amai08,
author = {Noa Agmon and Noam Hazon and Gal A. Kaminka},
title = {The Giving Tree: Constructing Trees for Efficient Offline and Online Multi-Robot Coverage},
journal = AMAI,
year = {2008},
OPTkey = {},
volume = {52},
number = {2--4},
pages = {143--168},
OPTmonth = {},
note = {},
OPTdoi = {http://dx.doi.org/10.1007/s10472-009-9121-1},
wwwnote = {},
abstract = {
This paper discusses the problem of building efficient coverage paths for a
team of robots. An efficient multi-robot 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. However, overall performance
of the coverage is heavily dependent on the given spanning tree. This paper focuses on the challenge of constructing a coverage spanning tree for
both online and offline coverage that minimizes the time to complete coverage. Our general approach involves building a spanning tree by growing
sub-trees from the initial location of the robots. This paper first describes a
polynomial time tree-construction algorithm for offline coverage. The use
of this algorithm is shown by extensive simulations to signiï¬cantly improve
the coverage time of the terrain even when used as a basis for a simple, inefficient, coverage algorithm. Second, this paper provides an algorithm for
online coverage of a finite terrain based on spanning-trees, that is complete
and guarantees linear time coverage with no redundancy in the coverage. In
addition, the solutions proposed by this paper guarantee robustness to failing robots: the offline trees are used as base for robust multi-robot coverage
algorithms, and the online algorithm is proven to be robust.
},
OPTannote = {}
}
Generated by bib2html.pl (written by Patrick Riley ) on Fri Aug 30, 2024 17:29:51