page 722

Figure 7.1b A Comparative Chart of Path Planning Methods

Machine

Rotation

Solution

Method

Space

& Time

Setup

Optimize

Type

Comments Multilink

Oct-Tree

3D

Perkin

yes

Solid

Distan

Searc

Has

Yes

(Faverjon,

-Elmer

Primitiv

ce &

h of

Potentia

1986)

under 1

es from

Avoidanc

Oct-

l in CIM

minute

custom

e

Tree

System

CAD

2D

yes

No

Potential

or 3D

SUN

Poly

This

Field

260, 10’s

gons or

Avoid

3

is slow,

(Y.K.Hwang,

of

Polyhed

ance &

Findpat

but it

N.Ahuja, 1988)

minutes

ra

Distance

h

produce

yes

routines

d some

Yes

2.5

in

good

Configuarati

D

VAX

Potentia

paths.

40.8 CONCLUSIONS

This is the most interesting section, but unfortunately, very vague. In the next few years Powerful computer hardware advances will allow low cost, but extremely powerful operations. This will make many memory intensive path planning methods feasible, the very complex operations will now be reasonable for calculation. If computers become powerful enough, then an expert path planning system would be a definite asset, making the robots flexible over a number of different frontiers, without any programming. The advance of customized computer hardware which now does graphics indicates that it is very feasible to convert complex robotic path planning from a software to a hardware domain. The potential of parallel processing also opens doors to solving very complex and involved problems.

A good direction for robotics research is to allow a path planning system which will combine the various problems and solutions. This will allow the robot to switch modes with an expert system and thus chose the solution to fit the problem, and not try to make the problem fit the solution, as is commonly done now. This would involve the use of rules and heuristics (based on the elements discussed in this paper) to build up a very complex and complete path planner from very simple methods (which are currently being researched). The multi-level path planning strategies are seen to also hold promise for robotic development (the author prefers the Dynamics Path Planning approach). These approaches allow the best of all planning methods.

40.9 APPENDIX A - OPTIMIZATION TECHNIQUES

Optimization involves modelling a system as a function of some variables, then deriving some cost, or measurement of performance from it. The variables are then adjusted to get the best measure of performance out. These methods give the best results, but they can be tricky to set up,

page 723

and they can be very slow.

40.9.1 OPTIMIZATION : VELOCITY

By optimizing the manipulator velocity the path time can be reduced, and the robot used to its full ability. One approach was made by S.Dubowsky, M.A. Norris and Z.Shiller [1986]. The thrust of their research was production of a Path Planning CAD System called OPTARM II. Their program will produce a path which is made up of smooth splines. The optimization is done to keep either the maximum or minimum torque on the robot actuators. Their success was in producing path within 5% of optimal value based on collision avoidance and motion limits on the joints. For a six degree of freedom manipulator the program produces smooth motion on the microVAX in a few minutes of CPU time, which will give optimal paths up to twice as fast as the constant velocity method for path motion.

A different approach to the velocity optimization problem was taken by B.Faverjon and P.Tournassoud [1987]. A fast method was found for finding distances of separation between objects in space. The world was modelled as geometrical primitives, and the primitives could be used to represent the world to various depths of complexity.

Figure A.1 Various Levels of Geometrical Representation

Using the distance of separation in a function for a velocity damper, the collisions were incorporated as a constraint. When the cost function was optimized for velocity the tendency was to avoid obstacles where velocity was damped. This method was also made to work with moving objects.

This method was intended for use with a 10 link nuclear manipulator, and it has been implemented on a SUN 3 computer. The actual run time was not given, but the routine ran at a tenth of the speed possible with the manipulator. The manipulator was said to have approached objects to within 1 cm.

40.9.2 OPTIMIZATION : GEOMETRICAL

A different approach based on the calculus of variations has been developed by R.O.Buchal and D.B.Cherchas [1989]. The techniques use convex polygons to represent objects, and an iterative technique to find the best path which avoids these polygons. The path is subdivided into

page 724

a number of smaller intervals, linking a set of pre specified via points. Convex hulls are used to represent the volume swept out by the motion of the moving object. The penetration depth, and penetration vector, are used to correct the path for each of the individual path segments.

Figure A.2 Path Segment Interference

obstacle

d

Approximating

Convex Hull

The penalty function is formulated as to consider the limits on the joints and actuators. The optimization routine is used to correct the path segments, and this procedure takes about 1 minute on a VAX 11/750 for a 2D model, with manipulator considered, without manipulator collisions. The main objective of this routine is to minimize time. This method needs a set of path points specified for good solutions, and this is a potential area of research.

40.9.3 OPTIMIZATION : PATH REFINEMENT

Some methods provide very rough paths containing jerky motions. To smooth the jerks in paths (as a post processor), a method was suggested by S.Singh and M.C.Leu [1987]. Using the technique of Dynamic Programming, time and energy for a given path are minimized. This method does not account for collisions, but is intended to just be run Off-line. A control strategy is suggested for the manipulator to use on the resulting path. Even though the performance of this method is not given, it looks like a good addition to any a priori programming strategy.

40.9.4 OPTIMIZATION : MOVING OBSTACLES

Every environment has something moving. To consider this problem B.H.Lee and Y.P.Chien [1987] suggest a method for off-line optimization of this problem. Unfortunately this method was not implemented, thus the success of the technique is unknown. The first constraint is a maximum time for motion, this is to force movement before iminent collision and also to force speed in the path. A constraint is assigned to the priority of the obstacle, which usually has first priority on the path. The constraints of start and stop points are also used. Collision constraints are also used,