Application of an Improved Voronoi-Lloyd Algorithm in Non-uniform Area Multi-Robot Coverage Control
Mingcong Zhang, Xin Chen · 2025
Area coverage control is vital for multi-robot systems in disaster response, environmental monitoring, agriculture, and surveillance. Traditional Voronoi-Lloyd algorithms partition a region among robots and iteratively adjust their positions to maximize coverage, but they perform poorly in non-uniform environments where task demands vary spatially. To address this, we propose a density-weighted Voronoi-Lloyd algorithm that incorporates both robot positions and spatial density into the partitioning process, assigning greater weight to high-demand areas. We also introduce a novel value function that evaluates coverage effectiveness by combining centroid distances with area density, thereby prioritizing dense regions and reducing movement costs. Simulations demonstrate that our method converges more rapidly and delivers superior coverage quality in both single-density and multi-density scenarios. This enhanced algorithm provides a more efficient, robust solution for real-world multi-robot coverage tasks.