Planning and Online Conflict-Aware Replanning Under Traffic Management Constraints for Closed-Loop Multi-UAV Execution

Abstract

Offline Multi-Agent Path Finding plans for multiple Unmanned Aerial Vehicles (UAVs) Unmanned Traffic Management (UTM) can fail during disturbed execution because stochastic delays break the joint timing assumptions that make nominal plans conflict-free. We present a closed-loop discrete UTM method that couples UTM-aware planning with online execution repair. It extends Lazy Constraints Addition Search for MAPF (LaCAM) with time-augmented joint states and successor filtering for temporal no-fly zones, heterogeneous protection footprints, and directional downwash risk envelopes. At execution time, Online Discrete Alignment and Replanning (ODAR) aligns observed UAV states to reference plans, applies bounded one-step repair and conflict-aware arbitration, and triggers replanning when local correction is insufficient. In discrete simulation with up to 300 UAVs, the proposed method preserves sub-second planning on benchmark maps. Under stochastic delays, offline execution and alignment-only variants leave measured execution conflicts, while full ODAR reduces the discrete conflicts to zero in the tested scenarios. Local conflictset replanning matches global replanning in completion while using 5.1% to 21.0% of the global cumulative replanning time per case and 9.4% in aggregate.