--------------------------------------------------------------
Sensor Model Learning in A Bayesian Method for Certainty Grids
--------------------------------------------------------------

Mobile Robot Laboratory working paper, December 1989
by
	 Hans Moravec,  Dong Woo Cho, Herbert Enderton
	 Robotics Institute
	 Carnegie-Mellon University
	 Pittsburgh, PA  15213

Abstract

	In earlier work we introduced a probabilistic, finite-element
representation of robot spatial knowledge we call ``certainty grids''.  The
grids allow the efficient accumulation of small amounts of information from
individual sensor readings into increasingly accurate maps of a robot's
surroundings. Early experiments using the method to interpret measurements
from a ring of 24 Polaroid sonar transducers carried on board an
autonomously navigating mobile robot were surprisingly successful, compared
with our earlier experiences with stereo-vision based programs that mapped
points on objects as error distributions in space. These older programs
enabled a robot to map and traverse cluttered 30 meter obstacle courses,
succeeding about three times in four attempts. By contrast the grid method
accomplished a similar task with a vanishingly small failure rate. We then
used the grid approach to a stereo-vision equipped robot, also with
excellent success. A subsequent experiment integrated sonar and vision data,
generating maps with correct features not found in those from either
sensor alone.

	These encouraging early results were obtained using ad-hoc
statistical models and methods. We then developed a Bayesian statistical
foundation for grid updates. A key result of this derivation was a combining
formula for integrating two independently derived maps of the same area, or
for adding a new reading to a developing map. This combining formula
incorporated in one expression (and improved on) several different parts of
the ad-hoc approach. In this paper we introduce a more specialized Bayesian
combining formula for inserting range readings into maps.  The formula is
suitable for sonar, stereo, laser, proximity and touch measurements. By
making use of the property of this kind of sensor that nearby objects
occlude distant ones, the new (context-sensitive) formula manages to extract
more information from a reading than the older (context-free) version. To
insert a sensor reading, the context free method has a computational cost
linear in the number of grid cells in the sensitive volume of the sensor.
The context-sensitive formula has a cost dominated by a term quadratic in
the volume of range uncertainty of the reading.  Using simulated data, we
compare the performances of the context-free formula, the context-sensitive
one used incrementally, and the context-sensitive formula operating in a
"batch" mode, in which every reading of a batch serves as context for all
the others. Given the same input, the context-sensitive formula produces
slightly better maps than the context-free method, and the batch mode does
better than the incremental mode. But typically the differences are small. A
few more readings processed by the cheaper context-free method can
compensate for its slightly less efficient use of each reading.

	The paper also shows how this approach allows sensor models to be
learned as a wandering robot equipped with several sensors gathers
experiences.  As an example, a sonar-type sensor whose characteristics are
initially completely unknown is well characterized after experiencing as few
as 10,000 random range measurements in a world well mapped by other sensors.
An experiment with real data acquired by a sonar equipped robot operating
in a narrow hallway of smooth, specularly reflecting walls shows the value
of learning.  With an initial model suitable for cluttered environemnts
where specular reflections are rare, the map returned in the specular
hallway is worthless for navigation since it consists mostly of artefacts.
With a learning-tuned model, however, a somewhat blurry but otherwise
good map emerges from the same data.  In this experiment the learned
sensor model indicates that (in this kind of environment) only about one
sonar measurement out of eight give a correct range.  The other seven are
specular artefacts.