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.
Get full access to this article
View all access options for this article.
References
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 .
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 .
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.
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 .
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 .
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 .
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 Journal36(5): 504–514 .
12.
Conway, J. H., and Sloane, N. J. A. 1999. Sphere Packings, Lattices, and Groups. Springer-Verlag, Berlin .
13.
Donald, B. R. 1987. A search algorithm for motion planning with six degrees of freedom . Artificial Intelligence31: 295–353 .
14.
Donald, B. R., Xavier, P. G., Canny, J., and Reif, J. 1993. Kinodynamic planning . Journal of the ACM40: 1048–1066 .
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 .
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 .
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 .
20.
Halton, J. H. 1960. On the efficiency of certain quasi-random sequences of points in evaluating multi-dimensional integrals . Numerical Mathematics2: 84–90 .
21.
Hammersley, J. M. 1960. Monte Carlo methods for solving multivariable problems . Annals of the New York Academy of Science86: 844–874 .
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.
23.
Hickernell, F. J., Hong, H. S., L’Ecuyer, P., and Lemieux, C. 2000. Extensible lattice sequences for quasi-Monte Carlo quadrature . SIAM Journal on Scientific Computing22: 1117–1138 .
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 .
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 Applications4: 495–512 .
27.
Hwang, Y. K., and Ahuja, N. 1992. A potential field approach to path planning . IEEE Transactions on Robotics and Automation8(1): 23–32 .
28.
Kambhampati, S., and Davis, L. S. 1986. Multiresolution path planning for mobile robots . IEEE Journal of Robotics and Automation2(3): 135–145 .
29.
Kavraki, L. E., Švestka, P., Latombe, J.-C., and Overmars, M. H. 1996. Probabilistic roadmaps for path planning in high-dimensional configuration spaces . IEEE Transactions on Robotics and Automation12(4): 566–580 .
30.
Kondo, K. 1991. Motion planning with six degrees of freedom by multistrategic bidirectional heuristic free-space enumeration . IEEE Transactions on Robotics and Automation7(3): 267–277 .
31.
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 .
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.
34.
Lengyel, J., Reichert, M., Donald, B. R., and Greenberg, D. P. 1990. Real-time robot motion planning using rasterizing computer graphics hardware . Computer Graphics24(4): 327–335 .
35.
Leven, P., and Hutchinson, S. 2000. Real-timemotion planning in changing environments . Proceedings of the International Symposium on Robotics Research, San Francisco, CA.
36.
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 .
37.
Lozano-Pérez, T. 1983. Spatial planning: a configuration space approach . IEEE Transactions on Computing C32(2): 108–120 .
38.
Matousek, J. 1999. Geometric Discrepancy Springer-Verlag, Berlin .
39.
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.
40.
Mazer, E., Ahuactzin, J. M., and Bessière, P. 1998. The Ariadne’s clew algorithm . Journal of Artificial Intelligence Research9: 295–316 .
41.
Niederreiter, H. 1992. Random Number Generation and Quasi-Monte Carlo Methods. Society for Industrial and Applied Mathematics, Philadelphia, PA .
42.
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.
43.
O’Dunlaing, C., and Yap, C. K. 1982. A retraction method for planning the motion of a disc . Journal of Algorithms6: 104–111 .
44.
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.
45.
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.
46.
Schwartz, J. T., and Sharir, M. 1983. On the piano movers’ problem: II. General techniques for computing topological properties of algebraic manifolds . Communications on Pure and Applied Mathematics36: 345–398 .
47.
Siméon, T., Laumond, J.-P., and Nissoux, C. 2000. Visibility based probabilistic roadmaps for motion planning . Advanced Robotics14(6): 477–493 .
48.
Sloan, I. H., and Joe, S. 1990. Lattice Methods for Multiple tegration. Oxford Science Publications, Englewood Cliffs, NJ .
49.
Sukharev, A. G. 1971. Optimal strategies of the search for an extremum . USSR Computational Mathematics and Mathematical Physics11(4) (translated from Russian, Zh. Vychisl. Mat. i Mat. Fiz.11(4):910–924).
50.
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.
51.
van der Corput, J. G. 1935. Verteilungsfunktionen I. Akad. Wetensch. 38:813–821.
52.
Wang, X., and Hickernell, F. J. 2000. Randomized Halton sequences . Mathematical and Computer Modelling32: 887–899 .
53.
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.
54.
Weyl, H. 1916. Über die Gleichverteilung von Zahlen mod Eins. Math. Ann. 77:313–352.
55.
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 .
