Multi-robot Collision Avoidance Based on Buffered Voronoi Diagram

Abstract

Multi-robot path planning is an essential research topic for coordinated robots. In this paper, we aim to enable teams of robots to navigate in a common environment samultanuously without collision. Our method is based on Voronoi diagram, an optimal spatial area assignment strategy. We take the localization inaccuracy in to consideration, which always exist in real-world senarioss and set a buffer to the ordinary Voronoi diagram for collision-free navigation amoung the robot team. We also combine the left-handed principle to handle the situation of deadlock, which may happen when robots reach the connors or edges of their Voronoi cells. We use MATLAB simulation to test the efficacy of our proposed algorithms in an open environment with twelve mobile robots. The results show that all robots reach the target efficiently without collision. We also compare our method with several related multi-robot path planning algorithms to demonstrate the efficiency of our proposed method.