Barrier coverage: deploying robot guards to prevent intrusion

Abstract

In this work, we formalize the problem of barrier coverage, that is, the problem of preventing undetected intrusion in a particular region using robot sensors. We give methods for complete barrier coverage in a two-dimensional polygonally-bounded region, for variable bounded-range line-of-sight sensors. To do this, we define barrier candidates, which allow us to search a limited set of possible guard configurations to find the minimum barrier, and convert the problem to a network flows problem. We extend this result to fixed-range line-of-sight, and fixed-range omnidirectional sensors. As the methods for fixed-range sensors are intractable, we also give efficient approximate methods. These approximate methods also use barrier candidates to quickly find good candidate deployments. We use these barriers together with noncooperative zero-sum game theory to construct partial barriers. These are strategies for minimizing undetected intrusion when there is a limitation on available guard resources. We give equilibrium strategies for guards and intruder for the above three guard types in two dimensions. For variable-length sensors we derive strategies using barrier candidates. For fixed length guards we derive strategies using minimum fixed-length barriers, in conjunction with thick paths.