DROPS

Document

DOI: 10.4230/LIPIcs.SoCG.2019.43

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

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

Published in: LIPIcs, Volume 129, 35th International Symposium on Computational Geometry (SoCG 2019)

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".

Cite as

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)

Copy BibTex To Clipboard

@InProceedings{hsu_et_al:LIPIcs.SoCG.2019.43,
  author =	{Hsu, Ching-Hsiang and Chiang, Yi-Jen and Yap, Chee},
  title =	{{Rods and Rings: Soft Subdivision Planner for R^3 x S^2}},
  booktitle =	{35th International Symposium on Computational Geometry (SoCG 2019)},
  pages =	{43:1--43:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-104-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{129},
  editor =	{Barequet, Gill and Wang, Yusu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.43},
  URN =		{urn:nbn:de:0030-drops-104477},
  doi =		{10.4230/LIPIcs.SoCG.2019.43},
  annote =	{Keywords: Algorithmic Motion Planning, Subdivision Methods, Resolution-Exact Algorithms, Soft Predicates, Spatial Rod Robots, Spatial Ring Robots}
}

Document

DOI: 10.4230/LIPIcs.SoCG.2016.68

Path Planning for Simple Robots using Soft Subdivision Search

Authors: Ching-Hsiang Hsu, John Paul Ryan, and Chee Yap

Published in: LIPIcs, Volume 51, 32nd International Symposium on Computational Geometry (SoCG 2016)

Abstract

The concept of resolution-exact path planning is a theoretically sound alternative to the standard exact algorithms, and provides much stronger guarantees than probabilistic or sampling algorithms. It opens the way for the introduction of soft predicates in the context of subdivision algorithm. Taking a leaf from the great success of the Probabilistic Road Map (PRM) framework, we formulate an analogous framework for subdivision, called Soft Subdivision Search (SSS). In this video, we illustrate the SSS framework for a trio of simple planar robots: disc, triangle and 2-links. These robots have, respectively, 2, 3 and 4 degrees of freedom. Our 2-link robot can also avoid self-crossing. These algorithms operate in realtime and are relatively easy to implement.

Cite as

Ching-Hsiang Hsu, John Paul Ryan, and Chee Yap. Path Planning for Simple Robots using Soft Subdivision Search. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 68:1-68:5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{hsu_et_al:LIPIcs.SoCG.2016.68,
  author =	{Hsu, Ching-Hsiang and Ryan, John Paul and Yap, Chee},
  title =	{{Path Planning for Simple Robots using Soft Subdivision Search}},
  booktitle =	{32nd International Symposium on Computational Geometry (SoCG 2016)},
  pages =	{68:1--68:5},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-009-5},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{51},
  editor =	{Fekete, S\'{a}ndor and Lubiw, Anna},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.68},
  URN =		{urn:nbn:de:0030-drops-59607},
  doi =		{10.4230/LIPIcs.SoCG.2016.68},
  annote =	{Keywords: Robot Path Planning, Soft Predicates, Resolution-Exact Algorithm, Subdivision Search}
}

Search Results

Documents authored by Hsu, Ching-Hsiang

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

Abstract

Cite as

Path Planning for Simple Robots using Soft Subdivision Search

Abstract

Cite as

Thanks for your feedback!

Could not send message