Page 241 - Introduction to Autonomous Mobile Robots

226

Figure 5.24 Chapter 5
Improving belief state by moving.

The basic idea, which we call randomized sampling, is known alternatively as particle filter
algorithms, condensation algorithms, and Monte Carlo algorithms [68, 144].
Irrespective of the specific technique, the basic algorithm is the same in all these cases.
Instead of representing every possible robot position by representing the complete and cor-
rect belief state, an approximate belief state is constructed by representing only a subset of
the complete set of possible locations that should be considered.
For example, consider a robot with a complete belief state of 10,000 possible locations
at time t. Instead of tracking and updating all 10,000 possible locations based on a new
sensor measurement, the robot can select only 10% of the stored locations and update only
those locations. By weighting this sampling process with the probability values of the loca-
tions, one can bias the system to generate more samples at local peaks in the probability