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

Jamie Snape,^* Jur van den Berg,^† Stephen J. Guy,^* and Dinesh Manocha *
^* 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

Abstract

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.

Keywords

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

Paper

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.

Acknowledgments

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

Jamie Snape and Dinesh Manocha, "Navigating multiple simple-airplanes in 3D workspace," IEEE Int. Conf. Robotics and Automation, Anchorage, Alaska, 2010.
Jamie Snape, Jur van den Berg, Stephen J. Guy, and Dinesh Manocha, "The hybrid reciprocal velocity obstacle," IEEE Trans. Robot., vol. 27, 2011.
Jur van den Berg, Stephen J. Guy, Ming Lin, and Dinesh Manocha, "Reciprocal n-body collision avoidance," Robotics Research: The 14th International Symposium ISRR, Springer Tracts in Advanced Robotics, 2011.