Page 449 - Introduction to AI Robotics

432
Exercise 11.7 11 Localization and Map Making
Suppose a localization algorithm had an order complexity of O(m n),where m is
the number of columns and n is the number of rows in the occupancy grid. Therefore
if the algorithm operated over a 10 10 grid, approximately 100 operations would be
executed for localization. What would be the number of operations if the grid were:
a. 100 100 ?
b. 1000 1000 ?
c. 5000 2000 ?

Exercise 11.8
2
Repeat the previous problem where the order complexity is O(( m n) ).
Exercise 11.9
Consider a robot beginning to map a new area (the occupancy grid is at an ini-
tial unsensed state), and how three different sonar updates create a certainty value

for a particular grid element. The sonar model is: range is 12, it’s = 15 ,the
0
M occupancy = a:98 ,and the tolerance is pm 1:0.At time t1, the sonar reading re-
x
turns 10.0. The grid element of interest is 9.5 units away from the robot with an
of 0.0. At t2, the robot has translated sideways. The sonar reading is 11.0. The grid
element is now 9.5 units away with an = :0.At t3, the sonar returns a value of 1 4
8.5 units. The robot has moved to the side and rotated; it is now 9.0 units from the

grid element with an of 5 .
a. What is the initial value of every element in the occupancy grid for
i) Bayesian
ii) Dempster-Shafer
iii) HIMM
b. Fill in the probabilities for the grid element for each sensor reading:
sonar Bayesian Dempster-Shafer HIMM
certainty: P (sjO) P (sjE) m(O) m(E) m(dontknow )
t1
t2
t3
c. Fill in the values for the grid element after every update:
after Bayesian Dempster-Shafer HIMM
update: P (Ojs) P (Ejs) m(O) m(E) m(dontknow )
t1
t2
t3

Exercise 11.10
Construct a series of readings that using the HIMM update rule would produce the
same final grid as produced by GRO in Fig. 11.13.