Capturing an area-covering robot

Abstract

Area coverage is a fundamental task in robotics, where one or more robots are required to visit all points in a target area at least once. In many real-world scenarios, the need arises for protecting one’s territory from being covered by a robot, e.g., when we need to defend a building from being surveyed by an adversarial force. Therefore, this paper discusses the problem of defending a given area from being covered by a robot. In this problem, the defender needs to choose the locations of k stationary guards in the target area, each one having some probability of capturing the robot, in a way that maximizes the probability of stopping the covering robot. We consider two types of covering robots: one that has an a-priori map of the environment, including the locations of the guards; and the other has no prior knowledge of the environment, and thus has to use real-time sensor measurements in order to detect the guards and plan its path according to their discovered locations. We show that in both cases the defender can exploit the target area’s topology, and specifically the vulnerability points in the area (i.e., places that must be visited by the robot more than once), in order to increase its chances of capturing the covering robot. We also show that although in general finding an optimal strategy for a defender with zero-knowledge on the robot’s coverage strategy is ${\mathcal {NP}}$-Hard, for certain values of k an optimal strategy can be found in polynomial time. For other cases we suggest heuristics that can significantly outperform the random baseline strategy. We provide both theoretical and empirical evaluation of our suggested algorithms.