Optimally Guarding Perimeters and Regions with Mobile Range Sensors
Siwei Feng, Jingjin Yu · 2020
We investigate the problem of using mobile robots equipped with 2D range sensors to optimally guard perimeters or regions.Given a bounded set in R 2 to be guarded, and k mobile sensors where the i-th sensor can cover a circular region with a variable radius ri, we seek the optimal strategy to deploy the k sensors to fully cover the set such that max ri is minimized.On the side of computational complexity, we show that computing a 1.152-optimal solution for guarding a perimeter or a region is NP-hard even when the set is a simple polygon or the boundary of a simple polygon, i.e., the problem is hard to approximate.The hardness result on perimeter guarding holds when each sensor may guard at most two disjoint perimeter segments.On the side of computational methods, for the guarding perimeters, we develop a fully polynomial time approximation scheme (FPTAS) for the special setting where each sensor may only guard a single continuous perimeter segment, suggesting that the aforementioned hard-toapproximate result on the two-disjoint-segment sensing model is tight.For the general problem, we first describe a polynomialtime (2 + ε)-approximation algorithm as an upper bound, applicable to both perimeter guarding and region guarding.This is followed by a high-performance integer linear programming (ILP) based method that computes near-optimal solutions.Thorough computational benchmarks as well as evaluation on potential application scenarios demonstrate the effectiveness of these algorithmic solutions.