Fast, On-line Collision Avoidance for Dynamic Vehicles Using Buffered Voronoi Cells

This letter presents a distributed collision avoidance algorithm for multiple dynamic vehicles moving in arbitrary dimensions. In our algorithm, each robot continually computes its buffered Voronoi cell (BVC) and plans its path within the BVC in a receding horizon fashion. We prove that our algorithm guarantees collision avoidance for robots with single integrator dynamics. We show that our algorithm has computational complexity of O(k), which is the same as that of the optimal reciprocal collision avoidance (ORCA) algorithm, and is considerably faster than model predictive control (MPC) and sequential convex programming (SCP) based approaches. Moreover, ORCA and MPC-SCP require relative position, velocity, and even other information, to be exchanged over a communication network among the robots. Our algorithm only requires the sensed relative position, and therefore is well suited for on-line implementation as it does not require a communication network, and it works well with noisy relative position sensors. Furthermore, we provide an extension of our algorithm to robots with higher-order dynamics like quadrotors. We demonstrate the capabilities of our algorithm by comparing it to ORCA in multiple benchmark simulation scenarios, and we present results of over 70 experimental trials using five quadrotors in a motion capture environment.