The DOI matches its Crossref record; 49 of the 49 references it cites were found in a registry or an index.
On the Probabilistic Foundations of Probabilistic Roadmap Planning
Open accessAbstract
Why is probabilistic roadmap (PRM) planning probabilistic? How does the probability measure used for sampling a robot’s configuration space affect the performance of a PRM planner? These questions have received little attention to date. This paper tries to fill this gap and identify promising directions to improve future planners. It introduces the probabilistic foundations of PRM planning and examines previous work in this context. It shows that the success of PRM planning depends mainly and critically on favorable “visibility” properties of a robot’s configuration space. A promising direction for speeding up PRM planners is to infer partial knowledge of such properties from both workspace geometry and information gathered during roadmap construction, and to use this knowledge to adapt the probability measure for sampling. This paper also shows that the choice of the sampling source—pseudo-random or deterministic—has small impact on a PRM planner’s performance, compared with that of the sampling measure. These conclusions are supported by both theoretical and empirical results.
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
The Art of Computer Programming
Knuth, D. E. (1968) · Cited by 16,337
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 3×
“To illustrate, Figure 6 compares the average running times of three versions of BasicPRM with distinct sampling strategies: the uniform strategy (whose sampling measure π is uniform over C), the Gaussian strategy of [4], and the two-phase connectivity expansion strategy of [27].”
BackgroundMethodSelf-citationThe Art of Computer Programming. Volume 2: Seminumerical Algorithms.
Taussky, O., & Knuth, D. E. (1970) · The American Mathematical Monthly · doi:10.2307/2317055 · Cited by 3,822
Proceedings. 1985 IEEE International Conference on Robotics and Automation
(1985) · doi:10.1109/robot.1985 · Cited by 3,673
Random Number Generation and Quasi-Monte Carlo Methods.
Collings, B. J., & Niederreiter, H. (1993) · Journal of the American Statistical Association · doi:10.2307/2290359 · Cited by 2,884
Random Number Generation and Quasi-Monte Carlo Methods
Niederreiter, H. (1992) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9781611970081 · Cited by 2,770
Introduction to Protein Structure
Branden, C. I., & Tooze, J. (2012) · Garland Science eBooks · doi:10.1201/9781136969898 · Cited by 2,382
Principles of Robot Motion: Theory, Algorithms, and Implementations
Choset, H., & Latombe, J. (2005) · Medical Entomology and Zoology · Cited by 2,149
Self-citationAn Introduction to Computational Learning Theory
Kearns, M. J., & Vazirani, U. (1994) · doi:10.7551/mitpress/3897.001.0001 · Cited by 1,697
Handbook of discrete and computational geometry
(1998) · Choice Reviews Online · doi:10.5860/choice.35-5707b · Cited by 1,456
Handbook of Discrete and Computational Geometry, Second Edition
(2004) · Chapman & Hall/CRC eBooks · doi:10.1201/9781420035315 · Cited by 1,208
Introduction to Protein Structure
BANASZAK, L. J. (2000) · Foundations of Structural Biology · doi:10.1016/b978-012077700-6/50001-8 · Cited by 1,052
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
Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time
Spielman, D. A., & Teng, S.-H. (2004) · Journal of the ACM · doi:10.1145/990308.990310 · Cited by 825
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
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
Self-citationThe Gaussian sampling strategy for probabilistic roadmap planners
Boor, V., Overmars, M. H., & van der Stappen, A. F. (2003) · Proceedings 1999 IEEE International Conference on Robotics and Automation (Cat. No.99CH36288C) · doi:10.1109/robot.1999.772447 · Cited by 541
On the Relationship between Classical Grid Search and Probabilistic Roadmaps
LaValle, S. M., Branicky, M. S., & Lindemann, S. R. (2004) · The International Journal of Robotics Research · doi:10.1177/0278364904045481 · Cited by 436
OBPRM: an obstacle-based PRM for 3D workspaces
Amato, N. M., Bayazıt, O. B., Dale, L. K., Jones, C. A., & Vallejo, D. (1998) · Cited by 414
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
Self-citationThe bridge test for sampling narrow passages with probabilistic roadmap planners
Hsu, D., Jiang, T., Reif, J., & Sun, Z. (2004) · 2003 IEEE International Conference on Robotics and Automation (Cat. No.03CH37422) · doi:10.1109/robot.2003.1242285 · Cited by 355
Self-citationOn the Relationship between Classical Grid Search and Probabilistic Roadmaps
LaValle, S. M., & Branicky, M. S. (2004) · Springer Tracts in Advanced Robotics · doi:10.1007/978-3-540-45058-0_5 · Cited by 338
Visibility-based probabilistic roadmaps for motion planning
Siméon, T., Laumond, J.-P., & Nissoux, C. (2000) · Advanced Robotics · doi:10.1163/156855300741960 · Cited by 329
On Finding Narrow Passages with Probabilistic Roadmap Planners
(1998) · Robotics: The Algorithmic Perspective · doi:10.1201/9781439863886-18 · Cited by 307
Useful metrics for modular robot motion planning
Pamecha, A., Ebert-Uphoff, I., & Chirikjian, G. S. (1997) · IEEE Transactions on Robotics and Automation · doi:10.1109/70.611311 · Cited by 249
On Delaying Collision Checking in PRM Planning: Application to Multi-Robot Coordination
Sánchez, G., & Latombe, J.-C. (2002) · The International Journal of Robotics Research · doi:10.1177/027836402320556458 · Cited by 248
Self-citationA Comparative Study of Probabilistic Roadmap Planners
Geraerts, R., & Overmars, M. H. (2004) · Springer Tracts in Advanced Robotics · doi:10.1007/978-3-540-45058-0_4 · Cited by 240
Collision and Proximity Queries
Lin, M. C., Manocha, D., & Kim, Y. J. (2017) · doi:10.1201/9781315119601-39 · Cited by 216
Nearest Neighbors in High-Dimensional Spaces
Indyk, P. (2004) · Discrete Mathematics and Its Applications · doi:10.1201/9781420035315.ch39 · Cited by 207
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
Hybrid PRM Sampling with a Cost-Sensitive Adaptive Strategy
Hsu, D., Sanchez‐Ante, G., & Sun, Z. (2006) · Proceedings - IEEE International Conference on Robotics and Automation/Proceedings · doi:10.1109/robot.2005.1570712 · Cited by 110
Self-citationToward Optimal Configuration Space Sampling
Burns, B., & Brock, O. (2005) · Robotics: Science and Systems · doi:10.15607/rss.2005.i.015 · Cited by 106
Randomized query processing in robot path planning
Kavraki, L. E., Latombe, J., Motwani, R., & Raghavan, P. (1995) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/225058.225159 · Cited by 104
Self-citationA Voronoi-based hybrid motion planner
Foskey, M. S., Garber, M., Lin, M. C., & Manocha, D. (2002) · IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) · doi:10.1109/iros.2001.973336 · Cited by 104
A Machine Learning Approach for Feature-Sensitive Motion Planning
Morales, M., Tapia, L., Pearce, R., Rodríguez, S., & Amato, N. M. (2005) · Springer tracts in advanced robotics · doi:10.1007/10991541_25 · Cited by 99
Guibas, L. J., Holleman, C., & Kavraki, L. E. (2003) · IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) · doi:10.1109/iros.1999.813013 · Cited by 96
Using Workspace Information as a Guide to Non-uniform Sampling in Probabilistic Roadmap Planners
van den Berg, J., & Overmars, M. H. (2005) · The International Journal of Robotics Research · doi:10.1177/0278364905060132 · Cited by 93
Interactive motion planning using hardware-accelerated computation of generalized Voronoi diagrams
Hoff, K., Culver, T., Keyser, J., Lin, M. C., & Manocha, D. (2002) · Proceedings - IEEE International Conference on Robotics and Automation/Proceedings · doi:10.1109/robot.2000.846473 · Cited by 93
Sampling-Based Motion Planning Using Predictive Models
Burns, B., & Brock, O. (2006) · Proceedings - IEEE International Conference on Robotics and Automation/Proceedings · doi:10.1109/robot.2005.1570590 · Cited by 91
Efficient nearest neighbor searching for motion planning
Atramentov, A., & LaValle, S. M. (2003) · Proceedings - IEEE International Conference on Robotics and Automation/Proceedings · doi:10.1109/robot.2002.1013429 · Cited by 88
Workspace importance sampling for probabilistic roadmap planning
Kurniawati, H., & Hsu, D. (2005) · IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) · doi:10.1109/iros.2004.1389627 · Cited by 82
Self-citationFinding Narrow Passages with Probabilistic Roadmaps: The Small-Step Retraction Method
Saha, M., Latombe, J., Chang, Y.-C., & Prinz, F. (2005) · Autonomous Robots · doi:10.1007/s10514-005-4748-1 · Cited by 68
Self-citationAdapting the sampling distribution in PRM planners based on an approximated medial axis
Yang, Y., & Brock, O. (2004) · Proceedings - IEEE International Conference on Robotics and Automation/Proceedings · doi:10.1109/robot.2004.1302411 · Cited by 67
Probabilistic Roadmaps of Trees for Parallel Computation of Multiple Query Roadmaps
Akinc, M., Bekris, K. E., Chen, B. Y., Ladd, A. M., Plaku, E., & Kavraki, L. E. (2005) · Springer tracts in advanced robotics · doi:10.1007/11008941_9 · Cited by 64
Incremental low-discrepancy lattice methods for motion planning
Lindemann, S. R., & LaValle, S. M. (2004) · Proceedings - IEEE International Conference on Robotics and Automation/Proceedings · doi:10.1109/robot.2003.1242039 · Cited by 61
Finding narrow passages with probabilistic roadmaps: the small step retraction method
Saha, M., & Latombe, J.-C. (2005) · IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) · doi:10.1109/iros.2005.1545606 · Cited by 55
Self-citationAlgorithmic Foundations of Robotics VI
Erdmann, M. A., van der Stappen, A. F., Overmars, M. H., & Hsu, D. (2005) · Springer tracts in advanced robotics · doi:10.1007/b96007 · Cited by 31
Self-citationOn probabilistic completeness and expected complexity for probabilistic path planning
Svestka, P. (1996) · Utrecht University Repository (Utrecht University) · Cited by 22
Cited by
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
Sampling-Based Robot Motion Planning: A Review
Elbanhawi, M., & Simic, M. (2014) · IEEE Access · doi:10.1109/access.2014.2302442 · Cited by 786
Heuristic approaches in robot path planning: A survey
Mac, T. T., Copot, C., Tran, D. T., & De Keyser, R. (2016) · Robotics and Autonomous Systems · doi:10.1016/j.robot.2016.08.001 · Cited by 641
Janson, L., Schmerling, E., Clark, A., & Pavone, M. (2015) · The International Journal of Robotics Research · doi:10.1177/0278364915577958 · Cited by 576
Path Planning for the Mobile Robot: A Review
Zhang, H.-Y., Lin, W.-M., & Chen, A.-X. (2018) · Symmetry · doi:10.3390/sym10100450 · Cited by 447
Metadata
- Authors
- Hsu, D., Latombe, J.-C., & Kurniawati, H.
- Venue
- The International Journal of Robotics Research
- Publisher
- SAGE Publications
- Published
- 2006-07
- Volume
- 25
- Issue
- 7
- Pages
- 627-643
- ISSN
- 0278-3649 (ISSN-L)
- 1741-3176
- OpenAlex
- W1971355878
- Cited by
- 260
- References
- 49
- FWCI
- 17.25
- 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.