Velocity obstacle

Last updated April 07, 2024

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]

Related Research Articles

Boids is an artificial life program, developed by Craig Reynolds in 1986, which simulates the flocking behaviour of birds, and related group motion. His paper on this topic was published in 1987 in the proceedings of the ACM SIGGRAPH conference. The name "boid" corresponds to a shortened version of "bird-oid object", which refers to a bird-like object. Reynolds' boid model is one example of a larger general concept, for which many other variations have been developed since. The closely related work of Ichiro Aoki is noteworthy because it was published in 1982 — five years before Reynolds' boids paper.

In artificial intelligence, a fluent is a condition that can change over time. In logical approaches to reasoning about actions, fluents can be represented in first-order logic by predicates having an argument that depends on time. For example, the condition "the box is on the table", if it can change over time, cannot be represented by $; a third argument is necessary to the predicate to specify the time: means that the box is on the table at time . This representation of fluents is modified in the situation calculus by using the sequence of the past actions in place of the current time.$

RAVON is a robot being developed at the Robotics Research Lab at University of Kaiserslautern, Germany. The vehicle is used, as a testbed to investigate behaviour-based strategies on motion adaptation, localization and navigation in rough outdoor terrain. The basis vehicle was produced by Robosoft.

A virtual fixture is an overlay of augmented sensory information upon a user's perception of a real environment in order to improve human performance in both direct and remotely manipulated tasks. Developed in the early 1990s by Louis Rosenberg at the U.S. Air Force Research Laboratory (AFRL), Virtual Fixtures was a pioneering platform in virtual reality and augmented reality technologies.

A rapidly exploring random tree (RRT) is an algorithm designed to efficiently search nonconvex, high-dimensional spaces by randomly building a space-filling tree. The tree is constructed incrementally from samples drawn randomly from the search space and is inherently biased to grow towards large unsearched areas of the problem. RRTs were developed by Steven M. LaValle and James J. Kuffner Jr. They easily handle problems with obstacles and differential constraints and have been widely used in autonomous robotic motion planning.

<span class="mw-page-title-main">Rhex</span>

RHex is an autonomous robot design, based on hexapod with compliant legs and one actuator per leg. A number of US universities have participated, with funding grants also coming from DARPA.

In robotics, Vector Field Histogram (VFH) is a real time motion planning algorithm proposed by Johann Borenstein and Yoram Koren in 1991. The VFH utilizes a statistical representation of the robot's environment through the so-called histogram grid, and therefore places great emphasis on dealing with uncertainty from sensor and modeling errors. Unlike other obstacle avoidance algorithms, VFH takes into account the dynamics and shape of the robot, and returns steering commands specific to the platform. While considered a local path planner, i.e., not designed for global path optimality, the VFH has been shown to produce near optimal paths.

In robotics motion planning, the dynamic window approach is an online collision avoidance strategy for mobile robots developed by Dieter Fox, Wolfram Burgard, and Sebastian Thrun in 1997. Unlike other avoidance methods, the dynamic window approach is derived directly from the dynamics of the robot, and is especially designed to deal with the constraints imposed by limited velocities and accelerations of the robot.

In robotics and computer vision, visual odometry is the process of determining the position and orientation of a robot by analyzing the associated camera images. It has been used in a wide variety of robotic applications, such as on the Mars Exploration Rovers.

Johann Borenstein is an Israeli roboticist and Professor at the University of Michigan. Borenstein is well known for his work in autonomous obstacle avoidance, and is credited with the development of the Vector Field Histogram.

Allen was a robot introduced by Rodney Brooks and his team in the late 1980s, and was their first robot based on subsumption architecture. It had sonar distance and odometry on board, and used an offboard lisp machine to simulate subsumption architecture. It resembled a footstool on wheels.

Any-angle path planning algorithms are pathfinding algorithms that search for a Euclidean shortest path between two points on a grid map while allowing the turns in the path to have any angle. The result is a path that cuts directly through open areas and has relatively few turns. More traditional pathfinding algorithms such as A* either lack in performance or produce jagged, indirect paths.

Jur P. van den Berg is the Chief Technology Officer and co-founder of driverless trucking startup Ike, which was sold to Nuro in 2020. He has been an assistant professor at the University of Utah. He was formerly a post-doctoral researcher in the Department of Industrial Engineering and Operations Research at the University of California, Berkeley and in the Department of Computer Science at the University of North Carolina at Chapel Hill. He has published more than 40 works in computational chemistry, computational geometry, computer animation, industrial engineering, robotics, and virtual reality. He has also coauthored the reciprocal velocity obstacle library for multi-agent navigation.

Differential dynamic programming (DDP) is an optimal control algorithm of the trajectory optimization class. The algorithm was introduced in 1966 by Mayne and subsequently analysed in Jacobson and Mayne's eponymous book. The algorithm uses locally-quadratic models of the dynamics and cost functions, and displays quadratic convergence. It is closely related to Pantoja's step-wise Newton's method.

<span class="mw-page-title-main">Oussama Khatib</span> American Roboticist

Oussama Khatib is a roboticist and a professor of computer science at Stanford University, and a Fellow of the IEEE. He is credited with seminal work in areas ranging from robot motion planning and control, human-friendly robot design, to haptic interaction and human motion synthesis. His work's emphasis has been to develop theories, algorithms, and technologies, that control robot systems by using models of their physical dynamics. These dynamic models are used to derive optimal controllers for complex robots that interact with the environment in real-time.

A behavior tree is a mathematical model of plan execution used in computer science, robotics, control systems and video games. They describe switchings between a finite set of tasks in a modular fashion. Their strength comes from their ability to create very complex tasks composed of simple tasks, without worrying how the simple tasks are implemented. Behavior trees present some similarities to hierarchical state machines with the key difference that the main building block of a behavior is a task rather than a state. Its ease of human understanding make behavior trees less error prone and very popular in the game developer community. Behavior trees have been shown to generalize several other control architectures.

PRAC (Probabilistic Action Cores) is an interpreter for natural-language instructions for robotic applications developed at the Institute for Artificial Intelligence at the University of Bremen, Germany, and is supported in parts by the European Commission and the German Research Foundation (DFG).

Robotic governance provides a regulatory framework to deal with autonomous and intelligent machines. This includes research and development activities as well as handling of these machines. The idea is related to the concepts of corporate governance, technology governance and IT-governance, which provide a framework for the management of organizations or the focus of a global IT infrastructure.

Margarita Chli is an assistant professor and leader of the Vision for Robotics Lab at ETH Zürich in Switzerland. Chli is a leader in the field of computer vision and robotics and was on the team of researchers to develop the first fully autonomous helicopter with onboard localization and mapping. Chli is also the Vice Director of the Institute of Robotics and Intelligent Systems and an Honorary Fellow of the University of Edinburgh in the United Kingdom. Her research currently focuses on developing visual perception and intelligence in flying autonomous robotic systems.

A continuum robot is a type of robot that is characterised by infinite degrees of freedom and number of joints. These characteristics allow continuum manipulators to adjust and modify their shape at any point along their length, granting them the possibility to work in confined spaces and complex environments where standard rigid-link robots cannot operate. In particular, we can define a continuum robot as an actuatable structure whose constitutive material forms curves with continuous tangent vectors. This is a fundamental definition that allows to distinguish between continuum robots and snake-arm robots or hyper-redundant manipulators: the presence of rigid links and joints allows them to only approximately perform curves with continuous tangent vectors.

References

1 2 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.

This robotics-related article is a stub. You can help Wikipedia by expanding it.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[fiorini98-1] 1 2 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]