As part of the Unmanned Ground Vehicle (UGV) project, we have developed an integrated obstacle avoidance system. This system can be used for on-road driving for avoiding discrete obstacles, or for off-road driving for avoiding untraversable regions of the terrain. For example, we have demonstrated the system by driving autonomously through unmapped natural terrain at continuous speeds on the order of 3m/s. The path is a one kilometer loop in this particular example.

This navigation system takes range data as input, processes it in order to find regions that cannot be safely driven over, and generates recommendations for steering the vehicle based on the distributions of these untraversable regions. The system is set up as a reactive system in that it outputs steering commands frequently instead of planning long trajectories ahead. We now briefly describe the three components of the system which are illustrated by the figures at the end of this sampler.

Range Data Processing: The purpose of the range data processing component is to extract terrain regions which cannot be traversed by the vehicle. The criterion used for deciding on the traversability of a terrain region combines the elevation of the region and its slope relative to the current vehicle position. The processing starts by converting pixels from a range image to points in space with respect to the current vehicle position. These points are then transformed into a two-dimensional discrete grid. Parameters such as slope, and min and max elevation are updated at a cell of the grid every time a new data point is added to the grid. The traversability of a grid cell is evaluated whenever a large enough number of data points is accumulated in the cell. The output of this procedure is a set of obstacle cells. In this approach, every time a new range pixel is processed, the corresponding grid cell is updated. This allows for greater flexibility in the format of the input range data, for example, it allows for the use of a single-line scanner instead of an imaging scanner. Also, this approach is more efficient because the obstacle cells are reported as soon as they are found in the range data instead of after an entire image has been processed.

Local Map Management: A local map of the obstacle cells is maintained as the vehicle travels. The local map is updated when new obstacle cells are reported by the range data processing component. The positions of the obstacle cells with respect to the vehicle are updated at regular intervals in order to take into account the motion of the vehicle. The update rate is typically 10Hz. The resolution of the local map is typically 40cm. This local map component is based on the Ganesha system also developed as part of the UGV project.

Arc Generation: The locations of the obstacle cells in the local map are used for evaluating the admissibility of a finite set of arcs. Each arc is assigned a vote between -1 (the arc is completely blocked by at least one obstacle cell) and 1 (all clear). In order to generate a single steering command for the vehicle, the distribution of votes is then sent to an arbiter which combines it with input from other modules, for example modules that steer the vehicle toward preset goal points, . The arc evaluation is performed at regular intervals, typically every 100 ms. This reactive approach to arc generation was developed as part of the Distributed Architecture for Mobile Navigation (DAMN ) which is the software architecture used in the UGV system.