# Efficient Multi-UAV Path Planning for Collaborative Area Search Operations
## 4 Multi-UAV Collaborative Search Algorithm
### Multiple UAVs Collaborative Search Algorithm Based on Binary Search Algorithm with Energy  
We propose a collaborative multi-UAV search algorithm based on binary search called MUCS-BS, which has been presented in our published works [43]. In the MUCS-BS, the binary search technique is used to distribute the running time \(t\) to the appropriate number of UAVs based on the total amount of time \(Maxtime\) required for a UAV to find all cells and return to its beginning location. We set the number of UAVs loaded by the unmanned vehicle to \(N\), denoted as the set \(D=\{1,2,\cdots,N\}\). When the UAV is located at \(P_{i}\), we calculate how long it takes for the UAV to reach \(P_{i+1}\), how long it takes to hover in the cell, and how long it takes to return to the starting position \(S\) from the \(P_{i+1}\) area. The UAV moves from \(P_{i}\) to the \(P_{i+1}\) area, the remaining working time itself needs to be calculated, minus the time from \(P_{i}\) to \(P_{i+1}\), the hovering time T and the time needed to return to the initial position from \(P_{i+1}\). If the remaining working time of the UAV is sufficient to meet the above requirements, the UAV moves from \(P_{i}\) to the \(P_{i+1}\) cell; otherwise, it returns to the starting position of \(S\). This rule is followed to determine the number of cells each UAV can reach in the currently allocated time \(t\). More specifically, if the first UAV successfully completes the job of covering the \(P_{i}\) cell within the allotted period \(t\), the second UAV will fly from the starting point \(s\) to the \(P_{i+1}\) cell and carry on along the path, and so on. A shorter working period \(t\) must be assigned if \(n\) cells are allocated and there are still UAVs without assignments. If all of the UAVs have been assigned, but there are still cells that have not been assigned. This indicates that more time needs to be given because the time that is presently allotted \(t\) is insufficient. By using the binary search technique, the shortest working time for each UAV is determined, and task paths are then given to each UAV.  
In MUCS-BS [43], we find the least time-consuming path assignment for the multi-UAV collaborative search task. However, we have to consider that UAVs consume energy when they move or hover in the air, so we needed to improve our MUCS-BS algorithm under energy constraints. We defined a multi-UAV collaborative search algorithm called MUCS-BSAE based on a binary search algorithm under energy constraints. MUCS-BSAE, like MUCS-BS, needs to preset the number of UAVs and the total time _Maxtime_ based on one UAV detecting all cells and returning to the starting position. The binary search algorithm is used to assign the running time \(t\) to the corresponding number of UAVs. The procedure is the same as for MUCS-BS, but the UAVs are assigned and there are no remaining cells. We calculate whether each UAV can complete the corresponding search mission at time \(t\) based on the energy consumption. If there are UAVs with uncompleted tasks among all UAVs, this means that the current allocated time \(t\) is too much and the allocated time needs to be reduced. The shortest working time is assigned to the least number of UAVs by the dichotomous finding method and the energy constraint, and the working path is assigned to each UAV. The pseudo-code code for the MUCS-BSAE algorithm is shown in Algorithm 6.