Bayesian Grids
Hans Moravec
February 1987
\section{Bayesian Reasoning}
In most of our work to date, we have used {\it adhoc}
formulas to update the certainty grid estimates. Recently a less
arbitrary statistical approach derived from Bayes theorem has captured
our attention. Preliminary results using this approach are at least
as good as those from the old formulas. Many puzzling aspects of the
old scheme have been clarified in the process.
Let $\p(AB)$ represent our best estimate of the likehood of
situation A if we have received information B. By definition
\begin{equation}
\p(AB) =
{{\p(A\land B)}\over{\p(B)}}
\end{equation}
Plain $\p(A)$ represents our estimate of $A$
given no special information. The alternative to event $A$ will be
referred to as $\n{A}$ (not $A$). For any $B$
\begin{equation}
\p(AB) + \p(\n{A}B) = 1
\end{equation}
A certainty grid is a regular finite element model of space.
Each cell of the grid contains a liklehood estimate (our
``certainty'') of a given property of the corresponding region of
space. Primarily we are concerned with simple occupancy of the
region, represented by $\p(\o [x])$, the 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)$.
We will be considering data derived from wide angle sonar
range measurements. A given measurement will be designated $M[i]$,
with $i$ being the sequential number of the reading. The intersection
of a set of readings can be designated by a range in subscript, as in
\begin{equation}
M[D
\end{equation}
since the edge blocks the view behind it, the measurement gives
us no special information beyond d=D.
Graphically:
\begin{verbatim}
1 ___
 
\p(dD)  ________________________________ \p(\o)

0 ______________________
d=0 d=D d>D
\end{verbatim}
Relationsip (16) holds only if the edge is exactly at distance $D$.
Measurement $m$ tells us only that there is a probability $\P(Dm)$
that this is the case. To get the overall probability, we must sum
the $\p(dD)$s over all possible $D$'s, each weighted by its
probability of actually being the case. Thus
\begin{equation}
\p(dm) = \sum_D{(\p(dD)\times\p(Dm))}
\end{equation}
This will generally have the form
\begin{verbatim}
1
__
\p(dm) / \________________________________ \p(\o)
__/
0 _____________
(17) d=0 d=m d>D
\end{verbatim}
Though if the spread of $\p(Dm)$ is very large the hump at $d=m$ will
be attenuated, and the curve will have the approximate shape:
\begin{verbatim}
1
\p(dm) _____________________________ \p(\o)
____
0 __________
(17) d=0 d=m d>D
\end{verbatim}
The values of $\p(dm)$ can be used directly to update maps by
use of the combining formula \ref{combine}.
\section{Acknowledgement}
I wish to thank Peter Cheeseman for setting my nose firmly in
this groove. {\bf Statistical Decision Theory and Bayesian Analysis}
by J. O. Berger, 1985, was helpful too.
\end{document}