We consider programmable matter that consists of computationally limited devices (which we call particles) that are able to self-organize in order to achieve some collective goal without the need for central control or external intervention. We use the geometric amoebot model to describe such self-organizing particle systems, which defines how particles can actively move and establish or release bonds with one another. Under this model, we investigate the feasibility of solving fundamental problems relevant to programmable matter. In this paper, we present an efficient local-control algorithm which solves the leader election problem in O(n) asynchronous rounds with high probability, where n is the number of particles in the system. Our algorithm relies only on local information (e.g., particles do not have unique identifiers, any knowledge of n, or any sort of global coordinate system), and requires only constant memory per particle.
In the area of , it is usually assumed that there is a collection of autonomous robots that can move freely in a given area and have limited sensing, vision, and communication ranges. They are used in a variety of contexts, including graph exploration (e.g., @cite_4 ), gathering problems (e.g., @cite_33 @cite_1 ), and shape formation problems (e.g., @cite_35 @cite_12 ). Surveys of recent results in swarm robotics can be found in @cite_14 @cite_36 ; other samples of representative work can be found in @cite_30 @cite_28 @cite_27 @cite_9 @cite_37 @cite_22 @cite_26 . While the analytic techniques developed in swarm robotics and natural swarms are of some relevance to this work, the individual units in those systems have more powerful communication and processing capabilities than in the systems we consider.
@cite_30 @cite_35 @cite_37 @cite_14 @cite_4 @cite_33 @cite_22 @cite_26 @cite_36 @cite_28 @cite_9 @cite_1 @cite_27 @cite_12
2085992503 1975531816 1965243636 2020796742 2066466105 1658640257 2468687866 2091969952 1983586118 2087073465 1967871771 2030775133
Self-assembly of active, robotic agents, rather than of passive agents such as molecules, is an emerging research field that is attracting increasing attention. Active self-assembly techniques are especially attractive at very small spatial scales, where alternative construction methods are unavailable or have severe limitations. Building nanostructures by using swarms of very simple nanorobots is a promising approach for manufacturing nanoscale devices and systems. The method described in this paper allows a group of simple, physically identical, identically programmed and reactive (i.e., stateless) agents to construct and repair polygonal approximations to arbitrary structures in the plane. The distributed algorithms presented here are tolerant of robot failures and of externally-induced disturbances. The structures are self-healing, and self-replicating in a weak sense. Their components can be re-used once the structures are no longer needed. A specification of vertices at relative positions, and the edges between them, is translated by a compiler into reactive rules for assembly agents. These rules lead to the construction and repair of the specified shape. Simulation results are presented, which validate the proposed algorithms. From an engineering point of view, the problem of coordinating a set of autonomous, mobile robots for the purpose of cooperatively performing a task has been studied extensively over the past decade. In contrast, in this paper we aim to understand the fundamental algorithmic limitations on what a set of autonomous mobile robots can or cannot achieve. We therefore study a hard task for a set of weak robots. The task is for the robots in the plane to form any arbitrary pattern that is given in advance. This task is fundamental in the sense that if the robots can form any pattern, they can agree on their respective roles in a subsequent, coordinated action. The robots are weak in several aspects. They are anonymous; they cannot explicitly communicate with each other, but only observe the positions of the others; they cannot remember the past; they operate in a very strong form of asynchronicity. We show that the tasks that such a system of robots can perform depend strongly on their common agreement about their environment, i.e. the readings of their environment sensors. If the robots have no common agreement about their environment, they cannot form an arbitrary pattern. If each robot has a compass needle that indicates North (the robot world is a flat surface, and compass needles are parallel), then any odd number of robots can form an arbitrary pattern, but an even number cannot (in the worst case). If each robot has two independent compass needles, say North and East, then any set of robots can form any pattern. This paper presents a distributed algorithm whereby a group of mobile robots self-organize and position themselves into forming a circle in a loosely synchronized environment. In spite of its apparent simplicity, the difficulty of the problem comes from the weak assumptions made on the system. In particular, robots are anonymous, oblivious (i.e., stateless), unable to communicate directly, and disoriented in the sense that they share no knowledge of a common coordinate system. Furthermore, robots' activations are not synchronized. More specifically, the proposed algorithm ensures that robots deterministically form a non-uniform circle in a finite number of steps and converges to a situation in which all robots are located evenly on the boundary of the circle. We consider the problem of exploring an anonymous unoriented ring by a team of k identical, oblivious, asynchronous mobile robots that can view the environment but cannot communicate. This weak scenario is standard when the spatial universe in which the robots operate is the two-dimensional plane, but (with one exception) has not been investigated before for networks. Our results imply that, although these weak capabilities of robots render the problem considerably more difficult, ring exploration by a small team of robots is still possible. We first show that, when k and n are not co-prime, the problem is not solvable in general, e.g., if k divides n there are initial placements of the robots for which gathering is impossible. We then prove that the problem is always solvable provided that n and k are co-prime, for kź17, by giving an exploration algorithm that always terminates, starting from arbitrary initial configurations. Finally, we consider the minimum number ź(n) of robots that can explore a ring of size n. As a consequence of our positive result we show that ź(n) is O(logn). We additionally prove that Ω(logn) robots are necessary for infinitely many n. We revisit the problem of gathering autonomous robots in the plane. In particular, we consider non-transparent unit-disc robots (i.e., fat) in an asynchronous setting with vision as the only means of coordination and robots only make local decisions. We use a state-machine representation to formulate the gathering problem and develop a distributed algorithm that solves the problem for any number of fat robots. The main idea behind the algorithm is to enforce the robots to reach a configuration in which all the following hold: (i) The robots' centers form a convex hull in which all robots are on the convex hull's boundary; (ii) Each robot can see all other robots; (iii) The configuration is connected: every robot touches another robot and all robots form together a connected formation. We show that starting from any initial configuration, the fat robots eventually reach such a configuration and terminate yielding a solution to the gathering problem. 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. Distributed algorithms for multi-robot systems rely on network communications to share information. However, the motion of the robots changes the network topology, which affects the information presented to the algorithm. For an algorithm to produce accurate output, robots need to communicate rapidly enough to keep the network topology correlated to their physical configuration. Infrequent communications will cause most multi-robot distributed algorithms to produce less accurate results, and cause some algorithms to stop working altogether. The central theme of this work is that algorithm accuracy, communications bandwidth, and physical robot speed are related. This thesis has three main contributions: First, I develop a prototypical multi-robot application and computational model, propose a set of complexity metrics to evaluate distributed algorithm performance on multi-robot systems, and introduce the idea of the robot speed ratio, a dimensionless measure of robot speed relative to message speed in networks that rely on multi-hop communication. The robot speed ratio captures key relationships between communications bandwidth, mobility, and algorithm accuracy, and can be used at design time to trade off between them. I use this speed ratio to evaluate the performance of existing distributed algorithms for multi-hop communication and navigation. Second, I present a definition of boundaries in multi-robot systems, and develop new distributed algorithms to detect and characterize them. Finally, I define the problem of dynamic task assignment, and present four distributed algorithms that solve this problem, each representing a different trade-off between accuracy, running time, and communication resources. All the algorithms presented in this work are provably correct under ideal conditions and produce verifiable real-world performance. They are self-stabilizing and robust to communications failures, population changes, and other errors. All the algorithms were tested on a swarm of 112 robots. (Copies available exclusively from MIT Libraries, Rm. 14-0551, Cambridge, MA 02139-4307. Ph. 617-253-5668; Fax 617-253-1690.) We consider the uniform scattering problem for a set of autonomous mobile robots deployed in a grid network: starting from an arbitrary placement in the grid, using purely localized computations, the robots must move so to reach in finite time a state of static equilibrium in which they cover uniformly the grid. The theoretical quest is on determining the minimal capabilities needed by the robots to solve the problem. We prove that uniform scattering is indeed possible even for very weak robots. The proof is constructive. We present a provably correct protocol for uniform self-deployment in a grid. The protocol is fully localized, collision-free, and it makes minimal assumptions; in particular: (1) it does not require any direct or explicit communication between robots; (2) it makes no assumption on robots synchronization or timing, hence the robots can be fully asynchronous in all their actions; (3) it requires only a limited visibility range; (4) it uses at each robot only a constant size memory, hence computationally the robots can be simple Finite-State Machines; (5) it does not need a global localization system but only orientation in the grid (e.g., a compass); (6) it does not require identifiers, hence the robots can be anonymous and totally identical. We study the computational power of a distributed system consisting of simple autonomous robots moving on the plane. The robots are endowed with visual perception but do not have any means of explicit communication with each other, and have no memory of the past. In the extensive literature it has been shown how such simple robots can form a single geometric pattern (e.g., a line, a circle, etc), however arbitrary, in spite of their obliviousness. This brings to the front the natural research question: what are the real computational limits imposed by the robots being oblivious? In particular, since obliviousness limits what can be remembered, under what conditions can oblivious robots form a series of geometric patterns? Notice that a series of patterns would create some form of memory in an otherwise memory-less system. In this paper we examine and answer this question showing that, under particular conditions, oblivious robot systems can indeed form series of geometric patterns starting from any arbitrary configuration. More precisely, we study the series of patterns that can be formed by robot systems under various restrictions such as anonymity, asynchrony and lack of common orientation. These results are the first strong indication that oblivious solutions may be obtained also for tasks that intuitively seem to require memory. Consider a set of @math identical mobile computational entities in the plane, called robots, operating in Look-Compute-Move cycles, without any means of direct communication. The Gathering Problem is the primitive task of all entities gathering in finite time at a point not fixed in advance, without any external control. The problem has been extensively studied in the literature under a variety of strong assumptions (e.g., synchronicity of the cycles, instantaneous movements, complete memory of the past, common coordinate system, etc.). In this paper we consider the setting without those assumptions, that is, when the entities are oblivious (i.e., they do not remember results and observations from previous cycles), disoriented (i.e., have no common coordinate system), and fully asynchronous (i.e., no assumptions exist on timing of cycles and activities within a cycle). The existing algorithmic contributions for such robots are limited to solutions for @math or for restricted sets of initial configura... This paper studies local algorithms for autonomous robot systems, namely, algorithms that use only information of the positions of a bounded number of their nearest neighbors. The paper focuses on the spreading problem. It defines measures for the quality of spreading, presents a local algorithm for the one-dimensional spreading problem, proves its convergence to the equally spaced configuration and discusses its convergence rate in the synchronous and semi-synchronous settings. It then presents a local algorithm achieving the exact equally spaced configuration in finite time in the synchronous setting, and proves it is time optimal for local algorithms. Finally, the paper also proposes a possible algorithm for the two-dimensional case and presents partial simulation results of its effectiveness. When individuals swarm, they must somehow communicate to direct collective motion. Swarms of robots need to deal with outliers, such as robots that move more slowly than the rest. created a large swarm of programmed robots that can form collaborations using only local information. The robots could communicate only with nearby members, within about three times their diameter. They were able to assemble into complex preprogrammed shapes. If the robots' formation hit snags when they bumped into one another or because of an outlier, additional algorithms guided them to rectify their collective movements. @PARASPLIT Science , this issue p. [795][1] @PARASPLIT [1]: lookup volpage 345 795?iss=6198