• Sorted by Date • Classified by Publication Type • Classified by Topic • Grouped by Student (current) • Grouped by Former Students •
Roi Yehoshua,
Noa Agmon, and Gal A. Kaminka. Robotic Adversarial Coverage of Known
Environments. International Journal of Robotics Research, 2016.
The article's web page on the journal home
is at http://ijr.sagepub.com/content/early/2016/02/20/0278364915625785
[PDF]650.1kB [gzipped postscript] [postscript] [HTML]
Coverage is a fundamental problem in robotics, where one or more robots are required to visit each point in a target area at least once. Most previous work concentrated on finding a coverage path that minimizes the coverage time. In this paper we consider a new and more general version of the problem: adversarial coverage. Here, the robot operates in an environment that contains threats that might stop the robot. The objective is to cover the target area as quickly as possible, while minimizing the probability that the robot will be stopped before completing the coverage. This version of the 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. In this paper we discuss the offline version of adversarial coverage, in which the map of threats is given to the robot in advance. First, we formally define the adversarial coverage problem, and present different optimizat ion criteria used for evaluation of coverage algorithms in adversarial environments. We show that finding an optimal solution to the adversarial coverage problem is NP-Hard. We therefore suggest two heuristic algorithms: STAC, a spanning-tree based coverage algorithm, and GAC, which follows a greedy approach. We establish theoretical bounds on the total risk involved in the coverage paths created by these algorithms and on their lengths. Lastly, we compare the effectiveness of these two algorithms in various types of environments and settings.
@article{ijrr15a,
author = {Roi Yehoshua and Noa Agmon and Gal A. Kaminka},
title = {Robotic Adversarial Coverage of Known Environments},
journal = IJRR,
OPTnote = {Your manuscript ID is IJR-15-2370},
year = {2016},
doi = {10.1177/0278364915625785},
wwwnote = {The article's web page on the journal home is at <a href="http://ijr.sagepub.com/content/early/2016/02/20/0278364915625785">http://ijr.sagepub.com/content/early/2016/02/20/0278364915625785</a>},
abstract = {Coverage is a fundamental problem in robotics, where one
or more robots are required to visit each point in a
target area at least once. Most previous work
concentrated on finding a coverage path that
minimizes the coverage time. In this paper we
consider a new and more general version of the
problem: \emph{adversarial coverage}. Here, the
robot operates in an environment that contains
threats that might stop the robot. The objective is
to cover the target area as quickly as possible,
while minimizing the probability that the robot will
be stopped before completing the coverage. This
version of the 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. In this paper we discuss the
offline version of adversarial coverage, in which
the map of threats is given to the robot in
advance. First, we formally define the adversarial
coverage problem, and present different optimizat
ion criteria used for evaluation of coverage
algorithms in adversarial environments. We show that
finding an optimal solution to the adversarial
coverage problem is NP-Hard. We therefore suggest
two heuristic algorithms: STAC, a spanning-tree
based coverage algorithm, and GAC, which follows a
greedy approach. We establish theoretical bounds on
the total risk involved in the coverage paths
created by these algorithms and on their
lengths. Lastly, we compare the effectiveness of
these two algorithms in various types of
environments and settings.},
}
Generated by bib2html.pl (written by Patrick Riley ) on Fri Apr 19, 2024 19:01:33