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