Evolutionary Planning of Multi-UAV Search for Missing Tourists

Abstract

In recent years, there have been increasing reports of missing tourists around the world. The use of unmanned aerial vehicles (UAVs) can significantly improve the performance of search and rescue operations. However, planning the search paths of UAVs can be a highly complex optimization problem, and one of the most challenging tasks in the problem formulation is the estimation of target location probability distribution over time. This paper presents a problem of scheduling multiple UAVs to search for missing tourists and proposes a method for estimating tourist location probabilities which change with topographic features, weather conditions, and time. To solve the problem efficiently, we propose a hybrid evolutionary algorithm which consists of the main algorithm and a sub-algorithm. The main algorithm uses specific migration and mutation operators to evolve a population of main solutions, and the sub-algorithm combines a problem-specific heuristic and tabu search method to optimize each UAV path. The experimental results on a wide variety of test instances (including five real-world instances) demonstrate the performance advantages of the proposed method.

Keywords

• Unmanned aerial vehicle (UAV)
• path planning
• discrete-time optimization
• evolutionary algorithms