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\geq 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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Competitive Perimeter Defense in Tree Environments
We consider a perimeter defense problem in a rooted full tree graph environment in which a single defending vehicle seeks to defend a set of specified vertices, termed as the perimeter from mobile intruders that enter th…
Perimeter Defense using a Turret with Finite Range and Service Times
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\geq 2$ in…
Vision-based Perimeter Defense via Multiview Pose Estimation
Previous studies in the perimeter defense game have largely focused on the fully observable setting where the true player states are known to all players. However, this is unrealistic for practical implementation since d…
Pose EstimationState EstimationGraph Neural Networks for Decentralized Multi-Agent Perimeter Defense
In this work, we study the problem of decentralized multi-agent perimeter defense that asks for computing actions for defenders with local perceptions and communications to maximize the capture of intruders. One major ch…
Imitation LearningLearning Decentralized Strategies for a Perimeter Defense Game with Graph Neural Networks
We consider the problem of finding decentralized strategies for multi-agent perimeter defense games. In this work, we design a graph neural network-based learning framework to learn a mapping from defenders' local percep…
Graph Neural Network