1.10.1 SPATIAL PLANNING : SWEPT VOLUME

Lozano-Perez and Wesley (1979) discuss a generate and test strategy used for path planning. The technique will begin with a straight line from start to goal, regardless of collisions. Then a repetitive cycle of analysing a path (by detecting collisions on the path with Swept Volumes) and then using the information to generate an improved path.

This method may be more formally described with a set of steps. The first step is to check the validity of the proposed path. The path validity is found by considering volume swept out as the object moves along the path. If a collision is not detected the method will be halted. In the case of collision, the information about the collision will be used for correction of path. This information used may include details about the collision, like shape of intersections of volumes, the object causing collision, depth of penetration, and the nearest free point.

The difficulties of this solution become obvious when some of the intricacies of the problem are considered. Models of complex surfaces can contain a very large number of simple surfaces. Calculating the intersections of these numerous simple surfaces can be a very difficult task. A second problem is how we may determine a global optimum when only local information about obstacles at collisions is made available. With the local information about collisions being used in path correction, radical different options are ignored. These two problems could result in an expensive search of the space of possible paths with a very large upper bound on the worst case path length.

Figure B.1 Swept Volume Path Planning

1.10.2 SPATIAL PLANNING : OPTIMIZATION

Lozano-Perez and Wesley [1979] describe their work (see Cartesian Configuration Space) as being an improvement over the Optimization Technique of Spatial Planning. The basic concept they describe, is to explicitly compute the collision constraints on the position of a moving object relative to other obstacles. The trajectory picked is the shortest path which will satisfy all of the path constraints.

With objects modelled as convex polyhedra, vertices of the moving object may move between the obstacle surface planes and collide. This condition is easy to detect, because if a vertices is outside any plane of an obstacle, there is no collision. One possible simplification is to use a circle to represent the objects geometry, and just maintain a radial clearance from all objects. It should also be noted that the circular geometry is not sensitive to rotation. This was the path planning technique used in a mobile vehicular robot called SHAKEY by N.J.Nilsson [1969].

Figure B.2 Spatial Planning - Optimization

1.10.3 SPATIAL PLANNING : GENERALIZED CONES

Generalized cones [R.A.Brooks, 1983] are a faster approach than the Cartesian Configuration Space method . These cones are achieved through a special representation of the environment. The surfaces of convex polygons are used to determine conically bounded pathways, for the path of the object being moved. The method of determining free pathways (or Freeways) is based on the use of cone shaped spaces. The cones fit snugly between objects and have spines that run along the centre of the cones. These spines are the paths that the object may travel along. This makes the method inherently 2D and thus has not been implemented in 3D as of yet, but it has spawned a method which is successful in 3D by Brooks[1983]. To determine which spines to follow, the author uses the A* search technique to explore the various paths along the spines. This leads to problems in cluttered spaces where certain possible paths may be overlooked by the generalized cones. This method chooses a path with considerable clearance of objects.

Figure B.3 Problem Represented with Generalized Cones

Figure B.4 Problem Represented with Generalized Cones

As can be seen the rotation with this technique is very restricted, and the object is typically oriented with the spine.

1.10.4 SPATIAL PLANNING : FREEWAYS

A follow up to R.A.Brooks [1983] research into the use of Generalized cones for the representation of Free Space, R.A. Brooks [1983] developed a method of path planning for manipulators with 5 or 6 d.o.f. motion. This method is able to solve the pick and place problem in under a minute on an MIT Lisp machine, by approximating the robot as a 4 d.o.f. manipulator. His method is based on the assumption that the world is represented as supported, and suspended, prisms. This method is suggested as a possible precursor for the use of video information about the workcell, from a high level vision system. This has two points of interest; the objects which are suspended from the side will be grossly misrepresented, but this form of encription suits video cameras well. The assumption that the manipulator may be treated as a set of 4 d.o.f. is based on the limitation of the problem to only pick and place operations and insertion (or fitting) operations. This unfortunately means that the objects may only be rotated about the vertical axis when in motion.

The use of Freeways between obstacles allows a choice between alternate paths.

Figure B.5 Freeway Between Blocks

The freeways are basis for maps of joint configurations which are acceptable for motion through these freeways. The methods then find the path using link constraints. This method is described in algorithm form, and the algorithms are quite substantial.

1.10.5 SPATIAL PLANNING : OCT-TREE

In a paper by T.Soetadji [1986] a method for 3D path planning by a mobile robot is suggested. The method is based upon use of an Oct-tree representation of 3D space. In the paper, the development of the Oct-Tree routines is discussed, and a robotic system for implementation is suggested. Once the Oct-tree is set up, an A* or a Breadth First search is used to find the best path for the mobile robot. This method finds the minimum distance (with collision avoidance) on a VAX 750. The search time for the path is on the order of 1 second. The tree structure also proves very efficient, because it had only occupied 1.7 MBytes of memory for a very complicated environment.

1.10.6 SPATIAL PLANNING : VORONOI DIAGRAMS

A newer approach to representing space has been done with Voronoi Diagrams. O.Takahashi and R.J.Schilling [1989] have suggested such a method. Using an environment of polygons, the pathways may be represented with Voronoi diagrams, then represented in a graph.

Figure B.6 Voronoi Diagram of Simple Work Space

After the Voronoi diagram has been set up in graph form, a path may be found. This is simplified by the use of some heuristic rules for wide paths, tight bends, narrow gaps, and reversing, which identify a number of orientations. This procedure produces short smooth paths (which avoid obstacles) for 2D objects on an IBM compatible computer with no co-processor in 10 seconds to 1 minute. This method has potential for use with vision systems. Algorithms suggested by A.C.Meng [1988] allow for fast udate of Voronoi diagrams, in a changing environment. This makes the operation much faster, by avoiding the complete reconstruction of the diagram, and makes real time trajectory correction feasible.

1.10.7 SPATIAL PLANNING : GENERAL INTEREST

E.G.Gilbert and D.W.Johnson [1985] created an optimization approach to path planning (with the piano movers problem), with rotations and collision avoidance. This method runs 10 to 20 minutes on a Harris-800 computer. This method was based on work which was later published by E.G.Gilbert, D.W.Johnson, and S.S.Keerthi [1987] which provides algorithms for calculating distances between convex (and concave) hulls in a very short time (order of milliseconds).

1.10.8 SPATIAL PLANNING - VGRAPHS

A method proposed by K.Kant and S.Zucker [1988] involves collision avoidance of rectangles based upon the search of a VGRAPH. This method also suggests the use of a Low Level controller Collision Avoidance Module. This controller would use low level information about the environment to behave as if experiencing forces from workspace obstacles. The manipulator would be experiencing a pull to the goal state. This method produces a Kinematic and Dynamic, Time Optimal path. None of the implementation details were given in the paper.

Figure B.7 - Visibility of Corners of Rectangles (VGRAPH)