Distributed Algorithm Library

The goal of this project is to design a library of practical, well-abstracted, multi-robot distributed algorithms, suitable for many applications. One example application was searching a building for an item of interest. Videos of some of the primitive behaviors are below, videos of the building search application are near the bottom of the page.

Publications

"Dynamic Task Assignment in Robot Swarms"
James McLurkin and Daniel Yamins, Robotics: Science and Systems Conference, June 8, 2005

"Distributed Algorithms for Dispersion in Indoor Environments using a Swarm of Autonomous Mobile Robots"
James McLurkin and Jennifer Smith, Distributed Autonomous Robotic Systems Conference, June 23, 2004

"Stupid Robot Tricks: A Behavior-Based Distributed Algorithm Library for Programming Swarms of Robots"
James McLurkin, S.M., M.I.T., 2004, Thesis Supervisor: Leslie P. Kaelbling

Videos

Primitive Behaviors

The behaviors described below are primitive building blocks for building more complicated swarm applications. Their inner workings are described in detail in my Master's Thesis.

matchOrientation (3,661,KB mpg)

The pictures above show the matchHeadingToRobot behavior in action. The robot with the antenna is the reference robot, all other robots are active robots.

beaconNavigation (3,071 KB mpg)

The pictures above show how a long-range ISIS beacon can be used with the matchHeadingToRobot behavior to guide the robots in along global heading. The robots are trying to move "north". As the beacon is rotated, all the robots change their direction accordingly. If the heading of the beacon is kept constant, the robots can use it like a compass to determine their absolute heading. Multiple beacons can be used to cover the entire workspace.

orbitRobot (4,027 KB mpg)

This video clip shows a group of robots orbiting a reference robot. The reference robot is the one with the tall black antenna.

disperseFromSource (3,702 KB mpg)

This video clip shows the disperseFromSource behavior in action.

disperseUniformly (4,363 KB mpg)

disperseUniformly-2 (4,010 KB mpg)

These video clips show the disperseUniformly behavior in action. For the keen of eye, robots that are near walls are flashing their blue light; robots in the interior are flashing their green light.

followTheLeader (20,903 KB mpg)

This video clip shows the followTheLeader behavior in action. Constant handshaking between successive robots keeps the line robust. If a robot does not respond, another is recruited to take its place. The chain breaks in image four, re-forms in image five, and is stable in the final image.

navigateGradient (4,948 KB mpg)

This video clip shows the navigateGradient behavior in action. The source robot is wearing a small flag and is highlighted in green in the bottom center of the images. The active robot is highlighted in red.

clusterOnSource (4,635 KB mpg)

This video clip shows the clusterOnSource behavior in action.

clusterIntoGroups (3,298 KB mpg)

This video clip shows the clusterIntoGroups behavior in action. There are three groups, red, green, and blue. Each group elects a leader, and robots use the navigateGradient behavior to move towards the leader of each group. Once robots are grouped, entire groups move away from other nearby groups.

counting (8,010 KB mpg)

This video clip shows the counting behavior in action.

dockToCharger (3,629 KB mpg)

This video clip shows the dockToCharger behavior in action.

Physical Bubble Sort (23,425 KB avi)

This video clip shows the bubble line physical bubble sort algorithm arrangeing the swarm into a line. The video is approximately 10x actual speed