We will now return to the issue of how to represent and compute the
belief distribution of the robot efficiently, describing what one
might think of as the ``nut and bolts'' of grid-based Markov
localization. Recall that to obtain accurate metric position
estimates, our approach to Markov localization uses a fine-grained
discretization of the state space. Here *L* is represented by a
three-dimensional, regularly spaced grid, where the spatial resolution
is usually between 10cm and 40cm and the angular resolution is usually
2 or 5 degrees. Figure 10 illustrates the structure
of a position probability grid. Each layer of such a grid corresponds
to all possible poses of the robot with the same orientation.

While such a fine-grained approximation makes it possible to estimate the robot's position with high accuracy, an obvious disadvantage of such a fine-grained discretization lies in the huge state space which has to be maintained. For a mid-size environment of size m , an angular grid resolution of , and a cell size of cm the state space consists of 7,200,000 states. The basic Markov localization algorithm updates each of these states for each sensory input and each atomic movement of the robot. Current computer speed, thus, makes it impossible to update matrices of this size in real-time.

To update such state spaces efficiently, we have developed two
techniques, which are described in the remainder of this section. The
first method, introduced in Section 3.4.1,
pre-computes the sensor model. It allows us to determine the likelihood
of sensor measurements by two look-up
operations--instead of expensive ray tracing operations. The second
optimization, described in Section 3.4.2,
is a *selective update* strategy. This strategy focuses the
computation, by only updating the *relevant* part of the state
space. Based on these two techniques, grid-based Markov localization
can be applied on-line to estimate the position of a mobile robot
during its operation, using a low-cost PC.

Fri Nov 19 14:29:33 MET 1999