The DOI matches its Crossref record; 39 of the 39 references it cites were found in a registry or an index.
Path Planning for Autonomous Vehicles in Unknown Semi-structured Environments
Abstract
We describe a practical path-planning algorithm for an autonomous vehicle operating in an unknown semi-structured (or unstructured) environment, where obstacles are detected online by the robot’s sensors. This work was motivated by and experimentally validated in the 2007 DARPA Urban Challenge, where robotic vehicles had to autonomously navigate parking lots. The core of our approach to path planning consists of two phases. The first phase uses a variant of A* search (applied to the 3D kinematic state space of the vehicle) to obtain a kinematically feasible trajectory. The second phase then improves the quality of the solution via numeric non-linear optimization, leading to a local (and frequently global) optimum. Further, we extend our algorithm to use prior topological knowledge of the environment to guide path planning, leading to faster search and final trajectories better suited to the structure of the environment. We present experimental results from the DARPA Urban Challenge, where our robot demonstrated near-flawless performance in complex general path-planning tasks such as navigating parking lots and executing U-turns on blocked roads. We also present results on autonomous navigation of real parking lots. In those latter tasks, which are significantly more complex than the ones in the DARPA Urban Challenge, the time of a full replanning cycle of our planner is in the range of 50—300 ms.
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
A Formal Basis for the Heuristic Determination of Minimum Cost Paths
Hart, P., Nilsson, N., & Raphael, B. (1968) · IEEE Transactions on Systems Science and Cybernetics · doi:10.1109/tssc.1968.300136 · Cited by 12,738
Real-Time Obstacle Avoidance for Manipulators and Mobile Robots
Khatib, O. (1986) · The International Journal of Robotics Research · doi:10.1177/027836498600500106 · Cited by 7,894 · cited 2×
“Potential fields (see, e.g., Andrews and Hogan (1983(@), Pavlov and Voronin (1984), Miyazaki and Arimoto (1985), and Khatib (1986)) are another common tool in motion planning.”
BackgroundMethodProbabilistic 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×
“An alternative approach that guarantees kinematic feasibility of the path is a forward search in continuous coordinates, e.g., using rapidly exploring random trees (Kavraki et al. 1996 LaValle 1998 Plaku et al. 2007).”
LaValle, S. M. (2006) · Cambridge University Press eBooks · doi:10.1017/cbo9780511546877 · Cited by 5,211
LaValle, S. M. (2006) · Cited by 4,177
Rapidly-exploring random trees : a new tool for path planning
LaValle, S. M. (1998) · Cited by 3,704
Proceedings. 1985 IEEE International Conference on Robotics and Automation
(1985) · doi:10.1109/robot.1985 · Cited by 3,673
Proceedings of the International Joint Conference on Artificial Intelligence 2007
Bundy, A. (2007) · International Joint Conference on Artificial Intelligence · Cited by 2,761
Principles of Robot Motion: Theory, Algorithms, and Implementations
Choset, H., & Latombe, J. (2005) · Medical Entomology and Zoology · Cited by 2,149
Exact robot navigation using artificial potential functions
Rimon, E., & Koditschek, D. E. (1992) · IEEE Transactions on Robotics and Automation · doi:10.1109/70.163777 · Cited by 1,835
Sequential Operations in Digital Picture Processing
Rosenfeld, A., & Pfaltz, J. L. (1966) · Journal of the ACM · doi:10.1145/321356.321357 · Cited by 1,675
Potential field methods and their inherent limitations for mobile robot navigation
Koren, Y., & Borenstein, J. (2002) · Proceedings. 1991 IEEE International Conference on Robotics and Automation · doi:10.1109/robot.1991.131810 · Cited by 1,570
Autonomous driving in urban environments: Boss and the Urban Challenge
Urmson, C., Anhalt, J., Bagnell, D., Baker, C., Bittner, R., Clark, M. N., Dolan, J., Duggins, D., Galatali, T., Geyer, C., et al. (2008) · Journal of Field Robotics · doi:10.1002/rob.20255 · Cited by 1,555
Optimal paths for a car that goes both forwards and backwards
Reeds, J., & Shepp, L. (1990) · Pacific Journal of Mathematics · doi:10.2140/pjm.1990.145.367 · Cited by 1,447
Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI 2017)
Amendola, G., Ricca, F., & Truszczyński, M. (2017) · International Joint Conference on Artificial Intelligence · Cited by 1,179
The focussed D* algorithm for real-time replanning
Stentz, A. (1995) · Cited by 865
Robot Motion Planning and Control
(1998) · Lecture Notes in Control and Information Sciences · doi:10.1007/bfb0036069 · Cited by 831
Path planning using Laplace's equation
Connolly, C. I., Burns, J. B., & Weiss, R. (2002) · Proceedings., IEEE International Conference on Robotics and Automation · doi:10.1109/robot.1990.126315 · Cited by 483
Theta*: any-angle path planning on grids
Nash, A., Daniel, K., Koenig, S., & Feiner, A. (2007) · National Conference on Artificial Intelligence · Cited by 381
Exact robot navigation by means of potential functions: Some topological considerations
Koditschek, D. (2005) · Proceedings. 1987 IEEE International Conference on Robotics and Automation · doi:10.1109/robot.1987.1088038 · Cited by 345
Guidelines in nonholonomic motion planning for mobile robots
Laumond, J. P., Sekhavat, S., & Lamiraux, F. (2006) · Lecture Notes in Control and Information Sciences · doi:10.1007/bfb0036070 · Cited by 330
2011 IEEE International Conference on Robotics and Automation (ICRA 2011)
(2010) · IEEE Transactions on Robotics · doi:10.1109/tro.2010.2062334 · Cited by 302
Improved 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
Sensor-Based Exploration: The Hierarchical Generalized Voronoi Graph
Choset, H., & Burdick, J. (2000) · The International Journal of Robotics Research · doi:10.1177/02783640022066770 · Cited by 288
Field D*: An Interpolation-Based Path Planner and Replanner
Ferguson, D., & Stentz, A. (2007) · Springer Tracts in Advanced Robotics · doi:10.1007/978-3-540-48113-3_22 · Cited by 250
Team AnnieWAY's autonomous system for the 2007 DARPA Urban Challenge
Kammel, S., Ziegler, J., Pitzer, B., Werling, M., Gindele, T., Jagzent, D., Schröder, J., Thuy, M., Goebl, M., Hundelshausen, F. V., et al. (2008) · Journal of Field Robotics · doi:10.1002/rob.20252 · Cited by 226
The 2005 DARPA Grand Challenge – The Great Robot Race
(2008) · Industrial Robot: An International Journal · doi:10.1108/ir.2008.04935fae.001 · Cited by 198
Smooth motion planning for car-like vehicles
Lamiraux, F., & Lammond, J.-P. (2001) · IEEE Transactions on Robotics and Automation · doi:10.1109/70.954762 · Cited by 186
Greedy but Safe Replanning under Kinodynamic Constraints
Bekris, K. E., & Kavraki, L. E. (2007) · Proceedings - IEEE International Conference on Robotics and Automation/Proceedings · doi:10.1109/robot.2007.363069 · Cited by 134
IEEE International Conference on Robotics and Automation
泰義, 横. (1992) · Journal of the Robotics Society of Japan · doi:10.7210/jrsj.10.552 · Cited by 133
2015 IEEE International Conference on Intelligent Robots and Systems (IROS)
Apostolopoulos, S., Leibold, M., & Buss, M. (2015) · mediaTUM – the media and publications repository of the Technical University Munich (Technical University Munich) · Cited by 129
Alice: An information‐rich autonomous vehicle for high‐speed desert navigation
Cremean, L. B., Foote, T. B., Gillula, J., Hines, G. H., Kogan, D., Kriechbaum, K. L., Lamb, J. C., Leibs, J., Lindzey, L., Rasmussen, C. E., et al. (2006) · Journal of Field Robotics · doi:10.1002/rob.20135 · Cited by 122
Team Cornell's Skynet: Robust perception and planning in an urban environment
Miller, I., Campbell, M., Huttenlocher, D. P., Kline, F., Nathan, A., Lupashin, S., Catlin, J., Schimpf, B., Moran, P., Zych, N. C., et al. (2008) · Journal of Field Robotics · doi:10.1002/rob.20253 · Cited by 116
Discrete Search Leading Continuous Exploration for Kinodynamic Motion Planning
Plaku, E., Kavraki, L. E., & Vardi, M. Y. (2007) · Robotics: Science and Systems · doi:10.15607/rss.2007.iii.040 · Cited by 84
Path planning and navigation of mobile robots in unknown environments
Ersson, T., & Xiaoming Hu, A. (2002) · IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) · doi:10.1109/iros.2001.976276 · Cited by 75
Autonomous driving in semi-structured environments: Mapping and planning
Dolgov, D., & Thrun, S. (2009) · Proceedings - IEEE International Conference on Robotics and Automation/Proceedings · doi:10.1109/robot.2009.5152682 · Cited by 70
Self-citationSelf-supervised aerial image analysis for extracting parking lot structure
Seo, Y., Ratliff, N., & Urmson, C. (2009) · Cited by 12
Cited by
A Survey of Autonomous Driving: Common Practices and Emerging Technologies
Yurtsever, E., Lambert, J., Carballo, A., & Takeda, K. (2020) · IEEE Access · doi:10.1109/access.2020.2983149 · Cited by 1,889
“A* trajectories were optimized with numeric non-linear functions in [258].”
MethodA Review of Motion Planning Techniques for Automated Vehicles
Gonzalez, D., Perez, J., Milanes, V., & Nashashibi, F. (2016) · IEEE Transactions on Intelligent Transportation Systems · doi:10.1109/tits.2015.2498841 · Cited by 1,670
Badue, C., Guidolini, R., Carneiro, R. V., Azevedo, P., Cardoso, V. B., Forechi, A., Jesus, L., Berriel, R., Paixão, T. M., Mutz, F., et al. (2021) · Expert Systems with Applications · doi:10.1016/j.eswa.2020.113816 · Cited by 1,209
Katrakazas, C., Quddus, M., Chen, W.-H., & Deka, L. (2015) · Transportation Research Part C: Emerging Technologies · doi:10.1016/j.trc.2015.09.011 · Cited by 800
Robust and Efficient Quadrotor Trajectory Generation for Fast Autonomous Flight
Zhou, B., Gao, F., Wang, L., Liu, C., & Shen, S. (2019) · IEEE Robotics and Automation Letters · doi:10.1109/lra.2019.2927938 · Cited by 747
Metadata
- Authors
- Dolgov, D., Thrun, S., Montemerlo, M., & Diebel, J.
- Venue
- The International Journal of Robotics Research
- Publisher
- SAGE Publications
- Published
- 2010-01-25
- Volume
- 29
- Issue
- 5
- Pages
- 485-501
- ISSN
- 0278-3649 (ISSN-L)
- 1741-3176
- OpenAlex
- W1996183429
- Cited by
- 976
- References
- 39
- FWCI
- 15.48
- Type
- journal article
- Language
- en
- Open access
- closed
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.