Velocity obstacle

From HandWiki
Short description: Term in robotics and motion planning
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 [math]\displaystyle{ A }[/math] induced by a robot [math]\displaystyle{ B }[/math] may be formally written as

[math]\displaystyle{ VO_{A|B} = \{ \mathbf{v}\,|\, \exists t \gt 0 : (\mathbf{v} - \mathbf{v}_B)t \in D(\mathbf{x}_B - \mathbf{x}_A, r_A + r_B) \} }[/math]

where [math]\displaystyle{ A }[/math] has position [math]\displaystyle{ \mathbf{x}_A }[/math] and radius [math]\displaystyle{ r_A }[/math], and [math]\displaystyle{ B }[/math] has position [math]\displaystyle{ \mathbf{x}_B }[/math], radius [math]\displaystyle{ r_B }[/math], and velocity [math]\displaystyle{ \mathbf{v}_B }[/math]. The notation [math]\displaystyle{ D(\mathbf{x}, r) }[/math] represents a disc with center [math]\displaystyle{ \mathbf{x} }[/math] and radius [math]\displaystyle{ r }[/math].

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]

References

  1. ↑ 1.0 1.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. doi:10.1177/027836499801700706. ISSN 0278-3649. 
  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. 
  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. 
  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. 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. 
  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 City: 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 City: 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 City: 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 City: IEEE. http://gamma.cs.unc.edu/HRVO/. 
  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 City: IEEE. pp. 734–739. doi:10.1109/ICARCV.2002.1238513. 
  12. ↑ "Reciprocal velocity obstacles for real-time multi-agent navigation". IEEE International Conference on Robotics and Automation (ICRA 08). New York City: IEEE. May 2008. pp. 1928–1935. 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 City: IEEE. pp. 1610–1616. doi:10.1109/ROBOT.2007.363554. 




Retrieved from "https://handwiki.org/wiki/index.php?title=Velocity_obstacle&oldid=3357261"