A Hyper-Heuristic Method for UAV Search Planning

Motivated by the wide use of unmanned aerial vehicles (UAV) in search-and-rescue operations, we consider a problem of planning the search sequence and search modes of UAV, the aim of which is to maximize the probability of finding the target in a complex environment with probabilistic belief of target location. We design five meta-heuristic algorithm for solving the complex problem, but find that none of them can always obtain satisfactory solutions on a variety of instances. To overcome this obstacle, we integrate these meta-heuristics into a hyper-heuristic framework, which adaptively manage the low-level heuristics (LLH) by using feedback of their real-time performance in problem solving, and thus can find the most suitable LLH or their combination that can outperform any single LLH on each given instance. Experiments show that the overall performance of the hyper-heuristic is significantly better than any individual heuristic on the test instances.