Grid based Approach for Navigation by Evidence Storage and Histogram Analysis

GANESHA (Grid based Approach for Navigation by Evidence Storage and Histogram Analysis) was designed for the Navlab using narrow beam, piezoceramic sonar sensors. It can also be used with other range sensors, such as microwave radar, laser or stereo. Each sensor measurement is tagged with the position of the vehicle in world coordinates. The position and orientation of each sensor on the vehicle is known and the sensor readings can now be used to build a local grid map of the immediate surrounding of the vehicle. The vehicle position is kept at a fixed point in the map. As the vehicle moves, objects in the map are moved from cell to cell relative to vehicle position. Once an object falls outside the map boundary it is discarded and the information is lost. Using just a local map has the advantage that error accumulation owing to dead reckoning is kept small, since only relative movements are considered. At present the area covered by the local map is 16.4 m x 70.2 m. Each grid cell has a resolution of 0.4 m along the x-axis, and a variable resolution of 0.4 m, 2 m or 4 m along the y-axis , depending upon distance from the vehicle. Each cell has the following set of parameters or annotations associated with it:

1. Object Type : This parameter is used to indicate if the object in that cell was seen at the current sensor reading, or if it was seen at a previous reading. If it was seen only at a previous reading, then the object type indicates that it must have moved to that particular cell due to vehicle motion only. The parameter is also used to denote objects detected by different types of sensors.
   
   

2. Position: indicates the x-y position of the object with respect to vehicle position.
   
   

3. History: This parameter counts the number of times an object was detected in a particular cell.
   
   

4. Radius Vector: is precomputed for each cell and denotes the range of steering radii that would avoid a collision between the vehicle and an object in that cell.
   
   

The resolution of the grid is fairly coarse and hence the position parameter is kept to avoid gross error accumulation when objects are transformed in the map. Only one object is kept per grid cell. Thus measurement uncertainty is part of the grid cell representation and any object detected within an area covered by a particular cell is taken to belong to the same object. New objects detected by the sensors are added to the map after the positions of all previous objects in the map are updated. The map parameter History is used for filtering the data. History is an indication of the confidence that a particular cell is occupied by an object. Objects in the map in a sensor’s field of view are deleted if the sensor does not detect them during a certain time period. This eventually eliminates spurious readings or objects that have moved away.

A navigation function using the grid map, is the tracking of features in the environment, such as a wall or parked cars. This type of feature appears in the map as a string of objects. Using additional knowledge about the approximate position of the feature, it can be determined which set of objects in the map belong to the feature. A line is then fitted to these objects, using the method of least squares and applying a median based filter technique to remove outliers. Once the position and orientation of the feature is known in the map, steering commands are generated, using the pure pursuit algorithm, to drive the vehicle on a path parallel to and at a constant distance from the feature.

To avoid obstacles, each occupied cell is examined. The Radius Vectors of all occupied cells are and’ed together to generate the list of safe steering directions. Vehicle speed is changed depending on the distance to the closest object.

Tracking a row of parallel parked cars, Ganesha can detect a parking gap. For parking, the vehicle lines up with the car in front of the gap and then backs into the gap along a precomputed S-curve. At present the curb cannot be sensed and therefore the width of the parking gap is assumed to be the average width of a car.