Motion planning for branching articulated figures with many degrees of freedom

The goal is to find a collision free path for three-dimensional anthropometric linkages within a cluttered environment. The linkages are characterized by having a large number of redundant degrees of freedom and a branching tree structure. The motion planning problem for articulated linkages have been investigated by researchers in robotics for a long time. Different algorithms have been presented over the years that made use of different heuristics to cut down the complexity of the problem. However, most of these algorithms handle robots with relatively few degrees of freedom (DOFs), like the mobile robots (3 DOFs) and the arm-like (PUMA) robots (6 DOFs). It is only during the past few years that algorithms have been presented that handle robots with many degrees of freedom. Nevertheless, the issue of managing a branching structure is not explicitly considered in these algorithms. Our algorithms resolve all of the issues involved when dealing with these types of redundant branching articulated figures. It is well known that the motion planning problem is a PSPACE-hard problem. The best exact algorithm found so far is exponential with the number of degrees of freedom in the figure. Our approach is to divide up the DOFs into groups. We plan the motion for the DOFs involved in each group in a sequential manner. The motion computed for each group depends on the path computed for the preceding group. We adopt a depth first order in traversing the tree structure. The branching structure of the figure raises specific issues which are addressed by our algorithms. The strength factors are considered by incorporating terms that correspond to comfort, energy and fatigue directly into the search function so that the final path obtained will be one that obeys the strength limits and desired comfort levels. The collision avoidance algorithms are being implemented in the Jack environment developed at the Computer Graphics Laboratory at the University of Pennsylvania