Document Open Access Logo

Sampling-Based Bottleneck Pathfinding with Applications to Fréchet Matching

Authors Kiril Solovey, Dan Halperin

PDF
Thumbnail PDF

File

LIPIcs.ESA.2016.76.pdf
  • Filesize: 0.63 MB
  • 16 pages

Document Identifiers

Author Details

Kiril Solovey
Dan Halperin

Cite As Get BibTex

Kiril Solovey and Dan Halperin. Sampling-Based Bottleneck Pathfinding with Applications to Fréchet Matching. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 76:1-76:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.ESA.2016.76

Abstract

We describe a general probabilistic framework to address a variety of Fréchet-distance optimization problems. Specifically, we are interested in finding minimal bottleneck-paths in d-dimensional Euclidean space between given start and goal points, namely paths that minimize the maximal value over a continuous cost map. We present an efficient and simple sampling-based framework for this problem, which is inspired by, and draws ideas from, techniques for robot motion planning. We extend the framework to handle not only standard bottleneck pathfinding, but also the more demanding case, where the path needs to be monotone in all dimensions. Finally, we provide experimental results of the framework on several types of problems.

Subject Classification

Keywords
  • Computational geometry
  • Fréchet distances
  • sampling-based algorithms
  • random geometric graphs
  • bottleneck pathfinding

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Aviv Adler, Mark de Berg, Dan Halperin, and Kiril Solovey. Efficient multi-robot motion planning for unlabeled discs in simple polygons. IEEE Trans. Automation Science and Engineering, 12(4):1309-1317, 2015. Google Scholar
  2. Helmut Alt and Michael Godau. Computing the Fréchet distance between two polygonal curves. Int. J. Comput. Geometry Appl., 5:75-91, 1995. Google Scholar
  3. Oktay Arslan and Panagiotis Tsiotras. Use of relaxation methods in sampling-based algorithms for optimal motion planning. In Robotics and Automation (ICRA), 2013 IEEE International Conference on, pages 2421-2428. IEEE, 2013. Google Scholar
  4. Francis Avnaim, Jean-Daniel Boissonnat, and Bernard Faverjon. A practical exact motion planning algorithm for polygonal objects amidst polygonal obstacles. In Robotics and Automation, 1988. Proceedings., 1988 IEEE International Conference on, pages 1656-1661. IEEE, 1988. Google Scholar
  5. Paul Balister, Amites Sarkar, and Béla Bollobás. Percolation, connectivity, coverage and colouring of random geometric graphs. In Béla Bollobás, Robert Kozma, and Dezso Miklós, editors, Handbook of Large-Scale Random Networks, pages 117-142. Springer Berlin Heidelberg, Berlin, Heidelberg, 2008. Google Scholar
  6. Karl Bringmann. Why walking the dog takes time: Fréchet distance has no strongly subquadratic algorithms unless SETH fails. In Foundations of Computer Science, pages 661-670, 2014. Google Scholar
  7. Karl Bringmann and Wolfgang Mulzer. Approximability of the discrete Fréchet distance. Journal of Computational Geometry, 7(2):46-76, 2016. Google Scholar
  8. Nicolas Broutin, Luc Devroye, Nicolas Fraiman, and Gábor Lugosi. Connectivity threshold of bluetooth graphs. Random Struct. Algorithms, 44(1):45-66, 2014. Google Scholar
  9. Kevin Buchin, Maike Buchin, Maximilian Konzack, Wolfgang Mulzer, and André Schulz. Fine-grained analysis of problems on curves. In EuroCG, Lugano, Switzerland, 2016. Google Scholar
  10. Kevin Buchin, Maike Buchin, Wouter Meulemans, and Wolfgang Mulzer. Four soviets walk the dog - with an application to Alt’s conjecture. In ACM-SIAM Symposium on Discrete Algorithms, pages 1399-1413, 2014. Google Scholar
  11. Kevin Buchin, Maike Buchin, and André Schulz. Fréchet distance of surfaces: Some simple hard cases. In European Symposium of Algorithms, pages 63-74, 2010. Google Scholar
  12. Kevin Buchin, Maike Buchin, Rolf van Leusden, Wouter Meulemans, and Wolfgang Mulzer. Computing the Fréchet distance with a retractable leash. In European Symposium of Algorithms, pages 241-252, 2013. Google Scholar
  13. Kevin Buchin, Maike Buchin, and Carola Wenk. Computing the Fréchet distance between simple polygons. Comput. Geom., 41(1-2):2-20, 2008. Google Scholar
  14. Erin W. Chambers, Éric Colin de Verdière, Jeff Erickson, Sylvain Lazard, Francis Lazarus, and Shripad Thite. Homotopic Fréchet distance between curves or, walking your dog in the woods in polynomial time. Comput. Geom., 43(3):295-311, 2010. Google Scholar
  15. Shiri Chechik, Haim Kaplan, Mikkel Thorup, Or Zamir, and Uri Zwick. Bottleneck paths and trees and deterministic graphical games. In Symposium on Theoretical Aspects of Computer Science, pages 27:1-27:13, 2016. Google Scholar
  16. Atlas F. Cook and Carola Wenk. Geodesic Fréchet distance inside a simple polygon. ACM Transactions on Algorithms, 7(1):9, 2010. Google Scholar
  17. Mark de Berg and Marc J. van Kreveld. Trekking in the alps without freezing or getting tired. Algorithmica, 18(3):306-323, 1997. Google Scholar
  18. Adrian Dumitrescu and Günter Rote. On the Fréchet distance of a set of curves. In Canadian Conference on Computational Geometry, pages 162-165, 2004. Google Scholar
  19. Chenglin Fan, Omrit Filtser, Matthew J. Katz, Tim Wylie, and Binhai Zhu. On the chain pair simplification problem. In Symposium on Algorithms and Data Structures, pages 351-362, 2015. Google Scholar
  20. GAMMA group. http://gamma.cs.unc.edu/SSV/, 1999. University of North Carolina at Chapel Hill, USA.
  21. Dan Halperin and Micha Sharir. A near-quadratic algorithm for planning the motion of a polygon in a polygonal environment. Discrete &Computational Geometry, 16(2):121-134, 1996. Google Scholar
  22. Sariel Har-Peled and Benjamin Raichel. The Fréchet distance revisited and extended. ACM Transactions on Algorithms, 10(1):3, 2014. Google Scholar
  23. John E. Hopcroft, Jacob T. Schwartz, and Micha Sharir. On the complexity of motion planning for multiple independent objects; PSPACE-hardness of the "Warehouseman’s problem". International Journal of Robotics Research, 3(4):76-88, 1984. Google Scholar
  24. David Hsu, Jean-Claude Latombe, and Rajeev Motwani. Path planning in expansive configuration spaces. Int. J. Comput. Geometry Appl., 9(4/5):495-512, 1999. Google Scholar
  25. Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which problems have strongly exponential complexity? J. Comput. Syst. Sci., 63(4):512-530, 2001. Google Scholar
  26. Lucas Janson, Edward Schmerling, Ashley A. Clark, and Marco Pavone. 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. Google Scholar
  27. Minghui Jiang, Ying Xu, and Binhai Zhu. Protein structure-structure alignment with discrete Fréchet distance. Journal of bioinformatics and computational biology, 6(01):51-64, 2008. Google Scholar
  28. Sertac Karaman and Emilio Frazzoli. Sampling-based algorithms for optimal motion planning. International Journal of Robotics Research, 30(7):846-894, 2011. Google Scholar
  29. Lydia E. Kavraki, Petr Švestka, Jean-Claude Latombe, and Mark H. Overmars. Probabilistic roadmaps for path planning in high dimensional configuration spaces. IEEE Transactions on Robotics and Automation, 12(4):566-580, 1996. Google Scholar
  30. Lutz Kettner, Kurt Mehlhorn, Sylvain Pion, Stefan Schirra, and Chee-Keng Yap. Classroom examples of robustness problems in geometric computations. Comput. Geom., 40(1):61-78, 2008. Google Scholar
  31. Michal Kleinbort, Oren Salzman, and Dan Halperin. Efficient high-quality motion planning by fast all-pairs r-nearest-neighbors. In IEEE International Conference on Robotics and Automation, pages 2985-2990, 2015. Google Scholar
  32. James J. Kuffner and Steven M. LaValle. RRT-Connect: An efficient approach to single-query path planning. In International Conference on Robotics and Automation (ICRA), pages 995-1001, 2000. Google Scholar
  33. S. M. LaValle. Planning algorithms. Cambridge University Press, 2006. Google Scholar
  34. Wouter Meulemans. Map matching with simplicity constraints. CoRR, abs/1306.2827, 2013. Google Scholar
  35. M. Muja and D. G. Lowe. Fast approximate nearest neighbors with automatic algorithm configuration. In VISSAPP, pages 331-340. INSTICC Press, 2009. Google Scholar
  36. Mathew Penrose. Random geometric graphs, volume 5. Oxford University Press, 2003. Google Scholar
  37. Barak Raveh, Angela Enosh, Ora Schueler-Furman, and Dan Halperin. Rapid sampling of molecular motions with prior information constraints. PLoS Computational Biology, 5(2), 2009. Google Scholar
  38. John H Reif. Complexity of the mover’s problem and generalizations: Extended abstract. In Foundations of Computer Science, pages 421-427, 1979. Google Scholar
  39. Oren Salzman and Dan Halperin. Asymptotically-optimal motion planning using lower bounds on cost. In IEEE International Conference on Robotics and Automation (ICRA), pages 4167-4172, 2015. Google Scholar
  40. Micha Sharir. Algorithmic motion planning. In Jacob E. Goodman and Joseph O'Rourke, editors, Handbook of Discrete and Computational Geometry, Second Edition., pages 1037-1064. Chapman and Hall/CRC, 2004. Google Scholar
  41. Jessica Sherette and Carola Wenk. Simple curve embedding. CoRR, abs/1303.0821, 2013. Google Scholar
  42. J. G. Siek, L.-Q. Lee, and A. Lumsdaine. The Boost Graph Library User Guide and Reference Manual. Addison-Wesley, 2002. Google Scholar
  43. Kiril Solovey and Dan Halperin. On the hardness of unlabeled multi-robot motion planning. In Robotics: Science and Systems (RSS), 2015. Google Scholar
  44. Kiril Solovey, Oren Salzman, and Dan Halperin. Finding a needle in an exponential haystack: Discrete RRT for exploration of implicit roadmaps in multi-robot motion planning. International Journal of Robotics Research, 35(5):501-513, 2016. Google Scholar
  45. Kiril Solovey, Oren Salzman, and Dan Halperin. New perspective on sampling-based motion planning via random geometric graphs. In Robotics: Science and Systems (RSS), Ann Arbor, Michigan, 2016. URL: http://dx.doi.org/10.15607/RSS.2016.XII.003.
  46. Kiril Solovey, Jingjin Yu, Or Zamir, and Dan Halperin. Motion planning for unlabeled discs with optimality guarantees. In Robotics: Science and Systems (RSS), 2015. Google Scholar
  47. Paul G. Spirakis and Chee-Keng Yap. Strong NP-hardness of moving many discs. Information Processing Letters, 19(1):55-59, 1984. Google Scholar
  48. R Sriraghavendra, K Karthik, and Chiranjib Bhattacharyya. Fréchet distance based approach for searching online handwritten documents. In Document Analysis and Recognition, volume 1, pages 461-465. IEEE, 2007. Google Scholar
  49. The CGAL Project. CGAL user and reference manual. CGAL editorial board, 4.8 edition, 2016. URL: http://www.cgal.org/.
  50. Matthew Turpin, Nathan Michael, and Vijay Kumar. Concurrent assignment and planning of trajectories for large teams of interchangeable robots. In International Conference on Robotics and Automation (ICRA), pages 842-848, 2013. Google Scholar
  51. Mark Walters. Random geometric graphs. In Robin Chapman, editor, Surveys in Combinatorics 2011, chapter 8, pages 365-401. Cambridge University Press, 2011. Google Scholar
  52. Virginia Vassilevska Williams. Efficient Algorithms for Path Problems in Weighted Graphs. Ph.D. thesis, School of Computer Science, Carnegie Mellon University, Pittsburgh, PA, USA, 2008. Google Scholar
  53. Jianbin Zheng, Xiaolei Gao, Enqi Zhan, and Zhangcan Huang. Algorithm of on-line handwriting signature verification based on discrete Fréchet distance. In Advances in Computation and Intelligence, pages 461-469. Springer, 2008. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact