We develop and analyze algorithms for dispersing a swarm of primitive robots in an unknown environment, R. The primary objective is to minimize the makespan, that is, the time to fill the entire region. An environment is composed of pixels that form a connected subset of the integer grid. There is at most one robot per pixel and robots move horizontally or vertically at unit speed. Robots enter R by means of k>=1 door pixels Robots are primitive finite automata, only having local communication, local sensors, and a constant-sized memory. We first give algorithms for the single-door case (i.e., k=1), analyzing the algorithms both theoretically and experimentally. We prove that our algorithms have optimal makespan 2A-1, where A is the area of R. We next give an algorithm for the multi-door case (k>1), based on a wall-following version of the leader-follower strategy. We prove that our strategy is O(log(k+1))-competitive, and that this bound is tight for our strategy and other related strategies.
@cite_18: In our Pheromone Robotics research, we are developing techniques for coordinating the actions of large numbers of small-scale robots to achieve useful large-scale results in surveillance, reconnaissance, hazard detection, and path finding. This paper describes progress in the areas of world- embedded computation and world-embedded displays that are enabled by our use of the biologically inspired notion of a "virtual pheromone." We describe the pheromone logic primitives that enable our robot collective to become a distributed computing mesh embedded within the environment, while simultaneously acting as a physical embodiment of the user interface.
@cite_26: 
@cite_22: 
@cite_29: The distributed coordination and control of a set of autonomous mobile robots is a problem widely studied in a variety of fields, such as engineering, artificial intelligence, artificial life, robotics. Generally, in these areas the problem is studied mostly from an empirical point of view. In contrast, we aim to understand the fundamental limitations on what a set of autonomous mobile robots can achieve. We describe the current investigations on what autonomous mobile robots can and can not do with respect to some coordination problems.
@cite_21: Efficient graph search is a central issue in many aspects of AI. In most of existing work there is a distinction between the active “searcher”, which both executes the algorithm and holds the memory, and the passive “searched graph”, over which the searcher has no control at all. Large dynamic networks like the Internet, where the nodes are powerful computers and the links have narrow bandwidth and are heavilydloaded, call for a different paradigm, in which most of the burden of computing and memorizing is moved from the searching agent to the nodes of the network. In this paper we suggest a method for searching an undirected, connected graph using the VertexdAntdWalk method, where an a(ge)nt walks along the edges of a graph G, occasionally leaving “pheromone” traces at nodes, and using those traces to guide its exploration. We show that the ant can cover the graph within time O (nd), where n is the number of vertices and d the diameter of G. The use of traces achieves a tradedoff between random and selfdavoiding walks, as it dictates a lower priority for alreadydvisited neighbors. Further properties of the suggested method are: (a) modularity: a group of searching agents, each applying the same protocol, can cooperate on a mission of covering a graph with minimal explicit communication between thems (b) possible convergence to a limit cycle: a Hamiltonian path in G (if one exists) is a possible limit cycle of the process.
@cite_1: The rapid evolution of micromechanical fabrication techniques and other sensor, effector, and processing technologies will soon make it possible to employ large numbers of very inexpensive autonomous mobile robots with fairly limited sensor capabilities to perform real- world missions in the ground, air, space, and underwater environments. One approach to such a system is to realize desired emergent collective group behaviors with simple sensor-based reactive planners. The initial thrust of this effort has been to develop generic ensemble behaviors, such as blanket, barrier, and sweep coverage, and various deployment and recovery modes, which can address a broad spectrum of generic applications, both military and civilian. However, while different applications may require similar group behaviors, the sensor, information, and communications resources available to the participating individual robots may be very different. This paper outlines the many-robot approach to real-world problem solving and discusses the various roles that different types of sensors can play in such systems. Analysis and simulation results are presented to show how useful behavioral algorithms can be designed to make use of diverse information resources, and the area search problem is analyzed to derive both system measures of effectiveness and system design considerations.© (1993) COPYRIGHT SPIE--The International Society for Optical Engineering. Downloading of the abstract is permitted for personal use only.
@cite_20: 
@cite_3: We discuss a method for controlling a group of mobile robots in a distributed manner. The method is distributed in the sense that all robots, or most of the robots in some cases, plan their motion individually based upon the given goal of the group and the observed positions of other robots. We illustrate the method by showing how a large number of robots can form an approximation of a circle, a simple polygon, or a line segment in the plane. We also show how the robots can distribute themselves nearly uniformly within a circle or a convex polygon in the plane. Finally, we show how the robots can be divided into two or more groups. It turns out that in many cases most robots execute an identical, simple algorithm. The performance of the method is demonstrated by simulation. © 1996 John Wiley & Sons, Inc.
@cite_0: 
@cite_24: 
@cite_23: 
@cite_2: 
@cite_15: 
@cite_16: Control and coordination of a set of autonomous vehicles that can freely move on a plane is a widely studied topic in robotics. The focus on this kind of problem has grown in recent years because of the increased interest in studying systems populated by many, simple units, instead of few, powerful ones. In particular, these units simply observe the environment by using their sensors, and react following simple rules: the reaction to the environmental stimuli is called the behavior of the unit. In this paper we study the flocking problem : a set of mobile units are required to follow a leader unit while keeping a predetermined formation (i.e., they are required to move in flock, like a group of soldiers). Moreover, the units in the flock do not know beforehand the path the leader will take: their task is just to follow him wherever he goes, and to keep the formation while moving.
@cite_13: In this note we make a minor correction to a scheme for robots to broadcast their private information. All major results of the paper [I. Suzuki and M. Yamashita, SIAM J. Comput., 28 (1999), pp. 1347-1363] hold with this correction.
@cite_25: In the world of living creatures, simple-minded animals often cooperate to achieve common goals with amazing performance. One can consider this idea in the context of robotics, and suggest models for programming goal-oriented behavior into the members of a group of simple robots lacking global supervision. This can be done by controlling the local interactions between the robot agents, to have them jointly carry out a given mission. As a test case we analyze the problem of many simple robots cooperating to clean the dirty floor of a non-convex region in Z2, using the dirt on the floor as the main means of inter-robot communication.
@cite_12: New reactive behaviors that implement formations in multirobot teams are presented and evaluated. The formation behaviors are integrated with other navigational behaviors to enable a robotic team to reach navigational goals, avoid hazards and simultaneously remain in formation. The behaviors are implemented in simulation, on robots in the laboratory and aboard DARPA's HMMWV-based unmanned ground vehicles. The technique has been integrated with the autonomous robot architecture (AuRA) and the UGV Demo II architecture. The results demonstrate the value of various types of formations in autonomous, human-led and communications-restricted applications, and their appropriateness in different types of task environments.
There has been considerable study recently of distributed control and coordination of a set of autonomous robots. Gage @cite_0 @cite_1 has proposed the development of command and control tools for arbitrarily large swarms of microrobots and has proposed coverage paradigms in the context of robot dispersal in an environment. @cite_18 @cite_15 propose the notion of pheromone robotics'' for world-embedded computation. @cite_22 @cite_25 @cite_23 @cite_21 developed multi-robot algorithms, directly inspired by ant behaviors, for searching and covering. @cite_26 @cite_29 and @cite_24 @cite_3 @cite_13 have studied algorithmic aspects of pattern formation in distributed autonomous robotics under various models of robots with minimal capabilities. The related flocking problem, which requires that a set of robots follow a leader while maintaining a formation, has been studied in several recent papers; see, e.g., @cite_12 @cite_2 @cite_16 . Balch @cite_20 has developed Teambots'', a Java-based general-purpose multi-robot simulator.