Files in this item



application/pdfBarrier Coverag ... s to Prevent Intrusion.pdf (4MB)
(no description provided)PDF


Title:Barrier Coverage: Deploying Robot Guards to Prevent Intrusion
Author(s):Kloder, Stephen
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 intractible, 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.
Issue Date:2008-05
Genre:Technical Report
Other Identifier(s):UIUCDCS-R-2008-2941
Rights Information:You are granted permission for the non-commercial reproduction, distribution, display, and performance of this technical report in any format, BUT this permission is only for a period of 45 (forty-five) days from the most recent time that you verified that this technical report is still available from the University of Illinois at Urbana-Champaign Computer Science Department under terms that include this permission. All other rights are reserved by the author(s).
Date Available in IDEALS:2009-04-22

This item appears in the following Collection(s)

Item Statistics