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


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.


answered 17 Nov '11, 19:20

WhitAngl's gravatar image


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).



answered 18 Nov '11, 01:35

jrt's gravatar image


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


answered 18 Nov '11, 16:26

Finix's gravatar image


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.



answered 17 Nov '11, 21:47

rover's gravatar image


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?


answered 18 Nov '11, 16:51

CharlesMerriam's gravatar image


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.


answered 19 Nov '11, 08:43

Blancmange's gravatar image


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.


answered 18 Nov '11, 16:50

Michael%20Jensen's gravatar image

Michael Jensen

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