Document Open Access Logo

Rods and Rings: Soft Subdivision Planner for R^3 x S^2

Authors Ching-Hsiang Hsu, Yi-Jen Chiang, Chee Yap

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2019.43.pdf
  • Filesize: 2.12 MB
  • 17 pages

Document Identifiers

Author Details

Ching-Hsiang Hsu
  • Department of Computer Science, Courant Institute, New York University, New York, NY, USA
Yi-Jen Chiang
  • Department of Computer Science and Engineering, Tandon School of Engineering, New York University, Brooklyn, NY, USA
Chee Yap
  • Department of Computer Science, Courant Institute, New York University, New York, NY, USA

Funding

Supported in part by NSF Grants #CCF-1423228 and #CCF-1563942.
  • Hsu, Ching-Hsiang: Supported by NSF Grant #CCF-1423228.
  • Yap, Chee: Supported in part by NSF Grants #CCF-1423228 and #CCF-1563942.

Cite As Get BibTex

Ching-Hsiang Hsu, Yi-Jen Chiang, and Chee Yap. Rods and Rings: Soft Subdivision Planner for R^3 x S^2. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 43:1-43:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.SoCG.2019.43

Abstract

We consider path planning for a rigid spatial robot moving amidst polyhedral obstacles. Our robot is either a rod or a ring. Being axially-symmetric, their configuration space is R^3 x S^2 with 5 degrees of freedom (DOF). Correct, complete and practical path planning for such robots is a long standing challenge in robotics. While the rod is one of the most widely studied spatial robots in path planning, the ring seems to be new, and a rare example of a non-simply-connected robot. This work provides rigorous and complete algorithms for these robots with theoretical guarantees. We implemented the algorithms in our open-source Core Library. Experiments show that they are practical, achieving near real-time performance. We compared our planner to state-of-the-art sampling planners in OMPL [Sucan et al., 2012].
Our subdivision path planner is based on the twin foundations of epsilon-exactness and soft predicates. Correct implementation is relatively easy. The technical innovations include subdivision atlases for S^2, introduction of Sigma_2 representations for footprints, and extensions of our feature-based technique for "opening up the blackbox of collision detection".

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
  • Computing methodologies → Robotic planning
Keywords
  • Algorithmic Motion Planning
  • Subdivision Methods
  • Resolution-Exact Algorithms
  • Soft Predicates
  • Spatial Rod Robots
  • Spatial Ring Robots

Metrics

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

Related Versions

References

  1. Saugata Basu, Richard Pollack, and Marie-Françoise Roy. Algorithms in Real Algebraic Geometry. Algorithms and Computation in Mathematics. Springer, 2nd edition, 2006. Google Scholar
  2. 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
  3. Rodney A. Brooks and Tomas Lozano-Perez. A subdivision algorithm in configuration space for findpath with rotation. In Proc. 8th Intl. Joint Conf. on Artificial intelligence - Volume 2, pages 799-806, San Francisco, CA, USA, 1983. Morgan Kaufmann Publishers Inc. Google Scholar
  4. John Canny. Computing roadmaps of general semi-algebraic sets. The Computer Journal, 36(5):504-514, 1993. 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. Howie Choset, Brian Mirtich, and Joel Burdick. Sensor based planning for a planar rod robot: Incremental construction of the planar Rod-HGVG. In IEEE Intl. Conf. on Robotics and Automation (ICRA'97), pages 3427-3434, 1997. Google Scholar
  7. James Cox and Chee K. Yap. On-line motion planning: case of a planar rod. Annals of Mathematics and Artificial Intelligence, 3:1-20, 1991. Special journal issue. Also: NYU-Courant Institute, Robotics Lab., No.187, 1988. Google Scholar
  8. Jory Denny, Kensen Shi, and Nancy M. Amato. Lazy Toggle PRM: a Single Query approach to motion planning. In Proc. IEEE Int. Conf. Robot. Autom. (ICRA), pages 2407-2414, 2013. Karlsrube, Germany. May 2013. Google Scholar
  9. David Eberly. Distance to circles in 3D, May 31 2015. Downloaded from https://www.geometrictools.com/Documentation/Documentation.html. Google Scholar
  10. Mohab Safey el Din and Eric Schost. A baby steps/giant steps probabilistic algorithm for computing roadmaps in smooth bounded real hypersurface. Discrete and Comp. Geom., 45(1):181-220, 2011. Google Scholar
  11. Hazel Everett, Christian Gillot, Daniel Lazard, Sylvain Lazard, and Marc Pouget. The Voronoi diagram of three arbitrary lines in ℝ³. In 25th European Workshop on Computational Geometry (EuroCG'09), 2009. March 2009, Bruxelles, Belgium. Google Scholar
  12. Hazel Everett, Daniel Lazard, Sylvain Lazard, and Mohab Safey el Din. The Voronoi diagram of three lines. Discrete and Comp. Geom., 42(1):94-130, 2009. See also 23rd SoCG, 2007. pp.255-264. Google Scholar
  13. Dan Halperin, Efi Fogel, and Ron Wein. CGAL Arrangements and Their Applications. Springer-Verlag, Berlin and Heidelberg, 2012. Google Scholar
  14. Dan Halperin, Oren Salzman, and Micha Sharir. Algorithmic motion planning. In Jacob E. Goodman, Joseph O'Rourke, and Csaba Toth, editors, Handbook of Discrete and Computational Geometry, chapter 50. Chapman &Hall/CRC, Boca Raton, FL, 3rd edition, 2017. Expanded from second edition. Google Scholar
  15. Michael Hemmer, Ophir Setter, and Dan Halperin. Constructing the exact Voronoi diagram of arbitrary lines in three-dimensional space. In Algorithms - ESA 2010, volume 6346 of Lecture Notes in Computer Science, pages 398-409. Springer Berlin / Heidelberg, 2010. Google Scholar
  16. Ching-Hsiang Hsu, Yi-Jen Chiang, and Chee Yap. Rods and rings: Soft subdivision planner for R^3 x S^2, 2019. Hosted on arXiv as https://arxiv.org/abs/1903.09416. Also available at http://cse.poly.edu/chiang/rod-ring18.pdf.
  17. V. Koltun. Pianos are not flat: rigid motion planning in three dimensions. In Proc. 16th ACM-SIAM Sympos. Discrete Algorithms, pages 505-514, 2005. Google Scholar
  18. Steven M. LaValle. Planning Algorithms. Cambridge University Press, Cambridge, 2006. Google Scholar
  19. Ji Yeong Lee and Howie Choset. Sensor-based planning for a rod-shaped robot in 3 dimensions: Piecewise retracts of R³ × S². Int'l. J. Robotics Research, 24(5):343-383, 2005. Google Scholar
  20. 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
  21. James R. Munkres. Topology. Prentice-Hall, Inc, second edition, 2000. Google Scholar
  22. Michal Nowakiewicz. MST-Based method for 6DOF rigid body motion planning in narrow passages. In Proc. IEEE/RSJ International Conf. on Intelligent Robots and Systems, pages 5380-5385, 2010. Oct 18-22, 2010. Taipei, Taiwan. Google Scholar
  23. Colm Ó'Dúnlaing, Micha Sharir, and Chee K. Yap. Retraction: a new approach to motion-planning. ACM Symp. Theory of Comput., 15:207-220, 1983. Google Scholar
  24. Colm Ó'Dúnlaing and Chee K. Yap. A "Retraction" method for planning the motion of a disc. J. Algorithms, 6:104-111, 1985. Also, Chapter 6 in Planning, Geometry, and Complexity, eds. Schwartz, Sharir and Hopcroft, Ablex Pub. Corp., Norwood, NJ. 1987. Google Scholar
  25. J. T. Schwartz and M. Sharir. On the piano movers' problem: I. The case of a two-dimensional rigid polygonal body moving amidst polygonal barriers. Communications on Pure and Applied Mathematics, 36:345-398, 1983. Google Scholar
  26. Jacob T. Schwartz and Micha Sharir. On the piano movers' problem: II. General techniques for computing topological properties of real algebraic manifolds. Advances in Appl. Math., 4:298-351, 1983. Google Scholar
  27. Jacob T. Schwartz and Micha Sharir. On the piano movers' problem: V. the case of a rod moving in three-dimensional space amidst polyhedral obstacles. Comm. Pure and Applied Math., 37(6):815-848, 1984. URL: http://dx.doi.org/10.1002/cpa.3160370605.
  28. M. Sharir, C. O'D'únlaing, and C. Yap. Generalized Voronoi diagrams for moving a ladder I: topological analysis. Communications in Pure and Applied Math., XXXIX:423-483, 1986. Also: NYU-Courant Institute, Robotics Lab., No. 32, Oct 1984. Google Scholar
  29. M. Sharir, C. O'D'únlaing, and C. Yap. Generalized Voronoi diagrams for moving a ladder II: efficient computation of the diagram. Algorithmica, 2:27-59, 1987. Also: NYU-Courant Institute, Robotics Lab., No. 33, Oct 1984. Google Scholar
  30. Vikram Sharma and Chee K. Yap. Robust geometric computation. In Jacob E. Goodman, Joseph O'Rourke, and Csaba Tóth, editors, Handbook of Discrete and Computational Geometry, chapter 45, pages 1189-1224. Chapman &Hall/CRC, Boca Raton, FL, 3rd edition, 2017. Revised and expanded from 2004 version. Google Scholar
  31. 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.
  32. 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, September 2015. Google Scholar
  33. 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
  34. Chee Yap, Vikram Sharma, and Jyh-Ming Lien. Towards exact numerical Voronoi diagrams. In 9th Int'l Symp. of Voronoi Diagrams in Science and Engineering (ISVD)., pages 2-16. IEEE, 2012. Invited Talk. June 27-29, 2012, Rutgers University, NJ. URL: http://dx.doi.org/10.1109/ISVD.2012.31.
  35. Chee K. Yap. Algorithmic motion planning. In J.T. Schwartz and C.K. Yap, editors, Advances in Robotics, Vol. 1: Algorithmic and geometric issues, volume 1, pages 95-143. Lawrence Erlbaum Associates, 1987. Google Scholar
  36. 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. A Computing Community Consortium (CCC) Best Paper Award, Robotics Science and Systems Conference (RSS 2013), Berlin. In arXiv:1402.3213. Google Scholar
  37. 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
  38. 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
  39. Bo Zhou, Yi-Jen Chiang, and Chee Yap. Soft subdivision motion planning for complex planar robots. In Proc. 26th European Symp. Algo.(ESA), pages 73:1-73:14, 2018. Helsinki, Finland, Aug 20-24, 2018. Google Scholar
  40. 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