Efficient mapping through exploitation of spatial dependencies

Occupancy grid mapping algorithms assume that grid block values are independently distributed. However, most environments of interest contain spatial patterns that are better characterized by models that capture dependencies among grid blocks. To account for such dependencies, we model the environment as a pairwise Markov random field. We specify a belief propagation-based mapping algorithm that takes these dependencies into account when estimating a map. To demonstrate the potential benefits of this approach, we simulate a simple multi-robot minefield mapping scenario. Minefields contain spatial dependencies since some landmine configurations are more likely than others, and since clutter, which causes false alarms, can be concentrated in certain regions and completely absent in others. Our belief propagation-based approach outperforms conventional occupancy grid mapping algorithms in the sense that better maps can be obtained with significantly fewer robot measurements. The belief propagation algorithm requires a modest amount of increased computation, but we contend that in applications where significant energy and time expenditure is associated with robot movement and active sensing, the reduction in the required number of samples justified the increased computation.

Authors

• Yaron Rachlin
• John M. Dolan
• Pradeep K. Khosla

Keywords

• Robot sensing systems
• Belief propagation
• Markov random fields
• Grid computing
• Computational efficiency
• Distributed computing
• Landmine detection
• Shafts
• Area measurement
• Fatigue
• Spatial Dependence
• False Alarm
• Mapping Algorithm
• Markov Random Field
• Minefield
• Robot Movement
• Occupancy Grid
• Conventional Grid
• Reduction In The Number
• Types Of Errors
• Spatial Model
• Map Of Area
• False Alarm Rate
• Noise Model
• Fewer Samples
• Normalization Constant
• Binary Map
• Log Odds Ratio
• Error Metrics
• Markov Random Field Model
• Ground Penetrating Radar
• Score Metrics
• Blocking Probability
• High False Alarm Rate
• High False Alarm
• occupancy grids
• demining