Safe motion planning in dynamic environments
Open accessThe DOI matches its Crossref record; 20 of the 20 references it cites were found in a registry or an index.
Abstract
This paper addresses the problem of motion planning (MP) in dynamic environments. It is first argued that dynamic environments impose a real-time constraint upon MP: it has a limited time only to compute a motion, the time available being a function of the dynamicity of the environment. Now, given the intrinsic complexity of MP, computing a complete motion to the goal within the time available is impossible to achieve in most real situations. Partial motion planning (PMP) is the answer to this problem proposed in this paper. PMP is a motion planning scheme with an anytime flavor: when the time available is over, PMP returns the best partial motion to the goal computed so far. Like reactive navigation scheme, PMP faces a safety issue: what guarantee is there that the system will never end up in a critical situation yielding an inevitable collision? The answer proposed in this paper to this safety issue relies upon the concept of inevitable collision states (ICS). ICS takes into account the dynamics of both the system and the moving obstacles. By computing ICS-free partial motion, the system safety can be guaranteed. Application of PMP to the case of a car-like system in a dynamic environment is presented.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Latombe, J.-C. (1991) · Springer eBooks · doi:10.1007/978-1-4615-4022-9 · Cited by 6,396
Probabilistic roadmaps for path planning in high-dimensional configuration spaces
Kavraki, L. E., Svestka, P., Latombe, J.-C., & Overmars, M. H. (1996) · IEEE Transactions on Robotics and Automation · doi:10.1109/70.508439 · Cited by 6,343 · cited 1×
“Fortunately, in the mid 90’s, probabilistic planners appeared [8] and brought a new powerful tool for rapid exploration of high dimensional state-time space, framework presented in [9] used for complex systems and dynamic environment description.”
The dynamic window approach to collision avoidance
Fox, D., Burgard, W., & Thrun, S. (1997) · IEEE Robotics & Automation Magazine · doi:10.1109/100.580977 · Cited by 3,771
Motion Planning in Dynamic Environments Using Velocity Obstacles
Fiorini, P., & Shiller, Z. (1998) · The International Journal of Robotics Research · doi:10.1177/027836499801700706 · Cited by 2,008
The focussed D* algorithm for real-time replanning
Stentz, A. (1995) · Cited by 865
Real-Time Motion Planning for Agile Autonomous Vehicles
Frazzoli, E., Dahleh, M. A., & Feron, E. (2002) · Journal of Guidance, Control, and Dynamics · doi:10.2514/2.4856 · Cited by 830
Randomized Kinodynamic Motion Planning with Moving Obstacles
Hsu, D., Kindel, R., Latombe, J.-C., & Rock, S. (2002) · The International Journal of Robotics Research · doi:10.1177/027836402320556421 · Cited by 771
Randomized kinodynamic planning
LaValle, S. M., & Kuffner, J. J. (2003) · Proceedings 1999 IEEE International Conference on Robotics and Automation (Cat. No.99CH36288C) · doi:10.1109/robot.1999.770022 · Cited by 673
High-speed navigation using the global dynamic window approach
Brock, O., & Khatib, O. (2003) · Proceedings 1999 IEEE International Conference on Robotics and Automation (Cat. No.99CH36288C) · doi:10.1109/robot.1999.770002 · Cited by 539
The curvature-velocity method for local obstacle avoidance
Simmons, R. (2002) · Proceedings of IEEE International Conference on Robotics and Automation · doi:10.1109/robot.1996.511023 · Cited by 522
Real-time randomized path planning for robot navigation
Bruce, J., & Veloso, M. (2003) · IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) · doi:10.1109/irds.2002.1041624 · Cited by 405
VFH/sup */: local obstacle avoidance with look-ahead verification
Ulrich, I., & Borenstein, J. (2002) · Proceedings 2000 ICRA. Millennium Conference. IEEE International Conference on Robotics and Automation. Symposia Proceedings (Cat. No.00CH37065) · doi:10.1109/robot.2000.846405 · Cited by 386
Inevitable collision states — a step towards safer robots?
Fraichard, T., & Asama, H. (2004) · Advanced Robotics · doi:10.1163/1568553042674662 · Cited by 324
Self-citationImproved fast replanning for robot navigation in unknown terrain
Koenig, S., & Likhachev, M. (2003) · Proceedings 2002 IEEE International Conference on Robotics and Automation (Cat. No.02CH37292) · doi:10.1109/robot.2002.1013481 · Cited by 294
Stachniss, C., & Burgard, W. (2003) · IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) · doi:10.1109/irds.2002.1041441 · Cited by 137
Kinodynamic motion planning amidst moving obstacles
Kindel, R., Hsu, D., Latombe, J.-C., & Rock, S. M. (2002) · Proceedings - IEEE International Conference on Robotics and Automation/Proceedings · doi:10.1109/robot.2000.844109 · Cited by 128
Learning motion patterns of persons for mobile service robots
Bennewitz, M., Burgard, W., & Thrun, S. (2003) · Proceedings - IEEE International Conference on Robotics and Automation/Proceedings · doi:10.1109/robot.2002.1014268 · Cited by 104
Motion prediction for moving objects: a statistical approach
Vasquez, D., & Fraichard, T. (2004) · Proceedings - IEEE International Conference on Robotics and Automation/Proceedings · doi:10.1109/robot.2004.1308883 · Cited by 101
Self-citationReal-time motion planning for agile autonomous vehicles
Frazzoli, E., Dahleh, M. A., & Féron, É. (2000) · AIAA Guidance, Navigation, and Control Conference and Exhibit · doi:10.2514/6.2000-4056 · Cited by 71
Towards real-time global motion planning in a dynamic environment using the NLVO concept
Large, F., Sekhavat, S., Shiller, Z., et al. (2003) · IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) · doi:10.1109/irds.2002.1041458 · Cited by 61
Cited by
A Survey of Motion Planning and Control Techniques for Self-Driving Urban Vehicles
Paden, B., Cap, M., Yong, S. Z., Yershov, D., & Frazzoli, E. (2016) · IEEE Transactions on Intelligent Vehicles · doi:10.1109/tiv.2016.2578706 · Cited by 2,585
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
Real-Time Motion Planning With Applications to Autonomous Urban Driving
Kuwata, Y., Karaman, S., Teo, J., Frazzoli, E., How, J. P., & Fiore, G. (2009) · IEEE Transactions on Control Systems Technology · doi:10.1109/tcst.2008.2012116 · Cited by 889
Planning-based prediction for pedestrians
Ziebart, B. D., Ratliff, N., Gallagher, G., Mertz, C., Peterson, K., Bagnell, J. A., Hebert, M., Dey, A. K., & Srinivasa, S. (2009) · 2009 IEEE/RSJ International Conference on Intelligent Robots and Systems · doi:10.1109/iros.2009.5354147 · Cited by 456
Metadata
- Authors
- Petti, S., & Fraichard, T.
- Venue
- 2005 IEEE/RSJ International Conference on Intelligent Robots and Systems
- Publisher
- IEEE
- Published
- 2005
- Pages
- 2210-2215
- OpenAlex
- W2000790002
- Cited by
- 264
- References
- 20
- FWCI
- 9.12
- Type
- conference paper
- Language
- en
- Open access
- green
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.