Catalogue of Artificial Intelligence Techniques
Occupancy Grid Mapping
Keywords: cells, grid, mapping, occupancy, sensor
Author(s): James Adwick
Within probabilistic robotics it is not always the case that the robot itself has a map of the environment it is in. Any task that a robot undertakes has a large amount of uncertainty associated with it and as they are real-time systems there is limited time to calculate its decisions. As maps may not always be available then it is important for the robot to have the ability to learn a map based on perceptions it receives.
Occupancy grid mapping is the set of algorithms that generate consistent maps by gathering measurements from sensors. It assumes knowledge of the robots location and orientation (pose). There are many obstacles that could exist in the robots environment such as furniture and moving objects (i.e. people) that do not correspond to a building blueprint or rough map. Occupancy grid mapping is a step towards true autonomous robots in AI but to succeed in this the robot must be able to learn and adapt to the environment and overcome the obstacles described.
Occupancy grid mapping splits the map into a series of cells in a grid formation and each cell has an assigned probability depending on whether it is occupied or not, initially beginning with 1/2. The robot will take a path through the environment and update the probabilities to generate a map. It may take several cycles to ensure that obstacles identified are consistent. For example, confirm it was not a person passing in front of the robot but a solid wall or table that will remain static. When this is displayed as a diagram the probability is represented by the darkness of the cell. The darker a grid cell is the higher the probability it is occupied.
An outline of the occupancy grid mapping algorithm is shown below (Follow reference for detailed description):
1. Calculate the posterior (New probability of situation based on new information).
2. Update the probability of the cell depending on if an obstacle was identified by the robots sensors.
3. Generate a map of the environment (Usually a 2D floor plan).
4. Cycle, changing route from start to end point.
An extension to the occupancy grid mapping algorithm is identifying conflicts in overlapping regions of the map. If an obstacle is detected in the above algorithm it is assumed to cover the whole arc of the sensor which is not necessarily true.
- Sebastian Thrun, Wolfram Burgard, Dieter Fox, Probabilistic Robotics (Ronald C. Arkined.), MIT Press, 2005, pp.281-304.