# Gal A. Kaminka's Publications

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

Roi Yehoshua, Noa Agmon, and Gal A. Kaminka. Safest Path Adversarial Coverage. In AAMAS workshop on Autonomous Robots and Multirobot Systems (ARMS), 2014. This is an early version of the IROS-14 paper of same title.

(unavailable)

### 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. While most previous work concentrated on finding a solution that completes the coverage as quickly as possible, in this paper we consider a new version of the problem: adversarial coverage. Here, the robot operates in an environment that contains threats that might stop the robot. We introduce the problem of finding the safest adversarial coverage path, and present different optimization criteria for the evaluation of these paths. We show that finding an optimal solution to the safest coverage problem is NP-Complete. We therefore suggest two heuristic algorithms: STAC, a spanning-tree based coverage algorithm, and GSAC, which follows a greedy approach. These algorithms produce close to optimal solutions in polynomial time. We establish theoretical Other Refereed Publicationbounds 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

@InProceedings{arms14roi,
author = {Roi Yehoshua and Noa Agmon and Gal A. Kaminka},
title  = {Safest Path Adversarial Coverage},
year   = {2014},
booktitle = {AAMAS workshop on Autonomous Robots and Multirobot Systems (ARMS)},
note = {This is an early version of the IROS-14 paper of same title.},
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. While
most previous work concentrated on finding a solution that completes the coverage
as quickly as possible, in this paper we consider a new version of the problem:
\emph{adversarial coverage}. Here, the robot operates in an environment that
contains threats that might stop the robot. We introduce the problem of finding the safest adversarial coverage path, and present different optimization criteria for
the evaluation of these paths. We show that finding an optimal solution to the
safest coverage problem is NP-Complete. We therefore suggest two heuristic  algorithms: STAC, a spanning-tree based coverage algorithm, and GSAC, which
follows a greedy approach. These algorithms produce close to optimal solutions
in polynomial time. We establish theoretical Other Refereed Publicationbounds 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 Sat Feb 24, 2018 00:31:02