Concurrent Nearest-Neighbor Searching for Parallel Sampling-Based Motion Planning in SO(3), SE(3), and Euclidean Spaces

1. Amato, N.M., Dale, L.K.: Probabilistic roadmap methods are embarrassingly parallel. In: Proceedings of IEEE International Conference Robotics and Automation, pp. 688–694 (1999)

   Google Scholar 

2. Andoni, A., Indyk, P.: Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions. In: 47th Annual IEEE Symposium on Foundations of Computer Science, 2006. FOCS 2006, pp. 459–468. IEEE (2006)

   Google Scholar 

3. Arya, S., Mount, D.M., Netanyahu, N.S., Silverman, R., Wu, A.Y.: An optimal algorithm for approximate nearest neighbor searching fixed dimensions. J. ACM 45(6), 891–923 (1998)

   Article  MathSciNet  Google Scholar 

4. Beis, J.S., Lowe, D.G.: Shape indexing using approximate nearest-neighbour search in high-dimensional spaces. In: 1997 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 1997. Proceedings, pp. 1000–1006. IEEE (1997)

   Google Scholar 

5. Bentley, J.L.: Multidimensional binary search trees used for associative searching. Commun. ACM 18(9), 509–517 (1975)

   Article  MathSciNet  Google Scholar 

6. Brin, S.: Near neighbor search in large metric spaces. In: Proceedings of 21st Conference on Very Large Databases (VLDB), Zurich, Switzerland, pp. 574–584 (1995)

   Google Scholar 

7. Choset, H., et al.: Principles of Robot Motion: Theory, Algorithms, and Implementations. MIT Press, Cambridge (2005)

   MATH  Google Scholar 

8. Şucan, I.A., Moll, M., Kavraki, L.E.: The open motion planning library. IEEE Robot. Autom. Mag. 19(4), 72–82 (2012). ompl.kavrakilab.org

   Article  Google Scholar 

9. Friedman, J.H., Bentley, J.L., Finkel, R.A.: An algorithm for finding best matches in logarithmic expected time. ACM Trans. Math. Softw. (TOMS) 3(3), 209–226 (1977)

   Article  Google Scholar 

10. Ichnowski, J., Alterovitz, R.: Scalable multicore motion planning using lock-free concurrency. IEEE Trans. Robot. 30(5), 1123–1136 (2014)

    Article  Google Scholar 

11. Ichnowski, J., Alterovitz, R.: Fast nearest neighbor search in SE(3) for sampling-based motion planning. In: Algorithmic Foundations of Robotics XI, pp. 197–214. Springer (2015)

    Google Scholar 

12. ISO/IEC: ISO international standard ISO/IEC 14882:2017(E)—programming languages—C++. Standard, International Organization for Standards (ISO), Geneva, Switzerland, December 2017

    Google Scholar 

13. Karaman, S., Frazzoli, E.: Sampling-based algorithms for optimal motion planning. Int. J. Robot. Res. 30(7), 846–894 (2011)

    Article  Google Scholar 

14. Kuipers, J.B., et al.: Quaternions and rotation sequences, vol. 66. Princeton University Press, Princeton (1999)

    MATH  Google Scholar 

15. Kung, H., Lehman, P.L.: Concurrent manipulation of binary search trees. ACM Trans. Database Syst. (TODS) 5(3), 354–382 (1980)

    Article  Google Scholar 

16. LaValle, S.M., Kuffner, J.J.: Rapidly-exploring random trees: Progress and prospects. In: Donald, B.R., et al. (eds.) Algorithmic and Computational Robotics: New Directions, pp. 293–308. AK Peters, Natick (2001)

    Google Scholar 

17. Sherlock, C., Golightly, A., Henderson, D.A.: Adaptive, delayed-acceptance MCMC for targets with expensive likelihoods. J. Comput. Graph. Stat. 26(2), 434–444 (2017)

    Article  MathSciNet  Google Scholar 

18. Silpa-Anan, C., Hartley, R.: Optimised kd-trees for fast image descriptor matching. In: IEEE Conference on Computer Vision and Pattern Recognition, 2008. CVPR 2008, pp. 1–8. IEEE (2008)

    Google Scholar 

19. Sproull, R.F.: Refinements to nearest-neighbor searching in k-dimensional trees. Algorithmica 6(1–6), 579–589 (1991)

    Article  MathSciNet  Google Scholar 

20. Yershova, A., LaValle, S.M.: Improving motion planning algorithms by efficient nearest-neighbor searching. IEEE Trans. Robot. 23(1), 151–157 (2007)

    Article  Google Scholar 

Download references