Adventures in robot path planning

        For our "robot creatures on a table" project, I put together this simple-minded algorithm that allows a bunch of robots to get from a start position to an end position, without crashing into each other.

The basic approach is "divide and conquer:" First find a position 1/2 way along the path where they don't crash into each other, then find 1/4 and 3/4 positions, and so on. Finally, gradually "relax" the paths, by alternately smoothing them and pushing them away from each other.

In this demo applet, we choose random setups (random start and end positions), and the robots need to figure out a path that works.


Drag on any robot to move it. Then:

  • Use ↑ and ↓ keys to move robots forward or back along path;
  • Use PgUp and PgDn keys to move robots to end or start of path;
  • Use '-' and '+' keys to shrink or grow robots;
  • Use ← and → keys to select previous or next random setup.

Source code: extends BufferedApplet

Copyright 2003 Ken Perlin