A Decision System For Autonomous Robot Navigation Over Rough Terrain

Abstract

In the implementation of an autonomous mobile robot, the navigation system must be able find an acceptable path through a region of multi-valued traversal costs (as opposed to a binary regime of obstacle avoidance). Information must be efficiently represented, with sufficient information density in the robot's immediate navigation domain, in a manner which facilitates a process of learning the terrain. This paper discusses a decision system built around a "Routing-Engine" employing a cellular-array processor to propagate a wave over an two-dimensional map in which the pointwise traversal costs are represented as pointwise refractive indices. The path returned is the locus of local normals to the wavefront of the first wave, originating at the robot's current location, to reach the goal. This routing-engine is run recursively on a hierarchical stack of maps arranged in linear-spatial registration with the coarsest information resolution in the most global map. The central fovea of each map in the hierarchy is "blown-up" to yield a map more local to the vehicle, with the lowest level map possessing sufficient resolution to maneuver the robot. As the robot moves, its registration in the centre of each map in the stack is maintained by "scrolling" the maps over each other. As this is done, sensed information is propagated through the stack updating the information stored at each level. The system has been implemented successfully in simulation.