Safest path adversarial coverage

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

Authors

• Roi Yehoshua
• Noa Agmon
• Gal A. Kaminka

Keywords

• Robots
• Joining processes
• Approximation algorithms
• Algorithm design and analysis
• Heuristic algorithms
• Complexity theory
• Linear programming
• Safest Path
• Target Area
• Type Of Environment
• Heuristic Algorithm
• Version Of Problem
• Spanning Tree
• Greedy Approach
• Coverage Problem
• Problem In Robotics
• Coverage Path
• Objective Function
• Estimation Algorithm
• Number Of Areas
• Grid Cells
• Edge Weights
• Percent Cover
• Nuclear Power Plant
• Polynomial-time Algorithm
• Safe Area
• Depth-first
• Dangerous Areas
• Contiguous Areas
• Dijkstra’s Algorithm
• Number Of Threats
• Traveling Salesman Problem
• Rows Of Cells
• Side Of Area