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.
Abstract:
There is a need for highly redundant manipulators to work in complex, cluttered environments. Our goal is to plan paths for such manipulators efficiently.
The path planning problem has been shown to be PSPACE-complete in terms of the number of degrees of freedom (DOF) of the manipulator. We present a method which overcomes the complexity with a strong heuristic: utilizing redundancy by means of a continuous manipulator model. The continuous model allows us to change the complexity of the problem from a function of both the DOF of the manipulator (believed to be exponential) and the complexity of the environment (polynomial), to a polynomial function of the complexity of the environment only.
The power of the continuous model comes from the ability to decompose the manipulator into segments, with the number, size, and boundaries of the segments, varying smoothly and dynamically. First, we develop motion schemas for the individual segments to achieve a basic set of goals in open and cluttered space. Second, we plan a smooth trajectory through free space for a point robot with a maximum curvature constraint. Third, the path generates a set of position subgoals for the continuous manipulator which are achieved by the basic motion schemas. Fourth, the mapping from the continuous model to an available jointed arm provides the curvature bound and obstacle envelopes required (in step 2) to guarantee a collision-free path.
The validity of the continuous model approach is also supported by an extensive simulation which we performed. While the simulation has been performed in 2-D, we show a natural extension to 3-D for each technique we have implemented for the 2-D simulation.