Sensor Placement for Globally Optimal Coverage of 3D-Embedded Surfaces
This work tackles sensor placement for applications like surveillance and disease prevention, but it is incremental as it builds on existing optimization frameworks.
The study addresses the problem of optimally placing mobile sensors to cover 2D surfaces in 3D workspaces, such as for surveillance or disinfection, by developing approximation schemes and mathematical programming models to solve computationally intractable formulations.
We carry out a structural and algorithmic study of a mobile sensor coverage optimization problem targeting 2D surfaces embedded in a 3D workspace. The investigated settings model multiple important applications including camera network deployment for surveillance, geological monitoring/survey of 3D terrains, and UVC-based surface disinfection for the prevention of the spread of disease agents (e.g., SARS-CoV-2). Under a unified general "sensor coverage" problem, three concrete formulations are examined, focusing on optimizing visibility, single-best coverage quality, and cumulative quality, respectively. After demonstrating the computational intractability of all these formulations, we describe approximation schemes and mathematical programming models for near-optimally solving them. The effectiveness of our methods is thoroughly evaluated under realistic and practical scenarios.