Theviyanthan Krishnamohan1*

 

1University of Westminster, London, UK

 

*Correspondence to: Theviyanthan Krishnamohan, Master, Software Engineer, Computer Science and Engineering, University of Westminster, 309 Regent Street, London W1B 2HW, UK; Email: theviyanthan@outlook.com

 

DOI: 10.53964/mit.2023001

 

Abstract

Swarm robotics applies swarm intelligence to robotics to solve real-life problems that cannot be solved by single, monolithic robots. This review first studies swarm robotics in depth and analyzes the different types of tasks carried out by swarms of robots. Then, the consensus-achievement behavior is elaborated on and its relation to the collective perception scenario is reviewed. The collective perception scenario is expounded in detail and the three discreet consensus-achievement strategies, namely the direct modulation of majority-based decision, direct modulation of voter-based decision, and direct comparison are discussed apropos of the collective perception scenario. This review then compares these strategies and explores their shortcoming such as the vulnerability to Byzantine robots.

 

Keywords: swarm robotics, swarm intelligence, collective perception, consensus achievement

 

1 INTRODUCTION

Swarm robotics tries to solve problems that cannot be solved by single, monolithic robots or multi-agent robots by using the principle of swarm intelligence. Swarm intelligence is a discipline that takes inspiration from biological systems found in nature such as bee colonies, bacterial growth, ant colonies, and bird flocking.

 

In swarm intelligence, complex problems are solved through coordination among simple individuals. For example, simple and almost homogenous individual insects in insect societies, which are decentralized and not synchronized, have been shown to be communicating with one another using pheromones to find the best path to a source using a positive feedback mechanism[1].

 

Robots are devices “capable of both mechanical and informational behavior”[2]. Swarm robotics makes use of multiple simple robots to imitate simple individuals found in swarms in nature and can be utilized to solve real-life problems that cannot be easily solved by other means.

 

Consequently, swarm robotics is formally defined as “the study of how large number of relatively simple physically embodied agents can be designed such that a desired collective behavior emerges from the local interactions among agents and between the agents and the environment”[2].

 

Even though there does not exist a consensus in the literature on the characteristic features of swarm robotics, the following characteristics are commonly found in most of the literature[3].

● A large number of members

● Simple members

● Homogeneity

● Decentralization

● Distribution

● Local sensing and communication

 

The many advantages of swarm robotics such as being able to mass-produce robots owing to their simplicity and the reliability that stems from their redundancy mean that this technology can be used for tasks such as those “that cover a region”, “that are dangerous”, “that scale up or down in time”, and “that require redundancy[1,2].

 

Environmental monitoring for oil leakage or nuclear radiation is an example of tasks that cover a region. Tasks that are dangerous are activities like demining minefields and firefighting. Swarm robotics is suitable for such tasks because individual robots cost less by virtue of their simplicity. Besides, the loss of a few robots will not affect the swarm, thereby ensuring reliability[2].

 

Oil leakage from a sunken ship is an excellent example of tasks that scale up or down in time. When swarm robotics is used to contain oil spillage, more robots can be deployed to the swarm if the oil leakage increases. An example of tasks that require redundancy is the use of swarm robotics on battlefields. A swarm of robots will continue to function even if a few robots are hit by bullets and are destroyed[2].

 

Existing reviews on consensus achievement in swarm robotics have studied the resilience of consensus protocols such as Linear Consensus Protocol and Weighted Mean Subsequence Reduced to Byzantine robots and the benefits of using blockchain in swarm robotics[4,5]. However, there is a dearth of reviews on the consensus-achievement strategies in the context of the collective perception scenario and this study attempts to fill this gap.

 

This paper is divided into 9 sections. The first section discusses how swarm engineering is classified, while the second and third sections discuss the consensus achievement problem and the collective perception problem respectively. In the fourth section, the different consensus-achievement strategies are elucidated. The collective-perception experiments are discussed in the fifth section, whereas the limitations of the consensus-achievement strategies are discussed in the sixth section. The challenges associated with Byzantine robots are examined in the seventh section, while the last two sections discuss what the future holds for consensus achievement in swarm robotics and the conclusion that can be drawn from the study.

 

2 CLASSIFICATION OF SWARM ENGINEERING

Winfield et al.[6] define swarm engineering as “a fusion of dependable systems engineering and swarm intelligence”. Brambilla et al.[7] classified swarm engineering based on existing works into two main taxonomies, namely methods and collective behaviors.

 

The methods used to design swarm robotics systems form the basis of the methods taxonomy and, thus, is of little importance to this study. Behaviors of swarms to solve real-world problems are used to form the collective-behaviors taxonomy.

 

Collective behaviors, in turn, are divided into four major groups, namely spatially organizing behaviors, navigation behaviors, collective decision-making behaviors, and other collective behaviors.

 

This study focuses on collective decision-making behaviors. Brambilla et al.[7] defined collective decision-making as “how robots influence each other when making choices”. Thus, collective decision-making is a process by which multiple individuals in a swarm come to an agreement on a decision[7].

 

Brambilla et al.[7] argued that the collective decision-making behavior can be used to perform two different functions, namely consensus achievement, and task allocation. Consensus achievement is the behavior of reaching an agreement on one decision among many others while task allocation is the behavior of robots delegating different tasks among themselves[7].

 

Of these two functions, this study concentrates on the consensus-achievement function. Consensus achievement is paramount in applications of swarm robotics such as detecting radiation leakage and oil spillage and draws inspiration from the behaviors of bees that collectively decide the best nesting or foraging location and insect species such as ants that collectively identify the shortest path with the use of pheromones[8,9].

 

3 CONSENSUS ACHIEVEMENT

Consensus achievement is having a swarm of robots come to an agreement on one choice among several other choices.

 

Valentini et al.[10] further classified the consensus achievement behavior into discrete and continuous consensus achievement. This classification is based upon the “cardinality of the choices available to the swarm”. The consensus achievement problem is discrete if the choices available to a swarm are finite and countable. On the other hand, if the choices available are infinite and measurable, then the consensus achievement problem is said to be continuous.

 

In order to create an abstraction of “the structure and logic of discrete consensus achievement”, Valentini et al.[10] introduced the best-of-n problem in their paper. Simply put, the best-of-n problem is choosing an option i among n number of options so that the quality of i is maximized and the cost of i is minimized. The quality and cost associated with an option are both functions of their environment.

 

Each robot in the swarm picks an option i, where i Î {1, 2, …n}. A collective decision is said to have been made when a large majority of the robots, characterized by m, where m ³ (1 - x)n and 0 £ x £ 0.5, agree on an opinion. Here, x is a threshold value set by the designer of the problem. If x = 0, then it becomes a consensus decision.

 

The authors further introduced taxonomies predicated upon the symmetricity of the quality and cost of the best-of-n problem. If all the options available are of equal quality, the quality is symmetric, which also holds true for cost. If there are options of different quality (or cost), then the quality (or cost) is said to be asymmetric.

 

Based on the symmetric and asymmetric nature of the cost and quality, Valentini et al.[10] (2017) classified the best-of-n problem into symmetric option qualities and costs, symmetric option qualities and asymmetric option costs, asymmetric option qualities and symmetric option costs, asymmetric option qualities and costs: synergic case, and asymmetric option qualities and costs: antagonistic case.

 

4 COLLECTIVE PERCEPTION

Valentini et al.[11], in a subsequent paper, argued that the effectiveness of a collective decision-making strategy can not only be decided by the accuracy of the decision and the time taken to make that decision but it can also be decided by the generality of the strategy. A general strategy will allow engineers to reuse the high-level control logic of the strategy to address varying problems.

 

The authors, in their seminal paper, consequently, introduced a novel decision-making scenario termed as the collective perception problem to test the generality of different decision-making strategies[11].

 

The collective perception problem is a discrete best-of-n problem where a swarm of robots has to come to an agreement on which of the two colors of black and white is most frequently found in the environment. To draw a real-life parallel, the collective perception problem is tantamount to a swarm of robots evaluating “the availability of precious metals”, or “the presence of pollutants or cancer cells” in an environment.

 

In the collective perception scenario, there exists a square area of area 200×200cm2 consisting of a grid that contains cells each of area 10×10cm2. The square area is bounded by walls and can be detected by the robots to avoid collisions.

 

Each cell in the square area is either colored black or white, with each color being an abstraction of a feature in an environment. Thus, the collective perception scenario is a best-of-2 problem since the swarm needs to choose one of the two available options.

 

The quality of the color is determined by its frequency. In the collective perception problem, the authors set black to be the most frequent color. Hence, the swarm is expected to choose black as the best option.

 

E-puck robots are used as the swarm members in this problem. The e-puck robots are equipped with sensors to both avoid collisions and detect the brightness of the floor, which they can then use to determine the color[12].

 

The smaller footprint (a diameter of 7cm) of the robots ensures that the environment is orders of magnitude larger than a single robot. Besides, an e-puck comes equipped with RGB LEDs, an accelerometer, a sound sensor, a low-resolution camera, and 8 proximity sensors. The robot also has three ground sensors that are used to measure the gray-scale values of the surface. Its battery can last up to 45min and the robot has the ability to move at 16cms-1.

 

In the collective perception scenario, the robots start with an initial opinion. The red LED is lit if their opinion is black, and the blue LED is lit if their opinion is white.

 

Since its publishing, this collective perception scenario has been used as a testing ground by subsequent researchers to test different consensus achievement strategies.

 

5 CONSENSUS ACHIEVEMENT STRATEGIES

Valentini et al.[11] used the collective perception scenario to test three different decision-making strategies that they had developed. The three strategies employed a set of common routines to find the best color and differed only in the way they chose the best option. The common routines are discussed in detail below.

 

There are two states in these strategies, namely the exploration state and the dissemination state and these are akin to the waggle dance found in the bee populations[13].

 

In the exploration state, as the name implies, the robots explore their environments by performing random walk and rotations. A robot moves in straight lines for a random time sampled from an exponential distribution with a mean value of 40s. Then, the robot turns for a random time chosen from a uniform distribution, which is between 0s to 4.5s. The direction of rotations is randomly chosen with both clockwise and counterclockwise rotations having an equal probability. Once the rotation is complete, the robots continue their linear motion.

 

If a robot stumbles upon an obstacle, either in the way of another robot or a wall, within approximately 30cm, the robot pauses its motion, and the obstacle avoidance routine is triggered.

 

During the obstacle avoidance routine, a robot utilizes its proximity sensors to detect the distance and bearing of each identified obstacle. It, then, makes use of this information to compute a new direction opposite to the obstacles. Following this, the robot starts its random walk again.

 

During this exploration state, the robots use their ground sensors to measure the quality of their opinion. To measure the quality of their opinion, the robots sample the color of the surface as they perform random walk. The quality pi of an opinion i, where i Î {a, b} (a corresponds to black and b to white), is defined as the fraction of the amount of time the robot perceived the color of its opinion (ti) over the total amount of time the robot spent in the exploration state (t). This is given by Equation (1).

 

 

For instance, if a robot’s opinion is black (opinion a) and it spends 20s in the exploration state, during which it perceives the color black on the floor for 10s, then the quality of its opinion pa is given by Equation (2).

 

 

This perceived quality is the metric based on which the swarm decides the best opinion. The exploration state is followed by the dissemination state. During the dissemination state, a robot engages in random walk, rotation, and obstacle avoidance as it does during the exploration state.

 

However, in addition to these general routines, the robot also broadcasts its opinion to its neighbors. As to what else happens during this state is determined by the decision-making strategy used.

 

5.1 Direct Modulation of Majority-based Decision (DMMD)

When the DMMD strategy is used, a robot remains in the dissemination state for a random amount of time sampled from an exponential distribution with a mean given by the quality of the robot’s opinion pi times a constant g. Here, g is a parameter whose value is decided by the designer. Thus, the higher the quality of opinion pi, the longer the robot remains in the dissemination state. This ensures that a robot with a higher quality opinion gets to broadcast its opinion to a lot of neighbors.

 

In this strategy, pi acts as a modulator, thus, giving this strategy a part of its name, and g acts as an unbiased dissemination time.

 

During the dissemination state, robots broadcast their opinion pi to their neighbors while receiving the opinions of the neighboring robots. Towards the end of the dissemination time, a robot changes its opinion to the opinion of the majority, which includes that of its own, and then switches back to the exploration state[14,15].

 

5.2 Direct Modulation of Voter-based Decision (DMVD)

The DMVD strategy is similar to the DMMD and differs only in its decision-making mechanism. Much like the DMMD strategy, the DMVD strategy also modulates its dissemination time based on the perceived quality of its opinion pi.

 

Nonetheless, when the DMVD strategy is used, robots adopt the opinion of a random neighbor as their own[11].

 

5.3 Direct Comparison (DC)

The DC strategy does not modulate the dissemination time like the DMMD and DMVD strategies. Instead, the dissemination time is a random sample drawn from an exponential distribution with a mean of g.

 

Moreover, the robots not only broadcast their own opinion to their neighbors, but they also broadcast the quality of their own opinion. At the same time, robots compare the quality of their opinion with that of a random neighbor and adopt the greater of the two as their own opinion[11].

 

Consensus is said to have been achieved when all the robots end up having the same opinion (Table 1).

 

Table 1. A Summary of the Consensus-achievement Strategies

 

6 COLLECTIVE PERCEPTION EXPERIMENTS

Valentini et al.[11] compared the three strategies discussed above using the collective perception scenario. In order to analyze the performance of the decision-making strategies, the authors used the exit probability EN and consensus time TN of the strategies.

 

The exit probability is the number of times a strategy resulted in the correct consensus over the total number of times the experiment was run. The consensus time is the average amount of time taken for a correct consensus.

 

The authors adjusted the difficulty of the scenario by adjusting the number of black and white cells. The difficulty pb* of choosing black as the best opinion is given by Equation (3).

 

 

In Equation (3), pa and pb are given by Equation (4) and Equation (5).

 

 

Where na is the number of black cells and nb is the number of white cells on the floor. In other words, the difficulty is the ratio between the percentage of black cells and white cells on the floor.

 

Furthermore, the initial number of robots with opinion a (Ea(0)) was also adjusted to study their impact on the performance, and the size of the swarm was set to 20 robots.

 

The authors used the ARGoS simulator to carry out the experiment[16]. Two difficulty values of 0.515 and 0.923 were used. The experiment was repeated 1000 times for each parameter configuration.

 

Following the experiment, the authors found that the exit probability EN increased with the increase in Ea(0) for all strategies. Besides, the authors also found DMMD to be the least accurate and DC to be the most accurate. In contrast, DMMD was the fastest strategy, and DC was the slowest.

 

In addition, DC was also found to have poor scalability as its consensus time increased much faster than other strategies when the size of the swarm was increased from 20 to 100.

 

7 LIMITATIONS

Even though Valentini’s decision-making strategies performed well in terms of exit probability and consensus time, they failed to account for Byzantine robots. Thus, the performance of these strategies in the presence of Byzantine robots was not studied.

 

The study conducted by Strobel et al.[19] found Valentini’s three strategies to fail to converge on the right opinion in the presence of around 4 or more Byzantine robots[4].

 

8 BYZANTINE ROBOTS

Byzantine robots are robots that lead to the Byzantine generals’ problem. The Byzantine generals’ problem is a situation where consensus needs to be achieved when some of the actors are unreliable[17]. Thus, Byzantine robots can be defined as robots that are either malicious or malfunctioning.

 

This is a critical issue since, as the study by Higgins et al.[18] shows, identity and authentication, and intrusion by foreign robots among others are major security challenges in a swarm robotic environment.

 

Subsequent studies have explored the possibility of using blockchain to mitigate the threat of Byzantine robots. Strobel et al.[19] developed a blockchain smart contract to identify and ignore the opinion of Byzantine robots. However, this solution suffered from the 51% attack problem that is endemic to the Proof-of-Work consensus algorithm used in blockchains. Moreover, the study failed to test the feasibility of using blockchain in swarm robots that are simple and powerless by design.

 

A new blockchain consensus algorithm called Proof of Identity was proposed to address the 51%-attack threat in Strobel’s solution[20]. Pacheco et al.[21] used the proof of authority algorithm to successfully mitigate the 51%-attack threat while demonstrating the feasibility of using blockchain in swarm robots by running experiments using Pi-puck robots.

 

9 FUTURE WORK

Swarm robotics is still in its infancy and the studies on consensus achievement augur well for the future of swarm robotics. The use of blockchain to solve consensus-achievement problems has opened up a new pathway in swarm robotics even though, this new paradigm is not without its drawbacks. For instance, the use of blockchain in consensus achievement involves achieving multiple blockchain consensuses before a swarm consensus can be reached. This calls into question the rationale of using blockchain in swarm robotics. However, since existing studies have already demonstrated the efficacy of blockchain, probably, future studies can explore the possibility of developing a blockchain algorithm that can reduce the number of blockchain consensus needed to reach swarm consensus while retaining the benefits afforded by blockchain to swarm robotics.

 

Moreover, the existing consensus-achievement strategies involve robots broadcasting their opinion only to their neighboring robots. This can be enhanced by using mesh-network protocols such as Zigbee that can be used to broadcast one robot’s opinion to the entire swarm. Besides, the advent of swarm robots such as Pi-puck robots that make use of efficient single-board computers like Raspberry Pi means that even Wi-Fi can be used to develop new faster, and more efficient consensus-achievement strategies.

 

10 CONCLUSION

Swarm robotics uses concepts of swarm intelligence to solve problems. Consensus achievement is one of the major behaviors exhibited by swarms of robots, where a swarm of robots tries to come to a consensus on the best of many choices available. Consensus achievement can be categorized into discrete consensus achievement and continuous consensus achievement based on the cardinality of the choices available. The collective perception scenario was introduced to test consensus-achievement strategies such as DMMD, DMVD, and DC. Even though these strategies solve the collective perception scenario with varying degrees of success, they are all vulnerable to Byzantine robots. Byzantine robots have been shown to be a security issue of concern. Thus, it is imperative that a solution to the vulnerability to Byzantine robots is found in consensus-achievement strategies.

 

Acknowledgements

The author would like to acknowledge Mr. Guhanathan Poravi and Mr. Ragu Sivaraman for the guidance and supervision provided throughout this study.

 

Conflicts of Interest

There is no conflict of interest.

 

Author Contribution

Krishnamohan T confirms sole responsibility for the following: study conception and design, literature review, analysis and interpretation of results, and manuscript preparation.

 

Abbreviation List

DC, Direct comparison

DMMD, Direct modulated majority-based decision

DMVD, Direct modulated voter-based decision

LED, Light emitting diode

RGB, Red green blue

 

References

[1] Beni G. From swarm intelligence to swarm robotics. Lect Notes in Computer Sci, 2005; 3342: 1-9. DOI: 10.1007/978-3-540-30552-1_1

[2] Şahin E. Swarm robotics: From sources of inspiration to domains of application. Lect Notes in Computer Sci, 2005; 3342: 10-20. DOI: 10.1007/978-3-540-30552-1_2

[3] Zakiev A, Tsoy T, Magid E. Swarm Robotics: Remarks on Terminology and Classification. Int Collab Robot, 2018; 11097: 291-298. DOI: 10.1007/978-3-319-99582-3_30

[4] Strobel V, Castelló Ferrer E, Dorigo M. Blockchain Technology Secures Robot Swarms: A Comparison of Consensus Protocols and Their Resilience to Byzantine Robots. Front Robot AI, 2020; 7: 54. DOI: 10.3389/frobt.2020.00054

[5] Du Y, Cao J, Yin J et al. An Overview of Blockchain-Based Swarm Robotics System. Lect Notes Elect Engineer, 2020; 572: 353-360. DOI: 10.1007/978-981-15-0187-6_41

[6] Winfield AFT, Harper CJ, Nembrini J. Towards dependable swarms and a new discipline of swarm engineering. Lect Notes Elect Engineer, 2005; 3342: 126-142. DOI: 10.1007/978-3-540-30552-1_11

[7] Brambilla M, Ferrante E, Birattari M et al. Swarm robotics: A review from the swarm engineering perspective. Swarm Intel, 2013; 7: 1-41. DOI: 10.1007/s11721-012-0075-2

[8] Camazine S, Deneubourg JL, Franks NR et al. Self-Organization in Biological Systems. Princeton University Press: Princeton, USA, 2003.

[9] Couzin ID, Krause J, Franks NR et al. Effective leadership and decision-making in animal groups on the move. Nature, 2005; 433: 513-516. DOI: 10.1038/nature03236

[10] Valentini G, Ferrante E, Dorigo M. The best-of-n problem in robot swarms: Formalization, state of the art, and novel perspectives. Front Robot AI, 2017; 4: 9. DOI: 10.3389/frobt.2017.00009

[11] Valentini G, Brambilla D, Hamann H et al. Collective Perception of Environmental Features in a Robot Swarm: Swarm Intelligence, 10th International Conference, ANTS 2016, Brussels, Belgium, 7-9 September 2016. DOI: 10.1007/978-3-319-44427-7_6

[12] Mondada F, Bonani M, Raemy X et al. The e-puck, a robot designed for education in engineering: Proceedings of the 9th conference on autonomous robot systems and competitions. IPCB, 2009; 1(CONF): 59-65.

[13] Frisch K. The Dance Language and Orientation of Bees. Harvard University Press, Harvard, USA, 1993. DOI: 10.4159/harvard.9780674418776

[14] Valentini G, Hamann H, Dorigo M. Efficient decision-making in a self-organizing robot swarm: On the speed versus accuracy trade-off: Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems. Istanbul, Turkey, 4-8 May 2015.

[15] Valentini G, Ferrante E, Hamann H et al. Collective decision with 100 Kilobots: speed versus accuracy in binary discrimination problems. Auton Agent Multi Agent Syst, 2016; 30: 553-580. DOI: 10.1007/s10458-015-9323-3

[16] Pinciroli C, Trianni V, O’Grady R et al. ARGoS: a modular, parallel, multi-engine simulator for multi-robot systems. Swarm Intell, 2012; 6: 271-295. DOI: 10.1007/S11721-012-0072-5

[17] Lamport L, Shostak R, Pease M. The Byzantine Generals Problem. ACM Transactions on Programming Languages and Systems (TOPLAS), 1981; 4: 382-401. DOI: 10.1145/357172.357176

[18] Higgins F, Tomlinson A, Martin KM. Survey on security challenges for swarm robotics: Proceedings of the 5th International Conference on Autonomic and Autonomous Systems, ICAS, 2009; 307-312. DOI: 10.1109/ICAS.2009.62

[19] Strobel V, Castelló Ferrer E, Dorigo M. Managing Byzantine Robots via Blockchain Technology in a Swarm Robotics Collective Decision Making Scenario. In Proc. of the 17th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2018), Stockholm, Sweden, 10-15 July 2018.

[20] Krishnamohan T. Proof of identity-a blockchain consensus algorithm to create a dynamically permissioned blockchain. Int J Blockchains Cryptocurrencies, 2022; 3: 289-301.

[21] Pacheco A, Strobel V, Dorigo M. A blockchain-controlled physical robot swarm communicating via an ad-hoc network: Swarm Intelligence: 12th International Conference, ANTS 2020, Barcelona, Spain, 26-28 October 2020. Springer International Publishing, Cham, the Netherlands, 2020; 3-15. DOI: 10.1007/978-3-030-60376-2_1

 

Copyright © 2023 The Author(s). This open-access article is licensed under a Creative Commons Attribution 4.0 International License (https://creativecommons.org/licenses/by/4.0), which permits unrestricted use, sharing, adaptation, distribution, and reproduction in any medium, provided the original work is properly cited.