Page 429 - Introduction to AI Robotics

412
Localization and Map Making
11
constructed with occupied points receiving 1.0 or 15 values and empty grid
elements 0. The performance can be computed as the sum of the differences
on a grid element by grid element basis:
X
j
]
(11.16) score = jtruth [i][ j] g r[i][ i d
j
i;j
Low scores mean there was less difference between the perfect map and the
sensed map.
Bayesian and Dempster-Shafer theory produce essentially the same re-
sults. This is not surprising since they both use the same model of uncer-
tainty for sonars. The major difference between Bayesian and Dempster-
Shafer is the weight of conflict metric.
HIMM tends to be less accurate than Bayesian or Dempster-Shafer theory,
as would be expected from a method that only updates along the acoustic
axis. But HIMM has almost an order of magnitude fewer elements to update
on average after each reading, making it much faster to execute.
Two solutions are available to improve Bayesian and Dempster-Shafer per-
formance. The first is to convert all floating point numbers to integers. The
area of coverage can be dynamically adapted as a function of the robot speed.
When the robot is going fast, it can’t afford to spend much time updating the
occupancy grid. At that point, it becomes reasonable to update only along
the acoustic axis. Errors due to the obstacle not being on the axis will be
smoothed out as the robot quickly moves to a new position and receives up-
dates. In this case, the term in the sensor model changes as a function of
speed. Murphy, Gomes, and Hershberger did a comparison of Dempster-
Shafer and HIMM with variable ; their results showed that the adaptive
approach produced better grids than a fixed or HIMM. 103

11.6.3 Errors due to observations from stationary robot

All three methods produce incorrect results if the robot is stationary and re-
peatedly returns the same range reading. HIMM is particularly vulnerable
to errors due to incorrect readings reinforcing extreme values on the grid.
Due to updating on the acoustic axis, only a very small part of the world is
updated after each observation. As a result, the robot sees a wall as a set of
isolated poles. If the wall is far enough away, the gaps between “poles” can
be quite large, causing the robot to attempt to head through them and then
have to avoid as subsequent updates prove the previous map wrong. If the
robot is experiencing incorrect or missing readings from specular reflection