Barrier Coverage for Variable Bounded-Range Line-of-Sight Guards

Abstract

In this paper, we formalize the problem of barrier coverage, that is, the problem of preventing undetected intrusion in a particular region using robot sensors. We solve the problem of finding the minimum-length barrier in the case of variable bounded-range line-of-sight sensors in a two-dimensional polygonally-bounded region. We do this by building a graph of candidate barriers that could potentially be in the minimum barrier. The dual of this graph shows the connectivity of the free space. We thus reduce the problem to the network flows maximum-flow/minimum-cut problem.