Jeff Trinkle
Rensselaer Polytechnic Institute
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.
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.
For appointments, please
contact Ruth Gaus (riw@cs.cmu.edu)
The Robotics Institute is part of the School of Computer Science, Carnegie Mellon University.
