An algorithmic approach to some problems in terrain navigation

摘要

Recent advances in the field of computational geometry have provided efficient algorithms for a variety of shortest path problems. Many problems in the field of terrain navigation can be cast as optimal path problems in a precise geometric model. With such a model one can develop and analyze algorithms for the solution of the original problem and can gain insights into how to design more efficient heuristics to deal with more complex problems. We examine the path planning problem in which we are given a “map” of a region of terrain and we are expected to find optimal paths from one point to another. This, for example, is a task which must be done repeatedly for the guidance of an autonomous vehicle. We examine how to formulate some path planning problems precisely, and we report algorithms to solve certain special cases.