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 the environment through the tree's leaves. We adopt the technique of competitive analysis to characterize the performance of an online algorithm for the defending vehicle. We first derive fundamental limits on the performance of any online algorithm relative to that of an optimal offline algorithm. Specifically, we give three fundamental conditions for finite, 2, and 3/2 competitive ratios in terms of the environment parameters. We then design and analyze three classes of online algorithms that have provably finite competitiveness under varying environmental parameter regimes. Finally, we give a numerical visualization of these regimes to better show the comparative strengths and weaknesses of each algorithm.
Code (0)
등록된 구현이 없습니다.
Methods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
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 rat…
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 LearningA Decentralized Multi-UAV Spatio-Temporal Multi-Task Allocation Approach for Perimeter Defense
This paper provides a new solution approach to a multi-player perimeter defense game, in which the intruders' team tries to enter the territory, and a team of defenders protects the territory by capturing intruders on th…