Occupancy grid mapping

<h2 id="algorithm-outline">Algorithm outline</h2>
<p>There are four major components of occupancy grid mapping approach. They are:
</p>
<ul><li>Interpretation</li>
<li>Integration</li>
<li>Position estimation</li>
<li>Exploration<a class="footnote-ref" id="fnref:3" href="#fn:3"><sup>3</sup></a></li></ul>
<h2 id="occupancy-grid-mapping-algorithm">Occupancy grid mapping algorithm</h2>
<p>The goal of an occupancy mapping algorithm is to estimate the <a href="/facts/Posterior_probability/fojsMD0D">posterior probability</a> over maps given the data: 
  
    
      
        p
        (
        m
        ∣
        
          z
          
            1
            :
            t
          
        
        ,
        
          x
          
            1
            :
            t
          
        
        )
      
    
    {\displaystyle p(m\mid z_{1:t},x_{1:t})}
  
, where 
  
    
      
        m
      
    
    {\displaystyle m}
  
 is the map, 
  
    
      
        
          z
          
            1
            :
            t
          
        
      
    
    {\displaystyle z_{1:t}}
  
 is the set of measurements from time 1 to t, and 
  
    
      
        
          x
          
            1
            :
            t
          
        
      
    
    {\displaystyle x_{1:t}}
  
 is the set of robot poses from time 1 to t. The controls and <a href="/facts/Odometry/Y6eSUM0N">odometry</a> data play no part in the occupancy grid mapping algorithm since the path is assumed known.
</p><p>Occupancy grid algorithms represent the map 
  
    
      
        m
      
    
    {\displaystyle m}
  
 as a fine-grained 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.
</p><p>If we let 
  
    
      
        
          m
          
            i
          
        
      
    
    {\displaystyle m_{i}}
  
 denote the <a href="/facts/Grid_cell_indices/GfIomenN">grid cell with index</a> i (often in 2d maps, two indices are used to represent the two dimensions), then the notation 
  
    
      
        p
        (
        
          m
          
            i
          
        
        )
      
    
    {\displaystyle p(m_{i})}
  
 represents the probability that cell i is occupied.
The computational problem with estimating the posterior 
  
    
      
        p
        (
        m
        ∣
        
          z
          
            1
            :
            t
          
        
        ,
        
          x
          
            1
            :
            t
          
        
        )
      
    
    {\displaystyle p(m\mid z_{1:t},x_{1:t})}
  
 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
          
        
      
    
    {\displaystyle 2^{10,000}}
  
. Thus calculating a posterior probability for all such maps is infeasible.
</p><p>The standard approach, then, is to break the problem down into smaller problems of estimating 
</p>

p
        (
        
          m
          
            i
          
        
        ∣
        
          z
          
            1
            :
            t
          
        
        ,
        
          x
          
            1
            :
            t
          
        
        )
      
    
    {\displaystyle p(m_{i}\mid z_{1:t},x_{1:t})}

<p>for all grid cells 
  
    
      
        
          m
          
            i
          
        
      
    
    {\displaystyle 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
</p>

p
        (
        m
        ∣
        
          z
          
            1
            :
            t
          
        
        ,
        
          x
          
            1
            :
            t
          
        
        )
        =
        
          ∏
          
            i
          
        
        p
        (
        
          m
          
            i
          
        
        ∣
        
          z
          
            1
            :
            t
          
        
        ,
        
          x
          
            1
            :
            t
          
        
        )
      
    
    {\displaystyle p(m\mid z_{1:t},x_{1:t})=\prod _{i}p(m_{i}\mid z_{1:t},x_{1:t})}
  
.
<p>Due to this factorization, a binary <a href="/facts/Bayes_filter/vzBrW5U4">Bayes filter</a> can be used to estimate the occupancy probability for each grid cell. It is common to use a <a href="/facts/Logit/5674C2DL">log-odds</a> representation of the probability that each grid cell is occupied.
</p>
<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Robotic_mapping/W9jnGGKe">Robotic mapping</a></li></ul>

<h2 id="external-links">External links</h2>
<ul><li><a href="https://www.cs.cmu.edu/~16831-f14/notes/F14/16831_lecture06_agiri_dmcconac_kumarsha_nbhakta.pdf">Lecture notes of 16-831: Statistical Techniques in Robotics at RI CMU</a></li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1"><p>H. Moravec; A. E. Elfes (1984). "High resolution maps from wide angle sonar". Proceedings. 1985 IEEE International Conference on Robotics and Automation. Silver Spring, MO: IEEE Computer Society Press. pp. 116–121. doi:10.1109/ROBOT.1985.1087316. S2CID 41852334. <a href="https://ieeexplore.ieee.org/document/1087316" target="_blank">https://ieeexplore.ieee.org/document/1087316</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li>
<li id="fn:2"><p>Thrun, S.; Burgard, W.; Fox, D. (2005). Probabilistic Robotics. Cambridge, Mass: MIT Press. ISBN 0-262-20162-3. OL 3422030M. <a href="0-262-20162-3" target="_blank">0-262-20162-3</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li>
<li id="fn:3"><p>Thrun, S. & Bücken, A. (1996). "Integrating grid-based and topological maps for mobile robot navigation" (PDF). Proceedings of the Thirteenth National Conference on Artificial Intelligence: 944–950. ISBN 0-262-51091-X. <a href="0-262-51091-X" target="_blank">0-262-51091-X</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li>
</ol>

Occupancy grid mapping open-in-new

Occupancy grid mapping