1.12.1 SPATIAL PLANNING : STEEPEST DESCENT
In an attempt to find a fast path planning method, the steepest descent method was proposed by P.W.Verbeek, L.Dorst, B.J.H. Verwer, and F.C.A. Groen [1987]. Their method is an array based method which will take the workspace represented polygons. This array is a two dimension representation of space in which the goal position is represented with a zero value, and the objects are represented with a value of infinity. Each element of the array is considered in a series of iterations over the array. The result of these iterations is a map of a ’height’ with respect to the goal state. The method then just follows the steepest gradient, down to the goal state.
Figure D.1 Steepest Descent Representation and Path
This method has been implemented for a 2D multilink manipulator, but it uses 4 Mbytes of memory for a workspace resolution of 32 by 32 by 32. On a 12 MHz, 68000 VME computer system the whole process takes about 12 seconds. This is broken up into a 6 seconds for detection and labelling of forbidden states, a 6 second generation of distance landscape, and less than a second for finding the shortest path by steepest descent.
1.12.2 SPATIAL PLANNING : POTENTIAL FIELD METHOD
When considering that the basic thrust of the path planning methods is to avoid obstacles, it is easy to compare this avoidance to repulsion. The basic concept of repulsion is based on potential fields, as thus the potential field method of W.T.Park [1984]. In particular, the method was directed towards a workcell with multiple manipulators. In this setting there is a problem with potential manipulator collisions, which must be considered when path planning. To do this a planar view of the work cell is created, and the arms are given a potential. The potential repulsion of the manipulators is mapped for a number of various joint and slider positions. In the work of Park, a manipulator with two revolute joints, and a Stanford manipulator is used. Both of the manipulators have two degrees of freedom, thus a number of two dimensional arrays are necessary to fully describe the work space. This memory requirement is very large, and thus is one of the drawbacks of this technique. The Even with the use of compression techniques, the arrays still consume over 100 KBytes each. In the experimental implementation, the computer used was a VAX 750. The problem was constrained to 4 d.o.f., which used 2 MBytes of memory, and took 8 hours of computation time, to calculate about a million combinations. This method may also get caught in cul-de-sacs. The bottom line on this method is it highly oriented to batch and workcell operations, but too staggering to consider for use in a practical system.
In a more complex vein, Y.K.Hwang and N.Ahuja [1988] have developed a method using polygons and polyhedra to represent objects, from which a potential field is generated. First general topilogical paths are found from valleys of potential minimums. The best of these paths is selected, and three FindPath algorithms are used to refine it, until it is acceptable. The first algorithm moves along the path and reduces potential numerically. Second, a tight fit algorithm is used for small pathways. Lastly, an algorithm which will move off the given path if necessary is used, as a last resort. This method has been implemented to run on a SUN 260 for a ’Piano Movers Problem’. The total runtime is in the tens of minutes, and it does fail in certain cases.
To avoid becoming trapped when using this method, another approach was developed to mapping the potential field by P.Khosla and R.Volpe [1988]. They have developed an alternate approach which avoids the local minima found in traditional potential field methods. To do this they have used superquadratic approximation of the potential fields to drop off from obstacles swiftly. The superquadratic is used to have a gradual slope to the goal, thus to make sure that its effect is more wide spread than the obstacles. The results which they have obtained are not described, but they have written a program which will work with a two link manipulator, ignoring link collisions.
