PLANNING SHORTEST PATHS (COMPUTATIONAL GEOMETRY, MOTION PLANNING, VISIBILITY GRAPHS, DIJKSTRA'S ALGORITHM, VORONOI DIAGRAMS)

Recent research in the algorithmic aspects of robot motion and terrain navigation has resulted in a number of interesting variants of the shortest path problem. A problem that arises when planning shortest collision-free paths for a robot is the following: Find the shortest path from START to GOAL for a point moving in two or three dimensions and avoiding a given set of polyhedral obstacles. In this thesis we survey some of the techniques used and some of our recent results in shortest path planning. We introduce a useful generalization of the shortest path problem, the "weighted region problem". We describe a polynomial-time algorithm which finds a shortest path through "weighted" polygonal regions, that is, which minimizes the sum of path lengths multiplied by the respective weight factors of the regions through which the path passes. Our algorithm exploits the fact that optimal paths obey Snell's Law of Refraction when passing through region boundaries. We also give an O(n('2) log n) algorithm for the special case of the three-dimensional shortest path problem in which paths are constrained to lie on the surface of a given (possibly non-convex) polyhedron. Both algorithms make use of a new technique of solving shortest path problems; we call this technique a "continuous Dijkstra algorithm", as it closely resembles the method used by Dijkstra to solve simple shortest path problems in a graph.