click on image to enlarge

Adventures in robot path planning Our lab's Planar Manipulator Display Project consists of lots of small robotic critters running around on a tabletop. For that project I threw 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. - Ken Perlin Instructions: 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: pathApplet.java extends BufferedApplet, calls PathFinder.java