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