I have some issues with understanding the Particle Filter for navigation through a known map. So, consider a situation where I want to write a Particle filter to navigate through a maze or a map that is known beforehand. I also know where is the target (exit from the maze/map). So, basically the idea is quite simple, since the map is known I can easily know where I should move on next.

The fields on the map have randomly assigned integers to them, so I can use them as observations. The only unknown thing is basically the random start point of the robot.

So, generally I have the following algorithm, which is a quite classic Bootstrap Filter I guess:

Sample N samples from p(x0) 
Assign all the weights value of 1/N
2.Importance Sampling
For 1 to N perform sampling xt from P(xt|xt-1)
For 1 to N assign weight based on P(yt|xt)
3.Resample with replacement based on weights

The only thing that I don't understand is how should the P(xt|xt-1) works in this case. I assume no noise, in this case, to make it easier. I mean, since the map is known beforehand and the target is known too, this means that there should be only one desired xt for each xt-1, but I am not sure how to capture that. Will be glad for some guidance.

EDIT: So basically the idea is that the observations(yt) are as I said some numbers that are on the floor in the maze (each field has only 1 number), but the numbers can be duplicated between multiple fields. Xt is in this case position of the robot as it's randomly generated and unknown to the robot.


This seems very confused, what are your xt and yt variables meant to be exactly?

Typically in a particle filter, xt is an unobserved state variable, and yt is an observation that depends on the state. The particle filter gives an estimate of the states xt. Its not obvious to me how your problem fits into this framework; nothing is unobserved, and nothing is being estimated.

| cite | improve this answer | |
  • $\begingroup$ Ah, perhaps I have explained that incorrectly. So, basically xt is unknown since it's randomly generated (and not known to the robot, kinda like in kidnapped robot problem), each field in the maze has a random number generated on it (obviously more than one field can have the same number). Edited the question :) $\endgroup$ – Dominik Wosiński Jun 24 at 7:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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