page 735

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 andWesley (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 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 crosssection 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.

page 736

Figure C.3 Joint Configuration Space for two Revolute Joints

A2

-180

0

180

180

A2

0

A1

A1

-180

Start State

Joint Space Map (in degrees)

	A2	180
-180	0		180
	S	G
			A1
			0
			-180

Goal State	Path in Joint Space

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 minicomputer 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 Octtree, 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

page 737

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