3

I am starting in robotics, and reading about Markov Localization, I have one doubt, probably very stupid, but, well, I want to solve it.

Let's take the CMU Website example: https://www.cs.cmu.edu/afs/cs/project/jair/pub/volume11/fox99a-html/node3.html

Basically and very summarized:

  1. The robot does not know its location (uniform probability of being at any point), but knows there are 3 doors.
  2. It senses a door, and since that door could be any one out of the 3, the belief distribution spikes at those 3 doors.
  3. It moves to the right, and the belief distribution shifts to the right also, let's say "following the robot movement", and then the convolution is done when finding the 2nd door... This gets described in the next graphic, from the CMU:

enter image description here

But why does the belief distribution get shifted to the right, and not to the left, as the door is left behind?

Shouldn't the robot sense that there's no door between door 1 and 2 (starting from the left)?

Is there something about probability theory I've forgotten (I studied it like 14 years ago)?

abhishek47
  • 327
  • 2
  • 12
xCovelus
  • 133
  • 5

3 Answers3

2

I think this is just a way of illustrating the main idea behind the probability distribution and the representation is not complete.

The idea is that there is a moment when the door is detected and the prior distribution not yet considered, this is when the robot assumes this could also be door 1 and therefore the positions of the other doors are as shown. There can be 3 similar images drawn, where the robot assumes standing in front of door 2 or door 3, but when the prior information is mixed in, only door 2 seems plausible.

I am just guessing, I did not read the book.

50k4
  • 6,652
  • 1
  • 12
  • 25
2

The robot has sensed a door, so the initial belief distribution matches the three possible door positions. i.e. the only three places that it is possible for the robot to be in that scenario.

The robot moves to the right so, since the belief distribution matches the possible positions of the robot, the belief distribution must also move to the right. As the robot moves, so the belief distribution must move with it.

Notice that the three peaks are no longer quite as well defined at this point because of that motion. Movement is inherently noisy, which introduces uncertainty. The more the robot moves, the less certain it becomes about its position, and the belief distribution thus tends to flatten or smooth out.

Finally, the robot senses the second door. Given the (previously known) possible door positions, the belief distribution now also centres on the second door in the diagram.

sempaiscuba
  • 1,064
  • 3
  • 13
  • 25
2

Here is what I 'believe'.

Lets make the diagram more labeled. Say door 1 starting from left most is at 4 meters from the origin at left, door 2 at 7 meters, door 3 at 15 meters.

When the robot senses a measurement corresponding to a door it thinks that it has high and equal probability of standing in front of any of those doors and very low probability that it is not in front of a door. Now it believes that it is highly at either 4,7 and 15 meters and low likely to be any other x meters. The position of a peak is where it think it might be(4,7 and 15). Here there are 3 doors so there are 3 peaks. Clear till now?

Now it moves 1 meters lets say. Now it will believe that it has high probability of being at either 4+1, 7+1 or 15+1 meters. Now you can see that the peaks has to be at 4+1, 7+1 and 15+1 meters as this is just a simple shift to update its current belief (Now it believes it is highly 1 meter right to any of those doors). That said the peaks has to be shifted or ultimately the whole distribution about its current belief. This is the reason why the distribution shifts towards right.

Rest of the answer is a bonus! Lets move ahead

Dang!!! but it knows that it might has not moved exactly to be 1 meter and has errors in movement (lets say 0.1 meters for every meter it moves). so it now might be at 4+1+-0.1 and so on. So the graph flattens a bit as now it thinks it is highly nearby 4+1, 7+1 and 15+1 but not exactly there!. So the peaks flatten.(black as in original "Probabilistic robotics book figure 1.1") If it has moved by 3 meters the uncertainty would be more to be at exactly 4+3, 7+3 and 15+3 meters (4+3+-0.3 etc). This explains, as answered above the more it moves the more its belief gets uncertain for those peaks(current highly possible positions)!

Now again it moves(by lets say 'nearly' 2 meters) and senses a door. So it shifts its distribution and changes it to 'around' 7,10 and 18 meters. Now as it has sensed a door it again thinks that it is in front of any of those doors. So 3 red peaks again at 4,7 and 15 meters. But given the black peaks already at around 7, 10 and 18 meters, logically it can only be at 7 as the intersection of those beliefs sets {4,7,15} and {7,10,18} is 7, Here we are talking about intersection of peaks (highly possible positions!!) now it is certain that it is at 7 meters. This can be done by just multiplying the probabilities distributions(of prior belief and belief according to 2nd measurement) as the two measurements are independent (that's why we took red peaks when it sensed a second door) as supported by Markov's independent assumption rule.

Now wherever it moves it belief of where it is moves.

Hope that helps.

Dhaval Ashokkumar Patel
  • 21
  • 2