# Large-Area Coverage Path Planning Method Based on Vehicle-UAV Collaboration
## 3 Coverage Path Planning Method Based on Vehicle-UAV Collaboration
### Generation of Vehicle-UAV Cooperative Coverage Paths  
Specifically, the vehicle needs to deliver the UAV to the vicinity of the target area, where the UAV is released, then the vehicle waits for the UAV to complete the scanning task in the sub-area. After the UAV returns to the vehicle platform, the vehicle replaces batteries and supplies for the UAV. Once the sub-area coverage is complete, the vehicle carries the UAV to the next sub-area until the entire large area is completed. Therefore, the vehicle and the UAV need a cooperative coverage path for coverage tasks for large areas, and more attention needs to be paid to the efficiency of vehicle movements and UAV flights. With regard to vehicle movements, the requirement for vehicle path planning is to traverse all supply points with the shortest vehicle path. Essentially, the vehicle path planning problem in our research work can be approximately classified as a typical Traveling Salesman Problem (TSP). TSP is a classic combinatorial optimization problem that is significant in operations research and theoretical computer science. Due to the fact that the feasible solution to this problem is the complete arrangement of all vertices, as the number of vertices increases, a combinatorial explosion occurs, making it an NP-Complete problem. It cannot be denied that, in practical applications, approximate solutions can generally meet the requirements of NPC problems. Therefore, an approximation solution is expected to find a near-optimal solution for TSP, providing a specific percentage of the optimal solution and requiring a reasonable time. In this research work, a classical ant colony optimization (ACO) algorithm [37] is adopted in the vehicle path planning method to guarantee a generated path with the shortest possible length. The Euclidean distance between two supply points is used as the weight of the connecting edge. Firstly, in the initial case, all supply points are inserted into a set, indicated by \(S\). A new set \(V\) is created to store the points on the shortest path determined by the computation. A preset supply point is selected as the starting point \(P\), and \(P\) is removed from the set \(S\) and then inserted into \(V\). Secondly, another supply point is selected from the remaining set \(S\) to ensure this supply point has the shortest possible distance to the points within set \(V\). Then, this set  
Figure 7: The modification of sub-area adjustment based on Voronoi Diagram. and \(\mathbf{V}\) are updated, and this supply point is removed from \(\mathbf{S}\) and added to \(\mathbf{V}\) accordingly. The above operations are repeated, and the vehicle path planning method ends when set \(\mathbf{S}\) is completely empty, and all the supply points have been added to set \(\mathbf{V}\). Finally, the sequence of supply points recorded in set \(\mathbf{V}\) represents the planning path of the vehicle, and it ensures the vehicle can traverse all supply points in the coverage are with the shortest possible route, as shown in Figure 8.  
It is noted that, to some extent, the number of supply points generated for large areas may not be critical to the proposed vehicle-UAV collaboration CCP method. On the one hand, in practice, the vehicle path planning procedure is performed in advance. In other words, there is sufficient time for the ACO algorithm to generate vehicle paths. On the other hand, in the algorithm design of our research work, the number of supply points is approximately the same as the number of segmentation units. The number of segmentation units can be reduced by expanding the area of the sub-areas, resulting in a decrease in the number and scale of the supply points. In terms of the path planning problem for UAVs in a large area, the requirement for the UAV is to complete the coverage task of the entire area in a divide-and-conquer manner. In each sub-area, the coverage path needs to integrate with the vehicle supply points, providing the benefits of improving efficiency in the CCP problem.