XXX probably need to re-read this paper. the notes don't seem very helpful.

"Reciprocal Velocity Obstacles for Real-Time Multi-Agent Navigation" Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), 2008. Jur van den Berg, Ming C. Lin, Dinesh Manocha

Allows you to detect if two objects moving at a given bearing and speed will infringe upon one another’s space.

Oscillation problem: when agents detect they will collide, chose a corrected course to avoid the collision, then later attempt to choose a faster course that ultimately is re-corrected because it collides again.

Velocity Obstacles

and are agents moving across the plane

is the position of agent A and is the position of agent B.

and are the velocities of agents A and B.

The set contains all velocities for A which will collide with B moving at .

is the Minkoswki sum of A and B.

• A means A reflected by its reference point.

Minkowski sum creates a “cone” which is the collision shape of something at its current bearing and speed and you can test if another object will collide on its course by testing if there will be a collision to this cone.

Reciprocal Velocity Obstacles

Set velocities for A and B to the average of their current velocity and a velocity which is outside the collision set.

If choosing the velocity which is closest to the hull but still outside then the pathing remains optimal but future readjustments will be stable and choose the same points repeatedly instead of “oscillating.”