Version 1.0, August 31, 2001, Copyright, Hugh Jack 1993-2001
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.