The DOI matches its Crossref record; 40 of the 40 references it cites were found in a registry or an index.
A Random Sampling Scheme for Path Planning
Abstract
Several randomized path planners have been proposed dur ing the last few years. Their attractiveness stems from their applicability to virtually any type of robots, and their empir ically observed success. In this article, we attempt to present a unifying view of these planners and to theoretically explain their success. First, we introduce a general planning scheme that consists of randomly sampling the robot 's configuration space. We then describe two previously developed planners as instances of planners based on this scheme, but applying very different sampling strategies. These planners are probabilis tically complete: if a path exists, they will find one with high probability, if we let them run long enough. Next, for one of the planners, we analyze the relation between the probability of failure and the running time. Under assumptions characteriz ing the "goodness" of the robot's free space, we show that the
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
Self-citationProbabilistic 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×
“Another planner, presented in [18, 20, 21, 24], precomputes a “roadmap” (network) of simple paths connecting randomly selected configurations and tries to construct a path between any two input configurations by connecting them to this roadmap; we will refer”
BackgroundResultSelf-citationMotwani, R., & Raghavan, P. (1995) · Cambridge University Press eBooks · doi:10.1017/cbo9780511814075 · Cited by 5,123
Self-citationComputational Geometry--An Introduction.
Atallah, M. J., Preparata, F. P., & Shamos, M. I. (1986) · Mathematics of Computation · doi:10.2307/2008200 · Cited by 4,238
Preparata, F. P., & Shamos, M. I. (1985) · Springer eBooks · doi:10.1007/978-1-4612-1098-6 · Cited by 3,655
Proceedings of the 56th Annual ACM Symposium on Theory of Computing
(2024) · doi:10.1145/3618260 · Cited by 1,730
A fast procedure for computing the distance between complex objects in three-dimensional space
Gilbert, E. G., Johnson, D. W., & Keerthi, S. S. (1988) · IEEE Journal on Robotics and Automation · doi:10.1109/56.2083 · Cited by 1,513
The complexity of robot motion planning
Canny, J. (1988) · Medical Entomology and Zoology · Cited by 1,375
Proceedings 1992 IEEE International Conference on Robotics and Automation
(1992) · doi:10.1109/robot.1992 · Cited by 1,084
Robot Motion Planning: A Distributed Representation Approach
Barraquand, J., & Latombe, J.-C. (1991) · The International Journal of Robotics Research · doi:10.1177/027836499101000604 · Cited by 995
Self-citationNumerical potential field techniques for robot path planning
Barraquand, J., Langlois, B., & Latombe, J.-C. (1992) · IEEE Transactions on Systems, Man, and Cybernetics · doi:10.1109/21.148426 · Cited by 889
Self-citationSchwartz, J. T., & Sharir, M. (1983) · Advances in Applied Mathematics · doi:10.1016/0196-8858(83)90014-3 · Cited by 801
Complexity of the mover's problem and generalizations
Reif, J. H. (1979) · 20th Annual Symposium on Foundations of Computer Science (sfcs 1979) · doi:10.1109/sfcs.1979.10 · Cited by 765
Proceedings of the 30th IEEE symposium on Foundations of computer science
Galil, Z., & Blum, E. K. (1994) · Cited by 677
Optimally combining sampling techniques for Monte Carlo rendering
Veach, E., & Guibas, L. J. (1995) · Proceedings of the 22nd annual conference on Computer graphics and interactive techniques - SIGGRAPH '95 · doi:10.1145/218380.218498 · Cited by 616
Hopcroft, J. E., Schwartz, J. T., & Sharir, M. (1984) · The International Journal of Robotics Research · doi:10.1177/027836498400300405 · Cited by 528
A fast algorithm for incremental distance calculation
Lin, M. C., & Canny, J. (2002) · Proceedings - IEEE International Conference on Robotics and Automation/Proceedings · doi:10.1109/robot.1991.131723 · Cited by 475
Randomized preprocessing of configuration for fast path planning
Kavraki, L., & Latombe, J.-C. (2002) · Proceedings of the 1994 IEEE International Conference on Robotics and Automation · doi:10.1109/robot.1994.350966 · Cited by 412
Self-citationAnalysis 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-citationEfficient distance computation between non-convex objects
Quinlan, S. (2002) · Proceedings of the 1994 IEEE International Conference on Robotics and Automation · doi:10.1109/robot.1994.351059 · Cited by 391
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
Planning motions with intentions
Koga, Y., Kondo, K., Kuffner, J., & Latombe, J.-C. (1994) · Proceedings of the 21st annual conference on Computer graphics and interactive techniques - SIGGRAPH '94 · doi:10.1145/192161.192266 · Cited by 269
Self-citationA probabilistic learning approach to motion planning
Overmars, M. H., & Švestka, P. (1995) · Cited by 170
[Proceedings 1988] 29th Annual Symposium on Foundations of Computer Science
(1988) · doi:10.1109/sfcs.1988 · Cited by 167
Assembly maintainability study with motion planning
Chang, H. T., & Li, T. (2002) · Proceedings - IEEE International Conference on Robotics and Automation/Proceedings · doi:10.1109/robot.1995.525415 · Cited by 130
Self-citationOn multi-arm manipulation planning
Koga, Y., & Latombe, J.-C. (2002) · Proceedings - IEEE International Conference on Robotics and Automation/Proceedings · doi:10.1109/robot.1994.351231 · Cited by 129
Self-citationRANDOM NETWORKS IN CONFIGURATION SPACE FOR FAST PATH PLANNING
Kavraki, L. E. (1994) · doi:10.12681/eadd/4455 · Cited by 110
Self-citationA random approach to motion planning
Overmars, M. H. (1992) · Cited by 94
Incremental algorithms for collision detection between solid models
Ponamgi, M. K., Manocha, D., & Lin, M. C. (1995) · ACM Symposium on Solid Modeling and Applications · doi:10.1145/218013.218076 · Cited by 86
Randomized Query Processing in Robot Path Planning
Kavraki, L. E., Latombe, J., Motwani, R., & Raghavan, P. (1998) · Journal of Computer and System Sciences · doi:10.1006/jcss.1998.1578 · Cited by 75
Self-citationDecoupling of a Two-Axis Robotic Manipulator Using Nonlinear State Feedback: A Case Study
Fournier, S. J., & Schilling, R. J. (1984) · The International Journal of Robotics Research · doi:10.1177/027836498400300304 · Cited by 72
Motion planning with many degrees of freedom-random reflections at C-space obstacles
Horsch, T., Schwarz, F., & Tolle, H. (2002) · Proceedings - IEEE International Conference on Robotics and Automation/Proceedings · doi:10.1109/robot.1994.351060 · Cited by 66
Arya, S., & Mount, D. M. (1995) · Annual Symposium on Computational Geometry (SoCG) · doi:10.1145/220279.220298 · Cited by 54
Randomized preprocessing of configuration space for path planning: articulated robots
Kavraki, L. E., & Latombe, J.-C. (2002) · IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) · doi:10.1109/iros.1994.407619 · Cited by 51
Self-citationOn the expected complexity of random path planning
Lamiraux, F., & Laumond, J. (2002) · Proceedings - IEEE International Conference on Robotics and Automation/Proceedings · doi:10.1109/robot.1996.509170 · Cited by 48
A parallel formulation of informed randomized search for robot motion planning problems
Challou, D., Boley, D. L., Gini, M. L., & Kumar, V. (2002) · Proceedings - IEEE International Conference on Robotics and Automation/Proceedings · doi:10.1109/robot.1995.525367 · Cited by 44
A probabilistic approach to motion planning for car-like robots
Švestka, P. (1993) · Cited by 26
Ahuactzin, J.-M. (1994) · HAL · Cited by 19
Integration of a Path Generation Algorithm into Off-line Programming of AIRBUS Panels
Graux, L., Millies, P., Kociemba, P. L., & Langlois, B. (1992) · SAE technical papers on CD-ROM/SAE technical paper series · doi:10.4271/922404 · Cited by 12
Controllability, recognizability, and complexity issues in robot motion planning
Latombe, J.-C. (2002) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1995.492579 · Cited by 9
Self-citation
Cited by
Sampling-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
RRT-connect: An efficient approach to single-query path planning
Kuffner, J. J., & LaValle, S. M. (2000) · Proceedings 2000 ICRA. Millennium Conference. IEEE International Conference on Robotics and Automation. Symposia Proceedings (Cat. No.00CH37065) · doi:10.1109/robot.2000.844730 · Cited by 3,555
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
Self-citationSampling-Based Robot Motion Planning: A Review
Elbanhawi, M., & Simic, M. (2014) · IEEE Access · doi:10.1109/access.2014.2302442 · Cited by 786
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
Self-citation
Metadata
- Authors
- Barraquand, J., Kavraki, L., Latombe, J.-C., Motwani, R., Li, T.-Y., & Raghavan, P.
- Venue
- The International Journal of Robotics Research
- Publisher
- SAGE Publications
- Published
- 1997-12
- Volume
- 16
- Issue
- 6
- Pages
- 759-774
- ISSN
- 0278-3649 (ISSN-L)
- 1741-3176
- OpenAlex
- W2134741043
- Cited by
- 277
- References
- 40
- FWCI
- 7.77
- 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.