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]

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 as

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

^ ^a ^b Fiorini, P.; Shiller, Z. (July 1998). "Motion planning in dynamic environments using velocity obstacles". The International Journal of Robotics Research. 17 (7): 760–772. CiteSeerX 10.1.1.56.6352. doi:10.1177/027836499801700706. ISSN 0278-3649. S2CID 9073894.
^ 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). pp. 1017–1021.
^ Fiorini, P.; Shiller, Z. (1993). Motion planning in dynamic environments using the relative velocity paradigm. IEEE Conference on Robotics and Automation. pp. 560–565.
^ Chakravarthy, A.; Ghose, D. (September 1998). "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. CiteSeerX 10.1.1.101.2050. doi:10.1109/3468.709600.
^ Damas, B.; Santos-Victor, J. (2009). Avoiding moving obstacles: the forbidden velocity map. IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). pp. 4393–4398.
^ Miller, F. S.; Everett, A. F. (1903). Instructions for the Use of Martin's Mooring Board and Battenberg's Course Indicator. Authority of the Lords of Commissioners of the Admiralty.
^ Abe, Y.; Yoshiki, M. (November 2001). Collision avoidance method for multiple autonomous mobile agents by implicit cooperation. IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 01). New York, N.Y.: IEEE. pp. 1207–1212. doi:10.1109/IROS.2001.977147.
^ 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. ACM SIGGRAPH/Eurographics Symposium on Computer Animation (SCA 09). New York, N.Y.: ACM. pp. 177–187. doi:10.1145/1599470.1599494.
^ Wilkie, D.; v.d. Berg, J.; Manocha, D. (October 2009). Generalized velocity obstacles. IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 09). New York, N.Y.: IEEE. doi:10.1109/IROS.2009.5354175.
^ 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.: IEEE.
^ Large, F.; Sekhavat, S.; Shiller, Z.; Laugier, C. (December 2002). Using non-linear velocity obstacles to plan motions in a dynamic environment. IEEE International Conference on Control, Automation, Robotics and Vision (ICARCV 02). New York, N.Y.: IEEE. pp. 734–739. doi:10.1109/ICARCV.2002.1238513.
^ v.d. Berg, J.; Lin, M.; Manocha, D. (May 2008). Reciprocal velocity obstacles for real-time multi-agent navigation. IEEE International Conference on Robotics and Automation (ICRA 08). New York, N.Y.: IEEE. pp. 1928–1935. CiteSeerX 10.1.1.127.6140. doi:10.1109/ROBOT.2008.4543489.
^ Fulgenzi, C.; Spalanzani, A.; Laugier, C. (April 2007). Dynamic obstacle avoidance in uncertain environment combining PVOs and occupancy grid. IEEE International Conference on Robotics and Automation (ICRA 07). New York, N.Y.: IEEE. pp. 1610–1616. CiteSeerX 10.1.1.696.8423. doi:10.1109/ROBOT.2007.363554.

[fiorini98-1] Fiorini, P.; Shiller, Z. (July 1998). "Motion planning in dynamic environments using velocity obstacles". The International Journal of Robotics Research. 17 (7): 760–772. CiteSeerX 10.1.1.56.6352. doi:10.1177/027836499801700706. ISSN 0278-3649. S2CID 9073894.

[tychonieivich89-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). pp. 1017–1021.

[fiorini93-3] Fiorini, P.; Shiller, Z. (1993). Motion planning in dynamic environments using the relative velocity paradigm. IEEE Conference on Robotics and Automation. pp. 560–565.

[chakravarthy98-4] Chakravarthy, A.; Ghose, D. (September 1998). "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. CiteSeerX 10.1.1.101.2050. doi:10.1109/3468.709600.

[5] Damas, B.; Santos-Victor, J. (2009). Avoiding moving obstacles: the forbidden velocity map. IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). pp. 4393–4398.

[miller03-6] Miller, F. S.; Everett, A. F. (1903). Instructions for the Use of Martin's Mooring Board and Battenberg's Course Indicator. Authority of the Lords of Commissioners of the Admiralty.

[7] Abe, Y.; Yoshiki, M. (November 2001). Collision avoidance method for multiple autonomous mobile agents by implicit cooperation. IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 01). New York, N.Y.: IEEE. pp. 1207–1212. doi:10.1109/IROS.2001.977147.

[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. ACM SIGGRAPH/Eurographics Symposium on Computer Animation (SCA 09). New York, N.Y.: ACM. pp. 177–187. doi:10.1145/1599470.1599494.

[9] Wilkie, D.; v.d. Berg, J.; Manocha, D. (October 2009). Generalized velocity obstacles. IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 09). New York, N.Y.: IEEE. doi:10.1109/IROS.2009.5354175.

[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.: IEEE.

[11] Large, F.; Sekhavat, S.; Shiller, Z.; Laugier, C. (December 2002). Using non-linear velocity obstacles to plan motions in a dynamic environment. IEEE International Conference on Control, Automation, Robotics and Vision (ICARCV 02). New York, N.Y.: IEEE. pp. 734–739. doi:10.1109/ICARCV.2002.1238513.

[12] v.d. Berg, J.; Lin, M.; Manocha, D. (May 2008). Reciprocal velocity obstacles for real-time multi-agent navigation. IEEE International Conference on Robotics and Automation (ICRA 08). New York, N.Y.: IEEE. pp. 1928–1935. CiteSeerX 10.1.1.127.6140. doi:10.1109/ROBOT.2008.4543489.

[13] Fulgenzi, C.; Spalanzani, A.; Laugier, C. (April 2007). Dynamic obstacle avoidance in uncertain environment combining PVOs and occupancy grid. IEEE International Conference on Robotics and Automation (ICRA 07). New York, N.Y.: IEEE. pp. 1610–1616. CiteSeerX 10.1.1.696.8423. doi:10.1109/ROBOT.2007.363554.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]