This paper presents a technique for improving the efficiency of
automated motion planners. Motion planning has application in
many areas such as robotics, virtual reality systems, computer-aided
design, and even computational biology.
Although there have been steady advances in motion planning algorithms,
especially in randomized approaches such as probabilistic roadmap methods
(PRMs) or rapidly-exploring random trees (RRTs), there are still some
classes of problems that cannot be solved efficiently using these
state-of-the-art motion planners.
In this paper, we suggest an iterative strategy addressing this problem
where we first simplify the problem by relaxing some feasibility
constraints, solve the easier version of the problem, and then use that
solution to help us find a solution for the harder problem.
We show how this strategy can be applied to rigid bodies and to
linkages with high degrees of freedom, including both open and closed chain
systems. Experimental results are presented for linkages composed of
Although we use PRMs as the automated planner, the framework is general
and can be applied with other motion planning techniques as well.