  In this paper, we describe a representation for spatial information, called
the stochastic map, and associated procedures for building it, reading
information from it, and revising it incrementally as new information is
obtained. The map contains the estimates of relationships among objects in the
map, and their uncertainties, given all the available information. The
procedures provide a general solution to the problem of estimating uncertain
relative spatial relationships. The estimates are probabilistic in nature, an
advance over the previous, very conservative, worst-case approaches to the
problem. Finally, the procedures are developed in the context of
state-estimation and filtering theory, which provides a solid basis for
numerous extensions.
