Lateral Reciprocal Collision Avoidance: A Probabilistic Social-Norm-Inspired Strategy for Deadlock-Free Multi-Robot Navigation

Abstract

Safe and efficient obstacle avoidance in multi-robot navigation is a challenging problem, with deadlock being a key issue due to strict collision-free constraints. This paper proposes a novel Lateral Reciprocal Collision Avoidance (LRCA) strategy based on velocity obstacle theory to mitigate deadlock among multiple robots. Inspired by pedestrian collision avoidance, LRCA incorporates symmetric lateral displacement to resolve deadlock. Unlike Optimal Reciprocal Collision Avoidance (ORCA) algorithm, which computes velocity constraints based on the minimal adjustment across the full velocity obstacle, our proposed method restricts the velocity changes of the agents to one randomly selected side of the relative velocity. This randomized directional selection strategy effectively prevents deadlock while preserving collision avoidance. This approach avoids conflicting velocity changes that could lead to mutual trapping. Theoretical analysis shows how ORCA cause deadlock using quadratic programming, Lagrangian functions, and KKT conditions, and how LRCA effectively prevents this. Extensive simulations across four benchmark multi-robot navigation scenarios show that LRCA outperforms existing algorithms in success rate, time to goal, path length, and computational efficiency.