Velocity obstacle information

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.

Velocity obstacle information

and 20 Related for: Velocity obstacle information

Velocity obstacle

PVO

Vo

CVO

Motion planning

Shear velocity

Virtual human

Speed of light

Wave

Rapids

List of 40 mm grenades

Doppler effect

Ripple tank

Boundary conditions in fluid dynamics

Stokes number

Coilgun

M60 tank

Lee wave

Echo

Dynamic window approach