Velocity obstacle

From formulasearchengine
Jump to navigation Jump to search
The velocity obstacle VOAB for a robot A, with position xA, induced by another robot B, with position xB and velocity vB.

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]

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 induced by a robot may be formally written as

where has position and radius , and has position , radius , and velocity . The notation represents a disc with center and radius .

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]


  1. 1.0 1.1 {{#invoke:Citation/CS1|citation |CitationClass=journal }}
  2. {{#invoke:citation/CS1|citation |CitationClass=conference }}
  3. {{#invoke:citation/CS1|citation |CitationClass=conference }}
  4. {{#invoke:Citation/CS1|citation |CitationClass=journal }}
  5. {{#invoke:citation/CS1|citation |CitationClass=conference }}
  6. {{#invoke:citation/CS1|citation |CitationClass=book }}
  7. {{#invoke:citation/CS1|citation |CitationClass=conference }}
  8. {{#invoke:citation/CS1|citation |CitationClass=conference }}
  9. {{#invoke:citation/CS1|citation |CitationClass=conference }}
  10. {{#invoke:citation/CS1|citation |CitationClass=conference }}
  11. {{#invoke:citation/CS1|citation |CitationClass=conference }}
  12. {{#invoke:citation/CS1|citation |CitationClass=conference }}
  13. {{#invoke:citation/CS1|citation |CitationClass=conference }}