Solving the kidnapped robot problem using particle filters

5

Hi,

I was wondering if it would be possible to solve the kidnapped robot problem (localization after a random replacement) using our particle filter implementation. Well, it's much easier than I initially expected. Actually, it took only 4 lines of additional code to solve the problem :)

Here's what I did: Each turn there's a 10% chance that the robot is replaced. Using the 'normal' solution for homework assignment 3.6 the algorithm is then (in most cases) unable to localize the robot again:

Incorrect position belief after replacement

So, in order to solve the problem all I had to do was to randomly seed some particles in the world for each iteration, which will result in something like this:

Correct position belief thanks to randomly distributed particles

And that's it! After a replacement the algorithm will converge to the correct position after 1-3 iterations.

Of course, this is not a new idea by any means, but I was still surprised how easy it was to implement this. Maybe some of you will find it interesting as well :)

I'll upload my code tomorrow, in the meantime you can see the algorithm working here:

Youtube video

I made some changes to the visualization, so that for each iteration the robot movement and the motion prediction is visualized as well.

Have fun :)

edit: Here's the code: Github

Add random particles:

for i in range(int(0.9 * N)):
      (Resampling wheel)
for i in range(N - (int(0.9 * N))):
      r = robot()
      r.set_noise(bearing_noise, steering_noise, distance_noise)
      p3.append(r)

asked 12 Mar '12, 19:46

neb-2's gravatar image

neb-2
86●2●5●7
accept rate: 0%

edited 13 Mar '12, 20:54

One Answer:
0

Really interesting!

I always had the intuition that it would be a good idea to add those random particles in each iteration, and this proves it useful.

link

answered 13 Mar '12, 21:06

Manuel%20Araoz's gravatar image

Manuel Araoz
1.4k●7●14●24

Yes, I think it's a good idea in general. Even when it's impossible that the robot is randomly replaced (e.g. if it's a car ;) there's still a slight chance that the particles won't converge to the correct position immediately.

(14 Mar '12, 05:28) neb-2 neb-2's gravatar image
Your answer
Question text:

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • image?![alt text](/path/img.jpg "Title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported

learn more about Markdown

Tags:

×5,185
×183
×76
×55
×6
×1

Asked: 12 Mar '12, 19:46

Seen: 395 times

Last updated: 14 Mar '12, 05:28

Related questions

[closed] Killing particles beyond boundaries,3-6

Intepreter only runs modified code

how to handle distance noise in hw3.6

[closed] HW3.6 "myrobot.sense()" missing parameter

unit 1.3 robot localization - does the robot have an internal map to start with?

Running Homework 3-6 repeatedly: Same "random" numbers?

[closed] HW3-6 : X and Y position swapped

[closed] HW 3.6 - what am I doing wrong?

[closed] HW3-6 Not Random in Udacity HW Environment

In HW 3.5 and 3.6 measurement vector has swapped columns 1-3 (?)