Some methods find it beneficial to transform the representation of space, so that it simplifies the search for the path. These methods may often be based on Spatial Planning, or any other technique, but they all remap space. These methods are usually very inflexible after mapping, and all environmental changes requires a remapping.

40.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.

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.

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.

40.11.1.1 - TRANSFORMED SPACE :

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.

40.11.2 TRANSFORMED SPACE : JOINT CONFIGURATION SPACE

The Cartesian Configuration Space Method uses a check for which particular points in space are free, and then chooses a free path through. This is not very useful when expanding to a multilink manipulator. Thus an approach has been formulated to determine which points in joint space are collision free. This method was formulated by W.E. Red and Hung-Viet Truong-Cao [1985]. This method was applied to manipulators with two revolute joints, and to a robot with one revolute and one prismatic joint. This method works best with two joints, and expansion to three joints requires more computation time. Thus this solution is ideal when the robot is operating in a 2D planar configuration. The effect is a setup time of 2 to 5 minutes, and then 15 seconds for any solution after the initial setup.

This technique has some definite advantages in the speed of solution. Resolution errors occur due to the resolution of the configuration space map. This table can only be used for the motion of two joints, the third increases the complexity exponentially, but it is still ideal for some batch processing applications.

40.11.3 TRANSFORMED SPACE : OCT-TREES

An interesting method created by B.Faverjon [1986] is to constructively model solid objects (via a custom CAD program) and then generate an Oct-tree representation of joint space from these. The A* search is used to find trajectories in the Oct-tree. This method works in cluttered environments for pick and place operations. The method was solved on a Perkin-Elmer mini-computer in under a minute.

40.11.4 TRANSFORMED SPACE : CONSTRAINT SPACE

K.L.Muck [1988] tried a different sort of mapping technique. Space is represented in an Oct-tree, with the Oct-tree representing robotic motion constraints in the environment. A connectivity graph is then generated from the Oct-tree and the A* search is used. The main thrust of this routine is to reduce the problem to solving the specific motion constraints which apply to the current condition. This technique was implemented for a single link manipulator in a convex hull environment.

40.11.5 TRANSFORMED SPACE : VISION BASED

Some of the potential of Spatial Planning is exposed in some of the current research. To allow the development of vision for use in the field of path planning, E.K. Wong and K.S. Fu [1986] have done some research. This research allows a path planning method to be run with three views of a work cell, and from these three views deduce the maximum filled volume. Once the information from the vision system has been interpreted to provide the basic world model, then the objects may be grown into configuration space for an arbitrary moving object. The three views of the object then may be examined from each of the three views, to determine the free path. This premise is based on the idea that if a clear path is visible in one view, then it is a clear path in three dimensional space. This technique uses oct-trees for the representation of space, thus the technique may be very efficient (depending upon the resolution of the oct-tree). This method was implemented on a VAX 11/780 to find a path for an obstacle in three space in 1 to twenty seconds (depending upon the oct-tree search depth). This had not been mated to a vision system in the cited paper.

40.11.6 TRANSFORMED SPACE : GENERAL INTEREST

E.Palma-Villalon and P.Dauchez [1988] came up with a method to do fast path planning for a mobile robot. Rectangles are used to represent obstacles, and the moving robot is represented with a circle. The obstacles are grown by the radius of the circle (into configuration space). A map is created with a course resolution is made to indicate which objects are present in a grid box.

This map only indicates an objects presence, the remainder of the information is kept in a concurrent list. By finding and using a series of holes and walls within the grid an A* search is applied to find the best path. The cost function of the search is based on the path length and the number of turns made. The performance of this method is not stated, and thus no basis for comparison is available. This method provides straight line path segments. The mapping to configuration space could be convenient for the first pass of a path planner for general path finding.