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