Swarm Intelligence

We present a robot swarm composed of Pi-puck robots that maintain a blockchain network. The blockchain serves as security layer to neutralize Byzantine robots (faulty, malfunctioning, or malicious robots). In the context of this work, we implemented a framework for high-throughput communication using a decentralized mobile ad-hoc network. This work serves as a building block for secure real-world deployments of robot swarms. Our results show that the use of a blockchain is feasible and warranted in embodied robot swarm deployments.

The overwhelming majority of ant colony optimization approaches from the literature is exclusively based on learning from positive examples. Natural examples from biology, however, indicate the potential usefulness of negative learning. Several research works have explored this topic over the last two decades in the context of ant colony optimization, with limited success. In this work we present an alternative proposal for the incorporation of negative learning in ant colony optimization. The results obtained for the capacitated minimum dominating set problem indicate that this approach can be quite useful. More specifically, our extended ant colony algorithm clearly outperforms the standard approach. Moreover, we were able to improve the current state-of-the-art results in 10 out of 36 cases.

Generating useful unit tests for object-oriented programs is difficult for traditional optimization methods. One not only needs to identify values to be used as inputs, but also synthesize a program which creates the required state in the program under test. Many existing Automated Test Generation (ATG) approaches combine search with performance-enhancing heuristics. We present Tiered Ant Colony Optimization (Taco) for generating unit tests for object-oriented programs. The algorithm is formed of three Tiers of ACO, each of which tackles a distinct task: goal prioritization, test program synthesis, and data generation for the synthesised program. Test program synthesis allows the creation of complex objects, and exploration of program state, which is the breakthrough that has allowed the successful application of ACO to object-oriented test generation. Taco brings the mature search ecosystem of ACO to bear on ATG for complex object-oriented programs, providing a viable alternative to current approaches. To demonstrate the effectiveness of Taco, we have developed a proof-of-concept tool which successfully generated tests for an average of 54% of the methods in 170 Java classes, a result competitive with industry standard Randoop.

Swarm robotics studies how a large number of relatively simple robots can accomplish various functions collectively and dynamically. Modular robotics concentrates on the design of specialized connected parts to perform precise tasks, while other swarms exhibit more fluid flocking and group adaptation. Here we focus on the process of morphogenesis per se, i.e. the programmable and reliable bottom-up emergence of shapes at a higher level of organization. We show that simple abstract rules of behavior executed by each agent (their “genotype”), involving message passing, virtual link creation, and force-based motion, are sufficient to generate various reproducible and scalable multi-agent branched structures (the “phenotypes”). On this basis, we propose a model of collective robot dynamics based on “morphogenetic engineering” principles, in particular an algorithm of programmable network growth, and how it allows a flock of self-propelled wheeled robots on the ground to coordinate and function together. The model is implemented in simulation and demonstrated in physical experiments with the PsiSwarm platform.

In this paper, we propose Distributed Bayesian Hypothesis Testing (DBHT) as a novel collective decision-making strategy to solve the collective perception problem. We experimented with different sampling and dissemination intervals for DBHT and concluded that the selection of both intervals presents a trade-off between speed and accuracy. After that, we compare the performance of DBHT in simulation with that of 3 other commonly used collective decision-making strategies, DVMD, DMMD and DC. We tested them on collective perception problems with different difficulties and feature patterns. We have concluded that DBHT outperforms considered existing algorithms significantly in collective perception tasks with high difficulty, namely close proportion of features and clustered feature distribution.

The rapidly changing paradigm in energy supply with a shift of operational responsibility towards distributed and highly fluctuating renewables demands for proper integration and coordination of a broad variety of small generation and consumption units. Many use cased demand for optimized coordination of electricity production or consumption schedules. In the discrete case, this is an NP-hard problem for step-controlled devices if some sort of intermediate energy buffer is involved. Systematically constructing feasible solutions during optimization degenerates to a difficult task. We present a model-integrated approach based on ant colony optimization. By using a simulation model for deciding on feasible branches (follow-up power operation levels), ants construct the feasible search graph on demand, thus avoiding exponential growth in this combinatorial problem. Applicability and competitiveness are demonstrated in several simulation studies using a model for a co-generation plant as typical small sized smart grid generation unit.

Building structures is a remarkable collective process but its automation remains an open challenge. Robot swarms provide a promising solution to this challenge. However, collective construction involves a number of difficulties regarding efficient robots allocation to the different activities, particularly if the goal is to reach an optimal construction rate. In this paper, we study an abstract construction scenario, where a swarm of robots is engaged in a collective perception process to estimate the density of building blocks around a construction site. The goal of this perception process is to maintain a minimum density of blocks available to the robots for construction. To maintain this density, the allocation of robots to the foraging task needs to be adjusted such that enough blocks are retrieved. Our results show a robust collective perception that enables the swarm to maintain a minimum block density under different rates of construction and foraging. Our approach leads the system to stabilize around a state in which the robots allocation allows the swarm to maintain a tile density that is close to or above the target minimum.

The multi-guide particle swarm optimization (MGPSO) algorithm is a multi-objective optimization algorithm that uses multiple swarms, each swarm focusing on an individual objective. This paper conducts an importance and sensitivity analysis on the MGPSO control parameters using functional analysis of variance (fANOVA). The fANOVA process quantifies the control parameter importance through analysing variance in the objective function values associated with a change in control parameter values. The results indicate that the inertia component value has the greatest sensitivity and is the most important control parameter to tune when optimizing the MGPSO.

We argue that heterogeneous threshold ranges allow agents in a decentralized swarm to effectively adapt thresholds in response to dynamic task demands while avoiding the pitfalls of positive feedback sinks. Dynamic response thresholds allow agents to dynamically evolve specializations which can improve the responsiveness and stability of a swarm. Dynamic thresholds that adapt in response to previous experience, however, are vulnerable to getting stuck in sink states due to the positive feedback nature of such systems. We show that heterogeneous threshold ranges result in comparable task allocation and improved stability as compared to homogeneous threshold ranges, and that simple static random thresholds should be considered in situations where agent resources are plentiful.

In this paper, we carry out a review of the grey wolf, the firefly and the bat algorithms. We identify the concepts involved in these three metaphor-based algorithms and compare them to those proposed in the context of particle swarm optimization. We provide compelling evidence that the grey wolf, the firefly, and the bat algorithms are not novel, but a reiteration of ideas introduced first for particle swarm optimization and reintroduced years later using new natural metaphors. These three algorithms can therefore be added to the growing list of metaphor-based algorithms—to which already belong algorithms such as harmony search and intelligent water drops—that are nothing else than repetitions of old ideas hidden by the usage of new terminology.

Scalability is a key feature of swarm robotics. Hence, measuring performance depending on swarm size is important to check the validity of the design. Performance diagrams have generic qualities across many different application scenarios. We summarize these findings and condense them in a practical performance analysis guide for swarm robotics. We introduce three general classes of performance: linear increase, saturation, and increase/decrease. As the performance diagrams may contain rich information about underlying processes, such as the degree of collaboration and chains of interference events in crowded situations, we discuss options for quickly devising hypotheses about the underlying robot behaviors. The validity of our performance analysis guide is then made plausible in a number of simple examples based on models and simulations.

Inter-agent variation is well-known in both the biology and computer science communities as a mechanism for improving task selection and swarm performance for multi-agent systems. Response threshold variation, the most commonly used form of inter-agent variation, desynchronizes agent actions allowing for more targeted agent activation. Recent research using a less common form of variation, termed dynamic response intensity, demonstrates that modeling levels of agent experience or varying physical attributes and using these to allow some agents to perform tasks more efficiently or vigorously, significantly improves swarm goal achievement when used in conjunction with response thresholds. Dynamic intensity values vary within a fixed range as agents activate for tasks. We extend previous work by demonstrating that adding another layer of variation to response intensity, in the form of heterogeneous ranges for response intensity values, provides significant performance improvements when response is probabilistic. Heterogeneous intensity ranges break the coupling that occurs between response thresholds and response intensities when the intensity range is homogeneous. The decoupling allows for increased diversity in agent behavior.

The research topic of human–human swam intelligence includes many mechanisms that need to be studied in controlled experiment conditions with multiple human subjects. Virtual environments are a useful tool to isolate specific human interactions for study, but current platforms support only a small scope of possible research areas. In this paper, we present HuGoS—‘Humans Go Swarming’—a multi-user virtual environment in Unity, as a comprehensive tool for experimentation in human–human swarm intelligence. We identify possible experiment classes for studying human collective behavior, and equip our virtual environment with sufficient features to support each of these experiment classes. We then demonstrate the functionality of the virtual environment in simple examples for three of the experiment classes: human collective decision making, human social learning strategies, and agent-level human interaction with artificial swarms, including robot swarms.

Foraging for resources is critical to the survival of many animal species. When resources are scarce, individuals can benefit from interactions, effectively parallelizing the search process. Moreover, communication between conspecifics can result in aggregation around salient patches, rich in resources. However, individual foragers often have short communication ranges relative to the scale of the environment. Hence, formation of a global, collective memory is difficult since information transfer between foragers is suppressed. Despite this limitation, individual motion can enhance information transfer, and thus enable formation of a collective memory. In this work, we study the effect of individual motion on the aggregation characteristics of a collective system of foragers during collective foraging. Using an agent-based model, we show that aggregation around salient patches can occur through formation of collective memory realized through local interactions and global displacement using Lévy walks. We show that the Lévy parameter that defines individual dynamics, and a decision parameter that defines the balance between exploration and exploitation, greatly influences the macroscopic aggregation characteristics. When individuals prefer exploration, global aggregation around a single patch occurs when explorative bouts are relatively short. In contrast, when individuals tend to exploit the collective memory, explorative bouts should be longer for global aggregation to occur. Local aggregation emerges when exploration is suppressed, regardless of the value of the decision parameter.

This paper presents a theoretical model for path planning in multi-robot navigation in swarm robotics. The plans for the paths are optimized using two objective functions, namely to maximize the safety distance between the agents and to minimize the mean time to complete a plan. The plans are designed for various vehicle models. The presented path planning model allows us to evaluate both decentralized and centralized planners. In this paper, we focus on decentralized planners and aim to find a set of Pareto-optimal plans, which enables us to investigate the fitness landscape of the problem. For solving the multi-objective problem, we design a modified version of NSGA-II algorithm with adapted operators to find sets of Pareto-optimal paths for several agents using various vehicle models and environments. Our experiments show that small problem instances can be solved well, while solving larger problems is not always possible due to the large complexity.

Information transfer among foragers is key for efficient allocation of work and adaptive responses within a honey bee colony. For information to spread quickly, foragers trying to recruit nestmates via the waggle dance (dancers) must reach as many other non-dancing foragers (followers) as possible. Forager bees may have different drives that influence their motion patterns. For instance, dancer bees need to widely cover the dance floor to recruit nestmates, the more broadly, the higher the food source profitability. Followers may instead move more erratically in the hope of meeting a dance. Overall, a good mixing of individuals is necessary to have flexibility at the level of the colony behavior and optimally respond to changing environmental conditions. We aim to determine the motion pattern that precedes communication events, exploiting a data-driven computational model. To this end, real observation data are used to define nest features such as the dance floor location, shape and size, as well as the foragers’ population size and density distribution. All these characteristics highly correlate with the bees walking pattern and determine the efficiency of information transfer among bees. A simulation environment is deployed to test different mobility patterns and evaluate the adherence with available real-world data. Additionally, we determine under what conditions information transfer is most efficient and effective. Owing to the simulation results, we identify the most plausible mobility pattern to represent the available observations.

We propose an approach to multi-robot coverage that combines aspects of centralized and decentralized control, based on the existing ‘mergeable nervous systems’ concept. In our approach, robots self-organize a dynamic ad-hoc communication network for distributed asymmetric control, enabling a degree of central coordination. In the coverage task, simulated ground robots coordinate with UAVs to explore an arena as uniformly as possible. Compared to strictly centralized and decentralized approaches, we test our approach in terms of coverage percentage, coverage uniformity, scalability, and fault tolerance.

We propose a solution to the problem of spatial interference between robots engaged in a planar construction task. Planar construction entails a swarm of robots pushing objects into a desired two-dimensional configuration. This problem is related to object clustering and sorting as well as collective construction approaches such as wall-building. In previous work we found robots were highly susceptible to collisions among themselves and with the boundary of the environment. Often these collisions led to deadlock and a dramatic reduction in task performance. To address these problems the solution proposed here subdivides the work area into lanes. Each robot determines its own lane and applies a novel control law to stay within it while nudging objects inwards towards the goal region. We show results using a realistic simulation environment. These results indicate that subdividing the arena into lanes can produce mild performance increases while being highly effective at keeping the robots separated. We also show that the introduction of lanes increases robustness to unforeseen obstacles in the environment.

This paper presents a hardware revision of the Pi-puck extension board that now includes support for the e-puck2. This Raspberry Pi interface for the e-puck robot provides a feature-rich experimentation platform suitable for multi-robot and swarm robotics research. We also present a new expansion board that features a 9-DOF IMU and XBee interface for increased functionality. We detail the revised Pi-puck hardware and software ecosystem, including ROS support that now allows mobile robotics algorithms and utilities developed by the ROS community to be leveraged by swarm robotics researchers. We also present the results of an illustrative multi-robot mapping experiment using new long-range Time-of-Flight distance sensor modules, to demonstrate the ease-of use and efficacy of this new Pi-puck ecosystem.

We present Arlequin, an off-line automatic design method that produces control software for robot swarms by combining behavioral neural-network modules generated via neuro-evolution. The neural-network modules are automatically generated once, in a mission-agnostic way, and are then automatically assembled into probabilistic finite-state machines to perform various missions. With Arlequin, our goal is to reduce the amount of human intervention that is required for the implementation or the operation of previously published modular design methods. Simultaneously, we assess whether neuro-evolution can be used in a modular design method to produce control software that crosses the reality gap satisfactorily. We present robot experiments in which we compare Arlequin with Chocolate, a state of the art modular design method, and EvoStick, a traditional neuro-evolutionary swarm robotics method. The preliminary results suggest that automatically combining neural-network modules into probabilistic finite-state machines is a promising approach to the automatic conception of control software for robot swarms.

The coalition formation problem arises when heterogeneous agents need to be gathered in groups in order to combine their capacities and solve an overall goal. But very often agents are different and can be distinguished by several characteristics like desires, beliefs or capacities. Our aim is to make groups of agents according to several characteristics. We argue that a swarming method inspired by group dynamics allows groups to be formed on the basis of several characteristics and makes it very robust in an open system context. We evaluate this approach by making groups of heterogeneous cognitive agents and show that our method is adapted to solve this problem.

Animals can carry their environmental sensing abilities beyond their own limits by using the advantage of being in a group. Some animal groups use this collective ability to migrate or to react to an environmental cue. The environmental cue sometimes consists of a gradient in space, for example represented by food concentration or predators’ odors. In this study, we propose a method for collective gradient perception in a swarm of flocking agents where single individuals are not capable of perceiving the gradient but only sample information locally. The proposed method is tested with multi-agent simulations and compared to standard collective motion methods. It is also evaluated using realistic dynamical models of autonomous aerial robots within the Gazebo simulator. The results suggest that the swarm can move collectively towards specific regions of the environment by following a gradient while solitary agents are incapable of doing it.

Recently, a particle swarm optimization (PSO) algorithm was used to fit a Gaussian mixture model (GMM). However, this algorithm incorporates an additional step in the optimization process which increases the algorithm complexity and scales badly to a large number of components and large datasets. This study proposes a cooperative approach to improve the scalability and complexity of the PSO approach and illustrates its effectiveness compared to the expectation-maximization (EM) algorithm and the existing PSO approach when applied to a number of clustering problems.

Formation control in a robot swarm targets the overall swarm shape and relative positions of individual robots during navigation. Existing approaches often use a global reference or have limited topology flexibility. We propose a novel approach without these constraints, by extending the concept of ‘mergeable nervous systems’ to establish distributed asymmetric control via a self-organized wireless communication network. In simulated experiments with UAVs and mobile robots, we present a proof-of-concept for three sub-tasks of formation control: formation establishment, maintenance during motion, and deformation. We also assess the fault tolerance and scalability of our approach.

In swarm robotics, self-organized aggregation refers to a collective process in which robots form a single aggregate in an arbitrarily chosen aggregation site among those available in the environment, or just in an arbitrarily chosen location. Instead of focusing exclusively on the formation of a single aggregate, in this study we discuss how to design a swarm of robots capable of generating a variety of final distributions of the robots to the available aggregation sites. We focus on an environment with two possible aggregation sites, A and B. Our study is based on the following working hypothesis: robots distribute on site A and B in quantities that reflect the relative proportion of robots in the swarm that selectively avoid A with respect to those that selectively avoid B. This is with an as minimal as possible proportion of robots in the swarm that selectively avoid one or the other site. We illustrate the individual mechanisms designed to implement the above mentioned working hypothesis, and we discuss the promising results of a set of simulations that systematically consider a variety of experimental conditions.

Swarms of autonomous agents are useful in many applications due to their ability to accomplish tasks in a decentralized manner, making them more robust to failures. Due to the difficulty in running experiments with large numbers of hardware agents, researchers typically resort to simulations with simplifying assumptions. While some assumptions are tolerable, we feel that two assumptions have been overlooked: one, that agents take up physical space, and two, that a collision avoidance algorithm is available to add safety to an existing algorithm. While there do exist minimally invasive collision avoidance algorithms designed to add safety while minimizing interference in the intended behavior, we show they can still cause unexpected interference. We use an illustrative example with a double-milling behavior and show, through simulations, that the collision avoidance can still cause unexpected interference and careful parameter tuning is needed.

Portfolio optimization is a complex real-world problem where assets are selected such that profit is maximized while risk is simultaneously minimized. In recent years, nature-inspired algorithms have become a popular choice for efficiently identifying optimal portfolios. This paper introduces such an algorithm that, unlike previous algorithms, uses a set-based approach to reduce the dimensionality of the problem and to determine the appropriate budget al.location for each asset. The results show that the proposed approach is capable of obtaining good quality solutions, while being relatively fast.