Occupancy Grid Mapping
Grid based approaches (metric paradigm), like the ones proposed by Moravec(1988) and many others, represent environments as evenly spaced grids, with information about obstacles attached. This approach is easy to build and maintain due to its simplicity and ease of representation. One of the main advantages of this approach is that the recognition of space is based on geometry, therefore is non-ambiguous and view point independent. Moreover building paths on such structures is easy, making the computation power needed to produce a result low. This method doesn’t however provide satisfying results when it comes to planning (resolution doesn’t depend on the environment) and provides poor interface for most symbolic problem solves. Moreover one needs to know the position of the robot with high accuracy (on point), which is hard to achieve using simple methods.
An alternative method is to represent the environment by graphs (topological paradigm) and was described in detail by Engelson and McDermott(1992), Kortenkamp and Weymouth(1994), Mataric(1994) and more. The nodes in those graphs are representing various landmarks such as doorways, which are connected, if a direct path between them exists. Those methods permit efficient path planning and low space complexity (the more objects in the environment, the graph will become more complex), while providing a convenient representation (and human readable) of the environment graph. Moreover, as opposed to grid based approaches, it does not need to know accurate determination of the robots position. However, graph approach brings new problems: it is difficult to build and maintain in large environments and highly depends on the point of view (often ambiguous). Also in the world of mobile robotics is known to yield suboptimal path results.
Due to the limitations of both algorithms Occupancy Grids were introduced. Buhmannet al. (1995) and Thrun and Bucken (1996b) show how Occupancy Grids are easy to construct and maintain even in large-scale environments. To construct such an environment, sensor values are interpreted by an artificial neural network and mapped into probabilities for occupancy. Multiple implementations are integrated over time using the Bayes’ rule. On top of the grid representation, compact topological maps are constructed by splitting the grid map into regions, that are separated by critical lines. Those critical lines correspond to doorways and other narrow passages between regions. The topic was described further in Thrun and Bucken (1996a) and Thrun et al. (2005).
To understand the sensor interpretation, one needs to understand that each cell of the grid representation has a occupancy value attached that measures the belief whether the intelligent agent can be moved to the center of that cell. To build a metric map, each sensor reading needs to be translated into occupancy values for each of the cells. A neural network is trained using Back Propagation that maps measurements into occupancy values:
- Four sensor readings closest to ,
- Two values that encode in polar coordinates relative to the robot (angle to four closest sensors and distance),
- if is occupied,
To get a consistent map, the sensor interpretations need to be integrated over time. In order to make it convenient (Thrun and Bucken (1996a), the network output for the -th sensor reading should be interpreted as the probability that the cell is occupied, conditioned by the sensor reading .
As mentioned above, the topological maps are built on top of the grid map representation. Free space gathered from the grid map is grouped into a number of regions, that are separated through critical lines (corresponding to passages). Critical lines are important to the process, because when the intelligent agent is passing through one, it enters a new region, decreasing planning performance loss. Moreover, critical lines can be blocked, for example by closing doors that they are described on. The partitioned map is then mapped into a isomorphic graph using the presented steps:
At the start each of the occupancy values is tresholded. Values that are below the treshold are marked as open space, while those that are at or above the treshold are marked occupied.
- Voronoi diagram
The Voronoi diagram is a set of points in the free space that have at least two different basis points. For each of the points from the free space, there is one or more nearest point in the occupied space. The distance between and its basis points is called the clearance.
- Critical points
To find the critical points, one needs to take the points from the Voronoi diagram that minimize clearance locally. Each of the critical points has two properties:
- It is part of the Voronoi diagram,
- The clearance of all neighbours in an -neighbourhood of is not smaller.
- Critical lines
To create a critical line, one needs to connect each critical point with its basis points. Each critical point has exactly two basis points, as that is needed to find the minima of the clearance function. The critical lines act as a border between regions.
- Topological graph
The region map is mapped into an isomorphic graph where each of the regions corresponds to a node in the graph. Similarly each critical line corresponds to an arc in the graph.
A nice image to show that in practice:
Generation of Topological Maps in Occupancy Grid algorithms as seen in Thrunand Bucken (1996a).