Optimal Uncertainty Reduction Search using the k-Shortest Path Algorithm

We propose a search algorithm for uninhabited autonomous aerial vehicles (UAAVs) performing a search and surveillance task, based on the uncertainty map of an unknown region. The search algorithm is based on the k-shortest path algorithm that maximizes the effectiveness of the search in terms of searching through the maximum uncertainty region, given a constraint on the endurance time of the UAAV. We compare the performance of this algorithm with a random search and a greedy strategy search. We also implement the algorithm for the case of multiple UAAVs searching an unknown region. Simulation results that demonstrate the efficacy of the technique are also presented