Page 424 - Introduction to AI Robotics

407
11.6 Comparison of Methods
Step 3: Update the current score with the past score and update the occu-
pancy grid.
The third step in the updating process is to combine the score for the grid
element from the current reading with the previous score stored there.
The Bayesian method uses the recursive form of Bayes’ rule, Eqn. 11.6:

P (s n jH)P (Hjs n 1 )
(11.12) P (Hjs n ) =
P (s n jH)P (Hjs n 1 ) P (s n j: H)P (: 1 )
+Hjs n
where s n 1 terms are from the reading stored at g r[3][10] i d and the s n terms
are the current reading. Substituting Occupied for H and E fo p t y
mr :H,
P (s n jH) becomes:

jO) = 0:54
P (s t 1
jE) = 0:46
P (s t 1
jO) = 0:50
P (s t 0
jE) = 0:50
P (s t 0
This yields:

)
) =
jO)P (Ojs t 0
P (s t 1
) jE)P (E j )
P (Ojs t 1
P (s t 1 jO)P (Ojs t 0 P (s t 1 +s t 0
(0 :54)(0 :50)
=
(0 :54)(0 :50)+ :46)(0 :50)
(0
= 0:54
) = 1 ) :46 = 0
P (Ejs t 1 P (Ojs t 1
The Dempster-Shafer updating takes the belief function stored at g r[3][10] i d
at time t 0 and combines it with the current belief function. This can be written
recursively as:
(11.13) B 0 = e B l t n e B l 0 e l
t n t n 1
The 0 means that the value is the one after any combination, so B 0 e l
t n 1
]
is the value currently stored at g r[i][ i dand B 0 e is the value that will be
j
l
t n
stored at g r[i][ i dafter the update. The method uses Dempster’s rule of
]
j
combination given in Eqn. 11.9 and reprinted below:
P
m(A i )m(B j )
A i \B j =C k ;C k 6=;
(11.14) m(C k ) P =
1 A i \B j =; m(A i )m(B j )