Soft subdivision motion planning for complex planar robots

Bo Zhou, Yi Jen Chiang, Chee Yap

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

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(m3) 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.

Original languageEnglish (US)
Title of host publication26th European Symposium on Algorithms, ESA 2018
EditorsHannah Bast, Grzegorz Herman, Yossi Azar
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Print)9783959770811
DOIs
StatePublished - Aug 1 2018
Event26th European Symposium on Algorithms, ESA 2018 - Helsinki, Finland
Duration: Aug 20 2018Aug 22 2018

Publication series

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

Other

Other26th European Symposium on Algorithms, ESA 2018
CountryFinland
CityHelsinki
Period8/20/188/22/18

Keywords

  • Algorithmic motion planning
  • Computational geometry
  • Planar robots with complex geometry
  • Resolution-exact algorithms
  • Soft predicates

ASJC Scopus subject areas

  • Software

Fingerprint Dive into the research topics of 'Soft subdivision motion planning for complex planar robots'. Together they form a unique fingerprint.

Cite this