Competitive perimeter defense with a turret and a mobile vehicle

[摘要] We consider perimeter defense problem in a planar conical environment with two cooperative heterogeneous defenders, i.e., a turret and a mobile vehicle, that seek to defend a concentric perimeter against mobile intruders. Arbitrary numbers of intruders are released at the circumference of the environment at arbitrary time instants and locations. Upon release, they move radially inwards with fixed speed towards the perimeter. The defenders are heterogeneous in terms of their motion and capture capabilities. Specifically, the turret has a finite engagement range and can only turn (clockwise or anti-clockwise) in the environment with fixed angular rate whereas, the vehicle has a finite capture radius and can move in any direction with unit speed. We present a competitive analysis approach to this perimeter defense problem by measuring the performance of multiple cooperative online algorithms for the defenders against arbitrary inputs, relative to an optimal offline algorithm that has information about the entire input sequence in advance. Specifically, we establish necessary conditions on the parameter space to guarantee finite competitiveness of any online algorithm. We then design and analyze four cooperative online algorithms and characterize parameter regimes in which they have finite competitive ratios. In particular, our first two algorithms are 1-competitive in specific parameter regimes, our third algorithm exhibits different competitive ratios in different regimes of problem parameters, and our fourth algorithm is 1.5-competitive in specific parameter regimes. Finally, we provide multiple numerical plots in the parameter space to reveal additional insights into the relative performance of our algorithms.

[发布日期] 2023-02-27

[关键词] online optimization;perimeter defense;competitive ratio;pursuit evasion games;dynamic vehicle routing;cooperative agents