Reciprocal collision avoidance for robots with linear dynamics using LQR-Obstacles

In this paper we present a formal approach to reciprocal collision avoidance for multiple mobile robots sharing a common 2-D or 3-D workspace whose dynamics are subject to linear differential constraints. Our approach defines a protocol for robots to select their control input independently (i.e. without coordination with other robots) while guaranteeing collision-free motion for all robots, assuming the robots can perfectly observe each other's state. To this end, we extend the concept of LQR-Obstacles (which is a generalization of Velocity Obstacles to robots with dynamics for collision avoidance among static obstacles) for reciprocal collision avoidance among multiple robots. We implemented and tested our approach in 3-D simulation environments for reciprocal collision avoidance of quadrotor helicopters, which have complex dynamics in 16-D state spaces. Our results show that our approach enables collision avoidance among over a hundred quadrotors in tight workspaces at real-time computation rates.