The Robotics Institute
RI | Seminar | October 24

Robotics Institute Seminar, October 24
Time and Place | Seminar Abstract | Speaker Biography | Speaker Appointments

Complete Motion Planning for Closed Kinematic Chains

Jeff Trinkle
Rensselaer Polytechnic Institute

Time and Place

Mauldin Auditorium (NSH 1305)
Refreshments 3:15 pm
Talk 3:30 pm


The motion planning problem is to construct a motion of a robotic system that takes it from an initial configuration to some other desired configuration without collisions. In the 1970s and 80s, complete algorithms were designed, but their intractibility (O(2^n) or worse) ultimately led to an interest in probabilistic methods, which are easy to implement (even as parallel algorithms), but unfortunately are not complete. Probabilistic Roadmap Methods (PRMs) and their derivatives are now the methods of choice in many application areas.

Our work has been motivated by the development of new mathematical techniques, the realization that even PRMs cannot escape the "curse of dimenionality," and the hope that complete, polynomial-time algorithms can be developed for some classes of practical problems. In this presentation, I will describe how the global properties of the configuration spaces of closed kinematic chains with spherical joints and any number of links have been analyzed. I will then show how this analysis was used to design a complete, robust, and efficient motion planning algorithm (ignoring obstacles), whose robustness was achieved by taking advantage of the local and global properties of the length function of an open kinematic chain. Finally, I will present numerical experiments for planar closed chains with revolute joints that demonstrate our algorithm's superiority over a typical simplistic algorithm that uses only local information. I will also briefly describe how one can use similar mathematical techniques to understand the global properties of configuration spaces with obstacles.

Speaker Biography

Jeffrey C. Trinkle received his bachelor's degrees in Physics (1979) and Engineering Science and Mechanics (1979) from Ursinus College and Georgia Institute of Technology, respectively. In 1987, he received his PhD from the Department of Systems Engineering at the University of Pennsylvania. Since 1987, he has held faculty positions the Department of Systems and Industrial Engineering at the University of Arizona, the Department of Computer Science at Texas A&M University, and spent five years as a research scientist at Sandia National Laboratories in Albuqueruqe, NM. He now holds the position of Professor and Chair of Computer Science at Rensselear Polytechnic Institute. Dr. Trinkle's primary research interests lie in the areas of robot manipulation planning, multibody dynamics, and automated manufacturing.

Speaker Appointments

For appointments, please contact Ruth Gaus (

The Robotics Institute is part of the School of Computer Science, Carnegie Mellon University.