/Hierarchical Terrain Representations for Off-Road Navigation

Hierarchical Terrain Representations for Off-Road Navigation

Jay Gowdy, Anthony (Tony) Stentz and Martial Hebert
Conference Paper, Proceedings of SPIE Symposium on Mobile Robots, January, 1990

Download Publication (PDF)

Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author’s copyright. These works may not be reposted without the explicit permission of the copyright holder.


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.

BibTeX Reference
author = {Jay Gowdy and Anthony (Tony) Stentz and Martial Hebert},
title = {Hierarchical Terrain Representations for Off-Road Navigation},
booktitle = {Proceedings of SPIE Symposium on Mobile Robots},
year = {1990},
month = {January},