Probabilistic Robotics Bayes Filter Implementations Discrete

Probabilistic Robotics Bayes Filter Implementations Discrete filters SA-1

Piecewise Constant 2

Discrete Bayes Filter Algorithm 1. 2. 3. 4. 5. 6. 7. 8. Algorithm Discrete Bayes filter( Bel(x),d ): 0 If d is a perceptual data item z then For all x do Bel ' ( x) P( z x) Bel ( x) Bel ' ( x) For all x do Bel ' ( x) 1 Bel ' ( x) 9. Else if d is an action data item u then 10. For all x do 11. Bel ' ( x) P( x u , x' ) Bel ( x' ) 12. Return Bel’(x) x' 3

Piecewise Constant Representation Bel ( xt x, y, ) 4

Implementation (1) To update the belief upon sensory input and to carry out the normalization one has to iterate over all cells of the grid. Especially when the belief is peaked (which is generally the case during position tracking), one wants to avoid updating irrelevant aspects of the state space. One approach is not to update entire sub-spaces of the state space. This, however, requires to monitor whether the robot is delocalized or not. To achieve this, one can consider the likelihood of the observations given the active components of the state space. 5

Implementation (2) To efficiently update the belief upon robot motions, one typically assumes a bounded Gaussian model for the motion uncertainty. This reduces the update cost from O(n2) to O(n), where n is the number of states. The update can also be realized by shifting the data in the grid according to the measured motion. In a second step, the grid is then convolved using a separable Gaussian Kernel. Two-dimensional example: 1/16 1/8 1/16 1/8 1/4 1/8 1/16 1/8 1/16 1/4 1/2 1/4 1/2 1/4 1/4 Fewer arithmetic operations Easier to implement 6

Grid-based Localization 7

Sonars and Occupancy Grid Map 8

Tree-based Representation Idea: Represent density using a variant of octrees 9

Tree-based Representations Efficient in space and time Multi-resolution 10

Xavier: Localization in a Topological Map [Courtesy of Reid Simmons] 11