Velocity obstacle explained

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

A induced by a robot B may be formally written asVO _{A|B} = \{ v | \exists t > 0 : ( v - v _{B)t} \in D( x _{B} - x _{A,} r _{A} + r _{B)} \}

where

A has position x _{A} and radius r _{A} , and B has position x _{B} , radius r _{B} , and velocity v _{B} . The notation D( x , r) represents a disc with center x and radius 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]

Notes and References

1. Fiorini, P. . Shiller, Z. . July 1998 . Motion planning in dynamic environments using velocity obstacles . 10.1177/027836499801700706 . The International Journal of Robotics Research . 17 . 7 . 760–772 . 0278-3649. 10.1.1.56.6352 . 9073894 .
2. Tychonievich, L. P. . Zaret, D. . Mantegna, R. . Evans, R. . Muehle, E. . Martin, S. . 1989 . A maneuvering-board approach to path planning with moving obstacles . International Joint conference on Artificial Intelligence (IJCAI) . 1017–1021.
3. Fiorini, P. . Shiller, Z. . 1993 . Motion planning in dynamic environments using the relative velocity paradigm . IEEE Conference on Robotics and Automation . 560–565.
4. 10.1109/3468.709600 . Chakravarthy, A. . Ghose, D. . Obstacle avoidance in a dynamic environment: A collision cone approach . IEEE Transactions on Systems, Man, and Cybernetics - Part A: Systems and Humans . 28 . 5 . 562–574 . September 1998. 10.1.1.101.2050 .
5. Damas, B. . Santos-Victor, J. . Avoiding moving obstacles: the forbidden velocity map . IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) . 2009 . 4393–4398.
6. Book: Miller, F. S. . Everett, A. F. . Instructions for the Use of Martin's Mooring Board and Battenberg's Course Indicator . Authority of the Lords of Commissioners of the Admiralty . 1903.
7. Abe, Y. . Yoshiki, M. . November 2001 . Collision avoidance method for multiple autonomous mobile agents by implicit cooperation . 10.1109/IROS.2001.977147 . IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 01) . IEEE. . . 1207–1212.
8. Guy, S. J. . Chhugani, J. . Kim, C. . Satish, N. . Lin, M. . Manocha, D. . Dubey, P. . August 2009 . ClearPath: Highly parallel collision avoidance for multi-agent simulation . 10.1145/1599470.1599494 . ACM SIGGRAPH/Eurographics Symposium on Computer Animation (SCA 09) . ACM.. . 177–187.
9. Wilkie, D. . v.d. Berg, J. . Manocha, D. . October 2009 . Generalized velocity obstacles . 10.1109/IROS.2009.5354175 . IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 09) . IEEE. . New York, N.Y..
10. Snape, J. . v.d. Berg, J. . Guy, S. J. . Manocha, D. . October 2009 . Independent navigation of multiple mobile robots with hybrid reciprocal velocity obstacles . IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 09) . . New York, N.Y..
11. Large, F. . Sekhavat, S. . Shiller, Z. . Laugier, C. . December 2002 . Using non-linear velocity obstacles to plan motions in a dynamic environment . 10.1109/ICARCV.2002.1238513 . IEEE International Conference on Control, Automation, Robotics and Vision (ICARCV 02) . . . 734–739.
12. v.d. Berg . J. . Jur P. van den Berg . Lin . M. . Manocha . D. . May 2008 . Reciprocal velocity obstacles for real-time multi-agent navigation . 10.1109/ROBOT.2008.4543489. IEEE International Conference on Robotics and Automation (ICRA 08) . . . 1928–1935. 10.1.1.127.6140 .
13. Fulgenzi, C. . Spalanzani, A. . Laugier, C. . April 2007 . Dynamic obstacle avoidance in uncertain environment combining PVOs and occupancy grid . 10.1109/ROBOT.2007.363554 . IEEE International Conference on Robotics and Automation (ICRA 07) . . . 1610–1616. 10.1.1.696.8423.