- References
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]
References
2. ^{{cite conference |author1=Tychonievich, L. P. |author2=Zaret, D. |author3=Mantegna, R. |author4=Evans, R. |author5=Muehle, E. |author6=Martin, S. |year=1989 |title=A maneuvering-board approach to path planning with moving obstacles |conference=International Joint conference on Artificial Intelligence (IJCAI) |pages=1017–1021}}
3. ^{{cite conference |author1=Fiorini, P. |author2=Shiller, Z. |year=1993 |title=Motion planning in dynamic environments using the relative velocity paradigm |conference=IEEE Conference on Robotics and Automation |pages=560–565}}
4. ^{{cite journal |doi=10.1109/3468.709600 |author1=Chakravarthy, A. |author2=Ghose, D. |title=Obstacle avoidance in a dynamic environment: A collision cone approach |journal=IEEE Transactions on Systems, Man and Cybernetics—Part A: Systems and Humans |volume=28 |issue=5 |pages=562–574 |date=September 1998|citeseerx=10.1.1.101.2050 }}
5. ^{{cite conference |author1=Damas, B. |author2=Santos-Victor, J. |title=Avoiding moving obstacles: the forbidden velocity map |conference=IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) |year=2009 |pages=4393–4398}}
6. ^{{cite book |author1=Miller, F. S. |author2=Everett, A. F. |title=Instructions for the Use of Martin's Mooring Board and Battenberg's Course Indicator |publisher=Authority of the Lords of Commissioners of the Admirality |year=1903}}
7. ^{{cite conference |author1=Abe, Y. |author2=Yoshiki, M. |date=November 2001 |title=Collision avoidance method for multiple autonomous mobile agents by implicit cooperation |doi=10.1109/IROS.2001.977147 |conference=IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 01) |publisher=IEEE. |location=New York, N.Y. |pages=1207–1212}}
8. ^{{cite conference |author1=Guy, S. J. |author2=Chhugani, J. |author3=Kim, C. |author4=Satish, N. |author5=Lin, M. |author6=Manocha, D. |author7=Dubey, P. |date=August 2009 |title=ClearPath: Highly parallel collision avoidance for multi-agent simulation |doi=10.1145/1599470.1599494 |conference=ACM SIGGRAPH/Eurographics Symposium on Computer Animation (SCA 09) |publisher=ACM.|location=New York, N.Y. |pages=177–187}}
9. ^{{cite conference |author1=Wilkie, D. |author2=v.d. Berg, J. |author3=Manocha, D. |date=October 2009 |title=Generalized velocity obstacles |doi=10.1109/IROS.2009.5354175 |conference=IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 09) |publisher=IEEE. |location=New York, N.Y.}}
10. ^{{cite conference |author1=Snape, J. |author2=v.d. Berg, J. |author3=Guy, S. J. |author4=Manocha, D. |date=October 2009 |title=Independent navigation of multiple mobile robots with hybrid reciprocal velocity obstacles |url=http://gamma.cs.unc.edu/HRVO/ |conference=IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 09) |publisher=IEEE |location=New York, N.Y.}}
11. ^{{cite conference |author1=Large, F. |author2=Sekhavat, S. |author3=Shiller, Z. |author4=Laugier, C. |date=December 2002 |title=Using non-linear velocity obstacles to plan motions in a dynamic environment |doi=10.1109/ICARCV.2002.1238513 |conference=IEEE International Conference on Control, Automation, Robotics and Vision (ICARCV 02) |publisher=IEEE |location=New York, N.Y. |pages=734–739}}
12. ^{{cite conference |last=v.d. Berg |first=J. |authorlink=Jur P. van den Berg |last2=Lin |first2=M. |last3=Manocha |first3=D. |date=May 2008 |title=Reciprocal velocity obstacles for real-time multi-agent navigation |doi=10.1109/ROBOT.2008.4543489|conference=IEEE International Conference on Robotics and Automation (ICRA 08) |publisher=IEEE |location=New York, N.Y. |pages=1928–1935}}
13. ^{{cite conference |author1=Fulgenzi, C. |author2=Spalanzani, A. |author3=Laugier, C. |date=April 2007 |title=Dynamic obstacle avoidance in uncertain environment combining PVOs and occupancy grid |doi=10.1109/ROBOT.2007.363554 |conference=IEEE International Conference on Robotics and Automation (ICRA 07) |publisher=IEEE |location=New York, N.Y. |pages=1610–1616}}
- Ragnhildr (disambiguation)
- Ragnhild Rød
- Ragnhild (saint)
- Ragnhild Tregagas
- Ragnhild Tregagás
- Ragnhild Tregagås
- Ragni Cawén
- Ragnildur Steinunn Jónsdóttir
- Ragni Piene
- Ragnitz
- Ragnvald Alfred Roscher Lund
- Ragnvald Blix
- Ragnvald Bodtker
- Ragnvald Bødtker
- Ragnvald Gjerlow
- Ragnvald Gjerløw
- Ragnvald Hedumhaere
- Ragnvald Hoier
- Ragnvald Høier
- Ragnvald Høyer
- Ragnvald III
- Ragnvald Knaphoevde
- Ragnvald Knaphovde
- Ragnvald Moe
- Ragnvald of Sweden