How Far Can You Reach? A Tale of Geometry, Robots and Proteins

03 Mar
03/03/2009 - 11:00am

Ileana Streinu
Smith College

Computer Science Building, Room 151

Andrew Barto

Robot arms and protein backbones can be described as three-dimensional polygonal chains with fixed lengths and angles. One of the most fundamental questions in Robotics, open for over 30 years, asks for a mathematical characterization and efficient computation of the maximum reach: the farthest achievable distance between the polygon's endpoints. Until now only numerical approximation methods were known.

I will present our recent, surprisingly elementary geometric solution. As an outcome, we obtain a linear time algorithm for finding and folding to the maximum and minimum reach, which is applicable to a large family of polygonal chains of practical interest (including the orthogonal ones).

The presentation includes 3-dimensional props and animated demos accessible even to non-specialists. I will conclude with a discussion of applications in robotics and protein kinematics.

This is joint work with Ciprian Borcea.