Generalized Reciprocal Collision Avoidance (pdf)

Daman Bareiss, Jur van den Berg


Reciprocal collision avoidance has become a popular area of research over recent years. Approaches have been developed for a variety of dynamic systems ranging from single integrators to car-like, differential-drive, and arbitrary, linear equations of motion. In this paper, we present two contributions. First, we provide a unification of these previous approaches undera single, generalized representation using Control Obstacles. In particular, we show how Velocity Obstacles (Fiorini and Shiller, 1998), Acceleration Velocity Obstacles (van den Berg et al., 2012), Continuous Control Obstacles (Ruffli et al., 2013), and LQR-Obstacles (Bareiss and van den Berg, 2013) are special instances of our generalized framework. Secondly, we present an extension of Control Obstacles to general reciprocal collision avoidance for non-linear; non-homogeneous systems where the robots may have different state spaces and different non-linear equations of motion from one another. Previous approaches to reciprocal collision avoidance could not be applied to such systems, as they use a relative formulation of the equations of motion and can, therefore, only apply to homogeneous, linear systems where all robots have the same linear equations of motion. Our approach allows for general mobile robots to independently select new control inputs while avoiding collisions with each other. We implemented our approach in simulation for a variety of mobile robots with non-linear equations of motion: differential-drive, differential-drive with a trailer, car-like, and hovercrafts. We also performed physical experiments with a combination of differential-drive, differential-drive with a trailer, and car-like robots. Our results show that our approach is capable of letting a non-homogeneous group of robots with non-linear equations of motion safely avoid collisions at real-time computation rates.