Recent research has demonstrated that blockchain-enabled robot swarms—where robots coordinate using blockchain technology—can secure robot swarms by neutralizing malicious and malfunctioning robots. This security is achieved through blockchain technology’s consistency properties. However, prior work addressed malfunctions at the information level, that is, it studied how to neutralize robots that stored information in the blockchain that did not correspond to the real-world state (i.e., it studied the oracle problem). In contrast, this study focuses on inconsistencies at the blockchain protocol level. We analyze how network partitions, which may arise from robots’ local-only communication capabilities, malfunctioning hardware, or external attacks, can lead to inconsistent information in a robot swarm. In order to mitigate these disruptions, we propose a decentralized approach to detect partitions and a corresponding response. We study our approach in a swarm robotics simulator, where we demonstrate its effectiveness in reducing blockchain inconsistencies.

Making fast and accurate consensus decisions through local communication and decentralised control in a swarm of simple robots can be a very challenging endeavour. In swarms of robots with limited capabilities, consensus decisions can be made using simple voting rules. In our study, the robots use rules based on the cross-inhibition model, which describes a voting mechanism observed in the house-hunting honeybee, that has been shown to efficiently allow consensus achievement in distributed robotic systems. The cross-inhibition mechanism has been shown to lead to a highly stable consensus, preventing the correction of possible group decision errors which can happen, for example, due to high noise in robots’ estimations. In this paper, we investigate the impact of miscommunication on the speed-accuracy trade-off in consensus decision-making in the context of a binary discrimination problem—i.e., choosing collectively the best of two options. We evaluate the accuracy of decision-making theoretically, using continuous and finite-size models, and experimentally in a collective perception scenario, using swarms of 100 simulated robots and 50 real Kilobots. Our study suggests that a certain level of miscommunication (or communication noise) among agents can increase the decision’s accuracy and, thus, can serve an important functional role in making collective decisions in robot swarms.

Hierarchical frameworks-a special class of directed frameworks with a layer-by-layer architecture-can be an effective mechanism to coordinate robot swarms. Their effectiveness was recently demonstrated by the mergeable nervous systems paradigm (Mathews et al., 2017), in which a robot swarm can switch dynamically between distributed and centralized control depending on the task, using self-organized hierarchical frameworks. New theoretical foundations are required to use this paradigm for formation control of large swarms. In particular, the systematic and mathematically analyzable organization and reorganization of hierarchical frameworks in a robot swarm is still an open problem. Although methods for framework construction and formation maintenance via rigidity theory exist in the literature, they do not address cases of hierarchy in a robot swarm. In this article, we extend bearing rigidity to directed topologies and extend the Henneberg constructions to generate self-organized hierarchical frameworks with bearing rigidity. We investigate three-key self-reconfiguration problems: 1) framework merging; 2) robot departure; and 3) framework splitting. We also derive the mathematical conditions of these problems and then develop algorithms that preserve rigidity and hierarchy using only local information. Our approach can be used for formation control generally, as in principle it can be coupled with any control law that makes use of bearing rigidity. To demonstrate and validate our proposed hierarchical frameworks and methods, we apply them to four scenarios of reactive formation control using an example control law.

Recent studies show that some security features that blockchains grant to decentralized networks on the internet can be ported to swarm robotics. Although the integration of blockchain technology and swarm robotics shows great promise, thus far, research has been limited to proof-of-concept scenarios where the blockchain-based mechanisms are tailored to a particular swarm task and operating environment. In this study, we propose a generic framework based on a blockchain smart contract that enables robot swarms to achieve secure consensus in an arbitrary observation space. This means that our framework can be customized to fit different swarm robotics missions, while providing methods to identify and neutralize Byzantine robots, that is, robots which exhibit detrimental behaviours stemming from faults or malicious tampering.

The particle swarm optimization (PSO) algorithm has been the object of many studies and modifications for more than 25 years. Ranging from small refinements to the incorporation of sophisticated novel ideas, the majority of modifications proposed to this algorithm have been the result of a manual process in which developers try new designs based on their own knowledge and expertise. However, manually introducing changes is very time consuming and makes the systematic exploration of all the possible algorithm configurations a difficult process. In this article, we propose to use automatic design to overcome the limitations of having to manually find performing PSO algorithms. We develop a flexible software framework for PSO, called PSO-X, which is specifically designed to integrate the use of automatic configuration tools into the process of generating PSO algorithms. Our framework embodies a large number of algorithm components developed over more than 25 years of research that have allowed PSO to deal with a large variety of problems, and usesirace, a state-of-the-art configuration tool, to automatize the task of selecting and configuring PSO algorithms starting from these components. We show thatiraceis capable of finding high-performing instances of PSO algorithms never proposed before.

Swarm robotics deals with the design, construction, and deployment of large groups of robots that coordinate and cooperatively solve a problem or perform a task. It takes inspiration from natural self-organizing systems, such as social insects, fish schools, or bird flocks, characterized by emergent collective behavior based on simple local interaction rules [1], [2]. Typically, swarm robotics extracts engineering principles from the study of those natural systems in order to provide multirobot systems with comparable abilities. This way, it aims to build systems that are more robust, fault-tolerant, and flexible than single robots and that can better adapt their behavior to changes in the environment.

Modern cities are growing ecosystems that face new challenges due to the increasing population demands. One of the many problems they face nowadays is waste management, which has become a pressing issue requiring new solutions. Swarm robotics systems have been attracting an increasing amount of attention in the past years and they are expected to become one of the main driving factors for innovation in the field of robotics. The research presented in this paper explores the feasibility of a swarm robotics system in an urban environment. By using bio-inspired foraging methods such as multi-place foraging and stigmergy-based navigation, a swarm of robots is able to improve the efficiency and autonomy of the urban waste management system in a realistic scenario. To achieve this, a diverse set of simulation experiments was conducted using real-world GIS data and implementing different garbage collection scenarios driven by robot swarms. Results presented in this research show that the proposed system outperforms current approaches. Moreover, results not only show the efficiency of our solution, but also give insights about how to design and customize these systems.

The population-based ant colony optimization algorithm (P-ACO) differs from other ACO algorithms because of its implementation of the pheromone update. P-ACO keeps track of a population of solutions, which serves as an archive of solutions generated by the ants' colony. Pheromone updates in P-ACO are only done based on solutions that enter or leave the solution archive. The population-based scheme reduces considerably the computation time needed for the pheromone update when compared to classical ACO algorithms such as Ant System. In this work, we study the behavior of P-ACO when solving the traveling salesman and the quadratic assignment problem. In particular, we investigate the impact of a local search on P-ACO parameters and performance. The results show that P-ACO reaches competitive performance but that the parameter settings and algorithm behavior are strongly problem-dependent.

We introduce the Kilogrid, a modular and scalable virtualization environment aimed at swarm robotics research with the Kilobot robot. The main purpose of the Kilogrid is to complement the Kilobots by overcoming some of their limitations (i.e., limited sensors and actuators), making it easier to experiment and to collect data with large groups of robots. The Kilogrid allows researchers to study scenarios featuring a level of complexity that cannot be reached using the Kilobots alone. The Kilogrid is composed of several modules, where each module contains four cells of 50×50 mm2. The cells allow for bi-directional communication with the Kilobots. Our first version of a Kilogrid is composed of 64 cells and covers a total area of 400×400 mm2. We demonstrate the features of the Kilogrid with two case studies in which: (i) we extend the sensory system of the Kilobots, (ii) we allow the Kilobots to modify the environment, and (iii) we collect data (e.g., position, state) from the Kilobots while the experiment is running.

This article investigates the use of the integral of linear birth-death processes in the context of analyzing swarm robotics systems. We show that when a robot swarm can be modeled as a linear birth-death process, well-established results can be used to compute the expected value and/or the distribution of important swarm performance measures, such as the swarm activity time or the swarm energy consumption. We also show how the linear birth-death model can be used to estimate the long-term value of such performance measures and design robot controllers that satisfy constraints on these measures.

In this paper, we propose a collective decision-making method for swarms of robots. The method enables a robot swarm to select, from a set of possible actions, the one that has the fastest mean execution time. By means of positive feedback the method achieves consensus on the fastest action. The novelty of our method is that it allows robots to collectively find consensus on the fastest action without measuring explicitly the execution times of all available actions. We study two analytical models of the decision-making method in order to understand the dynamics of the consensus formation process. Moreover, we verify the applicability of the method in a real swarm robotics scenario. To this end, we conduct three sets of experiments that show that a robotic swarm can collectively select the shortest of two paths. Finally, we use a Monte Carlo simulation model to study and predict the influence of different parameters on the method.

We study a self-organized collective decision-making strategy to solve a site-selection problem using a swarm of simple robots. Robots can only move forward or turn in place; sense the intensity of the ambient light; and exchange 3-byte messages with peers in a limited range. The goal of the swarm is to collectively decide which of the sites available in the environment is the best candidate site. We define a distributed and iterative decision-making strategy: robots explore the available options, determine the options' qualities, decide autonomously which option to take, and communicate their decision to neighboring robots. We study the effectiveness and robustness of the proposed strategy using a swarm of 100 Kilobots and we focus on the impact of the neighborhood size over the dynamics of the system.

Division of labor is ubiquitous in biological systems, as evidenced by various forms of complex task specialization observed in both animal societies and multicellular organisms. Although clearly adaptive, the way in which division of labor first evolved remains enigmatic, as it requires the simultaneous co-occurrence of several complex traits to achieve the required degree of coordination. Recently, evolutionary swarm robotics has emerged as an excellent test bed to study the evolution of coordinated group-level behavior. Here we use this framework for the first time to study the evolutionary origin of behavioral task specialization among groups of identical robots. The scenario we study involves an advanced form of division of labor, common in insect societies and known as "task partitioning", whereby two sets of tasks have to be carried out in sequence by different individuals. Our results show that task partitioning is favored whenever the environment has features that, when exploited, reduce switching costs and increase the net efficiency of the group, and that an optimal mix of task specialists is achieved most readily when the behavioral repertoires aimed at carrying out the different subtasks are available as pre-adapted building blocks. Nevertheless, we also show for the first time that self-organized task specialization could be evolved entirely from scratch, starting only from basic, low-level behavioral primitives, using a nature-inspired evolutionary method known as Grammatical Evolution. Remarkably, division of labor was achieved merely by selecting on overall group performance, and without providing any prior information on how the global object retrieval task was best divided into smaller subtasks. We discuss the potential of our method for engineering adaptively behaving robot swarms and interpret our results in relation to the likely path that nature took to evolve complex sociality and task specialization.

In this article, we present property-driven design, a novel top-down design method for robot swarms based on prescriptive modeling and model checking. Traditionally, robot swarms have been developed using a code-and-fix approach: in a bottom-up iterative process, the developer tests and improves the individual behaviors of the robots until the desired collective behavior is obtained. The code-and-fix approach is unstructured, and the quality of the obtained swarm depends completely on the expertise and ingenuity of the developer who has little scientific or technical support in his activity. Property-driven design aims at providing such scientific and technical support, with many advantages compared to the traditional unstructured approach. Property-driven design is composed of four phases: first, the developer formally specifies the requirements of the robot swarm by stating its desired properties; second, the developer creates a prescriptive model of the swarm and uses model checking to verify that this prescriptive model satisfies the desired properties; third, using the prescriptive model as a blueprint, the developer implements a simulated version of the desired robot swarm and validates the prescriptive model developed in the previous step; fourth, the developer implements the desired robot swarm and validates the previous steps. We demonstrate property-driven design using two case studies: aggregation and foraging.

This special issue pays tribute to 20 years of artificial life research in Europe. Since its inception around a coffee table in Paris in the summer of 1990, the European Conference on Artificial Life (ECAL) has grown and evolved to incorporate multiple research disciplines that aim to combine the natural and computational sciences. In addition to extending a long and rich tradition in theoretical biology present at that time in Europe toward the computational sciences and engineering, ECAL has also provided a platform for different innovative ideas that have produced a significant impact on other research domains or have resulted in novel research directions with their own workshops and conferences. This influence continues today, with the consideration of the different models and methods that are currently extensively used to answer biological questions in domains such as computational and systems biology. This evolution will benefit the field and will ensure that our models continue to push the envelope as they have been doing for the last two decades.Together with the reviewers and conference chairs of ECAL 2011 in Paris, we selected a small number of especially interesting contributions among the conference's 128 accepted submissions. Their authors were asked to extend their manuscripts for a wider audience and to provide more details than what was allowed by the conference format. The reader can find below a brief description of these articles, which range from artificial chemistry to evolutionary robotics and computational biology. We hope that this selection will provide an incentive for researchers from related fields to pay closer attention to the innovations created within the artificial life community and to motivate researchers already interested in this field to make further advances in the realism and influence of their models. In the following we summarize the topics discussed in this special issue.Xabier Barandiaran and Matthew Egbert study how norms become established from an organism-centered perspective. They give an in-depth analysis and evaluation of a minimal model capable of establishing norms dynamically. The model clearly opens a novel road toward answering questions associated to the notion of minimal agency, which is essential to a wide variety of artificial life models.The work of Navneet Bhalla, Peter Bentley, Peter Vize, and Christian Jacob focuses on the use of staging in the context of physical self-assembling systems made of magnetic shapes. They investigate whether replacing a full mix with gradual addition of morphological information manages to produce more stable constructs for systems composed of elements with heterogeneous properties. They show that this staging methodology can solve complex self-assembly problems by reducing the possibilities of errors in the shape-matching process.Tom Froese, Nathaniel Virgo, and Takashi Ikegami argue in the third article that time scales should play a central role in all models aiming to answer questions linked to the origin of life. Using a reaction-diffusion model, they assert that adaptive behavior realized at intermediate time scales by spatiotemporally localized self-producing systems may have been already present in the beginnings, and conclude with the feasibility of a movement-first approach to the origin of life.In the fourth contribution, Heiko Hamann, Thomas Schmickl, and Karl Crailsheim investigate the relevance of statistical mechanics, and more specifically of the fluctuation theorem, to understanding the collective behavior of simulated swarms. They are able to show that an inverted fluctuation theorem is present in this type of systems, which they claim may be generally applicable to different self-organizing systems studied in artificial life.Tsutomu Oohashi, Tadao Maekawa, Osamu Ueno, Norie Kawai, Emi Nishina, and Manabu Honda investigate a completely different question: Can organisms evolve to give up their immortality? Using an artificial-chemistry-based model called SIVA, they examine the evolution of programmed self-decomposition. Interestingly, they identify the conditions for mortal organisms emerging from immortal ones to outcompete them, which they associate with the emergence of an altruistic activity in terrestrial life.As mentioned earlier, artificial life modeling has a prominent role to play in computational and systems biology. The manuscript of Joshua Payne, Jason Moore, and Andreas Wagner is an example of this cross-fertilization. The authors investigate the space of signal-integration functions, which are defined as functions that map regulatory signals to gene expression states. Their aim is to understand the relationship between the robustness and evolvability of gene expression states when genetic perturbations modify these functions. They show, among other things, that the majority of signal-integration functions are resistant to perturbation.José Pereira, Porfírio Silva, Pedro Lima, and Alcherio Martinoli propose in their work a new framework to coordinate the actions of robot teams using concepts from the field of institutional economics. They first introduce the notion of executable Petri nets (EPNs), which can be run directly on a robot. These EPNs are then used to define institutions and individual robot behaviors, resulting in what they call an institutional agent controller. To validate this new approach, they design some swarm-related experiments in which robots need to coordinate to remain connected over a wireless network, showing that their novel institutional robotics framework can perform as well as some of the other approaches that aim to design swarm behavior, while offering a higher potential for modular control design and consideration of social behavior in robot teams.In the eighth contribution to this special issue, John Rieffel, Davis Knox, Schuyler Smith, and Barry Trimmer provide insight into four years of research into soft robotics. They particularly focus on the question of how to coevolve soft robot morphology and control. They argue that the evolution of soft robots corresponds to solving a problem of three tightly interdependent variables, namely material, morphology and control. In their study, they provide three approaches to address this problem, showing a way to achieve physically embodied soft robots.Within the 20 years of the European Conference of Artificial Life, numerous articles have addressed new evolutionary algorithms designed to solve particular problems or to overcome specific issues in the model originally proposed by John Holland. The ninth and last article, by Nicholas Tomko, Inman Harvey, Nathaniel Virgo, and Andrew Philippides, focuses here on the question of how to improve on prior work about niching and speciation. They suggest a new genetic algorithm (GA), called the group GA, which is based on principles of group or multilevel selection. They show that this new algorithm outperforms some of the earlier works in the same context, and that the group size need not be preset but can itself be evolved.

We study task partitioning in the context of swarm robotics. Task partitioning is the decomposition of a task into subtasks that can be tackled by different workers. We focus on the case in which a task is partitioned into a sequence of subtasks that must be executed in a certain order. This implies that the subtasks must interface with each other, and that the output of a subtask is used as input for the subtask that follows. A distinction can be made between task partitioning with direct transfer and with indirect transfer. We focus our study on the first case: The output of a subtask is directly transferred from an individual working on that subtask to an individual working on the subtask that follows. As a test bed for our study, we use a swarm of robots performing foraging. The robots have to harvest objects from a source, situated in an unknown location, and transport them to a home location. When a robot finds the source, it memorizes its position and uses dead reckoning to return there. Dead reckoning is appealing in robotics, since it is a cheap localization method and it does not require any additional external infrastructure. However, dead reckoning leads to errors that grow in time if not corrected periodically. We compare a foraging strategy that does not make use of task partitioning with one that does. We show that cooperation through task partitioning can be used to limit the effect of dead reckoning errors. This results in improved capability of locating the object source and in increased performance of the swarm. We use the implemented system as a test bed to study benefits and costs of task partitioning with direct transfer. We implement the system with real robots, demonstrating the feasibility of our approach in a foraging scenario.

In this paper, we introduce ACOMV: an ant colony optimization (ACO) algorithm that extends the ACORalgorithm for continuous optimization to tackle mixed-variable optimization problems. In ACOMV, the decision variables of an optimization problem can be explicitly declared as continuous, ordinal, or categorical, which allows the algorithm to treat them adequately. ACOMVincludes three solution generation mechanisms: a continuous optimization mechanism (ACOR), a continuous relaxation mechanism (ACOMV-o) for ordinal variables, and a categorical optimization mechanism (ACOMV-c) for categorical variables. Together, these mechanisms allow ACOMVto tackle mixed-variable optimization problems. We also define a novel procedure to generate artificial, mixed-variable benchmark functions, and we use it to automatically tune ACOMV's parameters. The tuned ACOMVis tested on various real-world continuous and mixed-variable engineering optimization problems. Comparisons with results from the literature demonstrate the effectiveness and robustness of ACOMVon mixed-variable optimization problems.

In swarm robotics, large groups of relatively simple robots cooperate so that they can perform tasks that go beyond their individual capabilities [1], [2]. The interactions among the robots are based on simple behavioral rules that exploit only local information. The robots in a swarm have neither global knowledge, nor a central controller. Therefore, decisions in the swarm have to be taken in a distributed manner based on local interactions. Because of these limitations, the design of collective decision-making methods in swarm robotic systems is a challenging problem. Moreover, the collective decision-making method must be efficient, robust with respect to robot failures, and scale well with the size of the swarm.

We introduce spatially targeted communication - a communication method for multirobot systems. This method allows an individual message sending robot to isolate selected message recipient robots based on their spatial location. The recipient robots can then be sent information targeted solely at them, even if the sending robot uses a broadcast communication modality. We demonstrate spatially targeted communication using a heterogeneous multirobot system composed of flying robots and ground-based self-assembling robots. Flying robots use their privileged view of the environment to determine and communicate information to groups of ground-based robots on what morphologies to form to carry out upcoming tasks.

Winner of the best paper award in the ant Colony Optimization and swarm intelligence track

We introduce enhanced directional self-assembly (EDSA) - a novel mechanism for morphology growth through the creation of directed connections in a self-assembling multirobot system. In our approach, a robot inviting a physical connection actively recruits the best located neighboring robot and guides the recruit to the location on its chassis where the connection is required. The proposed mechanism relies on local, high-speed communication between connection inviting robots and their recruits. Communication is based on a hybrid technology that combines radio and infrared to provide local relative positioning information when messages are transmitted between adjacent robots. Experiments with real robotic hardware show that EDSA is precise (misalignment of only 1.2° on average), robust (100% success rate for the experiments in this study) and fast (16.1 seconds on average from a distance of 80 cm). We show how the speed and precision of the new approach enable adaptive recruitment and connection in dynamic environments, a high degree of parallelism, and growth of a moving morphology.

We present ARGoS, a novel open source multi-robot simulator. The main design focus of ARGoS is the real-time simulation of large heterogeneous swarms of robots. Existing robot simulators obtain scalability by imposing limitations on their extensibility and on the accuracy of the robot models. By contrast, in ARGoS we pursue a deeply modular approach that allows the user both to easily add custom features and to allocate computational resources where needed by the experiment. A unique feature of ARGoS is the possibility to use multiple physics engines of different types and to assign them to different parts of the environment. Robots can migrate from one engine to another transparently. This feature enables entirely novel classes of optimizations to improve scalability and paves the way for a new approach to parallelism in robotics simulation. Results show that ARGoS can simulate about 10,000 simple wheeled robots 40% faster than real-time.

Incremental social learning (ISL) was proposed as a way to improve the scalability of systems composed of multiple learning agents. In this paper, we show that ISL can be very useful to improve the performance of population-based optimization algorithms. Our study focuses on two particle swarm optimization (PSO) algorithms: a) the incremental particle swarm optimizer (IPSO), which is a PSO algorithm with a growing population size in which the initial position of new particles is biased toward the best-so-far solution, and b) the incremental particle swarm optimizer with local search (IPSOLS), in which solutions are further improved through a local search procedure. We first derive analytically the probability density function induced by the proposed initialization rule applied to new particles. Then, we compare the performance of IPSO and IPSOLS on a set of benchmark functions with that of other PSO algorithms (with and without local search) and a random restart local search algorithm. Finally, we measure the benefits of using incremental social learning on PSO algorithms by running IPSO and IPSOLS on problems with different fitness distance correlations.

Particle swarm optimization (PSO) is a swarm intelligence technique originally inspired by models of flocking and of social influence that assumed homogeneous individuals. During its evolution to become a practical optimization tool, some heterogeneous variants have been proposed. However, heterogeneity in PSO algorithms has never been explicitly studied and some of its potential effects have therefore been overlooked. In this paper, we identify some of the most relevant types of heterogeneity that can be ascribed to particle swarms. A number of particle swarms are classified according to the type of heterogeneity they exhibit, which allows us to identify some gaps in current knowledge about heterogeneity in PSO algorithms. Motivated by these observations, we carry out an experimental study of two heterogeneous particle swarms each of which is composed of two kinds of particles. Directions for future developments on heterogeneous particle swarms are outlined.

We have designed and built a new open hardware/software board that lets miniaturized robots communicate and at the same time obtain the range and bearing of the source of emission. The open E-puck Range & Bearing board improves an existing infrared relative localization/communication software library (libIrcom) developed for the e-puck robot and based on its on-board infrared sensors. The board allows the robots to have an embodied, decentralized and scalable communication system. Its use and capabilities are demonstrated via an alignment experiment.

Swarm intelligence is the discipline that deals with natural and artificial systems composed of many individuals that coordinate using decentralized control and self-organization. In particular, it focuses on the collective behaviors that result from the local interactions of the individuals with each other and with their environment. The characterizing property of a swarm intelligence system is its ability to act in a coordinated way without the presence of a coordinator or of an external controller. Swarm robotics could be defined as the application of swarm intelligence principles to the control of groups of robots. In this talk I will discuss results of Swarm-bots, an experiment in swarm robotics. A swarm-bot is an artifact composed of a swarm of assembled s-bots. The s-bots are mobile robots capable of connecting to, and attached to each other and, when needed, become a single robotic system that can move and change its shape. S-bots have relatively simple sensors and motors and limited computational capabilities. A swarm-bot can solve problems that cannot be solved by s-bots alone. In the talk, I will shortly describe the s-bots hardware and the methodology we followed to develop algorithms for their control. Then I will focus on disconnecting from, other s-bots. In the swarm-bot form, the s-bots are the capabilities of the swarm-bot robotic system by showing video recordings of some of the many experiments we performed to study coordinated movement, path formation, self-assembly, collective transport, shape formation, and other collective behaviors. I will conclude presenting initial results of the Swarmanoid experiment, an extension of swarm-bot to 3- dimensional environments.

This research work illustrates an approach to the design of controllers for self-assembling robots in which the self-assembly is initiated and regulated by perceptual cues that are brought forth by the physical robots through their dynamical interactions. More specifically, we present a homogeneous control system that can achieve assembly between two modules (two fully autonomous robots) of a mobile self-reconfigurable system without a priori introduced behavioral or morphological heterogeneities. The controllers are dynamic neural networks evolved in simulation that directly control all the actuators of the two robots. The neurocontrollers cause the dynamic specialization of the robots by allocating roles between them based solely on their interaction. We show that the best evolved controller proves to be successful when tested on a real hardware platform, the swarm-bot. The performance achieved is similar to the one achieved by existing modular or behavior-based approaches, also due to the effect of an emergent recovery mechanism that was neither explicitly rewarded by the fitness function, nor observed during the evolutionary simulation. Our results suggest that direct access to the orientations or intentions of the other agents is not a necessary condition for robot coordination: Our robots coordinate without direct or explicit communication, contrary to what is assumed by most research works in collective robotics. This work also contributes to strengthening the evidence that evolutionary robotics is a design methodology that can tackle real-world tasks demanding fine sensory-motor coordination.

One of the essential benefits of swarm robotic systems is redundancy. In case one robot breaks down, another robot can take steps to repair the failed robot or take over the failed robot's task. Although fault tolerance and robustness to individual failures have often been central arguments in favor of swarm robotic systems, few studies have been dedicated to the subject. In this paper, we take inspiration from the synchronized flashing behavior observed in some species of fireflies. We derive a completely decentralized algorithm to detect non-operational robots in a swarm robotic system. Each robot flashes by lighting up its on-board light-emitting diodes (LEDs), and neighboring robots are driven to flash in synchrony. Since robots that are suffering catastrophic failures do not flash periodically, they can be detected by operational robots. We explore the performance of the proposed algorithm both on a real-world swarm robotic system and in simulation. We show that failed robots are detected correctly and in a timely manner, and we show that a system composed of robots with simulated self-repair capabilities can survive relatively high failure rates.

Swarm robotics draws inspiration from decentralized self-organizing biological systems in general and from the collective behavior of social insects in particular. In social insect colonies, many tasks are performed by higher order group or team entities, whose task-solving capacities transcend those of the individual participants. In this paper, we investigate the emergence of such higher order entities. We report on an experimental study in which a team of physical robots performs a foraging task. The robots are "identical" in hardware and control. They make little use of memory and take actions purely on the basis of local information. Our study advances the current state of the art in swarm robotics with respect to the number of real-world robots engaging in teamwork (up to 12 robots in the most challenging experiment). To the best of our knowledge, in this paper we present the first self-organized system of robots that displays a dynamical hierarchy of teamwork (with cooperation also occurring among higher order entities). Our study shows that teamwork requires neither individual recognition nor differences between individuals. This result might also contribute to the ongoing debate on the role of these characteristics in the division of labor in social insects.

During the last decade, many variants of the original particle swarm optimization (PSO) algorithm have been proposed. In many cases, the difference between two variants can be seen as an algorithmic component being present in one variant but not in the other. In the first part of the paper, we present the results and insights obtained from a detailed empirical study of several PSO variants from a component difference point of view. In the second part of the paper, we propose a new PSO algorithm that combines a number of algorithmic components that showed distinct advantages in the experimental study concerning optimization speed and reliability. We call this composite algorithm Frankenstein's PSO in an analogy to the popular character of Mary Shelley's novel. Frankenstein's PSO performance evaluation shows that by integrating components in novel ways effective optimizers can be designed.

In this paper, we propose SWARMORPH: a distributed morphology generation mechanism for autonomous self-assembling mobile robots. Self-organized growth of global morphological structures emerges through the repeated application of local morphology extension rules. We present details of the directional self-assembly mechanism that provides control over the orientation of interrobot connections. We conduct real-world experiments to validate the low-level directional self-assembly mechanism and the growth of global morphologies. We demonstrate the scalability of the approach with large numbers of robots in simulation-based experiments.

In this study, we show a group of robots can synchronize based on firefly-inspired flashing behavior and how dead robots can be detected by other robots. The algorithm is completely distributed. Each robot flashes by lighting up its on-board LEDs and neighboring robots are driven to flash in synchrony. Since robots that are suffering catastrophic failures do not flash periodically, they can be detected by operational robots. On a real multi-robot system of 10 autonomous robots, we show how the group can correctly detect multiple faults, and that when given (simulated) repair capabilities, the group can survive a relatively high rate of failure.

This article describes a simulation model in which artificial evolution is used to design homogeneous control structures and adaptive communication protocols for a group of three autonomous simulated robots. The agents are required to cooperate in order to approach a light source while avoiding collisions. The robots are morphologically different: Two of them are equipped with infrared sensors, one with light sensors. Thus, the two morphologically identical robots should take care of obstacle avoidance; the other one should take care of phototaxis. Since all of the agents can emit and perceive sound, the group's coordination of actions is based on acoustic communication. The results of this study are a proof of concept: They show that dynamic artificial neural networks can be successfully synthesized by artificial evolution to design the neural mechanisms required to underpin the behavioral strategies and adaptive communication capabilities demanded by this task. Postevaluation analyses unveil operational aspects of the best evolved behavior. Our results suggest that the building blocks and the evolutionary machinery detailed in the article should be considered in future research work dealing with the design of homogeneous controllers for groups of heterogeneous cooperating and communicating robots.

In recent years, much attention has been devoted to the development of metaheuristics and local search algorithms for tackling stochastic combinatorial optimization problems. This paper focuses on local search algorithms; their effectiveness is greatly determined by the evaluation procedure that is used to select the best of several solutions in the presence of uncertainty. In this paper, we propose an effective evaluation procedure that makes use of empirical estimation techniques. We illustrate this approach and we assess its performance on the probabilistic traveling salesman problem. Experimental results on a large set of instances show that the proposed approach can lead to a very fast and highly effective local search algorithm.

In this paper, we review half a century of research on the design of systems displaying (physical) self-assembly of macroscopic components. We report on the experience gained in the design of 21 such systems, exhibiting components ranging from passive mechanical parts to mobile robots. We present a taxonomy of the systems and discuss design principles and functions. Finally, we summarize the main achievements and indicate potential directions for future research.

This paper proposes a distributed control mechanism for a self-propelled self-assembling robotic system that allows robots to form specific, connected morphologies. Global morphologies are 'grown' using local visual perception only. The robots in the system do not have access to a blueprint of the global pattern and the algorithmic rules are solely based on what a single robot can see in its immediate surroundings. None of the robots have any predefined position in the final morphology, except for the seed robot that initiates the self-assembly process. Robots that are part of the connected entity indicate where new robots should attach in order to grow the local structure appropriately. The paper demonstrates the efficacy of the mechanism by letting groups of up to 9 real robots self-assemble into four different morphologies: line, star, arrow, and dense.

Mobile robots are said to be capable of self- assembly when they can autonomously form physical connections with each other. Despite the recent proliferation of self- assembling systems, little work has been done on using self- assembly to add functional value to a robotic system, and even less on quantifying the contribution of self-assembly to system performance. In this study we demonstrate and quantify the performance benefits of i) acting as a physically larger self-assembled entity, ii) using self-assembly adaptively and iii) making the robots morphologically aware (the self-assembled robots leverage their new connected morphology in a task specific way). In our experiments, two real robots must navigate to a target over a-priori unknown terrain. In some cases the terrain can only be overcome by a self-assembled connected entity. In other cases, the robots can reach the target faster by navigating individually.

Ant colony optimization (ACO) is a promising metaheuristic and a great amount of research has been devoted to its empirical and theoretical analysis. Recently, with the introduction of the hypercube framework, Blum and Dorigo have explicitly raised the issue of the invariance of ACO algorithms to transformation of units. They state (Blum and Dorigo, 2004) that the performance of ACO depends on the scale of the problem instance under analysis. In this paper, we show that the ACO internal state—commonly referred to as the pheromone—indeed depends on the scale of the problem at hand. Nonetheless, we formally prove that this does not affect the sequence of solutions produced by the three most widely adopted algorithms belonging to the ACO family: ant system, MAX-MIN ant system, and ant colony system. For these algorithms, the sequence of solutions does not depend on the scale of the problem instance under analysis. Moreover, we introduce three new ACO algorithms, the internal state of which is independent of the scale of the problem instance considered. These algorithms are obtained as minor variations of ant system, MAX-MIN ant system, and ant colony system. We formally show that these algorithms are functionally equivalent to their original counterparts. That is, for any given instance, these algorithms produce the same sequence of solutions as the original ones.

An important goal of collective robotics is the design of control systems that allow groups of robots to accomplish common tasks by coordinating without a centralized control. In this paper, we study how a group of physically assembled robots can display coherent behavior on the basis of a simple neural controller that has access only to local sensory information. This controller is synthesized through artificial evolution in a simulated environment in order to let the robots display coordinated-motion behaviors. The evolved controller proves to be robust enough to allow a smooth transfer from simulated to real robots. Additionally, it generalizes to new experimental conditions, such as different sizes/shapes of the group and/or different connection mechanisms. In all these conditions the performance of the neural controller in real robots is comparable to the one obtained in simulation.

This paper addresses the cooperative transport of a heavy object by a group of mobile robots. We present a system in which group members lacking knowledge about the position of the transport target exploit physical interactions with other members of the group that have such knowledge. This is the first such system to achieve a performance superior to that of a passive caster. The system is fully decentralized and the information flow between the robots is limited to physical interactions. The robots have no knowledge about their relative positions. A comprehensive experimental study with up to six physical robots confirms the effectiveness, reliability, and robustness of the system. Finally, the system is examined in rough terrain conditions

We present a first attempt to accomplish a simple object manipulation task using the self-reconfigurable robotic system swarm-bot. The number of modular entities involved, their global shape or size and their internal structure are not pre-determined, but result from a self-organized process in which the modules autonomously grasp each other and/or an object. The modules are autonomous in perception, control, action, and power. We present quantitative results, obtained with six physical modules, that confirm the utility of self-assembling robots in a concrete task

Ant-based clustering and sorting is a nature-inspired heuristic first introduced as a model for explaining two types of emergent behavior observed in real ant colonies. More recently, it has been applied in a data-mining context to perform both clustering and topographic mapping. Early work demonstrated some promising characteristics of the heuristic but did not extend to a rigorous investigation of its capabilities. We describe an improved version, called ATTA, incorporating adaptive, heterogeneous ants, a time-dependent transporting activity, and a method (for clustering applications) that transforms the spatial embedding produced by the algorithm into an explicit partitioning. ATTA is then subjected to the most rigorous experimental evaluation of an ant-based clustering and sorting algorithm undertaken to date: we compare its performance with standard techniques for clustering and topographic mapping using a set of analytical evaluation functions and a range of synthetic and real data collections. Our results demonstrate the ability of ant-based clustering and sorting to automatically identify the number of clusters inherent in a data collection, and to produce high quality solutions; indeed, we show that it is particularly robust for clusters of differing sizes and for overlapping clusters. The results obtained for topographic mapping are, however, disappointing. We provide evidence that the solutions generated by the ant algorithm are barely topology-preserving, and we explain in detail why results have--in spite of this--been misinterpreted (much more positively) in previous research.

In this article, we analyze the behavior of a group of robots involved in an object retrieval task. The robots' control system is inspired by a model of ants' foraging. This model emphasizes the role of learning in the individual. Individuals adapt to the environment using only locally available information. We show that a simple parameter adaptation is an effective way to improve the efficiency of the group and that it brings forth division of labor between the members of the group. Moreover, robots that are best at retrieving have a higher probability of becoming active retrievers. This selection of the best members does not use any explicit representation of individual capabilities. We analyze this system and point out its strengths and its weaknesses.

This article illustrates the methods and results of two sets of experiments in which a group of mobile robots, calleds-bots, are required to physically connect to each other, that is, to self-assemble, to cope with environmental conditions that prevent them from carrying out their task individually. The first set of experiments is a pioneering study on the utility of self-assembling robots to address relatively complex scenarios, such as cooperative object transport. The results of our work suggest that the s-bots possess hardware characteristics which facilitate the design of control mechanisms for autonomous self-assembly. The control architecture we developed proved particularly successful in guiding the robots engaged in the cooperative transport task. However, the results also showed that some features of the robots' controllers had a disruptive effect on their performances. The second set of experiments is an attempt to enhance the adaptiveness of our multi-robot system. In particular, we aim to synthesise an integrated (i.e., not-modular) decision-making mechanism which allows the s-bot to autonomously decide whether or not environmental contingencies require self-assembly. The results show that it is possible to synthesize, by using evolutionary computation techniques, artificial neural networks that integrate both the mechanisms for sensory-motor coordination and for decision making required by the robots in the context of self-assembly.

In this paper, we discuss the self-assembling capabilities of the swarm-bot, a distributed robotics concept that lies at the intersection between collective and self-reconfigurable robotics. A swarm-bot is comprised of autonomous mobile robots called s-bots. S-bots can either act independently or self-assemble into a swarm-bot by using their grippers. We report on experiments in which we study the process that leads a group of s-bots to self-assemble. In particular, we present results of experiments in which we vary the number of s-bots (up to 16 physical robots), their starting configurations, and the properties of the terrain on which self-assembly takes place. In view of the very successful experimental results, swarm-bot qualifies as the current state of the art in autonomous self-assembly

This paper provides an overview of the SWARM-BOTS project, a robotics project sponsored by the Future and Emerging Technologies program of the European Commission (IST-2000-31010). We describe the s-bot, a small autonomous robot with self-assembling capabilities that we designed and built within the project. Then we illustrate the cooperative object transport scenario that we chose to use as a test-bed for our robots. Last, we report on results of experiments in which a group of s-bots perform a variety of tasks within the scenario which may require self-assembling, physical cooperation and coordination.

A swarm robotic system is normally characterised by many individuals, each having a partial/limited knowledge about the global pattern of which it constitutes an element. In such a system, decision-making processes may be problematic. However, inspiration can be drawn from insect societies, in which self-organisation plays a crucial role in most of the decisions taken by the colony. In this work, we show how, in a swarm robotic system, a decision can be the result of a collective process: it emerges from the numerous interactions among the individuals and between individuals and environment. We present a task in which a swarm of physically connected, simulated robots has to take a decision whether to pass over a trough or change direction of motion if the gap is too wide to be bridged. We show how such a decision can be collectively taken, based only on a self-organising process.

One of the problems encountered when applying ant colony optimization (ACO) to combinatorial optimization problems is that the search process is sometimes biased by algorithm features such as the pheromone model and the solution construction process. Sometimes this bias is harmful and results in a decrease in algorithm performance over time, which is called second-order deception. In this work, we study the reasons for the occurrence of second-order deception. In this context, we introduce the concept of competition-balanced system (CBS), which is a property of the combination of an ACO algorithm with a problem instance. We show by means of an example that combinations of ACO algorithms with problem instances that are not CBSs may suffer from a bias that leads to second-order deception. Finally, we show that the choice of an appropriate pheromone model is crucial for the success of the ACO algorithm, and it can help avoid second-order deception.

In this paper, we aim to design decision-making mechanisms for a simulated Khepera robot equipped with simple sensors, which integrates over time its perceptual experience in order to initiate a simple signalling response.Contrary to other previous similar studies, in this work the decision-making is uniquely controlled by the time-dependent structures of the agent controller, which in turn are tightly linked to the mechanisms for sensorimotor coordination.The results of this work show that a single dynamic neural network, shaped by evolution, makes an autonomous agent capable of 'feeling' time through the flow of sensations determined by its actions.Further analysis of the evolved solutions reveals the nature of the selective pressures that facilitate the evolution of fully discriminating and signalling agents.Moreover, we show that, by simply working on the nature of the fitness function, it is possible to bring forth discrimination mechanisms that generalize to conditions never encountered during evolution.

Ant colony optimization is a metaheuristic approach belonging to the class of model-based search algorithms. In this paper, we propose a new framework for implementing ant colony optimization algorithms called the hyper-cube framework for ant colony optimization. In contrast to the usual way of implementing ant colony optimization algorithms, this framework limits the pheromone values to the interval [0,1]. This is obtained by introducing changes in the pheromone value update rule. These changes can in general be applied to any pheromone value update rule used in ant colony optimization. We discuss the benefits coming with this new framework. The benefits are twofold. On the theoretical side, the new framework allows us to prove that in Ant System, the ancestor of all ant colony optimization algorithms, the average quality of the solutions produced increases in expectation over time when applied to unconstrained problems. On the practical side, the new framework automatically handles the scaling of the objective function values. We experimentally show that this leads on average to a more robust behavior of ant colony optimization algorithms.

In this article, we study the relationship between the two techniques known as ant colony optimization (ACO) and stochastic gradient descent. More precisely, we show that some empirical ACO algorithms approximate stochastic gradient descent in the space of pheromones, and we propose an implementation of stochastic gradient descent that belongs to the family of ACO algorithms. We then use this insight to explore the mutual contributions of the two techniques.

SCOPUS: ed.j

We prove some convergence properties for a class of ant colony optimization algorithms. In particular, we prove that for any small constant /spl epsiv/ > 0 and for a sufficiently large number of algorithm iterations t, the probability of finding an optimal solution at least once is P*(t) /spl ges/ 1 - /spl epsiv/ and that this probability tends to 1 for t/spl rarr//spl infin/. We also prove that, after an optimal solution has been found, it takes a finite number of iterations for the pheromone trails associated to the found optimal solution to grow higher than any other pheromone trail and that, for t/spl rarr//spl infin/, any fixed ant will produce the optimal solution during the tth iteration with probability P /spl ges/ 1 /spl epsiv//spl circ/(/spl tau//sub min/, /spl tau//sub max/), where /spl tau//sub min/ and /spl tau//sub max/ are the minimum and maximum values that can be taken by pheromone trails.

We present a new local optimizer called SOP-3-exchange for the sequential ordering problem that extends a local search for the traveling salesman problem to handle multiple constraints directly without increasing computational complexity. An algorithm that combines the SOP-3-exchange with an Ant Colony Optimization algorithm is described, and we present experimental evidence that the resulting algorithm is more effective than existing methods for the problem. The best-known results for many of a standard test set of 22 problems are improved using the SOP-3-exchange with our Ant Colony Optimization algorithm or in combination with the MPO/AI algorithm (Chen and Smith 1996).

Recently, a number of algorithms inspired by the foraging behavior of ant colonies have been applied to the solution of difficult discrete optimization problems. We put these algorithms in a common framework by defining the Ant Colony Optimization (ACO) meta-heuristic. A couple of paradigmatic examples of applications of these novel meta-heuristic are given, as well as a brief overview of existing applications.

This article presents an overview of recent work on ant algorithms, that is, algorithms for discrete optimization that took inspiration from the observation of ant colonies' foraging behavior, and introduces the ant colony optimization (ACO) metaheuristic. In the first part of the article the basic biological findings on real ants are reviewed and their artificial counterparts as well as the ACO metaheuristic are defined. In the second part of the article a number of applications of ACO algorithms to combinatorial optimization and routing in communications networks are described. We conclude with a discussion of related work and of some of the most important aspects of the ACO metaheuristic.

info:eu-repo/semantics/published

We propose a modular architecture for autonomous robots which allows for the implementation of basic behavioral modules by both programming and training, and accommodates for an evolutionary development of the interconnections among modules. This architecture can implement highly complex controllers and allows for incremental shaping of the robot behavior. Our proposal is exemplified and evaluated experimentally through a number of mobile robotic tasks involving exploration, battery recharging and object manipulation.

This paper introduces AntNet, a novel approach to the adaptive learning of routing tables in communications networks. AntNet is a distributed, mobile agents based Monte Carlo system that was inspired by recent work on the ant colony metaphor for solving optimization problems. AntNet's agents concurrently explore the network and exchange collected information. The communication among the agents is indirect and asynchronous, mediated by the network itself. This form of communication is typical of social insects and is called stigmergy. We compare our algorithm with six state-of-the-art routing algorithms coming from the telecommunications and machine learning fields. The algorithms' performance is evaluated over a set of realistic testbeds. We run many experiments over real and artificial IP datagram networks with increasing number of nodes and under several paradigmatic spatial and temporal traffic distributions. Results are very encouraging. AntNet showed superior performance under all the experimental conditions with respect to its competitors. We analyze the main characteristics of the algorithm and try to explain the reasons for its superiority.

Q-learning can greatly improve its convergence speed if helped by immediate reinforcements provided by a trainer able to judge the usefulness of actions as stage setting with respect to the goal of the agent. This article experimentally investigates this hypothesis studying the integration of immediate reinforcements (also called training reinforcements) with standard delayed reinforcements (namely, reinforcements assigned only when the agent–environment relationship reaches a peculiar state, such as when the agent reaches a target). The article proposes two new algorithms (TL and MTL) able to exploit even locally wrong and misleading training reinforcements. The proposed algorithms are tested against Q-learning and other algorithms (AB–LEC and BB–LEC) described in the literature [S. D. Whitehead, TR-365, University of Rochester, NY, 1991], which also make use of training reinforcements. Experiments are run in a grid world where a Q-agent, a simple simulated robot, must learn to reach a target. © 1997 John Wiley & Sons, Inc.

This paper introduces the ant colony system (ACS), a distributed algorithm that is applied to the traveling salesman problem (TSP). In the ACS, a set of cooperating agents called ants cooperate to find good solutions to TSPs. Ants cooperate using an indirect form of communication mediated by a pheromone they deposit on the edges of the TSP graph while building solutions. We study the ACS by running experiments to understand its operation. The results show that the ACS outperforms other nature-inspired algorithms such as simulated annealing and evolutionary computation, and we conclude comparing ACS-3-opt, a version of the ACS augmented with a local search procedure, to some of the best performing algorithms for symmetric and asymmetric TSPs.

We propose Behavior Engineering as a new technological area whose aim is to provide methodologies and tools for developing autonomous robots. Building robots is a very complex engineering enterprise that requires the exact definition and scheduling of the activities which a designer, or a team of designers, should follow. Behavior Engineering is, within the autonomous robotics realm, the equivalent of more established disciplines like Software Engineering and Knowledge Engineering. In this article we first give a detailed presentation of a Behavior Engineering methodology, which we call Behavior Analysis and Training (BAT), where we stress the role of learning and training. Then we illustrate the application of the BAT methodology to three cases involving different robots: two mobile robots and a manipulator. Results show the feasibility of the proposed approach.

An analogy with the way ant colonies function has suggested the definition of a new computational paradigm, which we call ant system (AS). We propose it as a viable new approach to stochastic combinatorial optimization. The main characteristics of this model are positive feedback, distributed computation, and the use of a constructive greedy heuristic. Positive feedback accounts for rapid discovery of good solutions, distributed computation avoids premature convergence, and the greedy heuristic helps find acceptable solutions in the early stages of the search process. We apply the proposed methodology to the classical traveling salesman problem (TSP), and report simulation results. We also discuss parameter selection and the early setups of the model, and compare it with tabu search and simulated annealing using TSP. To demonstrate the robustness of the approach, we show how the ant system (AS) can be applied to other optimization problems like the asymmetric traveling salesman, the quadratic assignment and the job-shop scheduling. Finally we discuss the salient characteristics-global data structure revision, distributed communication and probabilistic transitions of the AS.

It is well known that standard learning classifier systems, when applied to many different domains, exhibit a number of problems: payoff oscillation, difficulty in regulating interplay between the reward system and the background genetic algorithm (GA), rule chains' instability, default hierarchies' instability, among others. ALECSYS is a parallel version of a standard learning classifier system (CS) and, as such, suffers from these same problems. In this paper we propose some innovative solutions to some of these problems. We introduce the following original features. Mutespec is a new genetic operator used to specialize potentially useful classifiers. Energy is a quantity introduced to measure global convergence to apply the genetic algorithm only when the system is close to a steady state. Dynamic adjustment of the classifiers set cardinality speeds up the performance phase of the algorithm. We present simulation results of experiments run in a simulated two-dimensional world in which a simple agent learns to follow a light source.

Intelligent robots should be able to use sensor information to learn how to behave in a changing environment. As environmental complexity grows, the learning task becomes more and more difficult. This problem is faced using an architecture based on learning classifier systems and on the structural properties of animal behavioral organization, as proposed by ethologists. After a description of the learning technique used and of the organizational structure proposed, experiments that show how behavior acquisition can be achieved are presented. The simulated robot learns to follow a light and to avoid hot dangerous objects. While these two simple behavioral patterns are independently learned, coordination is attained by means of a learning coordination mechanism.>