Imagine coating buildings and bridges with smart particles (also coined smart paint) that monitor structural integrity and sense and report on traffic and wind loads, leading to technology that could do such inspection jobs faster and cheaper and increase safety at the same time. In this paper, we study the problem of uniformly coating objects of arbitrary shape in the context of self-organizing programmable matter, i.e., programmable matter which consists of simple computational elements called particles that can establish and release bonds and can actively move in a self-organized way. Particles are anonymous, have constant-size memory, and utilize only local interactions in order to coat an object. We continue the study of our universal coating algorithm by focusing on its runtime analysis, showing that our algorithm terminates within a linear number of rounds with high probability. We also present a matching linear lower bound that holds with high probability. We use this lower bound to show a linear lower bound on the competitive gap between fully local coating algorithms and coating algorithms that rely on global information, which implies that our algorithm is also optimal in a competitive sense. Simulation results show that the competitive ratio of our algorithm may be better than linear in practice.
@cite_18: In this work, we study protocols so that populations of distributed processes can construct networks. In order to highlight the basic principles of distributed network construction, we keep the model minimal in all respects. In particular, we assume finite-state processes that all begin from the same initial state and all execute the same protocol. Moreover, we assume pairwise interactions between the processes that are scheduled by a fair adversary. In order to allow processes to construct networks, we let them activate and deactivate their pairwise connections. When two processes interact, the protocol takes as input the states of the processes and the state of their connection and updates all of them. Initially all connections are inactive and the goal is for the processes, after interacting and activating deactivating connections for a while, to end up with a desired stable network. We give protocols (optimal in some cases) and lower bounds for several basic network construction problems such as spanning line, spanning ring, spanning star, and regular network. The expected time to convergence of our protocols is analyzed under a uniform random scheduler. Finally, we prove several universality results by presenting generic protocols that are capable of simulating a Turing Machine (TM) and exploiting it in order to construct a large class of networks. We additionally show how to partition the population into ksupernodes, each being a line of @math logk nodes, for the largest such k. This amount of local memory is sufficient for the supernodes to obtain unique names and exploit their names and their memory to realize nontrivial constructions.
@cite_21: Nowadays the capabilities of autonomous robots have increased rapidly. However there are situations where one robot is not sufficient. In this paper we will introduce a completely distributed algorithm for tracing and surrounding moving objects or targets using homogenous, medium scaled swarm robots based on local sensing. Our new approach is based on the already known concept of basis behaviors as ubiquitous general building blocks for synthesizing artificial group behavior. Our goal was to generate an algorithm based on simple rules in order to protect a territory from a human intruder. In contrast with the common solution which is employing potential fields, we tried to keep our method as simple as possible by utilizing rule-based control mechanism. We will also present our virtual simulation environment and experimental results.
@cite_6: In this paper we present a distributed algorithm, which enables to follow and surround moving objects by a swarm of homogenous robots that only use local sensing. We introduce the multi orbit surrounding problem and present a solution for it. We prove that our solution always guarantees that the robots enclose the target and circulate around them. We also evaluate our solution by simulations.
@cite_19: In this paper, we present an approach to designing decentralized robot control policies that mimic certain microscopic and macroscopic behaviors of ants performing collective transport tasks. In prior work, we used a stochastic hybrid system model to characterize the observed team dynamics of ant group retrieval of a rigid load. We have also used macroscopic population dynamic models to design enzyme-inspired stochastic control policies that allocate a robotic swarm around multiple boundaries in a way that is robust to environmental variations. Here, we build on this prior work to synthesize stochastic robot attachment–detachment policies for tasks in which a robotic swarm must achieve non-uniform spatial distributions around multiple loads and transport them at a constant velocity. Three methods are presented for designing robot control policies that replicate the steady-state distributions, transient dynamics, and fluxes between states that we have observed in ant populations during group retrieval. The equilibrium population matching method can be used to achieve a desired transport team composition as quickly as possible; the transient matching method can control the transient population dynamics of the team while driving it to the desired composition; and the rate matching method regulates the rates at which robots join and leave a load during transport. We validate our model predictions in an agent-based simulation, verify that each controller design method produces successful transport of a load at a regulated velocity, and compare the advantages and disadvantages of each method.
@cite_2: We present a novel analytical approach to computing the population and geometric parameters of a multi-robot system that will provably produce specified boundary coverage statistics. We consider scenarios in which robots with no global position information, communication, or prior environmental data have arrived at uniformly random locations along a simple closed or open boundary. This type of scenario can arise in a variety of multi-robot tasks, including surveillance, collective transport, disaster response, and therapeutic and imaging applications in nanomedicine. We derive the probability that a given point robot configuration is saturated, meaning that all pairs of adjacent robots are no farther apart than a specified distance. This derivation relies on a geometric interpretation of the saturation probability and an application of the InclusionExclusion Principle, and it is easily extended to finite-sized robots. In the process, we obtain formulas for (a) an integral that is in general computationally expensive to compute directly, and (b) the volume of the intersection of a regular simplex with a hypercube. In addition, we use results from order statistics to compute the probability distributions of the robot positions along the boundary and the distances between adjacent robots. We validate our derivations of these probability distributions and the saturation probability using Monte Carlo simulations of scenarios with both point robots and finite-sized robots.
@cite_13: Swarm robotics is an approach to collective robotics that takes inspiration from the self-organized behaviors of social animals. Through simple rules and local interactions, swarm robotics aims at designing robust, scalable, and flexible collective behaviors for the coordination of large numbers of robots. In this paper, we analyze the literature from the point of view of swarm engineering: we focus mainly on ideas and concepts that contribute to the advancement of swarm robotics as an engineering field and that could be relevant to tackle real-world applications. Swarm engineering is an emerging discipline that aims at defining systematic and well founded procedures for modeling, designing, realizing, verifying, validating, operating, and maintaining a swarm robotics system. We propose two taxonomies: in the first taxonomy, we classify works that deal with design and analysis methods; in the second taxonomy, we classify works according to the collective behavior studied. We conclude with a discussion of the current limits of swarm robotics as an engineering discipline and with suggestions for future research directions.
@cite_12: The computational power of networks of small resource-limited mobile agents is explored. Two new models of computation based on pairwise interactions of finite-state agents in populations of finite but unbounded size are defined. With a fairness condition on interactions, the concept of stable computation of a function or predicate is defined. Protocols are given that stably compute any predicate in the class definable by formulas of Presburger arithmetic, which includes Boolean combinations of threshold-k, majority, and equivalence modulo m. All stably computable predicates are shown to be in NL. Assuming uniform random sampling of interacting pairs yields the model of conjugating automata. Any counter machine with O (1) counters of capacity O (n) can be simulated with high probability by a conjugating automaton in a population of size n. All predicates computable with high probability in this model are shown to be in P; they can also be computed by a randomized logspace machine in exponential time. Several open problems and promising future directions are discussed.
@cite_20: This work presents a novel control approach for allocating a robotic swarm among boundaries. It represents the first step toward developing a methodology for encounter-based swarm allocation that incorporates rigorously characterized spatial effects in the system without requiring analytical expressions for encounter rates. Our approach utilizes a macroscopic model of the swarm population dynamics to design stochastic robot control policies that result in target allocations of robots to the boundaries of regions of different types. The control policies use only local information and have provable guarantees on the collective swarm behavior. We analytically derive the relationship between the stochastic control policies and target allocations for a scenario in which circular robots avoid collisions with each other, bind to boundaries of disk-shaped regions, and command bound robots to unbind. We validate this relationship in simulation and show that it is robust to environmental changes, such as a change in the number or size of robots and disks.
Our focus, however, is on active systems, in which computational particles control their actions and motions to complete specific tasks. Coating has been extensively studied in the area of , but not commonly treated as a stand-alone problem; it is instead examined as part of (e.g., @cite_19 ) or (e.g., see respective section of @cite_13 ). Some research focuses on coating objects as an independent task under the name of or . The techniques used in this context include stochastic robot behaviors @cite_2 @cite_20 , rule-based control mechanisms @cite_21 and potential field-based approaches @cite_6 . While the analytic techniques developed in swarm robotics are somewhat relevant to this work, many such systems assume more computational power and movement capabilities than the model studied in this work does. Michail and Spirakis recently proposed a model @cite_18 for network construction inspired by population protocols @cite_12 . The population protocol model is related to self-organizing particle systems, but is different in that agents (corresponding to our particles) can move freely in space and establish connections at any time. It would, however, be possible to adapt their approach to study coating problems under the population protocol model.