Hierarchical Terrain Representations for Off-Road Navigation

Abstract

For most autonomous land vehicle tasks, creating the terrain representation is the greatest part of the problem. For example, once a road following system represents the terrain presented to it as road and non-road it is relatively easy to plan a path through the terrain. However, off road navigation does not have the luxury of such a compact representation. An off-road planner needs a detailed map of the terrain, and needs an efficient way of querying that terrain map. We have implemented a system that satisfies these two constraints for off-road navigation. We first build a Cartesian elevation map from a series of laser range finder images. This map is a complete, but intractable, representation of the terrain. We use the map to build a hierarchical representation of the terrain that we call a "terrain pyramid." Each cell at a level of the terrain pyramid holds the maximum and minimum elevation of the four cells in the !evel below it. We also build pyramids for various features in the Cartesian map such as terrain discontinuity and slope. The terrain pyramids are shipped to a planner module. We provide the planner module with calls to find the minimum and maximum values of a feature over any rectangle in the terrain. With these calls taking advantage of the hierarchical representation of the terrain. the planner can efficiently determine a safe path through the terrain.