Priority-Based Deadlock Recovery for Distributed Swarm Obstacle Avoidance in Cluttered Environments

We propose a novel hierarchical priority mechanism for deadlock recovery of distributed swarm via on-demand collision avoidance in cluttered dynamic environments. The proposed priority mechanism dynamically assigns certain priority and an optimized detour point for each agent based on its spatial context to avoid deadlocks which are predicted by properly designed deadlock conditions; as a byproduct, this priority mechanism allows us to effectively resolve livelocks as well. The resulting optimization problem is then solved by polar reformulation and alternating minimization methods. Simulation results demonstrate that, in both static and dynamic environments, our method (termed PriDRAM) outperforms the baseline Alternating Minimization Swarm (AMSwarm) method which does not explicitly account for deadlock recovery, with a 10.5% improvement in average smoothness and a 4.8% reduction in flight time. Moreover, for narrow passages, our method shows a superior performance against the Distributed Linear Safe Corridor (DLSC) method, with a more reasonable passing order and an achievement of up to 40% reduction in flight path length. Finally, we verify the efficacy of our proposed method with a Crazyflie 2.1 quadrotor swarm.