page 699

Optimization methods are typically slow, and thus the three dimensional path planning problem will have to be solved off line for now. If a good fast solution is discovered for this problem, it will eliminate the need for the 2D and 2.5D problems.

40.2.3 COLLISION AVOIDANCE

Collision detection is the most important factor of Path Planning. Without automatic collision avoidance, the robotic workcell must be engineered to be collision free, or sub-optimal paths must be chosen by a human programmer. Local Collsion Detection is important when moving through an unknown, or uncertain environment. These allow for feedback to the planner, for halting paths which contain collisions. Global Collision Avoidance may be done for planning paths which should avoid objects by a certain margin of safety. The actual detail of the method may vary, but moving close to obstacles is avoided by these methods.

Figure 2.3 Collision Avoidance

Goal

No Collision Avoidance

Start	Collision
	Goal

Local Collision Avoidance

Start Collision

Goal

Global Collision Avoidance

Start

40.2.4 MULTILINK

One problem that tends to paralyse most methods is the expansion to multilink systems. The first implementation of most techniques is made with a simple mobile robot. When the method is

page 700

increased by adding oddly sized links, and then a payload, the complexity grows at a more than exponential rate.

The number of degrees of freedom also play in the applications of the robot. If a manipulator has 6 degrees of freedom, then it can obtain any position or orientation in space. Some specific cases of problems require only 3 or 4 degrees of freedom. This can be a great time saver.

When an environment becomes cluttered then it may be desirable to have a higher number of degrees of freedom than six, so that the redundancy of the robot can move through the environment. The complexity of most routines increases exponentially with the number of degrees of freedom, thus it is best to match the manipulator degrees of freedom to the complexity of the task to be done.

One assumption that helps reduce the problem complexity is the approximation of motion in a single plane. The net result of this effort is that the robot is reduced to 2 or 3 degrees of freedom. The payload may also be neglected, or fixed, and thus the degrees of freedom are reduced. A second approach is to approximate the volume of the links swept out over a small volume in space. This volume is then checked against obstacles for collisions. A payload on a manipulator may sometimes be approximated as part of the robot if, it is small, or it is symmetrical. This means that the number of degrees of freedom for a manipulator may be reduced, and thus the problem simplified in some cases.

page 701

Figure 2.4 Multi-Link Approaches

Real Work Space (with payload)

Simple Degree of Freedom Reduction (this has only 2 d.o.f.)

Approximated Volumes (of lower arm and payload)

Multilink manipulators also come in a variety of configurations. These configurations lend themselves to different simplifications, which may sometime provide good fast solutions in path planning.

-Cartesian (i.e. X, Y, Z motions)

-Cylindrical

-Spherical (Stanford Manipulator)

-Revolute (Like Human arm)

-Scara

The various robot configurations are fundamentally different. Many approaches have tried to create general solutions for all configurations, or alternate solutions for different specific manipulators. The fastest solutions are the ones which have been made manipulator specific. With a manipulator it is also possible to describe motions in both Joint Space (Manipulator Space), and Cartesian Space (Task Space). There are approaches which use one, or both of these.

page 702

40.2.5 ROTATIONS

Rotations are another problem for some path planners. It can be difficult to rotate during motion, thus some will not rotate, some will rotate only at certain ’safe’ points, and some will rotate along a complete path. The best scenario is when rotations may be performed to avoid collisions, and not just to meet the orientation of the goal state.

Figure 2.5 Payload Rotation

goal

No Rotation

start

goal

Rotations at Points

rotation

point start

goal

Rotation Along Path

start

40.2.6 OBSTACLE MOTION PROBLEM

Motion of obstacles can cause significant path planning problems. Motion occurs in the form of rotation, and translation. In most path planners the only motions considered are for the payload and manipulator. In most cases an obstacle in the environment will experience both rotation and translation. This has devastating effects on all of the path planning methods, because some tough