• Sorted by Date • Classified by Publication Type • Classified by Topic • Grouped by Student (current) • Grouped by Former Students •
Roi Yehoshua. Robotic Adversarial Coverage. Ph.D.
Thesis, Bar Ilan University, 2018.
Coverage is a fundamental problem in robotics, where one or more robots are required to visit every point in a target area at least once. All previous work on the coverage problem focused on finding a coverage path that minimizes the coverage time. In this work we consider a new and more generalversion of the problem: adversarial coverage. Here, the robot operates inan hazardous environment that contains threats that might stop the robot.The objective is to find a coverage path that both minimizes the coveragetime and maximizes the probability of completing the coverage. Adversarialcoverage has many real-world applications, from searching for melted fuelrods in damaged nuclear power plants to demining and surveillance of enemyforces in the battlefield.In the first part of the work we formally define the adversarial coverageproblem, examine various variants of the problem, and suggest algorithmsfor solving them. We initially handle the offline version of the problem, inwhich a map of the threats is given to the robot in advance, thus the coverage path can be computed prior to the coverage. We suggest two heuristicalgorithms for computing the coverage path in polynomial time. We establish theoretical bounds on the performance of these algorithms, and comparetheir effectiveness in various types of environments and settings. We alsoshow how the optimal coverage path can be found in small instances of theproblem by modeling it as a Markov Decision Process (MDP). Second, wedeal with the online version of the problem, in which the robot has no mapof the environment, and thus has to use real-time sensor measurements inorder to detect the threats. We describe an online sensor-based algorithmfor the coverage, that uses the safest possible coverage path, and analyze itsperformance. Third, we show how using a multi-robot team for the coveragecan both increase the probability of completing the coverage and reduce thetotal coverage time. We describe a multi-robot adversarial coverage algorithm, that divides the coverage task between the robots in the team in away that maximizes their survivability while optimizing the coverage time.The proposed algorithms have been tested both in simulation and on realrobotic platforms.In the second part of the work we examine the problem of adversarialcoverage from the perspective of the adversary. The adversary’s goal is toprotect its territory from being covered by a robot. Thus, it needs to place thethreats in the environment in a way that maximizes its probability of stopping the robot. This problem, named the coverage defending problem, has itsown real-world applications, such as the strategic placement of surveillancecameras in a building as to protect it from being explored by an adversarialforce. We describe different strategies for the adversary (the defender) forchoosing the locations of the threats, depending upon its knowledge of therobot’s coverage strategy. We show that in some cases the optimal strategyfor the adversary can be computed in polynomial time (e.g., when the adversary has full-knowledge of the robot’s coverage strategy), and for other caseswe suggest heuristics that can significantly outperform the random baselinestrategy.In the last part of the work we describe a new general method for solvingMDPs based on real-time dynamic programming, that provides a significantimprovement over state-of-the-art methods. We show how this method canbe used to find near-optimal solutions to the adversarial coverage problem, aswell as solve other benchmark problems from the MDP literature, empiricallyyielding up to a six-fold reduction in the amount of time required to achievepolicy performance comparable to existing methods.
@PhdThesis{yehoshua-phd,
author = {Roi Yehoshua},
title = {Robotic Adversarial Coverage},
school = {{B}ar {I}lan {U}niversity},
year = {2018},
wwwnote = {},
OPTannote = {} ,
abstract = {
Coverage is a fundamental problem in robotics, where one or more robots are required to visit every point in a target area at least once.
All previous work on the coverage problem focused on finding a coverage path that minimizes
the coverage time. In this work we consider a new and more general
version of the problem: adversarial coverage. Here, the robot operates in
an hazardous environment that contains threats that might stop the robot.
The objective is to find a coverage path that both minimizes the coverage
time and maximizes the probability of completing the coverage. Adversarial
coverage has many real-world applications, from searching for melted fuel
rods in damaged nuclear power plants to demining and surveillance of enemy
forces in the battlefield.
In the first part of the work we formally define the adversarial coverage
problem, examine various variants of the problem, and suggest algorithms
for solving them. We initially handle the offline version of the problem, in
which a map of the threats is given to the robot in advance, thus the coverage
path can be computed prior to the coverage. We suggest two heuristic
algorithms for computing the coverage path in polynomial time. We establish
theoretical bounds on the performance of these algorithms, and compare
their effectiveness in various types of environments and settings. We also
show how the optimal coverage path can be found in small instances of the
problem by modeling it as a Markov Decision Process (MDP). Second, we
deal with the online version of the problem, in which the robot has no map
of the environment, and thus has to use real-time sensor measurements in
order to detect the threats. We describe an online sensor-based algorithm
for the coverage, that uses the safest possible coverage path, and analyze its
performance. Third, we show how using a multi-robot team for the coverage
can both increase the probability of completing the coverage and reduce the
total coverage time. We describe a multi-robot adversarial coverage algorithm, that divides the coverage task between the robots in the team in a
way that maximizes their survivability while optimizing the coverage time.
The proposed algorithms have been tested both in simulation and on real
robotic platforms.
In the second part of the work we examine the problem of adversarial
coverage from the perspective of the adversary. The adversary’s goal is to
protect its territory from being covered by a robot. Thus, it needs to place the
threats in the environment in a way that maximizes its probability of stopping
the robot. This problem, named the coverage defending problem, has its
own real-world applications, such as the strategic placement of surveillance
cameras in a building as to protect it from being explored by an adversarial
force. We describe different strategies for the adversary (the defender) for
choosing the locations of the threats, depending upon its knowledge of the
robot’s coverage strategy. We show that in some cases the optimal strategy
for the adversary can be computed in polynomial time (e.g., when the adversary
has full-knowledge of the robot’s coverage strategy), and for other cases
we suggest heuristics that can significantly outperform the random baseline
strategy.
In the last part of the work we describe a new general method for solving
MDPs based on real-time dynamic programming, that provides a significant
improvement over state-of-the-art methods. We show how this method can
be used to find near-optimal solutions to the adversarial coverage problem, as
well as solve other benchmark problems from the MDP literature, empirically
yielding up to a six-fold reduction in the amount of time required to achieve
policy performance comparable to existing methods.
},
}
Generated by bib2html.pl (written by Patrick Riley ) on Sun Feb 08, 2026 18:23:11