Gal A. Kaminka's Publications

Sorted by DateClassified by Publication TypeClassified by TopicGrouped by Student (current)Grouped by Former Students

Editorial: Annals of Mathematics and Artificial Intelligence special issue on multi-robot coverage, search, and exploration

Gal A. Kaminka and Amir Shapiro. Editorial: Annals of Mathematics and Artificial Intelligence special issue on multi-robot coverage, search, and exploration . Annals of Math and Artificial Intelligence, 52(2--4):107–108, 2008.

Download

(unavailable)

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 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.

Additional Information

The article's official web page is at: .

BibTeX

@Article{amai08editorial,
author = {Gal A. Kaminka and Amir Shapiro},
title = {Editorial: Annals of Mathematics and Artificial Intelligence special issue on multi-robot coverage, search, and exploration },
journal = AMAI,
year = {2008},
OPTkey = {},
volume = {52},
number = {2--4},
pages = {107--108},
OPTmonth = {April},
note = {},
  OPTdoi = {http://dx.doi.org/10.1007/s10472-008-9105-6},  
  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 significantly 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 Sun Oct 29, 2017 21:31:22