Competitive Perimeter Defense on a Line

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.