 Occupancy grid mapping

Occupancy Grid Mapping refers to a family of computer algorithms in probabilistic robotics for mobile robots which address the problem of generating maps from noisy and uncertain sensor measurement data, with the assumption that the robot pose is known.
The basic idea of the occupancy grid is to represent a map of the environment as an evenly spaced field of binary random variables each representing the presence of an obstacle at that location in the environment. Occupancy grid algorithms compute approximate posterior estimates for these random variables.^{[1]}
Contents
Algorithm Outline
There are four major components of occupancy grid mapping approach. They are:
 Interpretation,
 Integration,
 Position estimation, and
 Exploration.^{[2]}
Occupancy Grid Mapping Algorithm
The goal of an occupancy mapping algorithm is to estimate the posterior probability over maps given the data: , where m is the map, z_{1:t} is the set of measurements from time 1 to t, and x_{1:t} is the set of robot poses from time 1 to t. The controls and odometry data play no part in the occupancy grid mapping algorithm since the path is assumed known.
Occupancy grid algorithms represent the map m as a finegrained grid over the continuous space of locations in the environment. The most common type of occupancy grid maps are 2d maps that describe a slice of the 3d world.
If we let m_{i} denote the grid cell with index i (often in 2d maps, two indices are used to represent the two dimensions), then the notation p(m_{i}) represents the probability that cell i is occupied. The computational problem with estimating the posterior is the dimensionality of the problem: if the map contains 10,000 grid cells (a relatively small map), then the number of possible maps that can be represented by this gridding is 2^{10,000}. Thus calculating a posterior probability for all such maps is infeasible.
The standard approach, then, is to break the problem down into smaller problems of estimating for all grid cells m_{i}. Each of these estimation problems is then a binary problem. This breakdown is convenient but does lose some of the structure of the problem, since it does not enable modelling dependencies between neighboring cells. Instead , the posterior of a map is approximated by factoring it into . Due to this factorization, a binary Bayes filter can be used to estimate the occupancy probability for each grid cell. It is frequent to use a logodds representation of the probability that each grid cell is occupied.
See also
References
 ^ Thrun, S., Burgard, W. and Fox, D. (2005). Probabilistic Robotics. Cambridge, Mass: MIT Press. ISBN 0262201623. OCLC OL3422030M. http://www.probabilisticrobotics.org/.
 ^ Thrun, S. and Bücken, A. (1996). "Integrating gridbased and topological maps for mobile robot navigation" (PDF). Proceedings of the Thirteenth National Conference on Artificial Intelligence: pp. 944–950. http://www.ri.cmu.edu/pub_files/pub1/thrun_sebastian_1996_8/thrun_sebastian_1996_8.pdf.
Categories: Robot navigation
Wikimedia Foundation. 2010.
Look at other dictionaries:
Robotic mapping — The problem of Robotic mapping is related to cartography.The goal is for an autonomous robot to be able to construct (or use ) a map or floor plan and to localize itself in it.Todd et al (1994) have shown that evolutionarily shaped blind action… … Wikipedia
Mobile Robotics Laboratory at IISc — Mobile Robotics Laboratory Established 2002 Type Public Location Bangalore, India Campus Indian Institute of Science … Wikipedia
Mobile Robotics Laboratory — Infobox University name = Mobile Robotics Laboratory established = 2002 type = Public head = [http://www.aero.iisc.ernet.in/dghose/welcome.html Dr. Debasish Ghose] city = Bangalore, India campus = Indian Institute of Science website =… … Wikipedia
Mobile Robot Programming Toolkit — (MRPT) Obstacle avoidance on a robotic wheelchair. Developer(s) The MAPIR group … Wikipedia
Mathematics and Physical Sciences — ▪ 2003 Introduction Mathematics Mathematics in 2002 was marked by two discoveries in number theory. The first may have practical implications; the second satisfied a 150 year old curiosity. Computer scientist Manindra Agrawal of the… … Universalium
Abkürzungen/Luftfahrt/L–R — Dies ist der vierte Teil der Liste Abkürzungen/Luftfahrt. Liste der Abkürzungen Teil 1 A A Teil 2 B–D B; C; D Teil 3 E–K … Deutsch Wikipedia
Boston — This article is about the capital of Massachusetts. For other uses, see Boston (disambiguation). Boston City Clockwise: Skyline of Back Bay seen from the … Wikipedia
Compact Muon Solenoid — Coordinates: 46°18′34″N 6°4′37″E / 46.30944°N 6.07694°E / 46.30944; 6.07694 … Wikipedia
Autonomous car — For the wider application of artificial intelligence to automobiles, see Vehicle Automation. Junior, a robotic Volkswagen Passat parked at Stanford University. An autonomous car, also known as robotic or informally as driverless, is an autonomous … Wikipedia
JERUSALEM — The entry is arranged according to the following outline: history name protohistory the bronze age david and first temple period second temple period the roman period byzantine jerusalem arab period crusader period mamluk period … Encyclopedia of Judaism