Abstract
The complexity of nearest-neighbor search dominates the asymptotic running time of many sampling-based motion-planning algorithms. However, collision detection is often considered to be the computational bottleneck in practice. Examining various asymptotically optimal planning algorithms, we characterize settings, which we call NN-sensitive, in which the practical computational role of nearest-neighbor search is far from being negligible, i.e., the portion of running time taken up by nearest-neighbor search is comparable to, or sometimes even greater than the portion of time taken up by collision detection. This reinforces and substantiates the claim that motion-planning algorithms could significantly benefit from efficient and possibly specially-tailored nearest-neighbor data structures. The asymptotic (near) optimality of these algorithms relies on a prescribed connection radius, defining a ball around a configuration q, such that q needs to be connected to all other configurations in that ball. To facilitate our study, we show how to adapt this radius to non-Euclidean spaces, which are prevalent in motion planning. This technical result is of independent interest, as it enables to compare the radial-connection approach with the common alternative, namely, connecting each configuration to its k nearest neighbors (K-NN). Indeed, as we demonstrate, there are scenarios where using the radial connection scheme, a solution path of a specific cost is produced ten-fold (and more) faster than with K-NN.
This work has been supported in part by the Israel Science Foundation (grant no. 825/15), by the Blavatnik Computer Science Research Fund, and by the Hermann Minkowski–Minerva Center for Geometry at Tel Aviv University. O. Salzman has been also supported by the National Science Foundation IIS (#1409003), Toyota Motor Engineering & Manufacturing (TEMA), and the Office of Naval Research. Part of this work was carried out while O. Salzman was a student at Tel Aviv University.
M. Kleinbort and O. Salzman contributed equally to this paper.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Arslan, O., Tsiotras, P.: Use of relaxation methods in sampling-based algorithms for optimal motion planning. In: ICRA. pp. 2413–2420 (2013)
Arya, S., Mount, D.M., Netanyahu, N.S., Silverman, R., Wu, A.Y.: An optimal algorithm for approximate nearest neighbor searching in fixed dimensions. Journal of the ACM 45(6), 891–923 (1998)
Bentley, J.L.: Multidimensional binary search trees used for associative searching. Commun. ACM 18, 509–517 (1975)
de Berg, M., Cheong, O., van Kreveld, M., Overmars, M.: Computational Geometry: Algorithms and Applications. Springer-Verlag, 3rd edn. (2008)
Bialkowski, J., Otte, M.W., Karaman, S., Frazzoli, E.: Efficient collision checking in sampling-based motion planning via safety certificates. I. J. Robotic Res. 35(7), 767–796 (2016)
Bohlin, R., Kavraki, L.E.: Path planning using lazy PRM. In: ICRA. pp. 521–528 (2000)
Brin, S.: Near neighbor search in large metric spaces. In: VLDB. pp. 574–584 (1995)
Chirikjian, G.S., Zhou, S.: Metrics on motion and deformation of solid models. J. Mech. Des. 120(2), 252–261 (1998)
Choset, H., Lynch, K.M., Hutchinson, S., Kantor, G., Burgard, W., Kavraki, L.E., Thrun, S.: Principles of Robot Motion: Theory, Algorithms, and Implementation. MIT Press (June 2005)
Cohen, J.D., Lin, M.C., Manocha, D., Ponamgi, M.: I-COLLIDE: an interactive and exact collision detection system for large-scale environments. In: Symposium on Interactive 3D Graphics. pp. 1891–96, 218 (1995)
Şucan, I.A., Moll, M., Kavraki, L.E.: The Open Motion Planning Library. IEEE Robotics & Automation Magazine 19(4), 72–82 (2012)
Friedman, J.H., Bentley, J.L., Finkel, R.A.: An algorithm for finding best matches in logarithmic expected time. ACM Trans. Math. Softw. 3(3), 209–226 (1977)
Gammell, J.D., Srinivasa, S.S., Barfoot, T.D.: Informed RRT*: Optimal samplingbased path planning focused via direct sampling of an admissible ellipsoidal heuristic. In: IROS. pp. 2997–3004 (2014)
Hauser, K.: Lazy collision checking in asymptotically-optimal motion planning. In: ICRA. pp. 2951–2957 (2015)
Hemmer, M., Kleinbort, M., Halperin, D.: Optimal randomized incremental construction for guaranteed logarithmic planar point location. Comput. Geom. 58,110–123 (2016)
Hubbard, P.M.: Approximating polyhedra with spheres for time-critical collision detection. ACM Trans. Graph. 15(3), 179–210 (1996)
Ichnowski, J., Alterovitz, R.: Fast nearest neighbor search in SE(3) for samplingbased motion planning. In: WAFR. pp. 197–214 (2014)
Indyk, P.: Nearest neighbors in high-dimensional spaces. In: Goodman, J.E., O’Rourke, J. (eds.) Handbook of Discrete and Computational Geometry, chap. 39, pp. 877–892. CRC Press LLC, Boca Raton, FL, 2nd edn. (2004)
Indyk, P., Motwani, R.: Approximate nearest neighbors: Towards removing the curse of dimensionality. In: STOC. pp. 604–613 (1998)
Janson, L., Schmerling, E., Clark, A.A., Pavone, M.: Fast marching tree: A fast marching sampling-based method for optimal motion planning in many dimensions. I. J. Robotic Res. 34(7), 883–921 (2015)
Karaman, S., Frazzoli, E.: Sampling-based algorithms for optimal motion planning. I. J. Robotic Res. 30(7), 846–894 (2011)
Kleinbort, M., Salzman, O., Halperin, D.: Efficient high-quality motion planning by fast all-pairs r-nearest-neighbors. In: ICRA. pp. 2985–2990 (2015)
Kleinbort, M., Salzman, O., Halperin, D.: Collision detection or nearest-neighbor search? On the computational bottleneck in sampling-based motion planning. CoRR abs/1607.04800 (2016)
Larsen, E., Gottschalk, S., Lin, M.C., Manocha, D.: Fast proximity queries with swept sphere volumes. Tech. rep., Department of Computer Science, University of North Carolina (1999), TR99-018
LaValle, S.M.: Planning Algorithms. Cambridge University Press (2006)
Lin, M.C., Manocha, D.: Collision and proximity queries. In: Goodman, J.E., O’Rourke, J. (eds.) Handbook of Discrete and Computational Geometry, chap. 35, pp. 767–786. CRC Press LLC, Boca Raton, FL, 2nd edn. (2004)
Marichal, J.L., Dorff, M.: Derivative relationships between volume and surface area of compact regions in \(\mathbb{R}^d\). Rocky Mountain J. Math. 37(2), 551–571 (2007)
Mazzola, G., Milmeister, G., Weissmann, J.: Comprehensive Mathematics for Computer Scientists 2, chap. 31, pp. 87–95. Springer, Berlin, Heidelberg (2005)
Pan, J., Chitta, S., Manocha, D.: FCL: A general purpose library for collision and proximity queries. In: ICRA. pp. 3859–3866 (2012)
Plaku, E., Kavraki, L.E.: Quantitative analysis of nearest-neighbors search in high-dimensional sampling-based motion planning. In: WAFR. pp. 3–18 (2006)
Salzman, O., Halperin, D.: Asymptotically-optimal motion planning using lower bounds on cost. In: ICRA. pp. 4167–4172 (2015)
Salzman, O., Halperin, D.: Asymptotically near-optimal RRT for fast, highquality, motion planning. IEEE Trans. Robotics 32(3), 473–483 (2016)
Solovey, K., Salzman, O., Halperin, D.: New perspective on sampling-based motion planning via random geometric graphs. Robots Science and Systems (RSS) (2016)
Yershova, A., LaValle, S.M.: Improving motion-planning algorithms by efficient nearest-neighbor searching. IEEE Trans. Robotics 23(1), 151–157 (2007)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this chapter
Cite this chapter
Kleinbort, M., Salzman, O., Halperin, D. (2020). Collision Detection or Nearest-Neighbor Search? On the Computational Bottleneck in Sampling-based Motion Planning. In: Goldberg, K., Abbeel, P., Bekris, K., Miller, L. (eds) Algorithmic Foundations of Robotics XII. Springer Proceedings in Advanced Robotics, vol 13. Springer, Cham. https://doi.org/10.1007/978-3-030-43089-4_40
Download citation
DOI: https://doi.org/10.1007/978-3-030-43089-4_40
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-43088-7
Online ISBN: 978-3-030-43089-4
eBook Packages: Intelligent Technologies and RoboticsIntelligent Technologies and Robotics (R0)