Robotic Adversarial Coverage

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

Date of Award	2018
Original language	American English
Awarding Institution	Bar-Ilan University
Supervisor	Gal Kaminka (Supervisor) & Noa Agmon (Supervisor)