The use of unmanned aerial vehicles (UAVs) is becoming commonplace in search and rescue tasks in complex terrains. In the literature, there are a number of studies on UAV search with the objective of minimizing search time and/or maximizing detection probability. However, little effort has been devoted to collaborative human and UAV search, which is necessary in many applications where the target has to be ultimately reached by human rescuers. In this paper we present a collaborative human-UAV search planning problem with the aim of minimizing the expected time at which the target is reached by human rescuers. The presented problem is of high complexity, and thus traditional exact algorithms would be very time-consuming or even impractical for solving even relatively small instances. We propose an evolutionary algorithm which uses biogeography-inspired operators to efficiently evolve a population of solutions to find the optimum or a near-optimum within an acceptable time. Computational experiments demonstrate the advantages of our algorithm over a number of other popular algorithms. The proposed method has been successfully applied to two real-world operations for searching and rescuing missing tourists in a nature reserve in China. It is estimated that, compared to the old method used by the organization, our method shortened the time required for reaching the targets by 79 minutes and 147 minutes in the two cases, respectively, providing a great improvement in the life-critical operations.
Filmed at the 2018 INFORMS Annual Meeting in Phoenix