Rods and rings: Soft subdivision planner for ℝ3 × S2

Ching Hsiang Hsu, Yi Jen Chiang, Chee Yap

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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 ℝ3 ×S2 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 [31]. Our subdivision path planner is based on the twin foundations of ε-exactness and soft predicates. Correct implementation is relatively easy. The technical innovations include subdivision atlases for S2, introduction of Σ2 representations for footprints, and extensions of our feature-based technique for “opening up the blackbox of collision detection”.

Original languageEnglish (US)
Title of host publication35th International Symposium on Computational Geometry, SoCG 2019
EditorsGill Barequet, Yusu Wang
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959771047
StatePublished - Jun 1 2019
Event35th International Symposium on Computational Geometry, SoCG 2019 - Portland, United States
Duration: Jun 18 2019Jun 21 2019

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
ISSN (Print)1868-8969


Conference35th International Symposium on Computational Geometry, SoCG 2019
Country/TerritoryUnited States


  • Algorithmic motion planning
  • Resolution-exact algorithms
  • Soft predicates
  • Spatial ring robots
  • Spatial rod robots
  • Subdivision methods

ASJC Scopus subject areas

  • Software


Dive into the research topics of 'Rods and rings: Soft subdivision planner for ℝ3 × S2'. Together they form a unique fingerprint.

Cite this