Multi Robot Collision Avoidance

During his internship at Willow Garage, Daniel Claes from Maastricht University worked on multi-robot collision avoidance. Put simply, he was able to get multiple robots to navigate efficiently while avoiding each other. 

Currently, many navigation algorithms assume that obstacles are static, which results in suboptimal or even unsafe paths in an environment featuring multiple moving robots.  In addition, a system of multiple robots with similar sensor locations such as the PR2's base laser, there is very little surface area that can be picked up by the sensors of other robots and thus prevents the robots from observing each other effectively.

Multi-robot collision avoidance is based on the velocity obstacle paradigm and incorporates the motion of other robots resulting in smoother and more efficient paths. The solution is a reactive and fully distributed approach running on the robots as a local planner.  Localization uncertainty is taken into account by virtually enlarging the robots footprint according to the covariance matrix of the AMCL pointcloud.

This key idea of this algorithm is that robots broadcast their positions and select collision-free velocities that continue to adapt as the robots approach their goals. These techniques allow them to react to nearby robots and does not require any centralized or coordinated planning. The work is based on the ORCA (optimal reciprocal collision avoidance) formulation developed by Berg et al.

This work was done with the TurtleBot and PR2 but it will work with any robots running the ROS navigation stack. This approach enables a wide variety of applications, from warehouse delivery to games.  

Willow Garage would also like to congradulate Daniel Claes, Daniel Hennes, Karl Tuyls, and Wim Meeussen on winning the Best Demonstration Award at the eleventh international conference on autonomous agents and multiagent systems (AAMAS’12, June 4th – June 8th 2012) with: “CALU: Collision Avoidance with Localization Uncertainty”.

See the demonstration video of their work and read the full paper here.

For more details visit see the multi robot collision stack.