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.
Drag on any robot to move it. Then: