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.
|School:||University of Illinois at Urbana-Champaign|
|School Location:||United States -- Illinois|
|Source:||DAI-B 69/05, Dissertation Abstracts International|
|Subjects:||Mathematics, Robots, Computer science|
|Keywords:||Barriers, Coverage, Geometry, Intrusion, Robots, Sensors, Separation|
Copyright in each Dissertation and Thesis is retained by the author. All Rights Reserved
The supplemental file or files you are about to download were provided to ProQuest by the author as part of a
dissertation or thesis. The supplemental files are provided "AS IS" without warranty. ProQuest is not responsible for the
content, format or impact on the supplemental file(s) on our system. in some cases, the file type may be unknown or
may be a .exe file. We recommend caution as you open such files.
Copyright of the original materials contained in the supplemental file is retained by the author and your access to the
supplemental files is subject to the ProQuest Terms and Conditions of use.
Depending on the size of the file(s) you are downloading, the system may take some time to download them. Please be