2024/10/11 by Ján Mikula, Mikula, Jan, Miroslav Kulich +1 · 1 citation
Computer Science · Engineering · #Computational Geometry (cs.CG) #Energy Efficient Wireless Sensor Networks #FOS: Computer and information sciences #Robotic Path Planning Algorithms #Robotics (cs.RO) #Robotics and Sensor-Based Localization
paper · pdf · doi:10.48550/arxiv.2410.08784
openalex publication_date 2024/10/11 · openalex created_date 2024/10/16 · openalex updated_date 2026/07/28
This paper studies the omnidirectional sensor-placement problem (OSPP), which involves placing static sensors in a continuous 2D environment to achieve a user-defined coverage requirement while minimizing sensor count. The problem is motivated by applications in mobile robotics, particularly for optimizing visibility-based route planning tasks such as environment inspection, target search, and region patrolling. We focus on omnidirectional visibility models, which eliminate sensor orientation constraints while remaining relevant to real-world sensing technologies like LiDAR, 360-degree cameras, and multi-sensor arrays. Three key models are considered: unlimited visibility, limited-range visibility to reflect physical or application-specific constraints, and localization-uncertainty visibility to account for sensor placement uncertainty in robotics. Our first contribution is a large-scale computational study comparing classical convex-partitioning and sampling-based heuristics for the OSPP, analyzing their trade-off between runtime efficiency and solution quality. Our second contribution is a new class of hybrid accelerated-refinement (HAR) heuristics, which combine and refine outputs from multiple sensor-placement methods while incorporating preprocessing techniques to accelerate refinement. Results demonstrate that HAR heuristics significantly outperform traditional methods, achieving the lowest sensor counts and improving the runtime of sampling-based approaches. Additionally, we adapt a specific HAR heuristic to the localization-uncertainty visibility model, showing that it achieves the required coverage for small to moderate localization uncertainty. Future work may apply HAR to visibility-based route planning tasks or explore novel sensor-placement approaches to achieve formal coverage guarantees under uncertainty.