Kk. Gupta et Zp. Guo, MOTION PLANNING FOR MANY DEGREES OF FREEDOM - SEQUENTIAL SEARCH WITH BACKTRACKING, IEEE transactions on robotics and automation, 11(6), 1995, pp. 897-906
In [7], we presented a sequential framework to develop practical motio
n planners for manipulator arms with many degrees of freedom. The crux
of this framework is to sequentially plan the motion of each link, st
arting from the base link, thereby solving n single link problems (eac
h of which is solved as a 2-D planning problem) instead of one n-dimen
sional problem. The solution of each single-link problem is based on t
he search of a visibility graph (V graph) constructed from a polygonal
representation of forbidden regions as seen in successive 2-D t(i) x
q(i) spaces. In this paper, we present a backtracking mechanism within
this sequential framework to make it more effective in planning colli
sion free paths in cluttered situations. The essence of the backtracki
ng mechanism is based on an edge deletion mechanism that modifies the
V graph in t(i-1) x q(i-1) space if no path is found in t(i) x q(i) sp
ace. The level of backtracking, b, i.e., the number of links the plann
er backtracks is an adjustable parameter that can trade off computatio
nal speed versus the relative completeness of the planner. Incorporati
ng such a backtracking mechanism has significantly improved the perfor
mance of planners developed within this framework. We present extensiv
e experimental results with up to eight degree-of-freedom manipulators
in quite cluttered 3-D environments. Although the planner is not comp
lete, our empirical results are very encouraging. These empirical resu
lts indicate that b can be chosen small-typically 2 or 3-in over 90% o
f the cases. These results show that our approach would be useful in p
ractice.