Abstract | ||
---|---|---|
We consider a perimeter defense problem in which a single vehicle seeks to defend a compact region from intruders in a one-dimensional environment parameterized by the perimeter size and the intruder-to-vehicle speed ratio. The intruders move inward with fixed speed and direction to reach the perimeter. We provide both positive and negative worst-case performance results over the parameter space using competitive analysis. We first establish fundamental limits by identifying the most difficult parameter combinations that admit no c-competitive algorithms for any constant c >= 1 and slightly easier parameter combinations in which every algorithm is at best 2-competitive. We then design three classes of algorithms and prove they are 1, 2, and 4-competitive, respectively, for increasingly difficult parameter combinations. Finally, we present numerical studies that provide insights into the performance of these algorithms against stochastically generated intruders. |
Year | DOI | Venue |
---|---|---|
2021 | 10.23919/ACC50511.2021.9483308 | 2021 AMERICAN CONTROL CONFERENCE (ACC) |
DocType | ISSN | Citations |
Conference | 0743-1619 | 0 |
PageRank | References | Authors |
0.34 | 0 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Shivam Bajaj | 1 | 0 | 0.34 |
Eric Torng | 2 | 0 | 0.68 |
Shaunak D. Bopardikar | 3 | 1 | 5.48 |