# Efficient Multi-UAV Path Planning for Collaborative Area Search Operations
## 2 Related Work
### Multi-UAV Cooperative Search Energy Consumption Problem  
Due to the variety of tasks that UAVs carry out and the unpredictability of the environment in which they operate, UAVs must be able to build an ad hoc network while carrying out their tasks. Each UAV connected to a network has to be able to send and receive messages, or to perform the role of a message router. The network is also continually being accessed or exited by UAVs, making it a very dynamic network. The network's dynamic nature has a significant influence on how the UAVs share information, collaborate on decisions, and use energy judiciously. Small UAVs carry limited battery energy, and reducing energy consumption is particularly important for UAV ad hoc networks. It is of practical significance to study how to maximize the use of limited battery energy and to reduce energy consumption, so as to prolong the life cycle of a UAV self-grouping network, reduce mutual interference between nodes, and improve the collaborative search efficiency of multi-UAVs. The collaborative search algorithm can evenly distribute the energy consumption of each UAV, equalize the energy consumption of each node, balance the overall load of the network, prevent some nodes from prematurely exiting the network due to energy consumption, and increase the stability of the network. An important goal of collaborative search algorithms is to improve the efficiency of the UAV swarm to complete the task [34]. For small UAVs with limited energy, we hope to save energy while maintaining network connectivity, extend the network lifetime and improve mission execution time, and finally achieve the purpose of improving the collaborative search efficiency of multi-UAVs. This paper considers how to improve the collaborative search efficiency of multiple UAVs by means of a collaborative search algorithm. In addition, the energy consumption of each UAV achieved is more balanced, so as to avoid the premature failure of some nodes due to energy exhaustion, resulting in network interruption or serious efficiency decline, and to enhance the overall stability of the network. The study of multi-UAV long-time operation represents the problem primarily as a scheduling problem--a typical problem is the MTSP. The essence of the MTSP is a multiple Hamiltonian loop problem, the main idea of which is to divide \(m\) cities into \(n\) classes, with each group corresponding to one merchandiser. Since the actual model is widely used when path planning problems and logistics problems are considered, MTSP and its related extensions have long attracted researchers to solve it [35]. In ref. [36], an aggregated clustering approach was used to solve the MTSP for multiple starting points. In ref. [37], graph theory was used to decompose the MTSP into TSPs and then proceed to obtain the optimal solution for the model. In addition, ref. [38] specifically considered the practical application of the MTSP in material distribution and route planning and proposed a corresponding algorithm to solve the problem--the basic idea was to first divide the service area according to the traveler's travel paths, and then to carry out route planning. In ref. [39], a starting point fixed MTSP was established and was solved using ACO. Different starting points were set for the experiments, and it was demonstratedthat choosing different starting points would have different effects on the algorithm's solution effectiveness. The multi-UAV path planning problem for accessing multiple target nodes is similar in nature to the standard MTSP but is different in certain respects. In the standard MTSP problem, assigning target nodes to multiple UAVs is a complex permutation problem, but the distance traveled by each traveler is not limited, whereas in the problem solved in this chapter, the energy of the UAVs is limited and the UAVs consume energy during flight, hovering and data collection and they visit different target points and incur different energy consumption costs in the process.