Robotic Mapping Occupancy Grid Mapping
Copyright By PowCoder代写 加微信 powcoder
• What make it challenging?
– Noisy measurement in local coordinate
– Motion involved – Change over time
Occupancy Grid Mapping
• Occupancy: binary random variable (R.V.) 𝑚𝑥,𝑦: 𝑓𝑟𝑒𝑒,𝑜𝑐𝑐𝑢𝑝𝑖𝑒𝑑 →{0,1}
[Review – Into Probability]
Given some probability space (Ω, 𝑃),
a random variable 𝑋: Ω → 𝑅 is a function that maps the sample space to the reals.
Occupancy Grid Mapping
• Occupancy: binary R.V.
𝑚𝑥,𝑦: 𝑓𝑟𝑒𝑒,𝑜𝑐𝑐𝑢𝑝𝑖𝑒𝑑 →{0,1}
• Occupancy grid map:
fine-grained grid map where an occupancy variable associated with
Occupancy Grid Mapping
• Occupancy grid mapping
: A Bayesian filtering to maintain a occupancy grid map.
Recursively update 𝑝(𝑚𝑥,𝑦) for each cell 𝑥
𝑝(𝑚1,2 )𝑝(𝑚1,3 )
Occupancy Grid Mapping
• Measurement
a range sensor
Occupancy Grid Mapping
• Measurement 𝑧~{0,1}
a range sensor
Occupancy Grid Mapping
• Measurement 𝑧~{0,1}
• Measurement model 𝑝(𝑧|𝑚𝑥,𝑦)
𝑝 𝑧 = 1|𝑚𝑥,𝑦 = 1 𝑝 𝑧 = 0|𝑚𝑥,𝑦 = 1 𝑝 𝑧=1|𝑚𝑥,𝑦 =0
𝑝 𝑧=0|𝑚𝑥,𝑦 =0
: True occupied measurement : False free measurement
: False occupied measurement : True free measurement
Occupancy Grid Mapping
• Measurement 𝑧~{0,1}
• Measurement model 𝑝(𝑧|𝑚𝑥,𝑦)
𝑝 𝑧=0|𝑚𝑥,𝑦 =1 =1− 𝑝 𝑧=0|𝑚𝑥,𝑦 =0 =1−
𝑝 𝑧=1|𝑚𝑥,𝑦 =0
𝑝 𝑧=1|𝑚𝑥,𝑦 =1
[Review – Into Probability]
𝑃 𝐴𝐶|𝐵 = 1 − 𝑃(𝐴|𝐵)
𝑝 𝑧=1|𝑚𝑥,𝑦 =1
𝑝 𝑧=1|𝑚𝑥,𝑦 =0
Occupancy Grid Mapping
Measurement Model
𝑝(𝑚1,2 )𝑝(𝑚1,3 )
Robotic Mapping
Occupancy Grid Mapping Log-odd Update
We are now going to learn mathematical notations to discuss Occupancy Grid Mapping.
Occupancy Grid Mapping
Posterior Map
Measurement Model
𝑝(𝑧|𝑚𝑥,𝑦) Likelihood
= 𝑝(𝑧|𝑚𝑥,𝑦)𝑝(𝑚𝑥,𝑦) 𝑝(𝑧)
Bayes’ Rule:
Occupancy Grid Mapping
We are now going to learn mathematical notations to discuss Occupancy Grid Mapping. We want to update the occupancy probability of each cell from our measurements in a Bayesian framework. However, keeping tracking of these probabilities is computationally expensive.
Q: any alternatives?
Instead of using occupancy probability itself, is there any other concept that can make the computation simpler?
Occupancy Grid Mapping Log-odd Update
Occupancy Grid Mapping
𝑂𝑑𝑑:= (𝑋h𝑎𝑝𝑝𝑒𝑛𝑠) = 𝑝(𝑋) (𝑋 𝑛𝑜𝑡 h𝑎𝑝𝑝𝑒𝑛𝑠) 𝑝(𝑋𝑐)
• More convenient when we use “Odd”
𝑂𝑑𝑑((𝑚𝑥,𝑦= 1) 𝑔𝑖𝑣𝑒𝑛 𝑧) = 𝑝(𝑚𝑥,𝑦 = 1|𝑧) 𝑝(𝑚𝑥,𝑦 =0|𝑧)
Occupancy Grid Mapping
𝑝 𝑚𝑥,𝑦 = 1|𝑧 = 𝑝(𝑧|𝑚𝑥,𝑦 = 1)𝑝(𝑚𝑥,𝑦 = 1)
𝑂𝑑𝑑 = 𝑝(𝑚𝑥,𝑦 = 1|𝑧) = 𝑝(𝑧|𝑚𝑥,𝑦 = 1)𝑝(𝑚𝑥,𝑦 = 1)/𝑝(𝑧) 𝑝(𝑚𝑥,𝑦 =0|𝑧) 𝑝(𝑚𝑥,𝑦 =0|𝑧)
(Bayes’ Rule)
Occupancy Grid Mapping
𝑂𝑑𝑑 = 𝑝(𝑚𝑥,𝑦 = 1|𝑧) = 𝑝(𝑧|𝑚𝑥,𝑦 = 1)𝑝(𝑚𝑥,𝑦 = 1)/𝑝(𝑧) 𝑝(𝑚𝑥,𝑦 =0|𝑧) 𝑝 𝑧𝑚𝑥,𝑦 =0 𝑝 𝑚𝑥,𝑦 =0 /𝑝(𝑧)
𝑝 𝑚𝑥,𝑦 = 0|𝑧 = 𝑝(𝑧|𝑚𝑥,𝑦 = 0)𝑝(𝑚𝑥,𝑦 = 0) 𝑝(𝑧)
(Bayes’ Rule)
Occupancy Grid Mapping
• Take the log!
𝑝(𝑚𝑥,𝑦 = 1|𝑧) = 𝑝(𝑧|𝑚𝑥,𝑦 = 1)𝑝(𝑚𝑥,𝑦 = 1)
𝑝(𝑚𝑥,𝑦 = 0|𝑧)
log 𝑝(𝑚𝑥,𝑦 = 1|𝑧) 𝑝(𝑚𝑥 ,𝑦 = 0|𝑧)
𝑝(𝑧|𝑚𝑥,𝑦 = 0)𝑝(𝑚𝑥,𝑦 = 0)
= log 𝑝(𝑧|𝑚𝑥,𝑦 = 1)𝑝(𝑚𝑥,𝑦 = 1) 𝑝(𝑧|𝑚𝑥 ,𝑦 = 0)𝑝(𝑚𝑥 ,𝑦 = 0)
=log𝑝 𝑧|𝑚𝑥,𝑦 =1 +log𝑝 𝑚𝑥,𝑦 =1 𝑝 𝑧|𝑚𝑥,𝑦 =0 𝑝 𝑚𝑥,𝑦 =0
log 𝑜𝑑𝑑+ = log 𝑜𝑑𝑑 𝑚𝑒𝑎𝑠 + log 𝑜𝑑𝑑−
Occupancy Grid Mapping
• Log-odd update
Posterior Map Measurement Prior Map
Log-odd-meas
log 𝑜𝑑𝑑+ = log 𝑜𝑑𝑑 𝑚𝑒𝑎𝑠 + log 𝑜𝑑𝑑−
Occupancy Grid Mapping
• Log-odd update
Posterior Map Measurement Prior Map
Log-odd-meas
log 𝑜𝑑𝑑+ = log 𝑜𝑑𝑑 𝑚𝑒𝑎𝑠 + log 𝑜𝑑𝑑−
• Two important points when doing the update: 1- we only need to update the observed/current cell
2- the updated values become priors when you receive new measurement in the new time steps
Occupancy Grid Mapping
• Measurement model in log-odd form log𝑝 𝑧|𝑚𝑥,𝑦 =1
𝑝 𝑧|𝑚𝑥,𝑦 = 0
• Two possible measurement:
CaseI:cellswithz=1 log𝑜𝑑𝑑_𝑜𝑐𝑐:=log𝑝 𝑧=1|𝑚𝑥,𝑦 =1
𝑝 𝑧=1|𝑚𝑥,𝑦 =0
Case II : cells with z=0
(Trivial Case : cells not measured)
log𝑜𝑑𝑑_𝑓𝑟𝑒𝑒:= log 𝑝 𝑧 = 0|𝑚𝑥,𝑦 = 0 𝑝 𝑧=0|𝑚𝑥,𝑦 =1
Occupancy Grid Mapping
Constant Measurement Model
log 𝑜𝑑𝑑_𝑜𝑐𝑐 ≔ 0.9 log 𝑜𝑑𝑑_𝑓𝑟𝑒𝑒 ≔ 0.7
Initial Map:
log 𝑜𝑑𝑑 = 0 for all (x,y)
𝑝 𝑚𝑥,𝑦 =1 =𝑝 𝑚𝑥,𝑦 =0 =0.5
Update Rule:
log 𝑜𝑑𝑑 += log 𝑜𝑑𝑑_𝑚𝑒𝑎𝑠
Occupancy Grid Mapping
Constant Measurement Model
log 𝑜𝑑𝑑_𝑜𝑐𝑐 ≔ 0.9 log 𝑜𝑑𝑑_𝑓𝑟𝑒𝑒 ≔ 0.7
§ Case I : cells with z=1 log 𝑜𝑑𝑑 ← 0 + log 𝑜𝑑𝑑_𝑜𝑐𝑐
§ Case II : cells with z=0 log 𝑜𝑑𝑑 ← 0 − log 𝑜𝑑𝑑_𝑓𝑟𝑒𝑒
Update Rule:
log 𝑜𝑑𝑑 += log 𝑜𝑑𝑑_𝑚𝑒𝑎𝑠
Occupancy Grid Mapping
Constant Measurement Model
log 𝑜𝑑𝑑_𝑜𝑐𝑐 ≔ 0.9 log 𝑜𝑑𝑑_𝑓𝑟𝑒𝑒 ≔ 0.7
§ Case I : cells with z=1
log 𝑜𝑑𝑑 ← 0 + log 𝑜𝑑𝑑_𝑜𝑐𝑐
§ Case II : cells with z=0 log 𝑜𝑑𝑑 ← 0 − log 𝑜𝑑𝑑_𝑓𝑟𝑒𝑒
Update Rule:
log 𝑜𝑑𝑑 += log 𝑜𝑑𝑑_𝑚𝑒𝑎𝑠
measurement
.9 -.7-.7-.7
-.7 -.7 -.7
00000000 0 .9-.7-.7-.70 0 0
0 .9 -.7 -.7-1.4 -1.4 -1.4 0 00000000
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com