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.