The DOI matches its Crossref record; 40 of the 40 references it cites were found in a registry or an index.
Fast marching tree: A fast marching sampling-based method for optimal motion planning in many dimensions
Open accessAbstract
In this paper we present a novel probabilistic sampling-based motion planning algorithm called the Fast Marching Tree algorithm (FMT*). The algorithm is specifically aimed at solving complex motion planning problems in high-dimensional configuration spaces. This algorithm is proven to be asymptotically optimal and is shown to converge to an optimal solution faster than its state-of-the-art counterparts, chiefly PRM* and RRT*. The FMT* algorithm performs a ‘lazy’ dynamic programming recursion on a predetermined number of probabilistically drawn samples to grow a tree of paths, which moves steadily outward in cost-to-arrive space. As such, this algorithm combines features of both single-query algorithms (chiefly RRT) and multiple-query algorithms (chiefly PRM), and is reminiscent of the Fast Marching Method for the solution of Eikonal equations. As a departure from previous analysis approaches that are based on the notion of almost sure convergence, the FMT* algorithm is analyzed under the notion of convergence in probability: the extra mathematical flexibility of this approach allows for convergence rate bounds—the first in the field of optimal sampling-based motion planning. Specifically, for a certain selection of tuning parameters and configuration spaces, we obtain a convergence rate bound of order O( n−1/ d+ ρ), where n is the number of sampled points, d is the dimension of the configuration space, and ρ is an arbitrarily small constant. We go on to demonstrate asymptotic optimality for a number of variations on FMT*, namely when the configuration space is sampled non-uniformly, when the cost is not arc length, and when connections are made based on the number of nearest neighbors instead of a fixed connection radius. Numerical experiments over a range of dimensions and obstacle configurations confirm our theoretical and heuristic arguments by showing that FMT*, for a given execution time, returns substantially better solutions than either PRM* or RRT*, especially in high-dimensional configuration spaces and in scenarios where collision-checking is expensive.
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
Adhi Harmoko, S., M.Komp, Jacquard, J. M., Zuse, K., & Eniac (2005) · Cited by 18,035
(1995) · Cited by 10,558
Thrun, S. (2002) · Communications of the ACM · doi:10.1145/504729.504754 · Cited by 7,994
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 2×
“This family of algorithms includes the probabilistic roadmap algorithm (PRM) [10] and its variants, e.”
MethodSampling-based algorithms for optimal motion planning
Karaman, S., & Frazzoli, E. (2011) · The International Journal of Robotics Research · doi:10.1177/0278364911406761 · Cited by 5,275
LaValle, S. M. (2006) · Cambridge University Press eBooks · doi:10.1017/cbo9780511546877 · Cited by 5,211
LaValle, S. M. (2006) · Cited by 4,177
Randomized Kinodynamic Planning
LaValle, S. M., & Kuffner, J. J. (2001) · The International Journal of Robotics Research · doi:10.1177/02783640122067453 · Cited by 3,254
A fast marching level set method for monotonically advancing fronts.
Sethian, J. A. (1996) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.93.4.1591 · Cited by 3,221
Penrose, M. (2003) · doi:10.1093/acprof:oso/9780198506263.001.0001 · Cited by 2,480
The Open Motion Planning Library
Sucan, I. A., Moll, M., & Kavraki, L. E. (2012) · IEEE Robotics & Automation Magazine · doi:10.1109/mra.2012.2205651 · Cited by 1,616
Bohlin, R., & Kavraki, L. E. (2000) · Proceedings 2000 ICRA. Millennium Conference. IEEE International Conference on Robotics and Automation. Symposia Proceedings (Cat. No.00CH37065) · doi:10.1109/robot.2000.844107 · Cited by 856
(2018) · Optimization Models · doi:10.1017/cbo9781107279667.013 · Cited by 818
Koenig, S., Likhachev, M. A., & Furcy, D. (2004) · Artificial Intelligence · doi:10.1016/j.artint.2003.12.001 · Cited by 662
Julia: A Fast Dynamic Language for Technical Computing
Anderson, T. A., Liu, H., Kuper, L., Totoni, E., Vitek, J., & Shpeisman, T. (2012) · arXiv (Cornell University) · doi:10.4230/lipics.ecoop.2017.4 · Cited by 627
Path planning in expansive configuration spaces
Hsu, D., Latombe, J.-C., & Motwani, R. (2002) · Proceedings of International Conference on Robotics and Automation · doi:10.1109/robot.1997.619371 · Cited by 552
Dynamic Programming and Optimal Control. Volume 1: Dynamic Programming and Optimal Control. Volume 2
Smith, D. K. (1996) · Journal of the Operational Research Society · doi:10.1057/jors.1996.103 · Cited by 448
Analysis of probabilistic roadmaps for path planning
Kavraki, L. E., Kolountzakis, M. N., & Latombe, J.-C. (2002) · Proceedings of IEEE International Conference on Robotics and Automation · doi:10.1109/robot.1996.509171 · Cited by 409
A Single-Query Bi-Directional Probabilistic Roadmap Planner with Lazy Collision Checking
Sánchez, G., & Latombe, J.-C. (2003) · Springer Tracts in Advanced Robotics · doi:10.1007/3-540-36460-9_27 · Cited by 313
A Random Sampling Scheme for Path Planning
Barraquand, J., Kavraki, L., Latombe, J.-C., Motwani, R., Li, T.-Y., & Raghavan, P. (1997) · The International Journal of Robotics Research · doi:10.1177/027836499701600604 · Cited by 277
PATH PLANNING IN EXPANSIVE CONFIGURATION SPACES
HSU, D., LATOMBE, J.-C., & MOTWANI, R. (1999) · International Journal of Computational Geometry & Applications · doi:10.1142/s0218195999000285 · Cited by 266
Dijkstra's algorithm revisited: the dynamic programming connexion
Sniedovich, M. (2006) · Minerva Access (University of Melbourne) · Cited by 264
On the Probabilistic Foundations of Probabilistic Roadmap Planning
Hsu, D., Latombe, J.-C., & Kurniawati, H. (2006) · The International Journal of Robotics Research · doi:10.1177/0278364906067174 · Cited by 260
Choosing good distance metrics and local planners for probabilistic roadmap methods
Amato, N. M., Bayazit, O. B., Dale, L. K., Jones, C., & Vallejo, D. (2002) · Proceedings. 1998 IEEE International Conference on Robotics and Automation (Cat. No.98CH36146) · doi:10.1109/robot.1998.677043 · Cited by 184
Use of relaxation methods in sampling-based algorithms for optimal motion planning
Arslan, O., & Tsiotras, P. (2013) · 2013 IEEE International Conference on Robotics and Automation · doi:10.1109/icra.2013.6630906 · Cited by 181
Sampling-based roadmap of trees for parallel motion planning
Plaku, E., Bekris, K. E., Chen, B. Y., Ladd, A. M., & Kavraki, L. E. (2005) · IEEE Transactions on Robotics · doi:10.1109/tro.2005.847599 · Cited by 172
A PRM-based motion planner for dynamically changing environments
Jaillet, L., & Simeon, T. (2005) · 2004 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) (IEEE Cat. No.04CH37566) · doi:10.1109/iros.2004.1389625 · Cited by 164
Sampling heuristics for optimal motion planning in high dimensions
Akgun, B., & Stilman, M. (2011) · 2011 IEEE/RSJ International Conference on Intelligent Robots and Systems · doi:10.1109/iros.2011.6095077 · Cited by 158
Kobilarov, M. (2012) · The International Journal of Robotics Research · doi:10.1177/0278364912444543 · Cited by 149
Measure theoretic analysis of probabilistic path planning
Ladd, A. M., & Kavraki, L. E. (2004) · IEEE Transactions on Robotics and Automation · doi:10.1109/tra.2004.824649 · Cited by 128
Rapidly-exploring roadmaps: Weighing exploration vs. refinement in optimal motion planning
Alterovitz, R., Patil, S., & Derbakova, A. (2011) · Proceedings - IEEE International Conference on Robotics and Automation/Proceedings · doi:10.1109/icra.2011.5980286 · Cited by 102
Guided Expansive Spaces Trees: a search strategy for motion- and cost-constrained state spaces
Phillips, J. M., Bedrossian, N. S., & Kavraki, L. E. (2004) · Proceedings - IEEE International Conference on Robotics and Automation/Proceedings · doi:10.1109/robot.2004.1308890 · Cited by 102
Fast set intersection in memory
Ding, B., & König, A. C. (2011) · Proceedings of the VLDB Endowment · doi:10.14778/1938545.1938550 · Cited by 97
Optimal sampling-based motion planning under differential constraints: The driftless case
Schmerling, E., Janson, L., & Pavone, M. (2015) · Proceedings - IEEE International Conference on Robotics and Automation/Proceedings · doi:10.1109/icra.2015.7139514 · Cited by 92
Self-citationAn asymptotically-optimal sampling-based algorithm for Bi-directional motion planning
Starek, J. A., Gomez, J. V., Schmerling, E., Janson, L., Moreno, L., & Pavone, M. (2015) · IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) · doi:10.1109/iros.2015.7353652 · Cited by 67
Self-citationArya, S., & Mount, D. M. (1995) · Annual Symposium on Computational Geometry (SoCG) · doi:10.1145/220279.220298 · Cited by 54
Asymptotically-optimal Motion Planning using lower bounds on cost
Salzman, O., & Halperin, D. (2015) · Proceedings - IEEE International Conference on Robotics and Automation/Proceedings · doi:10.1109/icra.2015.7139773 · Cited by 52
Gammell, J. D., Srinivasa, S. S., & Barfoot, T. D. (2014) · arXiv (Cornell University) · Cited by 41
Sampling heuristics for optimal motion planning in high dimensions
Akgün, B., & Stilman, M. (2011) · IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) · doi:10.1109/iros.2011.6048838 · Cited by 23
Fly Cheaply: On the Minimum Fuel Consumption Problem
Chan, T. M., & Efrat, A. (2001) · Journal of Algorithms · doi:10.1006/jagm.2001.1189 · Cited by 16
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
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
Geometrically Constrained Trajectory Optimization for Multicopters
Wang, Z., Zhou, X., Xu, C., & Gao, F. (2022) · IEEE Transactions on Robotics · doi:10.1109/tro.2022.3160022 · Cited by 434
Learning Sampling Distributions for Robot Motion Planning
Ichter, B., Harrison, J., & Pavone, M. (2018) · 2018 IEEE International Conference on Robotics and Automation (ICRA) · doi:10.1109/icra.2018.8460730 · Cited by 370
Self-citationCui, R., Li, Y., & Yan, W. (2016) · IEEE Transactions on Systems, Man, and Cybernetics: Systems · doi:10.1109/tsmc.2015.2500027 · Cited by 312
Metadata
- Authors
- Janson, L., Schmerling, E., Clark, A., & Pavone, M.
- Venue
- The International Journal of Robotics Research
- Publisher
- SAGE Publications
- Published
- 2015-05-18
- Volume
- 34
- Issue
- 7
- Pages
- 883-921
- ISSN
- 0278-3649 (ISSN-L)
- 1741-3176
- OpenAlex
- W1864112212
- Cited by
- 576
- References
- 40
- FWCI
- 30.33
- Type
- journal article
- 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.