Distributed Collision Avoidance of Multiple Robots with Probabilistic Buffered Voronoi Cells

This paper introduces Probabilistic Buffered Voronoi Cell (PBVC) collision avoidance for multiple robots using noisy on-board sensing. The work builds upon the previously proposed Buffered Voronoi Cell (BVC) approach. We introduce a probabilistic formulation to construct a family of BVCs with specified safety levels, which take into account uncertainty in sensor measurements among the robots. The safety level of a PBVC represents the probability that the area is contained inside the robot's true (but unknown) BVC. The PBVC provides a set of probabilistically safe positions for the robot to navigate to. Each agent chooses its next position constrained within the PBVC of a desired safety level, while minimizing the deviation from its reference trajectory. We prove a conservative bound on the probability of collision given this reciprocal strategy. We also validate through simulations that the proposed approach achieves safe navigation among multiple robots in challenging scenarios, and provides a significantly lower risk of collision than either the Reciprocal Velocity Obstacles (RVO) method or the Buffered Voronoi Cell (BVC) method when the robots use noisy relative measurements. We also show in experiments with small-scale robotic cars that the algorithm is fast, effective and is useful in real applications.