Gal A. Kaminka's Publications

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

Robotic Adversarial Coverage of Known Environments

Roi Yehoshua, Noa Agmon, and Gal A. Kaminka. Robotic Adversarial Coverage of Known Environments. International Journal of Robotics Research, 2016. In press
The article's web page on the journal home is at http://ijr.sagepub.com/content/early/2016/02/20/0278364915625785

Download

[PDF]650.1kB  [gzipped postscript] [postscript] [HTML] 

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

BibTeX

@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>}, 
  note = {In press},
 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 Sun Jul 23, 2017 22:08:49