Our map representation is based on the occupancy grids approach, but has been modified to include more state information. We use a spatial grid to partition our space and represent it. The granularity of the grid can be modified depending on the characteristics of the robot and the environment. Along with the robot's current position (identified by the X), we also define a neighborhood around the robot. This neighborhood allows us to concentrate our computational resources to an area having direct bearing on the robot's navigation. Thus, while we have a global representation, we do local mapping and processing to update this representation. Each cell in the grid also stores information about the identity, location and properties of the various objects in the environment. Bayesian networks that are used to update the beliefs of these objects are also associated with the cells.
We have addressed the issue of belief propagation through time in the previous task. However, beliefs can also propagate through space. For example, if the sensors detect a car moving along a road, then as time progresses, the beliefs associated with the car will propagate through the space (as represented by our map). The spatial belief manager uses the short-term memory to perform spatial propagation and stores the resulting beliefs in the dynamic occupancy grid.
There are two kinds of spatial belief propagation we propose to incorporate in our system architecture. In the first case, we simply propagate the belief about the presence of objects along the direction of motion of the objects. For example, assume A represents a car at the indicated location in our spatial map moving due east. At the next time step, we propagate this belief to the next adjacent location in the eastern direction (getting C). This spatial propagation is governed by the motion characteristics of the individual objects.
In the second case (B), we have beliefs about the presence of the same object type in two adjacent locations. This is possible when, say, an object is large and extends over multiple locations in the spatial grid. The objective then is to identify whether it is the same object (for example - a long building) or two separate objects of the same type (for example - two cars). If we determine that it is a single object, then we fuse the two beliefs together and obtain the same situation as described in C. If the two beliefs are about two different objects (of the same type), we do not combine their beliefs.
The map manager then takes the dynamic occupancy grid and overlays it with potentials. Lower potentials represent areas that are easy to navigate upon (like roads, pathways etc.) and higher potentials represent obstacles (like walls, trees, etc.) A potential gradient map is then generated from this overlayed occupancy grid map.
This page is maintained by Amit Singhal.
Last update: 11/17/97.