Shortest paths avoiding polyhedral obstacles in 3-dimensional euclidean space

Algebraic and geometric algorithms are presented to solve the general and some specific instances of the following problem which is known as FINDPATH in artificial intelligence: "Given a set of polyhedra and two external points (source and goal), calculate the shortest path between these points under the Euclidean metric, constrained to avoid intersections with the given polyhedra." The shortest path is a polygonal path connecting the source and the goal, possibly bending at some edges of the given polyhedra while subtending equal entry and exit angles. The general problem can then be solved exactly using symbolic algebra and is based upon finding the real roots of a system of non-linear equations (stating the angular equality conditions) by elimination. If approximate solutions are acceptable this can also be done using numerical methods such as continuation, or using optimization methods to minimize a sum of square roots (expressing the length of the shortest path). In addition, two special cases are solved where there exists a single convex polyhedron, and the source and the goal are on its boundary or exterior. These solutions make use of planar developments of polyhedra and polyhedral visibility. Two Voronoi-based locus methods are also introduced to solve FINDPATH. These methods use preprocessing to speed up subsequent searches for a shortest path. The first method partitions the boundary of a convex polyhedron given only the source on it so that, for a later goal on the boundary, the shortest path is found efficiently. It makes use of standard point location algorithms for a straight-edge planar subdivision once the partitioning is done. The second method, currently more of a descriptive nature than algorithmic, is based on W. R. Franklin's "Partitioning the Plane to Calculate Minimal Paths to any Goal around Obstructions" Tech. Rep., ECSE Dept., Rensselaer Polytechnic Inst., Troy, NY, Nov. 1982 , and for a given source, partitions the free space around polyhedra into regions (bounded by high-order surfaces) so that the shortest paths for all goals in a given region follow the same sequence of edges of the given polyhedra. This method makes use of a recent spatial point location algorithm for arbitrary algebraic varieties. Finally, an overview of a workbench (called SP) which implements some of the above and thus allows experimentation with shortest paths is given.