 |
 |
 |
| |
|
|
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, 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.
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 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.
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, with every object represented as a sphere. The Cost function considers smoothness of the path, and the torque of the actuators, to ensure that the robot is not overstretched.
40.9.5 OPTIMIZATION : SENSOR BASED
An interesting approach to path planning was suggested by B.Espiau and R.Boulic [1986]. In the attempt to find a path planning method for a 10 degree of freedom manipulator, they came up with an unusual approach to optimization. With proximity or contact sensors mounted on every link of the manipulator, the path was navigated. To do this the sensor data would be used alter the penalty functions to represent detected obstacles encountered by the manipulator. The cost function was based on velocity and dynamic functions. This gave a dynamic approach to finding paths in which the path was found by the local optimization of trajectories. For this particular method a large number of sensors are required, and unfortunately the authors did not provide statistics about the performance of the method.
40.9.6 OPTIMIZATION : ENERGY
In a method suggested by M.Vukobratovic and M.Kircanski [1982] the energy of the system was proposed as an excellent method for path planning. Using the techniques of optimization for energy the best path is found. This is done by calculating the dynamics at certain points in space, and then using the dynamic programming technique (of operations research) to find the best path. This technique runs a few minutes on a PDP11/70. The end effector is ignored in this method as negligible. This method is only intended to smooth paths, so that the stresses on the load and manipulator are decreased. The information provided on this method was not very complete.
| |
|
|
