Algorithms for swarm robotics

The emerging field of swarm robotics is devoted to the utilization of a multitude of very small robots, each with limited capabilities, to perform relatively complex cooperative tasks. The actions of these robots are affected by the local features of the environment as well as low bandwidth communications between robots that are in close proximity. The behavior of a robot swarm can be compared to models of collective behavior observed in nature, e.g., in ants, bees, and birds.; We focus on two algorithmic problems that arise in the area of swarm robotics: The Freeze-Tag Problem (FTP) and the Disperse and Fill Problem (DFP). We propose and analyze heuristics for both problems; our contributions include both theoretical and experimental results.; In the FTP, the goal is to devise simple strategies so that a swarm of robots can be “awakened” in the shortest amount of time. In order to wake up a sleeping robot, an awake robot must move to within close proximity of the asleep robot. When a robot awakens, it must decide where to go next in order to assist the swarm in awakening other sleeping robots. We analyze theoretically and experimentally a class of “greedy” strategies for the FTP.; The goal in the DFP is to devise sensing and motion strategies for a swarm of robots to disperse as quickly as possible in an unknown environment, while maintaining communication connectivity of the swarm. We devise strategies that replace direct communication among robots with the use of “virtual pheromones” that serve as small independent beacons. We perform experiments to compare strategies within a software simulation we developed.; Finally, we study a problem of terrain simplification that arises in applying visibility-based algorithms on complex geometric terrains. The novelty of our study is that it is directed at a new performance measure in compressing geometric terrain data—preserving as much as possible the inter-point visibility relationships for a given set of sample points above the terrain. We implement and compare experimentally a few different strategies for visibility-preserving terrain simplification.