Dissertation/Thesis Abstract

Barrier coverage: Deploying robot guards to prevent intrusion
by Kloder, Stephen, Ph.D., University of Illinois at Urbana-Champaign, 2008, 139; 3314962
Abstract (Summary)

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.

Indexing (document details)
Advisor: Hutchinson, Seth
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
Publication Number: 3314962
ISBN: 978-0-549-65031-7
Copyright © 2021 ProQuest LLC. All rights reserved. Terms and Conditions Privacy Policy Cookie Policy