Bayesian method for localization and map making

Bayesian methods rely on the usage of bayes theorem 20220301203417 for computing the probability that a region of the grid is occupied or not given a particular reading, and use this readings for updating the probabilities of each grid cell.

Sonar probabilities

When using the sonar sensor model 20220228203000 bayes uses this formulas to state if a region (either region I or II) is occupied or not:

For region I:

\(P(Occupied)=\\frac{(\\frac{R-r}{R})+(\\frac{\\beta-\\alpha}{\\beta})}{2} \* Max\_{occupied}\) P(Empty) = 1 − P(Occupie**d) For region II, equations are:

P(Occupied*) = 1 − *P*(*Empt**y) \(P(Empty)=\\frac{(\\frac{R-r}{R})+(\\frac{\\beta-\\alpha}{\\beta})}{2}\) Note that, although we can never be fully aware if a region is Occupied (whats why we have MaxOccupied) we can be sure that a region is empty.

Bayes theorem on occupancy and sensor readings

From bayes theorem, we can say that: \(P(Occupied|s)=\\frac{P(s|Occupied)P(Occupied)}{P(s|Occupied)P(Occupied)+P(s|Empty)P(Empty)}\) We know P(s|Occupied*) and *P*(*s*|*Empty*) from our sensor readings, and *P*(*Occupied) and P(Empty) is our prior knowledge about a given cell being empty or not. If we don’t know, we can assume that P(Occupied*) = *P*(*Empt**y) = 0.5. We can then calculate the probability of being occupied of the cell for our new readings.

Updating probabilities

The priors can be initialized as 0.5, as we stated before. If we know that our readings are independent experiments, we can say that P(s1, s2, …, sn|H)P(H) = P(s1|H)P(s2|H)…P(sn|H). We need to store all readings, which can translate into a storage problem. Fortunately, a recursive version of Bayes rules can be derive that states: \(P(H|s\_n)=\\frac{P(s\_n|H)P(H|s\_{n-1})}{P(s\_n|H)P(H|s\_{n-1})+P(s\_n|\\neg H)P(\\neg H|s\_{n-1})}\) With this formula we need only to store the last probability computed in order to continuously update the map when processing new data.

Notes References

20220301203417 Bayes theorem

20220228202048 Iconic localization and map making

20210514183815 INDEX - Robotics

References

(Murphy 2000)

Murphy, Robin. 2000. Introduction to AI Robotics. Intelligent Robotics and Autonomous Agents. Cambridge, Mass: MIT Press.