Soft subdivision motion planning for complex planar robots

Bo Zhou, Yi Jen Chiang, Chee Yap

Research output: Contribution to journalArticlepeer-review


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 their implementability 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)
Article number101683
JournalComputational Geometry: Theory and Applications
StatePublished - Jan 2021


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

ASJC Scopus subject areas

  • Computer Science Applications
  • Geometry and Topology
  • Control and Optimization
  • Computational Theory and Mathematics
  • Computational Mathematics


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

Cite this