next up previous
Next: Selective Update Up: Grid-based Representation of the Previous: Grid-based Representation of the

Pre-Computation of the Sensor Model


As described in Section 3.2, the perception model tex2html_wrap_inline2919 for proximity sensors only depends on the distance tex2html_wrap_inline2985 to the closest obstacle in the map along the sensor beam. Based on the assumption that the map of the environment is static, our approach pre-computes and stores these distances tex2html_wrap_inline2985 for each possible robot location l in the environment. Following our sensor model, we use a discretization tex2html_wrap_inline2987 of the possible distances tex2html_wrap_inline2985 . This discretization is exactly the same for the expected and the measured distances. We then store for each location l only the index of the expected distance tex2html_wrap_inline2985 in a three-dimensional table. Please note that this table only needs one byte per value if 256 different values for the discretization of tex2html_wrap_inline2985 are used. The probability tex2html_wrap_inline3279 of measuring a distance tex2html_wrap_inline3001 if the closest obstacle is at distance tex2html_wrap_inline2985 (see Figure 6) can also be pre-computed and stored in a two-dimensional lookup-table.

As a result, the probability tex2html_wrap_inline2919 of measuring s given a location l can quickly be computed by two nested lookups. The first look-up retrieves the distance tex2html_wrap_inline2985 to the closest obstacle in the sensing direction given the robot is at location l. The second lookup is then used to get the probability tex2html_wrap_inline3295 . The efficient computation based on table look-ups enabled our implementation to quickly incorporate even laser-range scans that consist of up to 180 values in the overall belief state of the robot. In our experiments, the use of the look-up tables led to a speed-up-factor of 10, when compared to a computation of the distance to the closest obstacle at run-time.

Dieter Fox
Fri Nov 19 14:29:33 MET 1999