Resolution-exact algorithms for link robots

Zhongdi Luo, Yi Jen Chiang, Jyh Ming Lien, Chee Yap

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


Motion planning is a major topic in robotics. Divergent paths have been taken by practical roboticists and theoretical motion planners. Our goal is to produce algorithms that are practical and have strong theoretical guarantees. Recently, we have proposed a subdivision approach based on soft predicates Wang, C., Chiang, Y.-J., Yap, C.: On soft predicates in subdivision motion planning. In: 29th ACM Symposium on Computational Geometry (SoCG’13), pp. 349–358 (2013). To appear CGTA, Special Issue for SoCG’13 [20], but with a new notion of correctness called resolution-exactness. Unlike mos ques for planar link robots. The technical contributions of this paper are the design of soft predicates for link robots, a novel “T/R splitting method” for subdivision, and feature-based search strategies. The T/R idea is to give primacy to the translational (T) components, and perform splitting of rotational components (R) only at the leaves of a subdivision tree. We implemented our algorithm for a 2-link robot with 4 degrees of freedom (DOFs). Our implementation achieves real-time performance on a variety of nontrivial scenarios. For comparison, our method outperforms sampling-based methods significantly. We extend our 2-link planner to thick link robots with little impact on performance. Note that there are no known exact algorithms for thick link robots.

Original languageEnglish (US)
Title of host publicationAlgorithmic Foundations of Robotics - Selected Contributions of the 11th International Workshop on the Algorithmic Foundations of Robotics, WAFR 2014
EditorsA. Frank van der Stappen, H. Levent Akin, Nancy M. Amato, Volkan Isler
PublisherSpringer Verlag
Number of pages18
ISBN (Print)9783319165943
StatePublished - 2015
Event11th International Workshop on the Algorithmic Foundations of Robotics, WAFR 2014 - Istanbul, Turkey
Duration: Aug 3 2014Aug 5 2014

Publication series

NameSpringer Tracts in Advanced Robotics
ISSN (Print)1610-7438
ISSN (Electronic)1610-742X


Other11th International Workshop on the Algorithmic Foundations of Robotics, WAFR 2014


  • Exact algorithms
  • Link robots
  • Motion planning
  • Resolution-exact algorithms
  • Soft predicates
  • Subdivision algorithms

ASJC Scopus subject areas

  • Electrical and Electronic Engineering
  • Artificial Intelligence


Dive into the research topics of 'Resolution-exact algorithms for link robots'. Together they form a unique fingerprint.

Cite this