# Large-Area Coverage Path Planning Method Based on Vehicle-UAV Collaboration
## 3 Coverage Path Planning Method Based on Vehicle-UAV Collaboration
### Modeling of Coverage Path Planning Problem  
In the CCP problem, the boundary contour of the coverage area is taken as a key consideration point for path planning. Note that, in practical coverage areas, like crop  
Figure 2: Flowchart of the proposed vehicle–UAV collaboration CCP method.  
growth detection on farms and wilderness search and rescue, there would be various types of special terrain or constraints, such as hills, no-fly zones, etc., in the CCP problem. These issues that need to be considered can be reduced into a polygon region filling problem in 2D space. The boundary contour in the CCP problem is regarded as a polygon, which is indicated as C. For the sake of simplicity, the following modeling issues related to the CCP problem of UAVs will be described from the perspective of computer graphics.  
The UAV energy model is a very complex research field, and the energy model calculation is closely related to various factors [13; 33; 34; 35], such as flight speed, load changes, flight altitude, etc. Intuitively, the energy calculation for a UAV is positively correlated with the flight distance (i.e., flight path length). Thus, in order to simplify the energy model calculation for a UAV, the global length of the sweeping planning paths in a 3D map of mountainous terrain is used as the main energy model indicator.  
For the paths in a 2D map, the traces of UAVs are described as a series of ordered coordinate points. Define the coverage path as \(\mathbf{Q}\), with the number of path points being q, then \(\mathbf{Q}\) can be expressed as (1):  
\[\mathrm{Q}=\left\{(\mathrm{x}_{1},\mathrm{y}_{1}),(\mathrm{x}_{2},\mathrm{y} _{2}),\ldots,\left(\mathrm{x}_{\mathrm{q}},\mathrm{y}_{\mathrm{q}}\right)\right\} \tag{1}\]  
where \((x_{i},y_{i}),\ i\in[1,q]\). In addition, the energy consumption-cost function of a UAV based on path length is defined as (2).  
\[H=\sum_{i=1}^{q-1}\sqrt{\left(x_{i}-x_{i+1}\right)^{2}+\left(y_{i}-y_{i+1} \right)^{2}} \tag{2}\]  
Another worthwhile issue is the work unit segmentation model problem for large-scale areas, which is related to the single UAV flight distance. It should be noted that, if the work unit area is divided into too-small areas, it will result in a sharp increase in the number of segmented work units, which will increase the burden on vehicle path planning. Conversely, if the partition work unit is too large, it will generate excessive UAV round-trip paths in each work unit, which is meaningless for the coverage mission and reduces the efficiency of the scanning coverage task. Therefore, the area of partition work units needs to be balanced, and it is assumed that only a small number of UAV flights are needed to complete the coverage task for the work units. Assuming that the coverage width of the UAV path is \(\mathbf{M}\), the total flight distance of a single UAV flight is \(\mathbf{L}\), and the number of UAV flights for the work unit is \(\mathbf{k}\), the area \(\mathbf{S}\) of a work unit can be calculated according to (3). Regular polygons, such as triangles, squares, and hexagons, are very suitable for solving the problem of work area division, generating relatively uniform work units. Regular hexagons are adopted for the work unit partition problem. Taking the relationship between the area of a regular hexagon and its edges, the edge value \(\mathbf{a}\) of a regular hexagon unit can be preliminarily calculated from (4), as shown in Figure 3.  
\[S=L*W*k \tag{3}\]  
\[\mathrm{a}=\sqrt{\frac{2S}{3\sqrt{3}}} \tag{4}\]