Hostname: page-component-586b7cd67f-g8jcs Total loading time: 0 Render date: 2024-11-22T08:35:02.408Z Has data issue: false hasContentIssue false
  • English
  • Français

Speeding up probabilistic roadmap planners with locality-sensitive hashing

Published online by Cambridge University Press:  09 April 2014

Mika T. Rantanen  and
Martti Juhola
Mika T. Rantanen*
Affiliation:
Computer Science, School of Information Sciences, Kalevantie 4, FI-33014, University of Tampere, Tampere, Finland
Martti Juhola
Affiliation:
Computer Science, School of Information Sciences, Kalevantie 4, FI-33014, University of Tampere, Tampere, Finland
*
*Corresponding author. E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Summary

A crucial part of probabilistic roadmap planners is the nearest neighbor search, which is typically done by exact methods. Unfortunately, searching the neighbors can become a major bottleneck for the performance. This can occur when the roadmap size grows especially in high-dimensional spaces. In this paper, we investigate how well the approximate nearest neighbor searching works with probabilistic roadmap planners. We propose a method that is based on the locality-sensitive hashing and show that it can speed up the construction of the roadmap considerably without reducing the quality of the produced roadmap.

Keywords

Motion planningProbabilistic roadmapsLocality-sensitive hashingObstacle avoidancePath planning
Type
Articles
Information
Robotica , Volume 33 , Issue 7 , August 2015 , pp. 1491 - 1506
Copyright
Copyright © Cambridge University Press 2014 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

1. Latombe, J.-C., Robot Motion Planning (Kluwer, Boston, MA, 1991).Google Scholar
2. Choset, H., Lynch, K. M., Hutchinson, S., Kantor, G., Burgard, W., Kavraki, L. E. and Thrun, S., Principles of Robot Motion: Theory, Algorithms, and Implementations (MIT Press, Cambridge, MA, 2005).Google Scholar
3. LaValle, S. M., Planning Algorithms (Cambridge University Press, Cambridge, UK, 2006).Google Scholar
4. Dadkhah, N. and Mettler, B., “Survey of motion planning literature in the presence of uncertainty: Considerations for UAV guidance,” J. Intell. Robot. Syst. 65, 233–246 (2012).Google Scholar
5. Smed, J. and Hakonen, H., “Path Finding,” In: Algorithms and Networking for Computer Games (John Wiley, 2006) pp. 97–113.Google Scholar
6. Al-Bluwi, I., Siméon, T. and Cortés, J., “Motion planning algorithms for molecular simulations: A survey,” Comput. Sci. Rev. 6 (4), 125–143 (2012).Google Scholar
7. Lozano-Pérez, T., “Spatial planning: A configuration space approach,” IEEE Trans. Comput. C-32 (2), 108–120 (1983).Google Scholar
8. Reif, J. H., “Complexity of the Mover's Problem and Generalizations,” Proceedings of the IEEE Symposium on Foundations of Computer Science, San Juan, Puerto Rico (Oct. 29–31, 1979) pp. 421–427.Google Scholar
9. Canny, J. F., The Complexity of Robot Motion Planning (MIT Press, Cambridge, MA, 1988).Google Scholar
10. Overmars, M. H., “A Random Approach to Motion Planning,” Technical Report RUU-CS-92-93, Department of Computer Science, Utrecht University, the Netherlands (1992).Google Scholar
11. Kavraki, L. and Latombe, J.-C., “Randomized Preprocessing of Configuration Space for Fast Path Planning,” Proceedings of the IEEE International Conference on Robotics and Automation, San Diego, CA (May 8–13, 1994) pp. 2138–2145.Google Scholar
12. Kavraki, L. E., Švestka, P., Latombe, J.-C. and Overmars, M. H., “Probabilistic roadmaps for path planning in high-dimensional configuration spaces,” IEEE Trans. Robot. Autom. 12 (4), 566–580 (1996).Google Scholar
13. Jaillet, L. and Siméon, T., “A PRM-Based Motion Planner for Dynamically Changing Environments,” Proceedings of IEEE/RSJ International Conference on Intelligent Robots and Systems, Sendai, Japan (Sept. 28–Oct. 2, 2004) pp. 1606–1611.Google Scholar
14. Sud, A., Gayle, R., Andersen, E., Guy, S., Lin, M. and Manocha, D., “Real-Time Navigation of Independent Agents Using Adaptive Roadmaps,” Proceedings of the ACM Symposium on Virtual Reality Software and Technology, Newport Beach, CA (Nov. 5–7, 2007) pp. 99–106.Google Scholar
15. Arya, S., Mount, D. M., Netanyahu, N. S., Silverman, R. and Wu, A. Y., “An optimal algorithm for approximate nearest neighbor searching in fixed dimensions,” J. ACM 45 (6), 891–923 (1998).Google Scholar
16. Muja, M. and Lowe, D. G., “Fast Approximate Nearest Neighbors with Automatic Algorithm Configuration,” Proceedings of the International Conference on Computer Vision Theory and Application, Lisboa, Portugal, (Feb. 5–8, 2009) pp. 331–340.Google Scholar
17. Indyk, P. and Motwani, R., “Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality,” Proceedings of ACM Symposium on Theory of Computing, Dallas, Texas, USA (May 23–26, 1998) pp. 604–613.Google Scholar
18. Gionis, A., Indyk, P. and Motwani, R., “Similarity Search in High Dimensions via Hashing,” Proceedings of International Conference on Very Large Data Bases, Edinburgh, Scotland (Sep. 7–10, 1999) pp. 518–529.Google Scholar
19. Andoni, A. and Indyk, P., “Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions,” Commun. ACM 51 (1), 117–122 (2008).Google Scholar
20. Kocis, L. and Whiten, W. J., “Computational investigations of low-discrepancy sequences,” ACM Trans. Math. Softw. 23 (2), 266–294 (1997).Google Scholar
21. Amato, N. M., Bayazit, O. B., Dale, L. K., Jones, C. and Vallejo, D., “OBPRM: An Obstacle-Based PRM for 3D Workspaces,” Proceedings of Workshop on Algorithmic Foundations of Robotics, Houston, Texas (Mar. 5–7, 1998) pp. 155–168.Google Scholar
22. Boor, V., Overmars, M. H. and van der Stappen, A. F., “The Gaussian Sampling Strategy for Probabilistic Roadmap Planners,” Proceedings of IEEE International Conference on Robotics & Automation, Detroit, MI (May 10–15, 1999) pp. 1018–1023.Google Scholar
23. Hsu, D., Jiang, T., Reif, J. and Sun, Z., “The Bridge Test for Sampling Narrow Passages with Probabilistic Roadmap Planners,” Proceedings of IEEE International Conference on Robotics & Automation, Taipei, Taiwan (Sep. 14–19, 2003) pp. 4420–4426.Google Scholar
24. Wilmarth, S. A., Amato, N. M. and Stiller, P. F., “MAPRM: A Probabilistic Roadmap Planner with Sampling on the Medial Axis of the Free Space,” Proceedings of IEEE International Conference on Robotics & Automation, Detroit, MI (May 10–15, 1999) pp. 1024–1031.Google Scholar
25. Holleman, C. and Kavraki, L. E., “A Framework for Using the Workspace Medial Axis in PRM Planners,” Proceedings of IEEE International Conference on Robotics & Automation, San Francisco, CA (Apr. 24–28, 2000) pp. 1408–1413.Google Scholar
26. Morales, M., Tapia, L., Pearce, R., Rodriguez, S. and Amato, N. M., “A Machine Learning Approach for Feature-Sensitive Motion Planning,” In: Algorithmic Foundations of Robotics VI (Erdmann, M., Overmars, M., Hsu, D. and van der Stappen, F., eds.) (Springer, Berlin, 2005), pp. 361–376.Google Scholar
27. Rodriguez, S., Thomas, S., Pearce, R. and Amato, N. M., “RESAMPL: A Region-Sensitive Adaptive Motion Planner,” In: Algorithmic Foundation of Robotics VII (Akella, S., Amato, N. M., Huang, W. H. and Mishra, B., eds.) (Springer, Berlin, 2008) pp. 285–300.Google Scholar
28. Rantanen, M. T., “A connectivity-based method for enhancing sampling in probabilistic roadmap planners,” J. Intell. Robot. Syst. 64 (2), 161–178 (2011).Google Scholar
29. Amato, N. M., Bayazit, O. B., Dale, L. K., Jones, C. and Vallejo, D., “Choosing good distance metrics and local planners for probabilistic roadmap methods,” IEEE Trans. Robot. Autom. 16 (4), 442–447 (2000).Google Scholar
30. Geraerts, R. and Overmars, M. H., “Reachability-based analysis for probabilistic roadmap planners,” Robot. Auton. Syst. 55 (11), 824–836 (2007).Google Scholar
31. Kuffner, J. J., “Effective Sampling and Distance Metrics for 3D Rigid Body Path Planning,” Proceedings of IEEE International Conference on Robotics & Automation, New Orleans, LA (Apr. 26–May 1, 2004) pp. 3993–3998.Google Scholar
32. Weber, R., Schek, H.-J. and Blott, S., “A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces,” Proceedings of International Conference on Very Large Databases, New York City, New York, USA (Aug. 24–27, 1998) pp. 194–205.Google Scholar
33. Bentley, J. L., “Multidimensional binary search trees used for associative searching,” Commun. ACM 18 (9), 509–517 (1975).Google Scholar
34. de Berg, M., van Kreveld, M., Overmars, M. and Schwarzkopf, O., Computational Geometry: Algorithms and Applications, 2nd ed. (Springer-Verlag, Berlin, Germany, 2000).Google Scholar
35. Yershova, A. and LaValle, S. M., “Improving motion-planning algorithms by efficient nearest-neighbor searching,” IEEE Trans. Robot. 23 (1), 151–157 (2007).Google Scholar
36. Ryynänen, M. and Klapuri, A., “Query by Humming of MIDI and Audio Using Locality Sensitive Hashing,” Proceedings of IEEE International Conference on Acoustics, Speech, and Signal Processing, Las Vegas, NV (Mar. 31–Apr. 4, 2008) pp. 2249–2252.Google Scholar
37. Buaba, R., Homaifar, A., Gebril, M. and Kihn, E., “Satellite Image Retrieval Application Using Locality Sensitive Hashing in L 2-Space,” Proceedings of IEEE Aerospace Conference, Big Sky, MT, USA (Mar. 5–12, 2011) pp. 1–7.Google Scholar
38. Datar, M., Immorlica, N., Indyk, P. and Mirrokni, V. S., “Locality-Sensitive Hashing Scheme Based on p-Stable Distributions,” Proceedings of Symposium on Computational Geometry, Brooklyn, New York, USA (Jun. 8–11, 2004) pp. 253–262.Google Scholar
39. Paulevé, L., Jégou, H. and Amsaleg, L., “Locality sensitive hashing: A comparison of hash function types and querying mechanisms,” Pattern Recognit. Lett. 31 (11), 1348–1358 (2010).Google Scholar
40. Aurenhammer, F., “Voronoi diagrams–a survey of a fundamental geometric data structure,” ACM Comput. Surv. 23 (3), 345–405 (1991).Google Scholar
41. Larsen, E., Gottschalk, S., Lin, M. C. and Manocha, D., “Fast Proximity Queries with Swept Sphere Volumes,” Technical Report TR99-018, Department of Computer Science, University of North Carolina, Wilmington, NC (1999).Google Scholar