Velocity obstacle

In robotics and motion planning, a velocity obstacle, commonly abbreviated VO, is the set of all velocities of a robot that will result in a collision with another robot at some moment in time, assuming that the other robot maintains its current velocity.^[1] If the robot chooses a velocity inside the velocity obstacle then the two robots will eventually collide, if it chooses a velocity outside the velocity obstacle, such a collision is guaranteed not to occur.^[1]

The velocity obstacle VO_AB for a robot A, with position x_A, induced by another robot B, with position x_B and velocity v_B.

This algorithm for robot collision avoidance has been repeatedly rediscovered and published under different names: in 1989 as a maneuvering board approach,^[2] in 1993 it was first introduced as the "velocity obstacle",^[3] in 1998 as collision cones,^[4] and in 2009 as forbidden velocity maps.^[5] The same algorithm has been used in maritime port navigation since at least 1903.^[6]

The velocity obstacle for a robot ${\displaystyle A}$ induced by a robot ${\displaystyle B}$ may be formally written as

${\displaystyle VO_{A|B}=\{\mathbf {v} \,|\,\exists t>0:(\mathbf {v} -\mathbf {v} _{B})t\in D(\mathbf {x} _{B}-\mathbf {x} _{A},r_{A}+r_{B})\}}$

where ${\displaystyle A}$ has position ${\displaystyle \mathbf {x} _{A}}$ and radius ${\displaystyle r_{A}}$, and ${\displaystyle B}$ has position ${\displaystyle \mathbf {x} _{B}}$, radius ${\displaystyle r_{B}}$, and velocity ${\displaystyle \mathbf {v} _{B}}$. The notation ${\displaystyle D(\mathbf {x} ,r)}$ represents a disc with center ${\displaystyle \mathbf {x} }$ and radius ${\displaystyle r}$.

Variations include common velocity obstacles (CVO),^[7] finite-time-interval velocity obstacles (FVO),^[8] generalized velocity obstacles (GVO),^[9] hybrid reciprocal velocity obstacles (HRVO),^[10] nonlinear velocity obstacles (NLVO),^[11] reciprocal velocity obstacles (RVO),^[12] and recursive probabilistic velocity obstacles (PVO).^[13]