Student or educator? Sign up with your school email and get 6 months of Pro free.
CoChat
Sign Up
Cited by 436

The DOI matches its Crossref record; 1 of the 1 references it cites were found in a registry or an index.

On the Relationship between Classical Grid Search and Probabilistic Roadmaps

LaValle, Steven M., Branicky, Michael S., Lindemann, Stephen R.·2004·The International Journal of Robotics Research
DOI 10.1177/0278364904045481
Open this paper in CoChat — free account

Abstract

We present, implement, and analyze a spectrum of closely-related planners, designed to gain insight into the relationship between classical grid search and probabilistic roadmaps (PRMs). Building on the quasi-Monte Carlo sampling literature, we have developed deterministic variants of the PRM that use low-discrepancy and low-dispersion samples, including lattices. Classical grid search is extended using subsampling for collision detection and also the dispersion-optimal Sukharev grid, which can be considered as a kind of lattice-based roadmap to complete the spectrum. Our experimental results show that the deterministic variants of the PRM offer performance advantages in comparison to the original, multiple-query PRM and the single-query, lazy PRM. Surprisingly, even some forms of grid search yield performance that is comparable to the original PRM. Our theoretical analysis shows that all of our deterministic PRM variants are resolution complete and achieve the best possible asymptotic convergence rate, which is shown to be superior to that obtained by random sampling. Thus, in surprising contrast to recent trends, there is both experimental and theoretical evidence that the randomization used in the original PRM is not advantageous.

Overview

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

Crossref · 10.1177/0278364904045481

Cites

1 of 1 references verified0 citation errors · 0 not checkable

Statistics

Verification

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

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

Show all 1 references

Research works printed but not linked: 53

  1. Amato, N. M., and Wu, Y. 1996. A randomized roadmap method for path and manipulation planning . Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), Minneapolis, MN, pp. 113–120 . · DOI · Paper page
  2. Amato, N. M., Bayazit, O.B., Dale, L.K., Jones, C., and Vallejo, D. 1998. OBPRM: an obstacle-based PRM for 3D workspaces . Proceedings of the 3rd International Workshop on the Algorithmic Foundations of Robotics (WAFR), Houston, TX, March 5–7, pp. 155–168 .
  3. Barraquand, J., and Latombe, J.C. 1990. A Monte Carlo algorithm for path planning with many degrees of freedom . Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), Cincinnati, OH, pp. 1712–1717 .
  4. Barraquand, J., Kavraki, L., Latombe, J.C., Li, T.Y., Motwani, R., and Raghavan, P. 1995. A random sampling scheme for robot path planning . Proceedings of the 7th International Symposium on Robotics Research, Munich, Germany, pp. 249–264 . · DOI
  5. Bohlin, R. 2001. Path planning in practice; lazy evaluation on a multiresolution grid . Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), Maui, Hawaii, October.
  6. Bohlin, R., and Kavraki, L. 2000. Path planning using lazy PRM . Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), San Francisco, CA, April 24–28. · DOI · Paper page
  7. Bohlin, R., and Kavraki, L. 2001. A randomized algorithm for robot path planning based on lazy evalaution. Handbook on Randomized Computation, S. Rajasekaran, P. Pardalos, J. Reif, and J. Rolim, editors. Kluwer Academic, Dordrecht . · DOI
  8. Boor, V., Overmars, N. H., and van der Stappen, A.F. 1999. The Gaussian sampling strategy for probabilistic roadmap planners . Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), Detroit, MI, pp. 1018–1023 . · DOI · Paper page
  9. Branicky, M. S., LaValle, S. M., Olson, K., and Yang, L. 2001. Quasi-randomized path planning . Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), Seoul, Korea, May 21–26, pp. 1481–1487 . · DOI · Paper page
  10. Canny, J. F. 1988. The Complexity of Robot Motion Planning. MIT Press, Cambridge, MA .
  11. Canny, J. 1995. Computing roadmaps of general semialgebraic sets . Computer Journal 36(5): 504–514 . · doi:10.1093/comjnl/36.5.504
  12. Conway, J. H., and Sloane, N. J. A. 1999. Sphere Packings, Lattices, and Groups. Springer-Verlag, Berlin . · DOI · Paper page
  13. 10.1016/0004-3702(87)90069-5 · DOI
  14. 10.1145/174147.174150 · DOI · Paper page
  15. Erdmann, M. A. 1989. On Probabilistic Strategies for Robot Tasks . PhD thesis, Massachusetts Institute of Technology, Cambridge, MA.
  16. Faverjon, B. 1984. Obstacle avoidance using an octree in the configuration space of a manipulator . Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), Atlanta, GA, pp. 504–512 . · DOI · Paper page
  17. Faverjon, B., and Tournassoud, P. 1987. A local based method for path planning of manipulators with a high number of degrees of freedom . Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), Raleigh, NC, pp. 1152–1159 . · DOI · Paper page
  18. Geraerts, R., and Overmars, M. H. 2002. A comparative study of probabilistic roadmap planners . Proceedings of the 5th InternationalWorkshop on the Algorithmic Foundations of Robotics (WAFR), Nice, France, December 15–17.
  19. Glavina, B. 1990. Solving findpath by combination of goaldirected and randomized search . Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), Cincinnati, OH, pp. 1718–1723 . · doi:10.1109/robot.1990.126257
  20. 10.1007/BF01386213 · DOI · Paper page
  21. Hammersley, J. M. 1960. Monte Carlo methods for solving multivariable problems . Annals of the New York Academy of Science 86: 844–874 . · DOI · Paper page
  22. Hickernell, F. J. 1998. Lattice rules: how well do they measure up? Random and Quasi-Random Point Sets, P. Bickel, editor. Springer-Verlag, Berlin , pp. 109–166. · DOI · Paper page
  23. 10.1137/S1064827599356638 · DOI
  24. Holleman, C., and Kavraki, L. E. 2000. A framework for using the workspace medial axis in PRM planners . Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), San Francisco, CA, April 24–28, pp. 1408–1413 . · DOI
  25. Hsu, D., Kavraki, L. E., Latombe, J.C., Motwani, R., and Sorkin, S. 1998. On finding narrow passages with probabilistic roadmap planners. Robotics: The Algorithmic Perspective, P. Agarwal, editor. A. K. Peters, Wellesley, MA , pp. 141–154.
  26. Hsu, D., Latombe, J.C., and Motwani, R. 1999. Path planning in expansive configuration spaces . International Journal of Computational Geometry and Applications 4: 495–512 . · DOI · Paper page
  27. 10.1109/70.127236 · DOI
  28. 10.1109/JRA.1986.1087051 · DOI · Paper page
  29. 10.1109/70.88136 · DOI
  30. Lamiraux, F., and Laumond, J.P. 1996. On the expected complexity of random path planning . Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), Minneapolis, MN, pp. 3306–3311 .
  31. Latombe, J.C. 1991. Robot Motion Planning. Kluwer Academic, Boston, MA . · DOI · Paper page
  32. LaValle, S. M., and Kuffner, J. J. 2001. Rapidly-exploring random trees: progress and prospects. Algorithmic and Computational Robotics: New Directions, B. R. Donald, K. M. Lynch, and D. Rus, editors. A. K. Peters, Wellesley, MA , pp. 293–308.
  33. 10.1145/97880.97915 · doi:10.1145/97880.97915
  34. Leven, P., and Hutchinson, S. 2000. Real-timemotion planning in changing environments . Proceedings of the International Symposium on Robotics Research, San Francisco, CA.
  35. Lindemann, S. R., and LaValle, S. M. 2003. Incremental lowdiscrepancy lattice methods for motion planning . Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), Taipei, Taiwan, pp. 2920–2927 . · DOI
  36. Lozano-Pérez, T. 1983. Spatial planning: a configuration space approach . IEEE Transactions on Computing C 32(2): 108–120 . · DOI · Paper page
  37. Matousek, J. 1999. Geometric Discrepancy Springer-Verlag, Berlin . · doi:10.1007/978-3-642-03942-3
  38. Mazer, E., Talbi, G., Ahuactzin, J. M., and Bessière, P. 1992. The Ariadne’s clew algorithm . Proceedings of the International Conference of Society of Adaptive Behavior, Honolulu, Hawaii.
  39. 10.1613/jair.468 · DOI
  40. Niederreiter, H. 1992. Random Number Generation and Quasi-Monte Carlo Methods. Society for Industrial and Applied Mathematics, Philadelphia, PA . · DOI · Paper page
  41. Niederreiter, H., and Xing, C. P. 1998. Nets, (t,s)-sequences, and algebraic geometry. Random and Quasi-Random Point Sets, Lecture Notes in Statistics, Vol. 138, P. Hellekalek and G. Larcher, editors. Springer-Verlag, Berlin , pp. 267–302. · DOI
  42. O’Dunlaing, C., and Yap, C. K. 1982. A retraction method for planning the motion of a disc . Journal of Algorithms 6: 104–111 . · DOI · Paper page
  43. Pisula, C., Hoff, K., Lin, M., and Manoch, D. 2000. Randomized path planning for a rigid body based on hardware acceleratedVoronoi sampling . Proceedings of the International Workshop on the Algorithmic Foundations of Robotics (WAFR), Hanover, NH, March 16–18.
  44. Sánchez, G., and Latombe, J.C. 2001. A single-query bidirectional probabilistic roadmap planner with lazy collision checking . Proceedings of the International Symposium on Robotics Research, Snowbird, UT.
  45. 10.1002/cpa.3160360305 · DOI · Paper page
  46. 10.1163/156855300741960 · DOI · Paper page
  47. Sloan, I. H., and Joe, S. 1990. Lattice Methods for Multiple tegration. Oxford Science Publications, Englewood Cliffs, NJ .
  48. Sukharev, A. G. 1971. Optimal strategies of the search for an extremum . USSR Computational Mathematics and Mathematical Physics 11(4) (translated from Russian, Zh. Vychisl. Mat. i Mat. Fiz.11(4):910–924). · DOI
  49. Tezuka, S. 2002. Quasi-Monte Carlo: the discrepancy between theory and practice. Monte Carlo and Quasi-Monte Carlo Methods 2000. Fang, F. J. Hickernell, and H. Niederreiter, editors. Springer-Verlag, Berlin , pp. 124–140. · doi:10.1007/978-3-642-56046-0_8
  50. 10.1016/S0895-7177(00)00178-3 · DOI · Paper page
  51. Wang, X., and Hickernell, F. J. 2002. An historical overview of lattice point sets. Monte Carlo and Quasi-Monte Carlo Methods 2000. Fang, F. J. Hickernell, and H. Niederreiter, editors. Springer-Verlag, Berlin , pp. 158–167. · doi:10.1007/978-3-642-56046-0_10
  52. Weyl, H. 1916. Über die Gleichverteilung von Zahlen mod Eins. Math. Ann. 77:313–352. · DOI · Paper page
  53. Wilmarth, S. A., Amato, N. M., and Stiller, P. F. 1999. MAPRM: a probabilistic roadmap planner with sampling on the medial axis of the free space . Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), Detroit, MI, pp. 1024–1031 . · DOI · Paper page

Cited by

See all 436

Metadata

Authors
LaValle, S. M., Branicky, M. S., & Lindemann, S. R.
Venue
The International Journal of Robotics Research
Publisher
SAGE Publications
Published
2004-08
Volume
23
Issue
7-8
Pages
673-692
ISSN
  • 0278-3649 (ISSN-L)
  • 1741-3176
DOI
10.1177/0278364904045481
OpenAlex
W4246226690
Cited by
436
References
1
FWCI
13.93
Type
journal article
Language
en
Open access
closed
Licence
journals.sagepub.com/page/policies/text-and-data-mining-license (tdm)

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

How to cite

Cite CoChat for the checks on this page, and the paper for its own findings.

This page
CoChat. (2026). Citation check: On the Relationship between Classical Grid Search and Probabilistic Roadmaps. https://app.cochat.ai/papers/10.1177/0278364904045481
The paper
LaValle, S. M., Branicky, M. S., & Lindemann, S. R. (2004). On the Relationship between Classical Grid Search and Probabilistic Roadmaps. The International Journal of Robotics Research. https://doi.org/10.1177/0278364904045481

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.