Space Partitioning and Path Planning for Mission Area Exploration Using Multiple UGVs

We propose a method for efficient partitioning and exploring complex mission areas using multiple unmanned ground vehicles (UGVs). We introduce two area partitioning algorithms that decompose a given mission area into segments appropriate for UGV navigation. The shape of the area determines the algorithms used. Additionally, we present a path-planning algorithm for each UGV's entry and mission paths. Consequently, our method generates a collision-free driving plan based on the path planning results.We have implemented the proposed method in a simulator and conducted verification tests on various mission area shapes and UGV numbers. Our findings show that it achieves a partitioning quality comparable to a previous Voronoi diagram-based approach while improving performance by up to 15.3 times. Furthermore, the driving plan generated by our method allows all UGVs to navigate their paths safely without colliding. We also validated the effectiveness of the proposed method on a small UGV test bed. These results collectively affirm the practicality and efficacy of the proposed approach.