1.11.1 TRANSFORMED SPACE : CARTESIAN CONFIGURATION SPACE
The Configuration Space method was popularized by Lozano-Perez and Wesley (1979), and was clarified later by Lozano-Perez (1983). The technique of Lozano-Perez and Wesley has become a very popular topic in path planning and is worth an exhaustive discussion. The method provides a simplified technique which will allow movement of one object through a scattered set of obstacles. This is done by simplifying the problem to moving a point through a set of obstacles. The major assumption of this technique is that the objects do not rotate and obstacles are all fixed convex polygons. The obstacles must be fixed to limit the complexity of the solution.
Figure C.1 Configuration Space (Find Space & Find Path)
The basic concept involves shrinking the moving object to a single reference point. This is done by growing the obstacles so that their new area covers all of the space in which the object would collide with the obstacles. After the determination of configuration space the problem is then reduced to moving a point through an array of obstacles (i.e.. through the free space).
Unfortunately, a set of obstacles which have been grown are good only for an object which has no rotation throughout its path. This problem is not insurmountable, and may be over come by creating a special representation of the moving object which identifies free space for the object to rotate in. This object will be a convex hull shaped to cover the area swept out when the block rotates about the reference vertex. The convex hull is used to grow the obstacles in configuration space, to find a possible rotation point. Then the path is planned by, finding a path to the rotation point in the first orientation, and a path from the rotation to the goal in the second orientation. The path may also be broken up into more than one rotation, as need demands. Each of these configuration space maps at different orientations are called slices. As seen in the Figure A.4, this has the potential of eliminating some potential paths, or complicating the problem.
Figure C.2 Object Rotation in Config Space
The algorithmic technique which Lozano-Perez suggests is a two step solution to the ’Spatial Planning Problem’. His solution covers two main algorithms, Findspace and Findpath. He compares the Findspace algorithm to finding a space in a car trunk for a suitcase. This is the part in which the obstacles are grown to two or three dimensions, rotations are accounted for, and degrees of freedom are considered. At this point is should be considered that the tendency is to work in cartesian coordinates, but use of other representations could simplifiy the object expansion, and the conversion to a VGRAPH. The Findpath problem is comparable to determining how to get the suitcase into that empty space. The Findpath algorithm determines the best path by finding a set of connecting free points in the Configuration Space. To do this a simple three step process has been used. The objects are first grown, and then a set of vertices for each is determined. Next the vertices are check for visibility (ie. can they be seen from the current point?) and a VGRAPH is constructed, and finally a search of the VGRAPH yields a solution. This is a good example of the problem solving techniques of artificial intelligence.
It is very obvious that the technique is not very advanced by itself. There has been some expansion on advanced topics, and these will be discussed below. Another consideration is the addition of a three dimensional setting. This becomes a much more complex problem because of the need to deal with deriving the hulls, locating intersections, finding enveloped points in space. When we expand to three dimensional space the algorithm is still attempting to navigate by corner vertices. In three dimensional trajectories the best paths are usually around edges of objects. A trick must be used to make the search graphs recognize the edges. The trick used is each edge is subdivided from a line with two vertices into a number of smaller lines (with a maximum length limit) and a greater number of vertices. This obviously does not ease the calculation time problem in three dimensions. Another trick is to use care points, located either inside or outside the objects, and then use these as points which require precise calculation nearby, and allow crude calculation when distant.
We must also consider the complexity introduced when a multi link manipulator is to be moved. Our object now becomes a non-convex hull, or a set of convex hulls, possibly represented as the previous slices represented rotations.
An alternate development of the configuration space method was done by R.H.Davis and M.Camacho [1984], which implements the Lozano-Perez methods in Prolog under UNIX. They basically have formulated the problem using the A* search, with a deeper development of the Path Finding Heuristics. Another variation on the Configuration Space Method was that of R.A.Brooks and Lozano-Perez [1985]. Configuration space was sliced and then broken into cells which could be full, half full or empty. From this representation a connectivity graph would be produced, and the A* search would be used to find a path, This technique required alterations to both the FindPath and FindSpace routines. This technique does allow rotations ( but the run time is in the order of tens of minutes on an MIT LISP machine).
An approach for using Cartesian Configuration Space on a Stanford Manipulator (1 Prismatic Joint) was proposed by J.Y.S.Luh and C.E.Campbell [1984]. This method had to consider both the front and the rear travelway for the sliding prismatic link. To do this the manipulator was shrunk to a point, and the rear obstacles translated to the ’front workspace’. The method also makes use of an algorithm for converting non-polygonal shapes to good approximation convex polygons. There were no statistics given with this method.
Configuration Space was used by J.Laumond [1986] to do planning for a two wheeled mobile robot. This method was successful in using configuration space to find paths from some very difficult problems. The best example given of the success of this technique is the Parking Spot problem. In this case the wheeled robot is very similar to an automobile which is stuck between two other parked cars. To get out the robot had to move in both forward and reverse directions to manoeuvre out of the ’tight spot’.
As for evaluating the overall success of this technique, the computational limits are the major concern. Lozano-Perez, claims success in a laboratory setting with his configuration space path planning routines on a seven degree of freedom manipulator. But he does not note his execution speed, nor does he describe his results quantitatively. This technique was implemented previously by Udupa (1977) for computer control of manipulators. His experiment used a robot with three approximated degree of freedom, in three dimensions. Because of the three degree of freedom limit, the robot was limited in cluttered environments, and had to depend upon some heuristics. His technique also made use of a variable description of space, using recursive addition of straight paths. The recursive determination of paths has some of the same drawbacks that the swept volume method has, and this is what Lozano-Perez and Wesley overcame with their graph search method. This technique is very useful for planning 2 dimensional paths, based on the easy and speed of calculation. There is also no doubt that this technique could be made to work with a more complex robot path planning problem, but the computational speed would be a major factor. Lozano-Perez and Wesley (1979) implemented their algorithms on an IBM370/168 in PL/1. This technique does not handle rotations well, and the result may be a non-optimal solution, or possibly even no solution. The algorithm will provide the shortest distance path, with collision avoidance, but it may not produce continuous paths. Lozano-Perez (1983) also discusses his algorithms in depth which means that his methodology is easy to incorporate in other projects.
1.11.1.1 - TRANSFORMED SPACE :
A CARTESIAN CONFIGURATION SPACE APPLICATION
A use of the Configuration Space method was made by C.Tseng, C.Crane and J.Duffy [1988] for a good solution to the pick and place problem. The objects as 2.5D in the environment by represention as upward extruded polygons. First the objects are grown to compensate for the cross-section of the manipulator. The manipulator arm is then ’lifted up’ to ensure clearance of all the objects in its path. This method may fail in the presence of very tall objects. The method was implemented on a VAX 750 and could find paths in cluttered workcells in under 2 seconds.
