The Swan's Neck


How To Escape From Configuration Space

The approach that Tomas Lozano-Perez developed for using configuration space to plan robot manipulator trajectories is clear and elegant, and certainly deserves the foundational role it has taken on in the field. Still, my intuition suggests that more degrees of freedom should be a benefit in manipulator planning, whereas under the c-space approach it is a cost, an exponential one, and one that must be paid up-front!

I was inspired one day by watching swans in a park. The swan uses its neck as though it is continuous and therefore has an infinite number of degrees of freedom, with little cognitive load. The key is that the configuration of the neck is determined by its curvature, c, which varies smoothly as a function of position, s, along the neck. In order to move the neck from one configuration to another, the curvature profile is changed, again smoothly, as represented by the continuous function c(s,t).

Working with my student Akira Hayashi, we showed that a small finite set of degrees of freedom could control a continuous neck to reach any desired position-orientation goal in an unobstructed convex region. In an obstructed space, if the path from base to goal (in the workspace, not configuration space) can be defined as a sequence of adjacent or overlapping convex regions, motion of a segment of the neck through each region can be controlled by one of the unobstructed-region motion routines. Treating the neck as continuous, the segment boundaries can be continuously adjusted as the head moves toward its goal. Therefore, motion in an obstructed space can be composed of motions for small open spaces.

Of course, most real manipulators have joints. Having planned a trajectory for a continuous neck, we approximate it with the segmented manipulator that is actually available. There is an error to this approximation, which can be bounded as a function of the maximum curvature taken on by the continuous neck and the maximum segment length in the segmented manipulator. Given the geometry of the segmented manipulator, we plan a continuous route for the neck with a bounded curvature. Growing the obstacles (in workspace, not configuration space) by the appropriate error bound ensures collision-free motion.

The elegant move here, from an algorithmic point of view, is that the number of degrees of freedom in the manipulator is converted from a cost (exponential time) to a benefit (decreased error bound)!

Having removed the exponential degree-of-freedom term, the dominant factor in complexity is the polynomial time required to find the convex free-space regions and a bounded-curvature route through them. This cost reflects the geometric complexity of the workspace, and is intuitively perfectly reasonable. At the moment this polynomial is of high order, but we haven't applied any computational geometry to the problem, so I am confident that it can be substantially reduced.

Naturally, this dramatic reduction in complexity requires some loss of completeness in the algorithm. For example, trajectories requiring ``folding-ruler'' moves may not be findable within given curvature bounds. Nonetheless, the approximations built into this approach seem well matched to the problem of controlling a physical high-degree-of-freedom manipulator.


[Robotics Home]