Adaptive Centroidal Voronoi Tessellation With Agent Dropout and Reinsertion for Multi-Agent Non-Convex Area Coverage

Abstract

Voronoi diagrams are widely used for area partitioning and coverage control. Nevertheless, their utilization in non-convex domains often necessitates additional computational procedures, such as diffeomorphism application, geodesic distance calculations, or the integration of local markers. Extending these techniques across diverse non-convex domains proves challenging. This paper introduces the adaptive centroidal Voronoi tessellation ( $\alpha $ CVT) algorithm, which combines iterative centroidal Voronoi tessellation ( $i$ CVT) with an innovative agent dropout and reinsertion strategy. This integration aims to enhance area coverage control in non-convex domains while maintaining adaptability across varied environments without the need for complex computational processes. The efficacy of this approach is validated through simulations involving non-convex domains with disjoint target areas, obstacles, and shape constraints for both homogeneous and heterogeneous agents. Additionally, the $\alpha $ CVT algorithm is extended for real-time coverage control scenarios. Performance metrics are employed to assess the distribution of partitioned Voronoi regions and the overall coverage of the target areas. Results demonstrate improved performance compared to methods that do not incorporate the agent dropout and reinsertion strategy.

Keywords

• Area partitioning
• non-convex area coverage control
• multi-agent system
• Voronoi tessellation