Perimeter Defense using a Turret with Finite Range and Startup Times
S. Bajaj, S. Bopardikar, A. Von Moll, E. Torng, D. Casbeer
Published in American Control Conference, 2023
We consider a perimeter defense problem in a planar conical environment comprising a single turret that has a finite range and non-zero service time. The turret seeks to defend a concentric perimeter against N ≥ 2 intruders. Upon release, each intruders move radially towards the perimeter with a fixed speed. To capture an intruder, the turret’s angle must be aligned with that of the intruder’s angle and must spend a specified capture time at that orientation. We present an online and an offline approach to this optimal problem. Specifically, for the offline approach, we establish that for general parameter regimes, this problem is equivalent to solving a Travelling Repairperson Problem with Time Windows (TRP- TW). We then identify specific parameter regimes in which there is a polynomial time algorithm that maximizes the number of intruders captured. For the online approach we present a competitive analysis technique in which we establish a fundamental guarantee on the existence of at best (N − 1)- competitive algorithms and design two online algorithms that are provably 1 and 2-competitive in specific parameter regimes.