Self-Reconfigurable Hierarchical Frameworks for Formation Control of 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.

A blockchain-based information market to incentivise cooperation in swarms of self-interested robots.

Robot swarms are generally considered to be composed of cooperative agents that, despite their limited individual capabilities, can perform difficult tasks by working together. However, in open swarms, where different robots can be added to the swarm by different parties with potentially competing interests, cooperation is but one of many strategies. We envision an information market where robots can buy and sell information through transactions stored on a distributed blockchain, and where cooperation is encouraged by the economy itself. As a proof of concept, we study a classical foraging task, where exchanging information with other robots is paramount to accomplish the task efficiently. We illustrate that even a single robot that lies to others-a so-called Byzantine robot-can heavily disrupt the swarm. Hence, we devise two protection mechanisms. Through an individual-level protection mechanism, robots are more sceptical about others' information and can detect and discard Byzantine information, at the cost of lower efficiency. Through a systemic protection mechanism based on economic rules regulating robot interactions, robots that sell honest information acquire over time more wealth than Byzantines selling false information. Our simulations show that a well-designed robot economy penalises misinformation spreading and protects the swarm from Byzantine behaviour. We believe economics-inspired swarm robotics is a promising research direction that exploits the timely opportunity for decentralised economies offered by blockchain technology.

Robot swarms neutralize harmful Byzantine robots using a blockchain-based token economy.

Through cooperation, robot swarms can perform tasks or solve problems that a single robot from the swarm could not perform/solve by itself. However, it has been shown that a single Byzantine robot (such as a malfunctioning or malicious robot) can disrupt the coordination strategy of the entire swarm. Therefore, a versatile swarm robotics framework that addresses security issues in inter-robot communication and coordination is urgently needed. Here, we show that security issues can be addressed by setting up a token economy between the robots. To create and maintain the token economy, we used blockchain technology, originally developed for the digital currency Bitcoin. The robots were given crypto tokens that allowed them to participate in the swarm's security-critical activities. The token economy was regulated via a smart contract that decided how to distribute crypto tokens among the robots depending on their contributions. We designed the smart contract so that Byzantine robots soon ran out of crypto tokens and could therefore no longer influence the rest of the swarm. In experiments with up to 24 physical robots, we demonstrated that our smart contract approach worked: The robots could maintain blockchain networks, and a blockchain-based token economy could be used to neutralize the destructive actions of Byzantine robots in a collective-sensing scenario. In experiments with more than 100 simulated robots, we studied the scalability and long-term behavior of our approach. The obtained results demonstrate the feasibility and viability of blockchain-based swarm robotics.

Learning from humans to build social cognition among robots.

Self-organized groups of robots have generally coordinated their behaviors using quite simple social interactions. Although simple interactions are sufficient for some group behaviors, future research needs to investigate more elaborate forms of coordination, such as social cognition, to progress towards real deployments. In this perspective, we define social cognition among robots as the combination of social inference, social learning, social influence, and knowledge transfer, and propose that these abilities can be established in robots by building underlying mechanisms based on behaviors observed in humans. We review key social processes observed in humans that could inspire valuable capabilities in robots and propose that relevant insights from human social cognition can be obtained by studying human-controlled avatars in virtual environments that have the correct balance of embodiment and constraints. Such environments need to allow participants to engage in embodied social behaviors, for instance through situatedness and bodily involvement, but, at the same time, need to artificially constrain humans to the operational conditions of robots, for instance in terms of perception and communication. We illustrate our proposed experimental method with example setups in a multi-user virtual environment.

3D hybrid formation control of an underwater robot swarm: Switching topologies, unmeasurable velocities, and system constraints.

This paper addresses formation control of underactuated autonomous underwater vehicles in three-dimensional space, using a hybrid protocol that combines aspects of centralized and decentralized control with constraints that are particular to underwater vehicles, including switching topologies, unmeasurable velocities, and system constraints. Using a distributed leader-follower model, the hybrid formation protocol does not require velocity sensing, access to global information, or static and connected topologies. To handle switching jointly connected networks-that is, to tolerate temporary disconnections-a distributed observer is designed for followers to cooperatively estimate leader states using local measurements and local interactions. On this basis, a compound formation control strategy is proposed to achieve geometric convergence. Firstly, cascaded extended state observers are developed to recover the unmeasurable velocities and unknown dynamic uncertainties induced by internal model uncertainty and external disturbances. Secondly, an improved three-dimensional line-of-sight guidance law at the kinematic level is used to address the underactuated configuration and the nonzero attack and sideslip angles. Thirdly, to overcome potential instability as a result of system constraints, including velocity constraints and input saturations, two adaptive compensators in the dynamic controller are used to address the negative effects of truncation. Using the proposed approach, the estimation errors and formation tracking errors are proved to be uniformly and ultimately bounded. Additionally, the numerical simulation results verify the performance of the approach and demonstrate improvement over both distributed and centralized state-of-the-art approaches.

Secure and secret cooperation in robot swarms.

The importance of swarm robotics systems in both academic research and real-world applications is steadily increasing. However, to reach widespread adoption, new models that ensure the secure cooperation of large groups of robots need to be developed. This work introduces a method to encapsulate cooperative robotic missions in an authenticated data structure known as a Merkle tree. With this method, operators can provide the "blueprint" of the swarm's mission without disclosing its raw data. In other words, data verification can be separated from data itself. We propose a system where robots in a swarm, to cooperate toward mission completion, have to "prove" their integrity to their peers by exchanging cryptographic proofs. We show the implications of this approach for two different swarm robotics missions: foraging and maze formation. In both missions, swarm robots were able to cooperate and carry out sequential tasks without having explicit knowledge about the mission's high-level objectives. The results presented in this work demonstrate the feasibility of using Merkle trees as a cooperation mechanism for swarm robotics systems in both simulation and real-robot experiments, which has implications for future decentralized robotics applications where security plays a crucial role.

Reflections on the future of swarm robotics.

Swarm robotics will tackle real-world applications by leveraging automatic design, heterogeneity, and hierarchical self-organization.

Language Evolution in Swarm Robotics: A Perspective.

While direct local communication is very important for the organization of robot swarms, so far it has mostly been used for relatively simple tasks such as signaling robots preferences or states. Inspired by the emergence of meaning found in natural languages, more complex communication skills could allow robot swarms to tackle novel situations in ways that may not be a priori obvious to the experimenter. This would pave the way for the design of robot swarms with higher autonomy and adaptivity. The state of the art regarding the emergence of communication for robot swarms has mostly focused on offline evolutionary approaches, which showed that signaling and communication can emerge spontaneously even when not explicitly promoted. However, these approaches do not lead to complex, language-like communication skills, and signals are tightly linked to environmental and/or sensory-motor states that are specific to the task for which communication was evolved. To move beyond current practice, we advocate an approach to emergent communication in robot swarms based on language games. Thanks to language games, previous studies showed that cultural self-organization-rather than biological evolution-can be responsible for the complexity and expressive power of language. We suggest that swarm robotics can be an ideal test-bed to advance research on the emergence of language-like communication. The latter can be key to provide robot swarms with additional skills to support self-organization and adaptivity, enabling the design of more complex collective behaviors.

Blockchain Technology Secures Robot Swarms: A Comparison of Consensus Protocols and Their Resilience to Byzantine Robots.

Consensus achievement is a crucial capability for robot swarms, for example, for path selection, spatial aggregation, or collective sensing. However, the presence of malfunctioning and malicious robots (Byzantine robots) can make it impossible to achieve consensus using classical consensus protocols. In this work, we show how a swarm of robots can achieve consensus even in the presence of Byzantine robots by exploiting blockchain technology. Bitcoin and later blockchain frameworks, such as Ethereum, have revolutionized financial transactions. These frameworks are based on decentralized databases (blockchains) that can achieve secure consensus in peer-to-peer networks. We illustrate our approach in a collective sensing scenario where robots in a swarm are controlled via blockchain-based smart contracts (decentralized protocols executed via blockchain technology) that serve as "meta-controllers" and we compare it to state-of-the-art consensus protocols using a robot swarm simulator. Additionally, we show that our blockchain-based approach can prevent attacks where robots forge a large number of identities (Sybil attacks). The developed robot-blockchain interface is released as open-source software in order to facilitate future research in blockchain-controlled robot swarms. Besides increasing security, we expect the presented approach to be important for data analysis, digital forensics, and robot-to-robot financial transactions in robot swarms.

Publisher Correction: Mergeable nervous systems for robots.

The original version of this Article contained an error in the author contributions section, whereby credit for design of the experiments was not attributed to N.M. This error has now been corrected in both the PDF and HTML versions of the Article.

Yield prediction in parallel homogeneous assembly.

We investigate the parallel assembly of two-dimensional, geometrically-closed modular target structures out of homogeneous sets of macroscopic components of varying anisotropy. The yield predicted by a chemical reaction network (CRN)-based model is quantitatively shown to reproduce experimental results over a large set of conditions. Scaling laws for parallel assembling systems are then derived from the model. By extending the validity of the CRN-based modelling, this work prompts analysis and solutions to the incompatible substructure problem.

Mergeable nervous systems for robots.

Robots have the potential to display a higher degree of lifetime morphological adaptation than natural organisms. By adopting a modular approach, robots with different capabilities, shapes, and sizes could, in theory, construct and reconfigure themselves as required. However, current modular robots have only been able to display a limited range of hardwired behaviors because they rely solely on distributed control. Here, we present robots whose bodies and control systems can merge to form entirely new robots that retain full sensorimotor control. Our control paradigm enables robots to exhibit properties that go beyond those of any existing machine or of any biological organism: the robots we present can merge to form larger bodies with a single centralized controller, split into separate bodies with independent controllers, and self-heal by removing or replacing malfunctioning body parts. This work takes us closer to robots that can autonomously change their size, form and function.Robots that can self-assemble into different morphologies are desired to perform tasks that require different physical capabilities. Mathews et al. design robots whose bodies and control systems can merge and split to form new robots that retain full sensorimotor control and act as a single entity.

The k -Unanimity Rule for Self-Organized Decision-Making in Swarms of Robots.

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.

A Design Pattern for Decentralised Decision Making.

The engineering of large-scale decentralised systems requires sound methodologies to guarantee the attainment of the desired macroscopic system-level behaviour given the microscopic individual-level implementation. While a general-purpose methodology is currently out of reach, specific solutions can be given to broad classes of problems by means of well-conceived design patterns. We propose a design pattern for collective decision making grounded on experimental/theoretical studies of the nest-site selection behaviour observed in honeybee swarms (Apis mellifera). The way in which honeybee swarms arrive at consensus is fairly well-understood at the macroscopic level. We provide formal guidelines for the microscopic implementation of collective decisions to quantitatively match the macroscopic predictions. We discuss implementation strategies based on both homogeneous and heterogeneous multiagent systems, and we provide means to deal with spatial and topological factors that have a bearing on the micro-macro link. Finally, we exploit the design pattern in two case studies that showcase the viability of the approach. Besides engineering, such a design pattern can prove useful for a deeper understanding of decision making in natural systems thanks to the inclusion of individual heterogeneities and spatial factors, which are often disregarded in theoretical modelling.

Evolution of Self-Organized Task Specialization in Robot Swarms.

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.

Task partitioning in a robot swarm: object retrieval as a sequence of subtasks with direct object transfer.

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.

Elasticity-based mechanism for the collective motion of self-propelled particles with springlike interactions: a model system for natural and artificial swarms.

We introduce an elasticity-based mechanism that drives active particles to self-organize by cascading self-propulsion energy towards lower-energy modes. We illustrate it on a simple model of self-propelled agents linked by linear springs that reach a collectively rotating or translating state without requiring aligning interactions. We develop an active elastic sheet theory, complementary to the prevailing active fluid theories, and find analytical stability conditions for the ordered state. Given its ubiquity, this mechanism could play a relevant role in various natural and artificial swarms.

Self-organized discrimination of resources.

When selecting a resource to exploit, an insect colony must take into account at least two constraints: the resource must be abundant enough to sustain the whole group, but not too large to limit exploitation costs, and risks of conflicts with other colonies. Following recent results on cockroaches and ants, we introduce here a behavioral mechanism that satisfies these two constraints. Individuals simply modulate their probability to switch to another resource as a function of the local density of conspecifics locally detected. As a result, the individuals gather at the smallest resource that can host the whole group, hence reducing competition and exploitation costs while fulfilling the overall group's needs. Our analysis reveals that the group becomes better at discriminating between similar resources as it grows in size. Also, the discrimination mechanism is flexible and the group readily switches to a better suited resource as it appears in the environment. The collective decision emerges through the self-organization of individuals, that is, in absence of any centralized control. It also requires a minimal individual cognitive investment, making the proposed mechanism likely to occur in other social species and suitable for the development of distributed decision making tools.

Incremental social learning in particle swarms.

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.