Shortest Path Problem in the Plane with Obstacles: Bounds on Path Lengths andShortest Paths Within Homotopy Classes

摘要

The problem of finding the shortest path between two points in the planecontaining obstacles is considered. The set of such paths is uncountably infinite, making an exhaustive search impossible. This difficulty is overcome by reducing the size of the search space. The search is first restricted to a countably infinite set by focusing attention on the set of homotopy classes. By applying simple optimality principles, we obtain a finite list of such classes whose union contains the shortest path. This process of simplification is discussed in the thesis of Capt Kevin D. Jenkins, U.S. Marine Corps. In this thesis we first discuss a computational investigation of two methods by which homotopy classes can be named. Next, a computational heuristic is presented that finds the lower bound for a path in a class. Finally, the true shortest path is found by searching these classes in order of increasing lower bound. One application of this study is in the area of robotic path planning.