page 714

directly enter robot motions and directly verify their safety and use tools to optimize the path. This is not desirable for path planning because it is time consuming and inflexible, this is similar to the original method of robot programming with set via points.

40.4.2 PATH PLANNING METHODS

This section will attempt to provide a simple point of view, to classify the path planning techniques available. It should be noted that all of the methods are trying to optimize some feature of the path, but they do not all use classical Optimization Techniques.

The most complete approach to path planning is Optimization. Optimization techniques may be done on a local and global basis. Through the calculation of costs, constraints, and application of optimization techniques, an optimal solution may be determined. Some of the mathematical methods used for the optimization technique are Calculus ofVariations, Trajectory optimization (hit or miss shoot for the goal state) and dynamic programming. The most noticable difference between Local and Global optimization is that Local optimization is concerned with avoiding collisions (it will come very close), and global optimization will avoid objects (make a wide path around, when possible).

The most intuitive approach is the Spatial Relationships between Robot and Obstacles. This approach uses direct examination of the actual orientations to find distances and free paths which may be traversed. It was suggested by Lozano-Perez (1983) that spatial planning "involves placing an object among other objects or moving it without colliding with nearby objects". There are quite a few methods already in existence.

The Transformed Space solutions are often based on Spatial Planning problems, they are actually attempts to reduce the complexity of the spatial planning problems by fixing the orientations of objects. These problems diverge quickly from spatial planning when they use tranformed maps of space. When space is transformed, it is usually mapped so as to negate the geometry of a manipulator. The best known approach is the Cartesian Configuration Space Approach as discussed by Lozano-Perez [1983]. These techniques have different approaches to representing the environment, but in effect are only interested in avoiding objects, by generating a mapped representation of ’free space’ and then determining free paths with a FindPath algorithm.

An alternative to the previous methods are the Field methods. These methods impose some distributed values over space. The Potential Field method is a technique similar to Spatial Planning representations. This involves representing the environment as potential sources and sinks and then following the potential gradient. This technique is slow and tends to get caught in Cul-de-sacs. The Gradient method is very similar to the Potential field method. It uses distance functions to represent the proximity of the next best point. This method is faster than the Potential field method, and it gets caught in Cul-de-sacs.

An approach which is beginning to gain popularity is the use of Controls Theory for path planning. This was done, very sucessfully, by E.Freund and H.Hoyer [1988]. This approach allows the non-linear control of a robot, which includes the collision avoidance for many moving objects, mobile robots, manipulator arms, and objects that may have a variable size. This approach seems to have great potential for use in low level control, in the A Postieri sense.

To be complete, there are some techniques that are uncommon (like path planning with simulated anealing S.Kirkpatrick, C.D.Gelatt, M.P.Vecchi [1983]), or are still in their infancy (like