Make robots be bats: specializing robotic swarms to the Bat algorithm
Introduction
For many years, the concept of intelligence was generally perceived to be an exclusive attribute of highly sophisticated individuals. Not surprisingly, this was also the approach taken in the early days of the artificial intelligence field. However, nature provides several examples of groups of animals that exhibit a more sophisticated social behavior than what would be possible through the simple aggregation of individual behavioral patterns. As a result, the social group is able to carry out complex tasks that their individual members cannot intend for. Take, for instance, the colonies of social insects (ants, termites, bees, fireflies), and other animal formations (fish schooling, bird flocking, animal herding, and so on). They come up with astonishingly complex social behaviors from the combined efforts of individuals with extremely limited intelligence. Amazingly, this complex collective behavior emerges from a small set of simple behavioral rules exploiting only low-level interactions between individuals and with the environment (stigmergy) using decentralized control and self-organization.
In this context, one of the most exciting breakthroughs in artificial intelligence during the last decades is the adoption and subsequent popularization of this collective intelligence arising from a collection of simple, unsophisticated, and generally homogeneous agents collaborating together to solve a complex problem. This field, globally known as swarm intelligence [5,6], is overcoming the traditional mathematical approaches for solving optimization problems and laying the foundations for a new computational paradigm: the swarm computation [13,27]. Under this new paradigm, there is no centralized intelligence controlling the swarm, taking decisions, and dictating how the swarm units should behave. Instead, local and (at some extent) random interactions between simple agents lead to the emergence of global sophisticated “intelligent” behaviors, unknown to the individual agents.
Nowadays, swarm intelligence is attracting increasing attention from researchers and practitioners owing to its potential applications to many problems. For instance, military and civil applications related to the control of unmanned vehicles have been described in Refs. [45,46,54]. Many other applications can also been found in the scientific literature; see Refs. [5,19,63] for several illustrative examples in different fields. The interested reader is also referred to [13,27] for a comprehensive overview about the field of swarm intelligence, its history, main techniques, and applications.
One of most relevant applications of swarm intelligence is robotics. Several scientific papers and research projects have shown that self-organizing swarm robots can potentially accomplish complex tasks and thus replace sophisticated and expensive robots by simple inexpensive drones, a research subfield usually referred to as swarm robotics [3,14,64]. The reader is kindly referred to [56] for some illustrative early examples and applications of swarm robotics; see also [50] for a more updated survey on recent advances in the field. As remarked by several authors [1,6], swarm robotic systems offer several interesting advantages, such as:
- •
Improved performance by parallelization: swarm intelligence systems are very well suited for parallelization, because the swarm members can perform different actions at different locations simultaneously. This feature makes the swarm more flexible and efficient for complex tasks, as individual robots (or groups of them) can solve different parts of a complex task independently.
- •
Task enablement: groups of robots can do certain tasks that are impossible or very difficult for a single robot (e.g., collective transport of too heavy items, dynamic target tracking, cooperative environment monitoring, autonomous surveillance of large areas).
- •
Scalability: inclusion of new robots into a swarm does not require reprogramming the whole swarm. Furthermore, because interactions between robots involve only neighboring individuals, the total number of interactions within the system does not increase dramatically by adding new units.
- •
Distributed sensing and action: a swarm of simple interconnected mobile robots deployed throughout a large search space possesses greater exploratory capacity and a wider range of sensing than a sophisticated robot. This makes the swarm much more effective in several tasks: exploration and navigation (e.g., in disaster rescue missions), nanorobotics-based manufacturing, microbotics for human body diagnosis, and many others.
- •
Fault tolerance: due to the decentralized and self-organized nature of the swarm, the failure of a single unit does not affect the completion of the given task.
All these advantages motivated a great interest in swarm robotics during the last two decades. The reader is kindly referred to Section 2 for further details on this issue.
Most of swarm intelligence methods are computational metaphors based on the dynamics of natural groups. A classical example is the ant colony optimization (ACO) method, based on the behavior of colonies of ants, which are able to carry out difficult tasks unattainable for individual ants [10,11]. Another example is the behavior of a flock of birds when moving all together following a common tendency in their displacements, an inspiration to the particle swarm optimization (PSO) method [12,25]. Other examples include popular optimization methods such as artificial bee colony, firefly algorithm, cuckoo search, and bat algorithm. These and many other examples lead to a valuable set of computational intelligence techniques known as nature-inspired metaheuristic methods. The reader is referred to [57] for a gentle introduction to several recent nature-inspired metaheuristic methods; see also [62,63].
Among them, the bat algorithm is an increasingly popular swarm intelligence algorithm originally proposed by Prof. Xin-She Yang in 2010 [58,60]. The algorithm is based on the peculiar behavior of microbats (see Section 3 for details). In our experience, the bat algorithm has shown to be a very effective method to solve complex multimodal nonlinear continuous optimization problems involving a large number of variables, such as data fitting through free-form parametric curves [20,21,23] and surfaces [22], and multi-objective problems [59]. On the other hand, the fundamental principle of the bat algorithm (namely, the echolocation through ultrasounds) along with some of its most important features and parameters (operating frequency, operating time, number of cycles per bust, accuracy range, traveling range of pulses, and so on) can readily be reproduced with current hardware (see Section 4 for details). This makes the bat algorithm an excellent method for potential applications in swarm robotics. Furthermore, some recent papers have reported successful applications of the bat algorithm to some problems in robotics [15,16]. However, these works are mostly focused on the problem of parameter tuning of PI-controllers for optimal positioning of robotic arms for safety and functionality, and have no direct relationship with the area of swarm robotics. Clearly, the application of bat algorithm to swarm robotics is a very promising yet unexplored field. In this paper we are aimed at filling this gap. Consequently, this is the algorithm used in this paper.
Despite of its remarkable features, to the best of our knowledge, the bat algorithm has never been applied so far in the context of swarm robotics. Aimed at filling this gap, a previous paper in Ref. [49] presented some initial ideas about the application of the bat algorithm to swarm robotics. However, that paper was based on very preliminary work and strongly affected by limitations of space. This paper is a substantial extension in several ways. The main contributions of this paper are:
- 1.
First and utmost contribution of this work is the first practical implementation of the bat algorithm for swarm robotics. To the best of our knowledge, no previous application of the bat algorithm to swarm robotics has been reported so far in the literature.
- 2.
Our implementation is performed at two levels: we introduce both a physical robotic prototype (described in Section 4.1) and a computational robotic simulation framework (described in Section 4.2).
- 3.
A key differential factor of our approach is its high specialization. The general trend in swarm robotics is to create flexible drones able to support several algorithms with just minor (if any) modifications. Although this approach can be useful for comparative purposes among algorithms, it also yields biased comparisons since the design and components are not optimally chosen for each particular algorithm under analysis. Opposed to previous approaches in the field, our implementation has been carefully designed to replicate faithfully almost all features of the real bats and the bat algorithm (see Section 4.3 for details). In other words, all our (physical and logical) components are fully optimized to follow the bat algorithm principles as accurate as possible.
- 4.
Our implementation has been applied to the problem of finding a target location within unknown static indoor 3D environments. To this aim, three different computational scenes have been considered. The first one has been recreated from the real-world storage room where we perform our experiments with the real robotic swarm.
- 5.
Our experiments show that the behavioral patterns observed in both the real and the simulated robotic swarms are very similar. Except for small deviations due to the typical noise in real-world conditions, the behavior and evolution of the robotic swarms at the physical and computational levels match each other fairly accurately.
This paper is organized as follows: previous work in the field of swarm robotics is briefly reported in Section 2. In Section 3 we provide the reader with a gentle overview about the bat algorithm and its main rules and features. We also describe the algorithm through its pseudocode. In Section 4 we describe the main features of our implementation of the bat algorithm for swarm robotics in terms of hardware and software. The analogies and differences among the real bats, the bat algorithm, and our physical and computational swarm robotics implementation are also discussed in that section. Some computational and real-world experiments about finding a target location with our robotic swarm are reported in detail in Section 5. The issue of comparison of our approach with other alternative methods in the literature is discussed in Section 6. The paper closes with the main conclusions and some hints about our future work in the field.
Section snippets
Previous work
In this section, some previous work on swarm robotics is briefly reported. Our contribution spans both the physical and logical levels, so we organize our description on previous work accordingly, with Sections 2.1 Robotic platforms, 2.2 Robotic simulation frameworks devoted to the robotic platforms (physical level) and the robotic simulation frameworks (logical level), respectively.
The Bat algorithm
The bat algorithm is a bio-inspired swarm intelligence algorithm originally proposed by Xin-She Yang in 2010 to solve optimization problems [58,60]. The algorithm is based on the echolocation behavior of bats. The author focused particularly on microbats, as they use a type of sonar called echolocation, with varying pulse rates of emission and loudness, to detect prey, avoid obstacles, and locate their roosting crevices in the dark. In this paper we also adhere to this approach, so (unless
Bat algorithm-based implementation for swarm robotics
In this section we report our implementation of the bat algorithm described above for swarm robotics by using a swarm of simple and identical robotic units. This implementation is performed at two levels: the robotic platform (physical level) and the robotic simulation framework (computational level). They are described in Sections 4.1 Robotic platform for Bat algorithm, 4.2 Robotic simulation framework for Bat algorithm, respectively.
Computational and real-world experiments
As described above, the major goal of this paper is to design and build a robotic swarm replicating the real bats and the bat algorithm as faithfully as possible. Once built, our robotic swarm is applied to some experiments about the problem of finding a target location, where the objective is to reach an unknown target location within an unknown static 3D indoor scene. This section is devoted to describe these computational and real-world experiments. The discussion starts with the description
Comparison with other alternative approaches
It is a common practice in swarm robotics to carry out comparative analysis about the performance of a robotic swarm implementation for different swarm intelligence methods. But while this question makes full sense for general-purpose robotic units, it does not apply to the implementation introduced in this paper. Since our robotic units are specifically designed for the bat algorithm, we cannot expect a good performance for any other swarm intelligence method. The real comparison should be
Conclusions and future work
In this paper we introduced the first practical implementation of the bat algorithm for swarm robotics. Our implementation is performed at two different and complementary levels: a physical real-world level, where we design and build a real robotic prototype; and a computational level, where we develop a robotic simulation framework for the bat algorithm in swarm robotics. A very important feature of our implementation is its high specialization at both levels. Our implementation has been
Accompanying material
In addition to this paper, the reader is kindly invited to take a look at the six videos submitted with this work. The videos, in MPEG-4 format, can be reproduced with popular media players such as VLC, QuickTime, KMP, and many others.
Acknowledgments
This research has been kindly supported by the Computer Science National Program of the Spanish Research Agency (Agencia Estatal de Investigación) and European Funds, Project #TIN2017-89275-R (AEI/FEDER, UE), the project EVOLFORMAS Ref. #JU12, jointly supported by public body SODERCAN of the Regional Government of Cantabria and the European funds FEDER, the project PDE-GIR of the European Union's Horizon 2020 research and innovation programme under the Marie Sklodowska-Curie Actions grant
References (64)
- et al.
Kilobot: a low cost robot with scalable operations designed for collective behaviors
Robot. Auton. Syst.
(2014) - et al.
Research advance in swarm robotics
Def. Technol. J.
(2013) - et al.
Micromanipulation, communication and swarm intelligence issues in a swarm microrobotic platform
Robot. Auton. Syst.
(2006) Behavior-based Robotics
(1998)- et al.
Development of a miniature robot for swarm robotic application
Int. J. Comput. Electr. Eng.
(2009) - et al.
Development of an autonomous micro robot for swarm robotics
- et al.
Colias-Φ: an autonomous micro robot for artificial pheromone communication
Int. J. Mech. Eng. Robot. Res.
(2015) - et al.
Swarm Intelligence: from Natural to Artificial Systems
(1999) - et al.
The autonomous micro robot ”Alice”: a platform for scientific and commercial applications
Fascination of down scaling - Alice the sugar cube robot
J. Micro Mechatron.
Mobile micro-robots ready to use: Alice
Optimization, Learning and Natural Algorithms
Ant colony system: a cooperative learning approach to the traveling salesman problem
IEEE Trans. Evol. Comput.
Particle swarm optimization: developments, applications and resources
Fundamentals of Computational Swarm Intelligence
Low-cost embedded system for relative localization in robotic swarms
Parameter tuning of PI-controller with bat algorithm
Informatica
Parameter tuning of PID controller with reactive nature-inspired algorithms
Robot. Auton. Syst.
The embodiment of cockroach aggregation behavior in a group of micro-robots
Artif. Life
The player/stage project: tools for multirobot and distributed sensor systems
Swarm Intelligence, Principles, Advances, and Applications
Bat algorithm for curve parameterization in data fitting with polynomial Bézier curves
Global-support rational curve method for data approximation with bat algorithm
Iterative sequential bat algorithm for free-form rational Bezier surface reconstruction
Int. J. Bio-Inspired Comput.
Multilayer embedded bat algorithm for B-spline curve reconstruction
Integrated Comput. Aided Eng.
Microsoft robotics studio: a technical introduction
IEEE Robot. Autom. Mag.
Particle swarm optimization
Re-embodiment of honeybee aggregation behavior in an artificial micro-robotic system
Adapt. Behav.
Swarm Intelligence
Causes and consequences of sociality in bats
Bioscience
Stupid Robot Tricks: a Behavior-based Distributed Algorithm Library for Programming Swarms of Robots
Cited by (58)
Optimizing SNR for indoor visible light communication by using TLBO algorithm
2024, Ad Hoc NetworksModeling and designing a robotic swarm: A quantum computing approach
2023, Swarm and Evolutionary ComputationSurveillance task optimized by Evolutionary shared Tabu Inverted Ant Cellular Automata Model for swarm robotics navigation control
2022, Results in Control and OptimizationCitation Excerpt :Swarm robotics is a multi-agent system coordination and control approach, where each agent is considered a physically simple robot [1]. From the cooperation and system stigmergy, a collective behavior can emerge from the interaction between robots and the environment [2,3]. This approach has been widely investigated by several researchers [4–7] due to the parallelism and multi-objective [8] that can occur in this system in relation to the traditional robotics usage [9], where a single robot can perform tasks sequentially [10,11].
A swarm intelligence-based robotic search algorithm integrated with game theory
2022, Applied Soft ComputingCitation Excerpt :That way, the robots never get stuck in local optimal areas and dead-ends. The value of this fitness function is calculated with the help of advanced Unity game engine routing algorithms [17]. This algorithm has also been studied in two other research [19,20], in which several robotic swarms have non-cooperatively searched for multiple targets.
Swarm intelligence based robotic search in unknown maze-like environments
2021, Expert Systems with ApplicationsCitation Excerpt :The problem of single target robotic search is also studied using swarm intelligence algorithms, such as PSO (Hereford, Siebold, & Nichols, 2007; Couceiro, Rocha, Ferreira, & Vargas, 2013; Dadgar, Couceiro, & Hamzeh, 2019; Yang, Wang, & Bauer, 2019) and Bat Optimization algorithm (BOA) (Suárez et al., 2018; Suárez et al., 2018). In 2019, Suárez, Iglesias, and Gálvez (2019) studied the problem of single target swarm robotic search in an extremely complex unknown environment. Their research innovation is to use the Bat optimization algorithm, invented by Yang in 2010 (Yang, 2010), for swarm robotic search.
Multi-objective optimization of a quadrotor flock performing target zone search
2021, Swarm and Evolutionary Computation