In order for an autonomous robot to “appropriately” navigate through a complex environment, it must have an in-depth understanding of the immediate surroundings. Appropriate navigation implies the robot will avoid collision or contact with hazards, will not be falsely rerouted around traversible terrain due to false hazard detections, and will exploit the terrain to maximize its concealment. Appropriate autonomous navigation requires the ability to detect and localize critical features in the environment. Examples of critical environmental features include rocks, trees, ditches, holes, bushes and water. Environmental features have a wide range of characteristics and multiple sensing phenomenologies are required to be able to detect them all. Once the data is acquired from these multiple phenomenologies, a mechanism is required to combine and analyze all of these disparate sources of information into one composite interpretation. In this paper we discuss the Demo III multi-sensor system for autonomous mobility, and the “operator-trained” fusion system called O-NAV (Object NAVigation) that is used to build a labeled three dimensional model of the immediate environment surrounding the robot vehicle so it can appropriately interact with its surroundings.