A Generalized Voronoi Graph based Coverage Control Approach for Non-Convex Environment

Zuyi Guo; Ronghao Zheng; Meiqin Liu; Senlin Zhang

cs.ROMar 10, 2026

A Generalized Voronoi Graph based Coverage Control Approach for Non-Convex Environment

Authors: Zuyi Guo, Ronghao Zheng, Meiqin Liu, Senlin Zhang

Organizations: the College of Electrical Engineering, Zhejiang University, Hangzhou 310027, China, and also with the State Key Laboratory of Industrial Control Technology, Zhejiang University, Hangzhou 310027, China · the National Key Laboratory of Human-Machine Hybrid Augmented Intelligence, Xi’an Jiaotong University, Xi’an 710049, China, and also with the State Key Laboratory of Industrial Control Technology, Zhejiang University, Hangzhou 310027, China

Abstract

To address the challenge of efficient coverage by multi-robot systems in non-convex regions with multiple obstacles, this paper proposes a coverage control method based on the Generalized Voronoi Graph (GVG), which has two phases: Load-Balancing Algorithm phase and Collaborative Coverage phase. In Load-Balancing Algorithm phase, the non-convex region is partitioned into multiple sub-regions based on GVG. Besides, a weighted load-balancing algorithm is developed, which considers the quality differences among sub-regions. By iteratively optimizing the robot allocation ratio, the number of robots in each sub-region is matched with the sub-region quality to achieve load balance. In Collaborative Coverage phase, each robot is controlled by a new controller to effectively coverage the region. The convergence of the method is proved and its performance is evaluated through simulations.

Figures & tables

Fig. 1: Overview of the proposed method, which includes Load-Balancing Algorithm phase (top) and Collaborative Coverage phase (bottom). Load-Balancing Algorithm determines the final number of robots in each region. In Collaborative Coverage phase, each robot are controlled to efficiently cover its region based on the designed controller.

Fig. 2: $V_{ij}$ and $V_{ji}$ are two GVG nodes defined by $E_{ij}$ . The circle is the node circle. The blue line represents the connection between the node and the intersection point of the circle and an obstacle, and it also serves as the boundary of the region.

Fig. 3: The non-convex area $D$ with four black holes. The red line represents the GVG curve, and each GVG cell is denoted by a distinct color.

Fig. 4: The final configuration of robots in each region.

Fig. 5: A comparison between the actual number of robots and the ideal number of robots in each region.

Panel of Figure 6 — Fig. 6: The initial configuration is shown in (a) and the configuration after the execution of the Load-Balancing Algorithm is shown in (b). The trajectories of robots is shown in (c) and (d) shows the final configuration and the circles represent the density.

Fig. 7: Cost $\mathcal{H}$ for the area.

Multi-Robot Coordination

Multi-robot coordination studies how teams of robots plan, communicate, allocate tasks, and act together safely and efficiently.

See all 326 papers

Multi-Robot Multitask Gaussian Process Estimation and Coverage
Mar 11, 2026Lai Wei, Andrew McDonald, Vaibhav SrivastavaMulti-Robot Coordination
Life Sciences Institute, University of Michigan, Ann Arbor, MI 48109 USA · University of Cambridge, Cambridge, UK. · Department of Electrical and Computer Engineering. Michigan State University, East Lansing, MI 48823 USA.
Energy-Efficient Multi-Robot Coverage Path Planning of Non-Convex Regions of Interests
Apr 24, 2026Sourav Raxit, Jose Fuentes, Paulo Padrao +4Multi-Robot Motion Planning Mobile Robotics
Department of Computer Science, University of New Orleans, New Orleans, LA 70148, USA · School of Computing and Information Sciences, Florida International University, Miami, FL 33199, USA · Department of Mathematics & Computer Science, Providence College, Providence, RI 02918
Density-Driven Area Coverage for Nonholonomic Multi-Robot Systems with Safety Guarantee
Sep 19, 2026Julian Martinez, Kooktae LeeRobotic Control Multi-Robot Systems
Department of Mechanical and Aerospace Engineering, Texas Tech University, Lubbock, TX 79409, USA

Mar 11, 2026J/K move · Enter open · S save

Multi-Robot Multitask Gaussian Process Estimation and Coverage

Lai Wei, Andrew McDonald, Vaibhav Srivastava

Life Sciences Institute, University of Michigan, Ann Arbor, MI 48109 USA · University of Cambridge, Cambridge, UK. · Department of Electrical and Computer Engineering. Michigan State University, East Lansing, MI 48823 USA.

Multi-Robot Coordination

Open paper AskPDF arXiv

Coverage control is essential for the optimal deployment of agents to monitor or cover areas with sensory demands. While traditional coverage involves single-task robots, increasing autonomy now enables multitask operations. This paper introduces a novel multitask coverage problem and addresses it for both the cases of known and unknown sensory demands. For known demands, we design a federated multitask coverage algorithm and establish its convergence properties. For unknown demands, we employ a multitask Gaussian Process (GP) framework to learn sensory demand functions and integrate it with the multitask coverage algorithm to develop an adaptive algorithm. We introduce a novel notion of multitask coverage regret that compares the performance of the adaptive algorithm against an oracle with prior knowledge of the demand functions. We establish that our algorithm achieves sublinear cumulative regret, and numerically illustrate its performance.

Abstract

Multi-Robot Coordination

Explore similar work

Multi-Robot Multitask Gaussian Process Estimation and Coverage

Energy-Efficient Multi-Robot Coverage Path Planning of Non-Convex Regions of Interests

Density-Driven Area Coverage for Nonholonomic Multi-Robot Systems with Safety Guarantee