Spatial Search via Adaptive Submodularity and Deep Learning

Abstract

Searching for the victim is the key part of search and rescue operations but finding an optimal search path is a NP-hard problem. Since the objective function of spatial search is submodular, greedy algorithms can generate near-optimal solutions. This research proposed an algorithm to enable an unmanned aerial vehicle (UAV) to adaptively search for a person in a 3D environment. The algorithm consists of adaptive submodularity and deep learning. The UAV learns the target distribution via the deep neural network. The learned networks can be applied to adaptive search for target that achieve (1 - 1/e) of the optimum. Experiments conducted with this algorithm demonstrate that the robot can search for the person faster than the benchmark approach.