Efficient Algorithms for Optimal Perimeter Guarding

Abstract—We investigate the problem of optimally assigning a
large number of robots (or other types of autonomous agents) to
guard the perimeters of closed 2D regions, where the perimeter of
each region to be guarded may contain multiple disjoint polygonal
chains. Each robot is responsible for guarding a subset of a
perimeter and any point on a perimeter must be guarded by
some robot. In allocating the robots, the main objective is to
minimize the maximum 1D distance to be covered by any robot
along the boundary of the regions. For this optimization problem
which we call optimal perimeter guarding (OPG), thorough
structural analysis is performed, which is then exploited to develop
fast exact algorithms that run in guaranteed low polynomial
time. In addition to formal analysis and proofs, experimental
evaluations and simulations are performed that further validate
the correctness and effectiveness of our algorithmic results.

Multi-Robot Systems,Monitoring,Surveillance,Optimality,Efficient Algorithms,Swarm Strategy,