Smooth and Collision-Free Navigation for Multiple Robots Under Differential-Drive Constraints

,* Jur van den Berg, ,* and *
* Department of Computer Science, University of North Carolina at Chapel Hill
 Department of Industrial Engineering and Operations Research, University of California, Berkeley

Diagram of the effective center (X,Y) and effective radius R of a differential-drive robot   Diagram of the half-plane of velocities ORCA permitted by optimal reciprocal collision avoidance   Photo of four iRobot Create differential-drive robots


We present a method for smooth and collision-free navigation for multiple independent robots under differential-drive constraints. Our algorithm is based on the optimal reciprocal collision avoidance formulation and guarantees both smoothness in the trajectories of the robots and locally collision-free paths. We provide proofs of these guarantees and demonstrate the effectiveness of our method in experimental scenarios using iRobot Create mobile robots navigating amongst each other.


Path planning for multiple mobile robots or agents; collision avoidance.


Jamie Snape, Jur van den Berg, Stephen J. Guy, and Dinesh Manocha, "Smooth and Collision-Free Navigation for Multiple Robots Under Differential-Drive Constraints," IEEE RSJ Int. Conf. Intelligent Robots and Systems, Taipei, Taiwan, 2010.


This work was supported by ARO under Contract W911NF-04-1-0088, by NSF under Award 0636208, Award 0917040, and Award 0904990, by DARPA and RDECOM under Contract WR91CRB-08-C-0137, and by Intel.

Related Work