Minimizing the searching time of multiple targets in uncertain environments with multiple UAVs

Abstract

The focus of this paper is the use of Unmanned Aerial Vehicles (UAVs) for searching multiple targets under uncertain conditions in the minimal possible time. The problem, known as Minimum Time Search (MTS), belongs to the Probabilistic Search (PS) field and addresses critical missions, such as search & rescue, and military surveillance. These operations, characterized by complex and uncertain environments, demand efficient UAV trajectory optimization. The multi-target version of PS introduces additional challenges, due to their higher complexity and the need to wisely distribute the UAV´s efforts among multiple targets. In order to tackle the under-explored multi-target aspect of MTS, we optimize the time to find all targets with new Ant Colony Optimization (ACO)-based planner. This novel optimization criterion is formulated using Bayes´ theory, considering probability models of the targets (initial belief and motion model) and the sensor likelihood. Our work contributes significantly by (i) developing an objective function tailored for multi-target MTS, (ii) proposing an ACO-based planner designed to effectively handle the complexities of multiple moving targets, and (iii) introducing a novel constructive heuristic that is used by the ACO-based planner, specifically designed for the multi-target MTS problem. The efficacy of our approach is demonstrated through comprehensive analysis and validation across various scenarios, showing superior performance over existing methods in complex multi-target MTS problems.