When designing swarm-robotic systems, systematic comparison of algorithms from different domains is necessary to determine which is capable of scaling up to handle the target problem size and target operating conditions. We propose a set of quantitative metrics for scalability, flexibility, and emergence which are capable of addressing these needs during the system design process. We demonstrate the applicability of our proposed metrics as a design tool by solving a large object gathering problem in temporally varying operating conditions using iterative hypothesis evaluation. We provide experimental results obtained in simulation for swarms of over 10,000 robots.
Within SR, no widely accepted theory of self-organizing systems exists @cite_7 @cite_23 . Cotsaftis presents a control-theoretic model of emergence, distinguishing between systems which can be studied by the methods of scientific reductionism, and systems which originate from the existence of a threshold above which interaction between system components overtakes outside interactions, leading to system self-organization and new behavior not predictable from component study, similar to @cite_24 . While many papers cite evidence that their algorithms exhibit emergent behavior @cite_16 @cite_2 @cite_17 @cite_22 , or even prove simple emergent properties via temporal logic ( @cite_5 ), few provide a quantitative method for measuring emergence (with the exception of @cite_13 , who used robot nearest-neighbor calculations to calculate a degree of interaction for the swarm). We present an empirical method for measuring the level of self organization present in a swarm by measuring the linearity of inter-robot interference as the swarm size is increased, as a small step towards the development of a more general emergence theory.
@cite_22 @cite_7 @cite_24 @cite_23 @cite_2 @cite_5 @cite_16 @cite_13 @cite_17
2146086743 2011995167 1501224446 2120573220 2108526989 2014403316 2107787644 2807731679
We present a decentralized, scalable approach to assembling a group of heterogeneous parts into different products using a swarm of robots. While the assembly plans are predetermined, the exact sequence of assembly of parts and the allocation of subassembly tasks to robots are determined by the interactions between robots in a decentralized fashion in real time. Our approach is based on developing a continuous abstraction of the system derived from models of chemical reactions and formulating the strategy as a problem of selecting rates of assembly and disassembly. These rates are mapped onto probabilities that determine stochastic control policies for individual robots, which then produce the desired aggregate behavior. This top-down approach to determining robot controllers also allows us to optimize the rates at the abstract level to achieve fast convergence to the specified target numbers of products. Because the method incorporates programs for assembly and disassembly, changes in demand can lead to reconfiguration in a seamless fashion. We illustrate the methodology using a physics-based simulator with examples involving 15 robots and two types of final products. Designing and analyzing self-organizing systems such as robotic swarms is a challenging task even though we have complete knowledge about the robot’s interior. It is difficult to determine the individual robot’s behavior based on the swarm behavior and vice versa due to the high number of agent–agent interactions. A step towards a solution of this problem is the development of appropriate models which accurately predict the swarm behavior based on a specified control algorithm. Such models would reduce the necessary number of time-consuming simulations and experiments during the design process of an algorithm. In this paper we propose a model with focus on an explicit representation of space because the effectiveness of many swarm robotic scenarios depends on spatial inhomogeneity. We use methods of statistical physics to address spatiality. Starting from a description of a single robot we derive an abstract model of swarm motion. The model is then extended to a generic model framework of communicating robots. In two examples we validate models against simulation results. Our experience shows that qualitative correctness is easily achieved, while quantitative correctness is disproportionately more difficult but still possible. We propose to investigate the concept of an Emergent Programming Environment enabling the development of complex adaptive systems. For this we use as a foundation the concept of emergence and a multi-agent system technology based on cooperative self-organizing mechanisms. The general objective is then to develop a complete programming language in which each instruction is an autonomous agent trying to be in a cooperative state with the other agents of the system, as well as with the environment of the system. The work presented here aims at showing the feasibility of such a concept by specifying, and experimenting with, a core of instruction-agents needed for a sub-set of mathematical calculus. The biologically-inspired swarm paradigm is being used to design self-organizing systems of locally interacting artificial agents. A major difficulty in designing swarms with desired characteristics is understanding the causal relation between individual agent and collective behaviors. Mathematical analysis of swarm dynamics can address this difficulty to gain insight into system design. This paper proposes a framework for mathematical modeling of swarms of microscopic robots that may one day be useful in medical applications. While such devices do not yet exist, the modeling approach can be helpful in identifying various design trade-offs for the robots and be a useful guide for their eventual fabrication. Specifically, we examine microscopic robots that reside in a fluid, for example, a bloodstream, and are able to detect and respond to different chemicals. We present the general mathematical model of a scenario in which robots locate a chemical source. We solve the scenario in one-dimension and show how results can be used to evaluate certain design decisions. It is a characteristic of swarm robotics that specifying overall emergent swarm behaviours in terms of the low-level behaviours of individual robots is very difficult. Yet if swarm robotics is to make the transition from the laboratory to real-world engineering realisation we need such specifications. This paper explores the use of temporal logic to formally specify, and possibly also prove, the emergent behaviours of a robotic swarm. The paper makes use of a simplified wireless connected swarm as a case study with which to illustrate the approach. Such a formal approach could be an important step toward a disciplined design methodology for swarm robotics. This article presents a simple adaptation mechanism to automatically adjust the ratio of foragers to resters (division of labor) in a swarm of foraging robots and hence maximize the net energy income to the swarm. Three adaptation rules are introduced based on local sensing and communications. Individual robots use internal cues (successful food retrieval), environmental cues (collisions with team-mates while searching for food) and social cues (team-mate success in food retrieval) to dynamically vary the time spent foraging or resting. Simulation results show that the swarm demonstrates successful adaptive emergent division of labor and robustness to environmental change (in food source density), and we observe that robots need to cooperate more when food is scarce. Furthermore, the adaptation mechanism is able to guide the swarm towards energy optimization despite the limited sensing and communication abilities of the individual robots and the simple social interaction rules. The swarm also exhibits the capacity to collectively perceive environmental changes; a capacity that can only be observed at a group level and cannot be deduced from individual robots. Understanding the behavior of complex systems is becoming a crucial issue as systems grow in size, and the interconnection and geographical distribution of their components diversifies. The interaction over time of many components often leads to emergent behavior, which can be harmful to the system. Despite this, very few practical approaches for the identification of emergent behavior exist, and many are unfeasible to implement. Approaches using interaction as a measure of emergence have the potential to alleviate this problem. In this paper, we analyse absolute and relative methods that use interaction as a measure of emergence. Absolute methods compute a degree of interaction that characterizes a system state as being emergent. Relative methods compare interaction graphs of the system state with interaction graphs of systems that have been shown previously to exhibit emergence. We present these approaches and discuss their advantages and limitations using theoretical and experimental analysis. Swarm robotics (SR) offers promising solutions to real-world problems that can be modeled as foraging tasks, e.g. disaster trash cleanup or object gathering for construction. Yet current SR foraging approaches make limiting assumptions that restrict their applicability to selected real-world environments. We propose an improved self-organized task allocation method based on task partitioning that removes restrictions such as: (1) a priori knowledge of foraging environment, and (2) strict limitations on intermediate drop pickup site behavior. With experiments in simulation, we show that under the proposed constraint relaxation, our approach still provides performance increases when compared to an unpartitioned strategy within some combinations of swarm sizes, robot capabilities, and environmental conditions. This work broadens the applicability of SR foraging approaches, showing that they can be effective under ideal conditions while continuing to perform robustly in more volatile challenging environments.