Cooperative Rapid Search for Evasive Targets Using Multiple UAVs Based on Graph Theory

Rapid search for evasive targets using multiple Unmanned Aerial Vehicles (UAVs) presents significant challenges, as it requires real-time target-motion prediction, multi-agent coordination, and adherence to kinematic constraints. Existing cooperative search methods often assume non-adversarial target behavior or model target motion independently of UAV actions, which reduces their effectiveness against targets that actively evade based on UAV positions. To address these limitations, this study introduces the Cooperative Rapid Search Algorithm for Evasive Targets (CRS-AET). The proposed framework utilizes graph-theoretic modeling to represent spatial-temporal relationships among UAVs, targets, and environmental grids. A directional gradient-based motion prediction (DG-Prediction) method first estimates probable movement areas of dynamic targets within the graph-structured environment. An improved multi-round auction algorithm with graph-based utility propagation (IMRAA) then optimizes UAV resource allocation. Finally, Dubins-Constrained Trajectory Optimization (DC-RTO) is integrated within a distributed model predictive control (DMPC) scheme to ensure kinematic feasibility. Simulation results across three representative scenarios indicate that CRS-AET enables faster target detection, enhanced area coverage, and more efficient coordination than baseline methods. Hardware-in-the-loop (HIL) experiments further confirm the robustness and practical applicability of the framework in realistic operational environments.