MOTION PLANNING FOR MANY DEGREES OF FREEDOM - SEQUENTIAL SEARCH WITH BACKTRACKING

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.