Ridge-valley path planning for 3D terrains

This paper presents a tactical path planning algorithm for following ridges or valleys across a 3D terrain. The intent is to generate a path that enables an unmanned vehicle to surveil with maximum observability by traversing the ridges of a terrain or to operate with maximum covertness by navigating the valleys. The input to the algorithm is a 3D triangle mesh model for the terrain of interest. This mesh may be non-uniform and non-regular. Thus, the algorithm leverages research from computer graphics and computer vision to identify ridge-valley features on the terrain. These features serve as "obstacles" for an artificial potential field algorithm. The valleys are obstacles for a surveillance path, or the ridges are obstacles for a covert path. We incorporate geodesic-rather than Euclidean-distances into the potential field formulation to extend path planning to 3D surfaces. We present the theory of our proposed algorithm and provide experimental results