# Efficient Multi-UAV Path Planning for Collaborative Area Search Operations
## 3 Path Planning Design  
This section belongs to the path planning design part of our methodology, as shown in Figure 2. In this section, we describe in detail the five routes used in the UAV flight in this paper and the route generation method. There are three main types of existing multi-UAV search studies [40]. The first type divides the area into multiple sub-areas equal to the number of UAVs, and then each sub-area is covered by a single UAV assigned to it [Figure 3a]. The second type divides the path of single aircraft coverage path planning into multiple segments, and each segment is covered by a single UAV [Figure 3b]. The third category divides the paths in parallel, using multiple UAVs to complete the coverage task in parallel [Figure 3c]. The third method of parallel coverage is to arrange multiple UAVs forward in parallel and to treat the whole as a single UAV with a larger coverage area to complete the coverage task. This method extends the coverage area of UAVs, and the degree of cooperation between multiple aircraft is higher so that relatively more complex tasks can be accomplished. However, it is not flexible enough to have fixed positions and a simple formation between multiple aircraft. It is not usually adopted in collaborative search studies of multiple UAVs. Figure 2: The structure of the path planning design part of the methodology  
These methods can effectively extend the coverage path planning method of a single machine to multiple UAVs and improve the coverage speed. However, these methods still cannot avoid the problems of backtracking traversal, repeated coverage, and low efficiency [41]. The CPP is one of the important research problems in the field of UAV control, and other researchers have provided some necessary standards when addressing the coverage planning path problem. 1. The UAV must pass all target cells in the work area to complete coverage of the area. 2. The paths must not overlap when the UAV covers the area. 3. The planned paths must be continuous and orderly. 4. The UAV must avoid all obstacles. 5. The planned path contains only simple actions. 6. The planned path is the shortest path. These criteria are not satisfied in all cases, and some conditions are even contradictory in certain environments but are still important indicators for research covering path planning studies. Path planning is an important part of UAV autonomous tasks. It requires quickly finding a good path formed by successively connecting multiple line segments or multiple waypoints in the planning space. There are two means of path representation: the first is a time series composed of speed and heading (based on dynamics). The second is a time series composed of the spatial position coordinates (based on geometry). Path planning of the UAV cluster needs to further consider the environmental constraints, self-constraints, and intra-cluster constraints on the basis of the general path planning model. We make the following assumptions for this problem:  
* Ignoring the impact of uncertain factors in the environment on the flight of the UAV, it is assumed that the UAV flies in a straight line and the flight height is fixed, and that no collision occurs between the UAVs performing the task together. * Starting from the central base station, the UAV needs to complete data collection from at least one target cell before returning to the central base station. * To ensure the reliability of data transmission, the UAV needs to hover over the target cell. That is, the UAV collects data only when hovering. The hover time at each target cell can be configured before departure. * Due to the significant difference between the communication energy consumption of UAVs used for data collection and the hovering and flying energy consumption of UAVs, and since this paper mainly addresses the path allocation of multi-UAV flying on different paths under the energy constraints of UAVs, we do not include the communication energy consumption of UAVs in our consideration of overall energy consumption.