4
2

Does anybody knows what are the 10 lines of C code mentioned by Prof. Sebastian to implement the robot localization using particle filters? It would be very useful seeing such code.

asked 17 Nov '11, 19:10

jorgerr's gravatar image

jorgerr
612


I really doubt these are 10 lines of C code. His algo was about 10 lines. So if you rely on a library to sample a pdf and that you remove all carriage returns from your code, you may end up in one line indeed... but otherwise, I wouldn't expect an implementation in less a 30-40 lines without loosing in readability and without using external libraries.

link

answered 17 Nov '11, 19:20

WhitAngl's gravatar image

WhitAngl
73812

This is python, but I'm really a C developer. You can follow it line by line against the algorithm presented in class (pretty much).

https://github.com/jtosey/particle_filter_demo

link

answered 18 Nov '11, 01:35

jrt's gravatar image

jrt
33619

1
So that's 188 lines...
(18 Nov '11, 16:02) Michael Jensen Michael%20Jensen's gravatar image
Ignoring white space lines, comments, initialization, moving, and taking the measurement, it's still a good 16 lines of code -- in a language "simpler" than C.
(18 Nov '11, 16:04) Michael Jensen Michael%20Jensen's gravatar image

Perhaps they are very loooooong lines. :-D

link

answered 18 Nov '11, 16:26

Finix's gravatar image

Finix
1.1k217

Here is a longish video lecture from Prof Simon Godsill on particle filters. Don't know how good it is because I myself have not seen it fully.

http://videolectures.net/mlss09uk_godsill_pf/

link

answered 17 Nov '11, 21:47

rover's gravatar image

rover
8666

edited 17 Nov '11, 21:48

I'll take a guess, though using Pythonish syntax:

num_particles = 10000
particles = [[random(width),random(height),random(360)] for i in range(num_particles)]  
# make a bunch of initial particles.  The ones stuck in walls will die soon enough.

while( stillMoving ):
   # move
   for each x, y, direction in particles:
      turn, move = move_robot()
      distance = move * random.guass(mu= 1.0, sigma = 0.6)
      direction = (turn + direction + turn * random.guass(mu = 0, signma = 3.0) % 360
      new_x, new_y = x + cos(direction) * distance), y + sin(direction) * distance
      if intersect_wall(map, (x,y), (new_x, new_y)):
             particle = random.choice(particles)
      x, y = new_x, new_y
      # move.  For each particle pick a different amount of distance and direction skew.
      # if it moved through a wall.  It's dead.  Maybe just copy a random live particle

      for distance, angle in scan_with_sensors():
          if math.abs(distance - nearest_wall(map, x, y, direction + sensor.angle)) > 1.8:
              particle = random.choice(particles) 
      # sense with range finders and kill particles where distance is off by too much.

OK, so this is one is fourteen lines plus comments, or eleven without the "move through a wall" step: those particles will die from sensor problems. The basic idea here was "move each particle by picking a random state transition. If it moves through a wall or disagrees with a range finder by more the 1.8, then that particle is an inconsistent belief and I can copy another particle and start diverging on the next step.

Given this is one pass without running it, what are the bugs and errors in thinking?

link

answered 18 Nov '11, 16:51

CharlesMerriam's gravatar image

CharlesMerriam
1.5k112

1
Don't know about bugs, but, if this were Python, your line "x, y = new_x, new_y" would be superfluous (i.e. you would not need to introduce new_x and new_y in the first place). Furthermore, given that your if statements are all essentially one liners, you could put them in one line e.g. "if this: that". Remove num_particles as a variable (i.e. hard-code the value) and you are down to 10 lines! ;-)
(18 Nov '11, 17:08) aroberge aroberge's gravatar image

It's probably about ten lines of code, all right, just without the housekeeping.

It's a bit like how pseudocode for the essence of the Bresenham line drawing algorithm (minus the octant selection) can be written on a postage stamp. The Bresenham circle drawing algorithm's only a wee bit bigger than that (It's so cool that it uses no transcendental functions or floating point, yet generates stable, accurate and nice looking circles!).

But the housekeeping code required for any of that on any real platform is huge and unfortunately tedious to write and is platform specific.

link

answered 19 Nov '11, 08:43

Blancmange's gravatar image

Blancmange
1.6k7

I'm guessing he's talking about: unit 11-20 -- but even then it's just pseudo code.

Though, from an abstract point of view, considering only the logic itself, minus all the implementation specific stuff (like state objects, control objects, probability & sampling functions, etc...) probably could be done in 10 lines of code.

link

answered 18 Nov '11, 16:50

Michael%20Jensen's gravatar image

Michael Jensen
929

Your answer
toggle preview

Follow this Question via Email

Once you sign in you will be able to subscribe for any updates here

Q&A Editor Basics

  • to upload an image into your question or answer hit
  • to create bulleted or numbered lists hit or
  • to add a title or header hit
  • to section your text hit
  • to make a link clickable, surround it with <a> and </a> (for example, <a>www.google.com</a>)
  • basic HTML tags are also supported (for those who know a bit of HTML)
  • To insert an EQUATION you can use LaTeX. (backslash \ has to be escaped, so in your LaTeX code you have to replace \ with \\). You can see more examples and info here

powered by OSQA