|
Bayazit's work at Parasol Lab.
O. Burchan Bayazit, Dawen Xie, Nancy M. Amato
Figure 1
|
We are presenting 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-expanding random trees (RRTs), there are still some
classes of problems that cannot be solved efficiently using
state-of-the-art motion planners.
In this project, 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
high dof articulated linkages, including both open and closed chain
systems; experimental results are presented for linkages composed of
9--98 links.
Although we use PRMs as the automated planner, the framework is general
and can be applied with other motion planning techniques as well.
There are many scenarios in which the critical feasible region of
C-space is so small relative to the entire search space that global
sampling approaches, such as PRMs, cannot be effective.
IRC (Iterative Relaxation of Constraints) is designed to address
this situation. IRC uses a hierarchical search strategy that
iteratively restricts the search to an increasingly refined
region of C-space. This is achieved by "relaxing" the feasibility
criteria (thereby making the problem easier) so that the planner
(in our case a PRM) is able to solve the relaxed version of
the problem.
Later, the solution of the relaxed version is modified so that
it meets the feasibility requirements of the original problem.
Algorithm
IRC is based on the principle that in some cases an approximate
solution for a given problem can help us solve the original problem.
For example, reducing the size of the robot
(Figure 2(a))
would reduce the size of the C-space obstacles
(Figure 2(b)).
Although a solution in this new space may not be valid for the
original problem (Figure 2(c)), we can
obtain a solution by fixing the invalid portions of the
approximate solution.
The potential for performance gains comes because we can restrict
our exploration to the regions where the solution is difficult.
That is, this technique assists us in identifying the easy and
difficult parts of the problem and allows us to neglect entire
regions of the space in our search (Figure 2(d)).
By defining a hierarchical set of feasibility constraints, this
approach yields an iterative process which starts
with the least constrained problem and progressively tightens the
constraints until the fully constrained problem is obtained.
That is, we first relax the feasibility constraints for a given
problem and find a solution to this problem ( approximate
solution). Next, we check if this solution applies for the problem
with strengthened constraints.
If not, we improve the solution until it is valid for these new
constraints ( improving solution). This process of
strengthening and improving the solution is repeated until a
solution to the original problem is found (or the iteration limit
is reached).
A block diagram illustrating our approach is shown in
Figure 3.
Figure 3
|
Movies
 |
20-link (25 DOF) robot moving in a narrow environment. (MPG 4.4MB)
|
 |
98-link (103 DOF) closed chain moving . (MPG 1.1MB)
|
Papers
Iterative Relaxation of Constraints: A Framework for Improving Automated Motion Planning,O. Burchan Bayazit, Dawen Xie and Nancy M. Amato,In Proc. IEEE Int. Conf. Intel. Rob. Syst. (IROS) , August 2005, To Appear. (pdf)
Solving Motion Planning Problems by Iterative Relaxation of Constraints,O. Burchan Bayazit,PhD Dissertation, Department of Computer Science, Texas A&M University , May 2003. (pdf)
|
