A Bayesian Method for Certainty Grids
Hans P. Moravec
Dong Woo Cho (Now at Pohang Institute of
Science and Technology
Pohang City, Kyoungbuk, Korea)
Carnegie-Mellon University
Pittsburgh, PA 15213 USA
January 1989
\section{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 1000 random range measurements in a world
well mapped by other sensors. }
\section{Introduction}
In a previous paper [\cite{Moravec88}] we described our
experiences with an evolving series of techniques that allow
information from various noisy sensors on a mobile robot to be
accumulated into an increasingly good spatial map of its
surroundings. In these techniques space is represented by a regular
grid with each cell holding a number representing the probability,
based on accumulated sensor readings, that a particular patch of space
is occupied (as opposed to being vacant). In this paper we present new
mathematical developments on these ideas.
\def\n{\overline}
\def\o{{\bf o}}
\def\p{{\bf p}}
\def\P{{\bf P}}
\section{Definitions}
A certainty grid is a regular finite element model of space.
Each cell of the grid contains a likelihood estimate (our
``certainty'') of a given property of the corresponding region of
space. Here we are concerned simply occupancy of the region,
represented by $\o_x$. $\p(\o_x)$ is the likelihood (or probability)
that region $x$ is occupied. When a discussion contains only one
particular $x$, we will drop the subscript, and refer simply to
$\p(\o)$.
\begin{figure}
\vspace{4in}
\special{picture Venn scaled 325}
\caption{Venn Diagram}
\label{Venn}
\end{figure}
Let $\p(A|B)$ represent our best estimate of the likelihood of
situation A if we have received information B. By definition
\begin{equation}
\p(A|B) = {{\p(A\land B)}\over{\p(B)}}
\end{equation}
Plain $\p(A)$ represents our estimate of $A$ given no special
information. The alternative to situation $A$ will be referred to as
$\n{A}$ (not $A$). For any $B$
\begin{equation}
\p(A|B) + \p(\n{A}|B) = 1
\end{equation}
\section{Fundamental Formula}
For the two occupancy cases of a cell $\o$ (the cell is
occupied) and $\n{\o}$ (the cell is empty), with prior likelihoods
$\p(\o)$ and $\p(\n{\o})$ and new information $M$, Bayes theorem can
be expressed:
\begin{equation}
{{\p(\o|M)}\over{\p(\n{\o}|M)}} =
{{\p(M|\o)}\over{\p(M|\n{\o})}}\times
{{\p(\o)}\over{\p(\n{\o})}} \label{bayodds}
\end{equation}
This relationship follows from simple geometry in figure
\ref{Venn}, if the geometric area of an expression corresponds to its
probability, and if $A$ is identified with $\o$ and $B$ with $M$.
\section{Map Combining Formula}
\begin{figure}
\vspace{2in}
\special{picture VennI scaled 337}
\caption{Venn Diagram for Independent Variables}
\label{VennI}
\end{figure}
Formula \ref{bayodds} combines independent sources of information
about $\o$ and $M$ into an estimate of a single quantity $\p(\o|M)$.
The new information $M$, occurs in terms of the probability of $M$ in
the situation that a particular cell is or is not occupied, $\p(M|\o)$
and $\p(M|\n{\o})$. This inversion of $\o$ and $M$ is a key feature
of Bayes' theorem. But consider the problem of generating a map from
information $M_1$ and $M_2$ when each has already been individually
processed into a map, i.e. find $\p(\o|M_1\land M_2)$ given
$\p(\o|M_1)$ and $\p(\o|M_2)$. This requires finding $\p(A\land{B})$
knowing $\p(A)$ and $\p(B)$, which is not possible in the general case
of figure \ref{Venn}. But if we assume that $A$ and $B$ represent
independent information, the relationship is as in figure \ref{VennI},
and $\p(A\land{B}) = \p(A) \times \p(B)$. Algebra then gives us:
\begin{equation}
{{\p(\o|M_1\land M_2)}\over{\p(\n{\o}|M_1\land M_2)}} =
{{\p(\o|M_1)}\over{\p(\n{\o}|M_1)}}\times
{{\p(\o|M_2)}\over{\p(\n{\o}|M_2)}}
\label{combinesimple}
\end{equation}
Suppose $M1$ and $M2$ are not entirely independent, but
contain some common information $M_c$. M1, for instance, would be
factored into an independent component $M'_1$ and the dependent
component $M_c$:
\begin{equation}
{{\p(\o|M_1)}\over{\p(\n{\o}|M_1)}} =
{{\p(\o|M'_1)}\over{\p(\n{\o}|M'_1)}}\times
{{\p(\o|M_c)}\over{\p(\n{\o}|M_c)}}
\label{mix}
\end{equation}
The combining equation would then be written:
\begin{equation}
{{\p(\o|M_1\land M_2)}\over{\p(\n{\o}|M_1\land M_2)}} =
{{\p(\o|M_1)}\over{\p(\n{\o}|M_1)}}\times
{{\p(\o|M_2)}\over{\p(\n{\o}|M_2)}} /
{{\p(\o|M_c)}\over{\p(\n{\o}|M_c)}}
\label{contextfree}
\end{equation}
Where the division by the third term serves to remove one of the
redundant occurrences of $M_c$ in the expression.
Formula \ref{contextfree} can be used to build maps from
sensor readings if $\p(\o|M_1)$ is interpreted as the developing map,
and $\p(\o|M_2)$ represents a reading. The values of $\p(\o|M_2)$ can
be determined in a training session by accumulating occupancy
statistics each possible reading for a sensor in a variety of known
environments. The resulting averages will contain information about
the occupancy density of the training spaces as well as of the sensor
response. This effect can be removed by identifying the training space
density with $\p(\o|M_c)$ and dividing it out in formula
\ref{contextfree}. Another way of determining the $\p(\o|M_2)$ values
is from a detailed sensor model, such as the one outlined in the next
section. The model is applied to a map of uniformly unknown cells,
causing it to contain information from one reading. The resulting map
is then used to update the accumulating map using formula
\ref{contextfree}. This approach will be called the {\it
Context-Free} method. It is potentially very fast because the learned
or modeled $M_2$ values are independent of the current map, and can be
stored in tables. An update can then be done with as little as one
arithmetic operation per cell in a sensor's sensitive volume.
\begin{figure}
\vspace{2in}
\special{picture Range scaled 575}
\caption{Range Sensor Model}
\label{Range}
\end{figure}
\section{Range Sensor Model}
Imagine a single reading from a range sensor, modeled with
enough generality to subsume imperfect sonar measurements, single
stereo depth determinations, proximity or touch readings. The reading
has both range and lateral uncertainty and a position-dependent missed
detection and false alarm rate. A stereo measurement has small lateral
and range uncertainty, sonar has high lateral and small range
uncertainty, while a proximity sensor would have large lateral and
range uncertainty. Figure \ref{Range} represents a range reading
superimposed on a Certainty Grid. The range transducer is on the lower
left, and its sensitivity is assumed to drop to zero at the lateral
wedge lines, and to terminate at the range of first detection, on the
circular range surface. The grid is two dimensional, but the following
argument works equally well for three (or more) dimensions.
Take the grid cells in the interior and range surface of the
reading and sort them into a one dimensional array $c_i$ in order of
increasing distance from the transducer. A range reading can then be
modeled as the sequential passage of a sensing wavefront through the
$c_i$ that is eventually stopped at a particular cell $c_M$. For the
moment, assume we know the identity of $M$.
\begin{figure}
\vspace{2.03in}
\special{picture Ideal scaled 468}
\caption{Ideal Map}
\label{Ideal}
\end{figure}
Each cell $c_i$ in the real world is assumed to be either
occupied or empty. The transducer model has two probability functions
$Pdet_i$, that gives the probability that the sensing wavefront will
be stopped at particular cell if it should happen to be occupied, and
$Pfal_i$ (false alarm), the probability that the wavefront will be
stopped at an empty cell.
At any time a robot has only an occupancy estimate $\p(\o_i)$
for each cell, derived from prior information. A reading updates this
estimate. In this circumstance, the probability that a wavefront will
be stopped at $c_i$ can be estimated by combining the two
possibilities, weighted by their probabilities: $\p(halt_i) = \p(\o_i)
Pdet_i + \p(\n{\o_i}) Pfal_i$
We can use formula \ref{bayodds} to update the map after a
reading if we can determine ${\p(M|\o)}/{\p(M|\n{\o})}$. \p(M) is the
probability that the sensing wavefront passes unstopped through every
$c_i$ before $c_M$, then stops at $c_M$. This is given by $\p(M) =
(\prod_{i