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 use the concept of LQR-Obstacles (a generalization of Velocity Obstacles to robots with dynamics) that define sets of forbidden control inputs that lead a robot to collision with obstacles, and extend it 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 suggest that our approach avoids collisions among over a hundred quadrotors in tight workspaces at real-time computation rates.

Videos

Video 1. Two Quadrotors using RCA - Two quadrotor helicopters are shown using our reciprocal collision avoidance algorithm. The quadrotors are controlled to swap positions and shown to avoid collisions while doing so.

Video 2. Four Quadrotors using RCA - Four quadrotor helicopters are shown using our reciprocal collision avoidance algorithm. The quadrotors are positioned in a square and controlled to swap positions with the quadrotor opposite itself along the square's diagonals.

Video 3. Eight Quadrotors using RCA - Eight quadrotor helicopters are shown using our reciprocal collision avoidance algorithm.

Video 4. Sixteen Quadrotors using RCA - Sixteen quadrotor helicopters are shown using our reciprocal collision avoidance algorithm.

Video 5. Twenty-Four Quadrotors using RCA - Twetnty-four quadrotor helicopters are shown using our reciprocal collision avoidance algorithm.

Video 6. One-Hundred Quadrotors using RCA - One-hundred quadrotor helicopters are shown using our reciprocal collision avoidance algorithm.