When using Hidden Markov Models in Global Localization problems on the prediction step there is a need to calculate the probability of robot's pose given the actions (control u, odometry):

p(Xt|Xt−1, Ut−1)

where xt-1 and ut-1 are the robot's previous pose and control.

There are different tutorials (this one for instance) and articles on the web with the examples, but most of these examples are for the 1D localization problem where action simply equals to 1 if the odometry is perfect.

What if I am considering 2D space? For example in 1D example for time step T=1 I would compute like:

p(Xt = 2 | Xt-1 = 1, Ut = 1) = 1

How should I do the computations for 2D case?


1 Answer 1


Multi-dimensional models

In the 2D case, $x_t$ is a vector with two components (e.g. position in $x$, $y$), but why stop at 2D? Often, the state vector $x_t$ will have your position in two or three dimensions, in addition to velocity and acceleration. Oftentimes we also include angular state in $x_t$ such as the heading and angular rate of change.

Your control is also often multi-dimensional, for example if you have a wheeled robot it could be the velocity of the left and right wheels.

Linear case (Kalman filter!)

Typically we have a model that maps the previous state and control actions to a new state and control action. In the linear, time invariant case, we have matrices $A$ and $B$, and $$x_t = A x_{t-1} + B u_t $$ in this setting we would probably use a Kalman filter to keep track of our belief about the distribution of $x_t$. The Kalman filter is nice because it gives a closed form solution to the estimation problem which is correct if noise/uncertainty is Gaussian.

More general models

The markov approach (as I understand it) let's us move past these assumptions (linearity and Gaussian noise) by using approximation methods such as particle filters to estimate the belief distribution of our state $x_t$. The markov assumption is saying that we only need the distribution of $x_t$ (and don't need to use the distribution of $x_{t-1},x_{t-2},\dots$) when computing the distribution of $x_{t+1}$. I think the figure on slide 30 of the link you posted illustrates this quite well.

Discrete (small) state space

As for your last question about how to find your belief: it depends on your application. If your state/controls are discrete, and you don't have very many of them, you can explicitly write down all of the transition probabilities $p(x_t \mid x_{t-1}, u_t)$ for every possible $x_t$, $x_{t-1}$ and $u_t$. Then when you do your estimation, you just look up the appropriate value.

Further reading

Typically states are continuous, or there are too many to compute/store every possible transition. If you're just getting started in this, try a Kalman filter and see how that works for you (there are many tutorials on them). If you want to see what else is out there, I recommend the Probabilistic Robotics book, which gives a still quite good overview of different approaches (including Kalman filters) for this localization problem.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.