2026-07-25T03:00:50Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10447 2024-03-06T10:46:00Z ddc:004 open_access

Rods and Rings: Soft Subdivision Planner for R^3 x S^2 Hsu, Ching-Hsiang Chiang, Yi-Jen Yap, Chee Algorithmic Motion Planning Subdivision Methods Resolution-Exact Algorithms Soft Predicates Spatial Rod Robots Spatial Ring Robots 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". Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ching-Hsiang Hsu and Yi-Jen Chiang and Chee Yap 2019 Is Part Of LIPIcs, Volume 129, 35th International Symposium on Computational Geometry (SoCG 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2019.43 urn:nbn:de:0030-drops-104477 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.43 eng https://creativecommons.org/licenses/by/3.0/legalcode