Environment sensing is required in order for robots to operate safely in either shared workspaces between robots and human or unpredictable natural environments. However, available perceptual inference algorithms require many smoothness assumptions such as a flat ground plane, straight walls, etc; thus their efficiency depends on the degree of smoothness of the beliefs. Indeed, current autonomous navigation techniques only work well in highly structured environments, but fail to deal with cluttered outdoor environments. Particularly, vegetated terrain introduces one more degree of freedom to...