Motion Planning in Dynamic Environments Using Velocity Obstacles
The DOI matches its Crossref record; 27 of the 27 references it cites were found in a registry or an index.
Abstract
This paper presents a method for robot motion planning in dynamic environments. It consists of selecting avoidance maneuvers to avoid static and moving obstacles in the velocity space, based on the cur rent positions and velocities of the robot and obstacles. It is a first- order method, since it does not integrate velocities to yield positions as functions of time. The avoidance maneuvers are generated by selecting robot ve locities outside of the velocity obstacles, which represent the set of robot velocities that would result in a collision with a given obstacle that moves at a given velocity, at some future time. To ensure that the avoidance maneuver is dynamically feasible, the set of avoidance velocities is intersected with the set of admissible velocities, defined by the robot's acceleration constraints. Computing new avoidance maneuvers at regular time intervals accounts for general obstacle trajectories. The trajectory from start to goal is computed by searching a tree of feasible avoidance maneuvers, computed at discrete time intervals. An exhaustive search of the tree yields near-optimal trajectories that either minimize distance or motion time. A heuristic search of the tree is applicable to on-line planning. The method is demonstrated for point and disk robots among static and moving obstacles, and for an automated vehicle in an intelligent vehicle highway system scenario.
Overview
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
In the citing paper
“2) the presence of dynamic obstacles needs to be detected for collision avoidance [6] and for spatial reasoning of the environment [7].”
From NavFormer: A Transformer Architecture for Robot Target-Driven Navigation in Unknown and Dynamic Environments (2024) · cites this paper as [6]
Citations
Cites
Principles of Artificial Intelligence
Nilsson, N. J. (1982) · doi:10.1007/978-3-662-09438-9 · Cited by 3,457 · cited 1×
“By assigning an appropriate cost to each branch, this tree can be searched for the trajectory that maximizes some objective function, such as distance traveled, motion time, or energy, using standard search techniques (Nilsson, 1980; Pearl, 1985).”
MethodDepth-first iterative-deepening
Korf, R. E. (1985) · Artificial Intelligence · doi:10.1016/0004-3702(85)90084-0 · Cited by 1,562
Principles of artificial intelligence
McDermott, J. (1980) · Artificial Intelligence · doi:10.1016/0004-3702(80)90026-0 · Cited by 814
Toward Efficient Trajectory Planning: The Path-Velocity Decomposition
Kant, K., & Zucker, S. W. (1986) · The International Journal of Robotics Research · doi:10.1177/027836498600500304 · Cited by 753
Erdmann, M., & Lozano-Pérez, T. (1987) · Algorithmica · doi:10.1007/bf01840371 · Cited by 736
New lower bound techniques for robot motion planning problems
Canny, J., & Reif, J. (1987) · 28th Annual Symposium on Foundations of Computer Science (sfcs 1987) · doi:10.1109/sfcs.1987.42 · Cited by 538
Motion planning in dynamic environments using the relative velocity paradigm
Fiorini, P., & Shiller, Z. (2002) · [1993] Proceedings IEEE International Conference on Robotics and Automation · doi:10.1109/robot.1993.292038 · Cited by 208
Self-citationA hierarchical strategy for path planning among moving obstacles (mobile robot)
Fujimura, K., & Samet, H. (1989) · IEEE Transactions on Robotics and Automation · doi:10.1109/70.88018 · Cited by 192
Collision-Free Motion Planning of Two Robots
Lee, B., & G. Lee, C. (1987) · IEEE Transactions on Systems, Man, and Cybernetics · doi:10.1109/tsmc.1987.289330 · Cited by 186
On the complexity of kinodynamic planning
Canny, J., Donald, B., Reif, J., & Xavier, P. (1988) · [Proceedings 1988] 29th Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1988.21947 · Cited by 184
A hierarchical strategy for path planning among moving obstacles
Fujimura, K., & Samet, H. (1989) · IEEE Journal on Robotics and Automation · Cited by 182
Motion planning in the presence of moving obstacles
Reif, J., & Sharir, M. (1994) · Journal of the ACM · doi:10.1145/179812.179911 · Cited by 174
Decomposition of Three-Dimensional Objects into Spheres
O’Rourke, J., & Badler, N. I. (1979) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.1979.4766925 · Cited by 146
Dynamic trajectory planning with dynamic constraints: A 'state-time space' approach
Fraichard, T. (2002) · IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) · doi:10.1109/iros.1993.583794 · Cited by 90
Time optimal trajectory planning in dynamic environments
Fiorini, P., & Shiller, Z. (2002) · Proceedings - IEEE International Conference on Robotics and Automation/Proceedings · doi:10.1109/robot.1996.506925 · Cited by 87
Self-citationCameron, S. (1984) · ERA · Cited by 63
A model of reaction for planning in dynamic environments
Sanborn, J. C., & Hendler, J. (1988) · Artificial Intelligence in Engineering · doi:10.1016/0954-1810(88)90025-8 · Cited by 57
Path-velocity decomposition revisited and applied to dynamic trajectory planning
Fraichard, T., & Laugier, C. (2002) · Proceedings - IEEE International Conference on Robotics and Automation/Proceedings · doi:10.1109/robot.1993.292121 · Cited by 57
Motion planning in a dynamic domain
Fujimura, K., & Samet, H. (2002) · Proceedings - IEEE International Conference on Robotics and Automation/Proceedings · doi:10.1109/robot.1990.125996 · Cited by 52
Tsubouchi, T., & Arimoto, S. (2002) · Proceedings - IEEE International Conference on Robotics and Automation/Proceedings · doi:10.1109/robot.1994.351140 · Cited by 47
Planning a time-minimal motion among moving obstacles
Fujimura, K., & Samet, H. (1993) · Algorithmica · doi:10.1007/bf01908631 · Cited by 46
Time-minimal paths among moving obstacles
Fujimura, K., & Samet, H. (2003) · Proceedings - IEEE International Conference on Robotics and Automation/Proceedings · doi:10.1109/robot.1989.100129 · Cited by 43
Time-minimum routes in time-dependent networks
Fujimura, K. (1995) · IEEE Transactions on Robotics and Automation · doi:10.1109/70.388776 · Cited by 40
Efficient Collision Prediction Among Many Moving Objects
Hayward, V., Aubry, S., Foisy, A., & Ghallab, Y. (1995) · The International Journal of Robotics Research · doi:10.1177/027836499501400203 · Cited by 34
Robot Motion Planning in Dynamic Environments
Fiorini, P., & Shiller, Z. (1996) · Springer eBooks · doi:10.1007/978-1-4471-1021-7_27 · Cited by 24
Self-citationMotion Planning Amid Transient Obstacles
Fujimura, K. (1994) · The International Journal of Robotics Research · doi:10.1177/027836499401300502 · Cited by 23
Emergency Maneuvers of Autonomous Vehicles
Shiller, Z., & Sundar, S. (1996) · IFAC Proceedings Volumes · doi:10.1016/s1474-6670(17)58995-8 · Cited by 11
Self-citation
Research works printed but not linked: 8
- Erdmann, M., 1986, Algorithmica, 2, 477
- Fiorini, P., 1995, Robot motion planning among moving obstacles. Ph.D. thesis
- Fiorini, P., 1997, J. Appl. Math. and Comp. Sci., 7, 101
- Fraichard, T., 1993, IEEE/RSJ Int. Conf. on Intell. Robots and Sys., 1393
- Fraichard, T., 1993, IEEE Int. Conf. of Automat. and Robot, 1, 40
- Pearl, J., 1985, Heuristics
- Reif, J., 1985, 25th IEEE Symp. on the Found. of Comp. Sci., 144
- Tsubouchi, T., 1994, IEEE Conf. on Robot. and Automat., 2470
Cited by
Reciprocal n-Body Collision Avoidance
van den Berg, J., Guy, S. J., Lin, M., & Manocha, D. (2011) · Springer Tracts in Advanced Robotics · doi:10.1007/978-3-642-19457-3_1 · Cited by 1,858
Reciprocal Velocity Obstacles for real-time multi-agent navigation
van den Berg, J., Lin, M., & Manocha, D. (2008) · 2008 IEEE International Conference on Robotics and Automation · doi:10.1109/robot.2008.4543489 · Cited by 1,722
A Review of Motion Planning for Highway Autonomous Driving
Claussmann, L., Revilloud, M., Gruyer, D., & Glaser, S. (2020) · IEEE Transactions on Intelligent Transportation Systems · doi:10.1109/tits.2019.2913998 · Cited by 670
Perception, Planning, Control, and Coordination for Autonomous Vehicles
Pendleton, S., Andersen, H., Du, X., Shen, X., Meghjani, M., Eng, Y., Rus, D., & Ang, M. (2017) · Machines · doi:10.3390/machines5010006 · Cited by 657
Safe Maritime Autonomous Navigation With COLREGS, Using Velocity Obstacles
Kuwata, Y., Wolf, M. T., Zarzhitsky, D. V., & Huntsberger, T. L. (2013) · IEEE Journal of Oceanic Engineering · doi:10.1109/joe.2013.2254214 · Cited by 495
Metadata
- Authors
- Fiorini, P., & Shiller, Z.
- Affiliations
- Jet Propulsion Laboratory (US)
- University of California, Los Angeles (US)
- Venue
- The International Journal of Robotics Research
- Publisher
- SAGE Publications
- Published
- 1998-07
- Volume
- 17
- Issue
- 7
- Pages
- 760-772
- ISSN
- 0278-3649 (ISSN-L)
- 1741-3176
- OpenAlex
- W2002440441
- Cited by
- 2,008
- References
- 27
- Citations by year
- 2026: 125 · 2025: 149 · 2024: 143 · 2023: 138 · 2022: 143 · 2021: 140 · 2020: 134 · 2019: 111 · 2018: 121 · 2017: 97 · 2016: 86 · 2015: 97 · 2014: 93 · 2013: 85 · 2012: 71
- FWCI
- 8.25
- Type
- journal article
- Language
- en
- Open access
- closed
- Licence
- journals.sagepub.com/page/policies/text-and-data-mining-license (tdm)
- Locations
- The International Journal of Robotics Research (publishedVersion)
- Funders
- Jet Propulsion Laboratory
- Topics
- Physical Sciences › Engineering › Control and Systems Engineering › Robotic Path Planning Algorithms
- Physical Sciences › Computer Science › Artificial Intelligence › Reinforcement Learning in Robotics
- Physical Sciences › Engineering › Control and Systems Engineering › Control and Dynamics of Mobile Robots
- Keywords
- robot motion planning, dynamic environments, velocity obstacle, collision avoidance, dynamic obstacles, velocity space, acceleration constraints, tree search, heuristic search, online planning, point robot, autonomous vehicles, intelligent transportation systems
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.