Document Open Access Logo

Soft Subdivision Motion Planning for Complex Planar Robots

Authors Bo Zhou, Yi-Jen Chiang, Chee Yap

PDF
Thumbnail PDF

File

LIPIcs.ESA.2018.73.pdf
  • Filesize: 0.84 MB
  • 14 pages

Document Identifiers

Author Details

Bo Zhou
  • Department of Computer Science and Engineering, New York University, Brooklyn, NY, USA
Yi-Jen Chiang
  • Department of Computer Science and Engineering, New York University, Brooklyn, NY, USA
Chee Yap
  • Department of Computer Science, New York University, New York, NY, USA

Cite As Get BibTex

Bo Zhou, Yi-Jen Chiang, and Chee Yap. Soft Subdivision Motion Planning for Complex Planar Robots. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 73:1-73:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.ESA.2018.73

Abstract

The design and implementation of theoretically-sound robot motion planning algorithms is challenging. Within the framework of resolution-exact algorithms, it is possible to exploit soft predicates for collision detection. The design of soft predicates is a balancing act between easily implementable predicates and their accuracy/effectivity.
In this paper, we focus on the class of planar polygonal rigid robots with arbitrarily complex geometry. We exploit the remarkable decomposability property of soft collision-detection predicates of such robots. We introduce a general technique to produce such a decomposition. If the robot is an m-gon, the complexity of this approach scales linearly in m. This contrasts with the O(m^3) complexity known for exact planners. It follows that we can now routinely produce soft predicates for any rigid polygonal robot. This results in resolution-exact planners for such robots within the general Soft Subdivision Search (SSS) framework. This is a significant advancement in the theory of sound and complete planners for planar robots.
We implemented such decomposed predicates in our open-source Core Library. The experiments show that our algorithms are effective, perform in real time on non-trivial environments, and can outperform many sampling-based methods.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
  • Computing methodologies → Robotic planning
Keywords
  • Computational Geometry
  • Algorithmic Motion Planning
  • Resolution-Exact Algorithms
  • Soft Predicates
  • Planar Robots with Complex Geometry

Metrics

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

Related Versions

References

  1. F. Avnaim, J-D. Boissonnat, and B. Faverjon. A practical exact motion planning algorithm for polygonal objects amidst polygonal obstacles. In Boissonnat J.D. and Laumond J.P., editors, Geometry and Robotics, LNCS Vol 391. Springer, Berlin-Heidelberg, 1989. Google Scholar
  2. M. Barbehenn and S. Hutchinson. Efficient search and hierarchical motion planning by dynamically maintaining single-source shortest paths trees. IEEE Trans. Robotics and Automation, 11(2), 1995. Google Scholar
  3. J. Basch, L.J. Guibas, D. Hsu, and A. Nguyen. Disconnection proofs for motion planning. In IEEE Int'l Conf. on Robotics Animation, pages 1765-1772, 2001. Google Scholar
  4. Huxley Bennett, Evanthia Papadopoulou, and Chee Yap. Planar minimization diagrams via subdivision with applications to anisotropic Voronoi diagrams. Eurographics Symposium on Geometric Processing, 35(5), 2016. SGP 2016, Berlin, Germany. June 20-24, 2016. Google Scholar
  5. H. Choset, K. M. Lynch, S. Hutchinson, G. Kantor, W. Burgard, L. E. Kavraki, and S. Thrun. Principles of Robot Motion: Theory, Algorithms, and Implementations. MIT Press, Boston, 2005. Google Scholar
  6. Core Library. https://cs.nyu.edu/exact/core_pages/downloads.html.
  7. Dan Halperin, Efi Fogel, and Ron Wein. CGAL Arrangements and Their Applications. Springer-Verlag, Berlin and Heidelberg, 2012. Google Scholar
  8. Ching-Hsiang Hsu, Yi-Jen Chiang, and Chee Yap. Rods and rings: Soft subdivision planner for R^3 x S^2, 2018. Available at http://cse.poly.edu/chiang/rod-ring18.pdf.
  9. Jean-Claude Latombe. Robot Motion Planning. Kluwer Academic Publishers, 1991. Google Scholar
  10. Steven M. LaValle. Planning Algorithms. Cambridge University Press, Cambridge, 2006. Google Scholar
  11. Zhongdi Luo, Yi-Jen Chiang, Jyh-Ming Lien, and Chee Yap. Resolution exact algorithms for link robots. In Proc. 11th Intl. Workshop on Algorithmic Foundations of Robotics (WAFR '14), volume 107 of Springer Tracts in Advanced Robotics (STAR), pages 353-370, 2015. 3-5 Aug 2014, Boǧazici University, Istanbul, Turkey. Google Scholar
  12. Victor Milenkovic, Elisha Sacks, and Steven Trac. Robust complete path planning in the plane. In Proc. 10th Workshop on Algorithmic Foundations of Robotics (WAFR 2012), Springer Tracts in Advanced Robotics, vol.86, pages 37-52. Springer, 2012. Google Scholar
  13. O. Salzman, M. Hemmer, B. Raveh, and D. Halperin. Motion planning via manifold samples. In Proc. European Symp. Algorithms (ESA), 2011. Google Scholar
  14. I.A. Şucan, M. Moll, and L.E. Kavraki. The Open Motion Planning Library. IEEE Robotics &Automation Magazine, 19(4):72-82, 2012. URL: http://dx.doi.org/10.1109/MRA.2012.2205651.
  15. Cong Wang, Yi-Jen Chiang, and Chee Yap. On Soft Predicates in Subdivision Motion Planning. Comput. Geometry: Theory and Appl. (Special Issue for SoCG'13), 48(8):589-605, 2015. Google Scholar
  16. Chee Yap, Zhongdi Luo, and Ching-Hsiang Hsu. Resolution-exact planner for thick non-crossing 2-link robots. In Proc. 12th Intl. Workshop on Algorithmic Foundations of Robotics (WAFR '16), 2016. 13-16 Dec 2016, San Francisco. The appendix in the full paper (and arXiv from http://cs.nyu.edu/exact/ (and arXiv:1704.05123 [cs.CG]) contains proofs and additional experimental data. Google Scholar
  17. Chee K. Yap. Soft Subdivision Search in Motion Planning. In A. Aladren et al., editor, Proceedings, 1st Workshop on Robotics Challenge and Vision (RCV 2013), 2013. Robotics Science and Systems Conference (RSS 2013), Berlin. In arXiv:1402.3213. Full paper: http://cs.nyu.edu/exact/papers/. Google Scholar
  18. Chee K. Yap. Soft Subdivision Search and Motion Planning, II: Axiomatics. In Frontiers in Algorithmics, volume 9130 of Lecture Notes in Comp.Sci., pages 7-22. Springer, 2015. Plenary Talk at 9th FAW. Guilin, China. Aug 3-5, 2015. Google Scholar
  19. Liangjun Zhang, Young J. Kim, and Dinesh Manocha. Efficient cell labeling and path non-existence computation using C-obstacle query. Int'l. J. Robotics Research, 27(11-12):1246-1257, 2008. Google Scholar
  20. Bo Zhou, Yi-Jen Chiang, and Chee Yap. Soft subdivision motion planning for complex planar robots, 2018. Full version available at http://cse.poly.edu/chiang/esa18-full.pdf.
  21. D.J. Zhu and J.-C. Latombe. New heuristic algorithms for efficient hierarchical path planning. IEEE Transactions on Robotics and Automation, 7:9-20, 1991. 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