PRACTICAL GLOBAL MOTION PLANNING FOR MANY DEGREES OF FREEDOM - A NOVEL-APPROACH WITHIN SEQUENTIAL FRAMEWORK

The sequential framework is a paradigm for developing practical motion planners for manipulators with many degrees of freedom (dof). The ess ence of this framework is to exploit the serial structure of manipulat or arms and decompose the n-dimensional problem of planning collision- free motions for an n-link manipulator into a sequence of smaller m-di mensional sub-problems (with backtracking), each of which corresponds to planning the motion of a sub-group of m - 1 links along a given pat h. In this article, we present a novel approach within the sequential framework to develop practical motion planners for many-dof arms. In t his approach, each sub-problem (m = 2) is solved by using numerical po tential fields defined over bitmap-based representations of the 2-dime nsional sub-spaces. Furthermore, an efficient backtracking mechanism b ased on a novel notion of virtual forbidden regions in these 2-dimensi onal sub-spaces is presented. This approach leads to much more efficie nt and robust motion planners than a previously reported visibility gr aph (in the 2-dimensional subspaces) based implementation. We have con ducted extensive experiments for arms with up to 8 dof in both 2-D and 3-D workspaces. Although it is not complete, the planner always succe eded in hundreds of simulations with only a few levels (less-than-or-e qual-to3) of backtracking. (C) 1995 John Wiley & Sons, Inc.