Cooperative navigation in robotic swarms

We study cooperative navigation for robotic swarms in the context of a general event-servicing scenario. In the scenario, one or more events need to be serviced at specific locations by robots with the required skills. We focus on the question of how the swarm can inform its members about events, and guide robots to event locations. We propose a solution based on delay-tolerant wireless communications: by forwarding navigation information between them, robots cooperatively guide each other towards event locations. Such a collaborative approach leverages on the swarm’s intrinsic redundancy, distribution, and mobility. At the same time, the forwarding of navigation messages is the only form of cooperation that is required. This means that the robots are free in terms of their movement and location, and they can be involved in other tasks, unrelated to the navigation of the searching robot. This gives the system a high level of flexibility in terms of application scenarios, and a high degree of robustness with respect to robot failures or unexpected events. We study the algorithm in two different scenarios, both in simulation and on real robots. In the first scenario, a single searching robot needs to find a single target, while all other robots are involved in tasks of their own. In the second scenario, we study collective navigation: all robots of the swarm navigate back and forth between two targets, which is a typical scenario in swarm robotics. We show that in this case, the proposed algorithm gives rise to synergies in robot navigation, and it lets the swarm self-organize into a robust dynamic structure. The emergence of this structure improves navigation efficiency and lets the swarm find shortest paths.     

Energy-efficient indoor search by swarms of simulated flying robots without global information

Swarms of flying robots are a promising alternative to ground-based robots for search in indoor environments with advantages such as increased speed and the ability to fly above obstacles. However, there are numerous problems that must be surmounted including limitations in available sensory and on-board processing capabilities, and low flight endurance. This paper introduces a novel strategy to coordinate a swarm of flying robots for indoor exploration that significantly increases energy efficiency. The presented algorithm is fully distributed and scalable. It relies solely on local sensing and low-bandwidth communication, and does not require absolute positioning, localisation, or explicit world-models. It assumes that flying robots can temporarily attach to the ceiling, or land on the ground for efficient surveillance over extended periods of time. To further reduce energy consumption, the swarm is incrementally deployed by launching one robot at a time. Extensive simulation experiments demonstrate that increasing the time between consecutive robot launches significantly lowers energy consumption by reducing total swarm flight time, while also decreasing collision probability. As a trade-off, however, the search time increases with increased inter-launch periods. These effects are stronger in more complex environments. The proposed localisation-free strategy provides an energy efficient search behaviour adaptable to different environments or timing constraints.     

Parameter Identification of Robot Manipulators: A Heuristic Particle Swarm Search Approach

Parameter identification of robot manipulators is an indispensable pivotal process of achieving accurate dynamic robot models. Since these kinetic models are highly nonlinear, it is not easy to tackle the matter of identifying their parameters. To solve the difficulty effectively, we herewith present an intelligent approach, namely, a heuristic particle swarm optimization (PSO) algorithm, which we call the elitist learning strategy (ELS) and proportional integral derivative (PID) controller hybridized PSO approach (ELPIDSO). A specified PID controller is designed to improve particles’ local and global positions information together with ELS. Parameter identification of robot manipulators is conducted for performance evaluation of our proposed approach. Experimental results clearly indicate the following findings: Compared with standard PSO (SPSO) algorithm, ELPIDSO has improved a lot. It not only enhances the diversity of the swarm, but also features better search effectiveness and efficiency in solving practical optimization problems. Accordingly, ELPIDSO is superior to least squares (LS) method, genetic algorithm (GA), and SPSO algorithm in estimating the parameters of the kinetic models of robot manipulators.     

Designing pheromone communication in swarm robotics: Group foraging behavior mediated by chemical substance

In swarm robotics, communication among the robots is essential. Inspired by biological swarms using pheromones, we propose the use of chemical compounds to realize group foraging behavior in robot swarms. We designed a fully autonomous robot, and then created a swarm using ethanol as the trail pheromone allowing the robots to communicate with one another indirectly via pheromone trails. Our group recruitment and cooperative transport algorithms provide the robots with the required swarm behavior. We conducted both simulations and experiments with real robot swarms, and analyzed the data statistically to investigate any changes caused by pheromone communication in the performance of the swarm in solving foraging recruitment and cooperative transport tasks. The results show that the robots can communicate using pheromone trails, and that the improvement due to pheromone communication may be non-linear, depending on the size of the robot swarm.     

Self-organised path formation in a swarm of robots

In this paper, we study the problem of exploration and navigation in an unknown environment from an evolutionary swarm robotics perspective. In other words, we search for an efficient exploration and navigation strategy for a swarm of robots, which exploits cooperation and self-organisation to cope with the limited abilities of the individual robots. The task faced by the robots consists in the exploration of an unknown environment in order to find a path between two distant target areas. The collective strategy is synthesised through evolutionary robotics techniques, and is based on the emergence of a dynamic structure formed by the robots moving back and forth between the two target areas. Due to this structure, each robot is able to maintain the right heading and to efficiently navigate between the two areas. The evolved behaviour proved to be effective in finding the shortest path, adaptable to new environmental conditions, scalable to larger groups and larger environment size, and robust to individual failures.     

Resolution of the stochastic strategy spatial prisoner's dilemma by means of particle swarm optimization

We study the evolution of cooperation among selfish individuals in the stochastic strategy spatial prisoner's dilemma game. We equip players with the particle swarm optimization technique, and find that it may lead to highly cooperative states even if the temptations to defect are strong. The concept of particle swarm optimization was originally introduced within a simple model of social dynamics that can describe the formation of a swarm, i.e., analogous to a swarm of bees searching for a food source. Essentially, particle swarm optimization foresees changes in the velocity profile of each player, such that the best locations are targeted and eventually occupied. In our case, each player keeps track of the highest payoff attained within a local topological neighborhood and its individual highest payoff. Thus, players make use of their own memory that keeps score of the most profitable strategy in previous actions, as well as use of the knowledge gained by the swarm as a whole, to find the best available strategy for themselves and the society. Following extensive simulations of this setup, we find a significant increase in the level of cooperation for a wide range of parameters, and also a full resolution of the prisoner's dilemma. We also demonstrate extreme efficiency of the optimization algorithm when dealing with environments that strongly favor the proliferation of defection, which in turn suggests that swarming could be an important phenomenon by means of which cooperation can be sustained even under highly unfavorable conditions. We thus present an alternative way of understanding the evolution of cooperative behavior and its ubiquitous presence in nature, and we hope that this study will be inspirational for future efforts aimed in this direction.     

A new particle swarm optimization algorithm for noisy optimization problems

We propose a new particle swarm optimization algorithm for problems where objective functions are subject to zero-mean, independent, and identically distributed stochastic noise. While particle swarm optimization has been successfully applied to solve many complex deterministic nonlinear optimization problems, straightforward applications of particle swarm optimization to noisy optimization problems are subject to failure because the noise in objective function values can lead the algorithm to incorrectly identify positions as the global/personal best positions. Instead of having the entire swarm follow a global best position based on the sample average of objective function values, the proposed new algorithm works with a set of statistically global best positions that include one or more positions with objective function values that are statistically equivalent, which is achieved using a combination of statistical subset selection and clustering analysis. The new PSO algorithm can be seamlessly integrated with adaptive resampling procedures to enhance the capability of PSO to cope with noisy objective functions. Numerical experiments demonstrate that the new algorithm is able to consistently find better solutions than the canonical particle swarm optimization algorithm in the presence of stochastic noise in objective function values with different resampling procedures.     

Particle Swarm Optimization with Scale-Free Interactions

The particle swarm optimization (PSO) algorithm, in which individuals collaborate with their interacted neighbors like bird flocking to search for the optima, has been successfully applied in a wide range of fields pertaining to searching and convergence. Here we employ the scale-free network to represent the inter-individual interactions in the population, named SF-PSO. In contrast to the traditional PSO with fully-connected topology or regular topology, the scale-free topology used in SF-PSO incorporates the diversity of individuals in searching and information dissemination ability, leading to a quite different optimization process. Systematic results with respect to several standard test functions demonstrate that SF-PSO gives rise to a better balance between the convergence speed and the optimum quality, accounting for its much better performance than that of the traditional PSO algorithms. We further explore the dynamical searching process microscopically, finding that the cooperation of hub nodes and non-hub nodes play a crucial role in optimizing the convergence process. Our work may have implications in computational intelligence and complex networks.     

Distributed scalable multi-robot learning using particle swarm optimization

Designing effective behavioral controllers for mobile robots can be difficult and tedious; this process can be circumvented by using online learning techniques which allow robots to generate their own controllers online in an automated fashion. In multi-robot systems, robots operating in parallel can potentially learn at a much faster rate by sharing information amongst themselves. In this work, we use an adapted version of the Particle Swarm Optimization algorithm in order to accomplish distributed online robotic learning in groups of robots with access to only local information. The effectiveness of the learning technique on a benchmark task (generating high-performance obstacle avoidance behavior) is evaluated for robot groups of various sizes, with the maximum group size allowing each robot to individually contain and manage a single PSO particle. To increase the realism of the technique, different PSO neighborhoods based on limitations of real robotic communication are tested and compared in this scenario. We explore the effect of varying communication power for one of these communication-based PSO neighborhoods. To validate the effectiveness of these learning techniques, fully distributed online learning experiments are run using a group of 10 real robots, generating results which support the findings from our simulations.     

Information flow principles for plasticity in foraging robot swarms

An important characteristic of a robot swarm that must operate in the real world is the ability to cope with changeable environments by exhibiting behavioural plasticity at the collective level. For example, a swarm of foraging robots should be able to repeatedly reorganise in order to exploit resource deposits that appear intermittently in different locations throughout their environment. In this paper, we report on simulation experiments with homogeneous foraging robot teams and show that analysing swarm behaviour in terms of information flow can help us to identify whether a particular behavioural strategy is likely to exhibit useful swarm plasticity in response to dynamic environments. While it is beneficial to maximise the rate at which robots share information when they make collective decisions in a static environment, plastic swarm behaviour in changeable environments requires regulated information transfer in order to achieve a balance between the exploitation of existing information and exploration leading to acquisition of new information. We give examples of how information flow analysis can help designers to decide on robot control strategies with relevance to a number of applications explored in the swarm robotics literature.     

Theoretical study on the structure and stability of [1,2,5] oxadiazolo [3,4-e] [1,2,3,4]-tetrazine-4,6-Di-N-dioxide (FTDO)

In protein–ligand docking, an optimization algorithm is used to find the best binding pose of a ligand against a protein target. This algorithm plays a vital role in determining the docking accuracy. To evaluate the relative performance of different optimization algorithms and provide guidance for real applications, we performed a comparative study on six efficient optimization algorithms, containing two evolutionary algorithm (EA)-based optimizers (LGA, DockDE) and four particle swarm optimization (PSO)-based optimizers (SODock, varCPSO, varCPSO-ls, FIPSDock), which were implemented into the protein–ligand docking program AutoDock. We unified the objective functions by applying the same scoring function, and built a new fitness accuracy as the evaluation criterion that incorporates optimization accuracy, robustness, and efficiency. The varCPSO and varCPSO-ls algorithms show high efficiency with fast convergence speed. However, their accuracy is not optimal, as they cannot reach very low energies. SODock has the highest accuracy and robustness. In addition, SODock shows good performance in efficiency when optimizing drug-like ligands with less than ten rotatable bonds. FIPSDock shows excellent robustness and is close to SODock in accuracy and efficiency. In general, the four PSO-based algorithms show superior performance than the two EA-based algorithms, especially for highly flexible ligands. Our method can be regarded as a reference for the validation of new optimization algorithms in protein–ligand docking.     

Accelerated Simplified Swarm Optimization with Exploitation Search Scheme for Data Clustering

Data clustering is commonly employed in many disciplines. The aim of clustering is to partition a set of data into clusters, in which objects within the same cluster are similar and dissimilar to other objects that belong to different clusters. Over the past decade, the evolutionary algorithm has been commonly used to solve clustering problems. This study presents a novel algorithm based on simplified swarm optimization, an emerging population-based stochastic optimization approach with the advantages of simplicity, efficiency, and flexibility. This approach combines variable vibrating search (VVS) and rapid centralized strategy (RCS) in dealing with clustering problem. VVS is an exploitation search scheme that can refine the quality of solutions by searching the extreme points nearby the global best position. RCS is developed to accelerate the convergence rate of the algorithm by using the arithmetic average. To empirically evaluate the performance of the proposed algorithm, experiments are examined using 12 benchmark datasets, and corresponding results are compared with recent works. Results of statistical analysis indicate that the proposed algorithm is competitive in terms of the quality of solutions.     

Particle swarm optimizer for weighting factor selection in intensity-modulated radiation therapy optimization algorithms

In inverse treatment planning of intensity-modulated radiation therapy (IMRT), the objective function is typically the sum of the weighted sub-scores, where the weights indicate the importance of the sub-scores. To obtain a high-quality treatment plan, the planner manually adjusts the objective weights using a trial-and-error procedure until an acceptable plan is reached. In this work, a new particle swarm optimization (PSO) method which can adjust the weighting factors automatically was investigated to overcome the requirement of manual adjustment, thereby reducing the workload of the human planner and contributing to the development of a fully automated planning process. The proposed optimization method consists of three steps. (i) First, a swarm of weighting factors (i.e., particles) is initialized randomly in the search space, where each particle corresponds to a global objective function. (ii) Then, a plan optimization solver is employed to obtain the optimal solution for each particle, and the values of the evaluation functions used to determine the particle’s location and the population global location for the PSO are calculated based on these results. (iii) Next, the weighting factors are updated based on the particle’s location and the population global location. Step (ii) is performed alternately with step (iii) until the termination condition is reached. In this method, the evaluation function is a combination of several key points on the dose volume histograms. Furthermore, a perturbation strategy – the crossover and mutation operator hybrid approach – is employed to enhance the population diversity, and two arguments are applied to the evaluation function to improve the flexibility of the algorithm. In this study, the proposed method was used to develop IMRT treatment plans involving five unequally spaced 6 MV photon beams for 10 prostate cancer cases. The proposed optimization algorithm yielded high-quality plans for all of the cases, without human planner intervention. A comparison of the results with the optimized solution obtained using a similar optimization model but with human planner intervention revealed that the proposed algorithm produced optimized plans superior to that developed using the manual plan. The proposed algorithm can generate admissible solutions within reasonable computational times and can be used to develop fully automated IMRT treatment planning methods, thus reducing human planners’ workloads during iterative processes.     

基于改进PSO的洞庭湖水源涵养林空间优化模型

以结构化森林经营思想为理论基础,从与水源林涵养水源、保持水土功能密切相关的林分物种组成(树种混交)、种内及种间竞争、空间分布格局、垂直结构4个方面选择混交度、竞争指数、角尺度、林层指数、空间密度指数、开阔比数作为水源林健康经营和林分空间结构优化的目标函数,建立洞庭湖水源林林分多目标空间优化模型,应用改进的群智能粒子群算法求解林分空间结构优化模型,并针对模型输出的目标树空间结构单元制定周密的经营策略.研究结果表明,优化模型能准确定位林分空间关系的薄弱环节,调控措施能显著改善林分空间结构,有利于促进森林生态系统的正向演替,为恢复洞庭湖水源林生态功能和健康经营提供理论依据和技术支撑.应用优化模型进行水源涵养林健康经营突破了传统森林经营模式,为智能信息技术在森林空间经营中的应用提供了新的思路.     

Searching for structural bias in particle swarm optimization and differential evolution algorithms

During the last two decades, a large number of metaheuristics have been proposed, leading to various studies that call for a deeper insight into the behaviour, efficiency and effectiveness of such methods. Among numerous concerns that are briefly reviewed in this paper, the presence of a structural bias (i.e. the tendency, not justified by the fitness landscape, to visit some regions of the search space more frequently than other regions) has recently been detected in simple versions of the genetic algorithm and particle swarm optimization. As of today, it remains unclear how frequently such a behaviour occurs in population-based swarm intelligence and evolutionary computation methods, and to what extent structural bias affects their performance. The present study focuses on the search for structural bias in various variants of particle swarm optimization and differential evolution algorithms, as well as in the traditional direct search methods proposed by Nelder–Mead and Rosenbrock half a century ago. We found that these historical direct search methods are structurally unbiased. However, most tested new metaheuristics are structurally biased, and at least some presence of structural bias can be observed in almost all their variants. The presence of structural bias seems to be stronger in particle swarm optimization algorithms than in differential evolution algorithms. The relationships between the strength of the structural bias and the dimensionality of the search space, the number of allowed function calls and the population size are complex and hard to generalize. For 14 algorithms tested on the CEC2011 real-world problems and the CEC2014 artificial benchmarks, no clear relationship between the strength of the structural bias and the performance of the algorithm was found. However, at least for artificial benchmarks, such old and structurally unbiased methods like Nelder–Mead algorithm performed relatively well. This is a warning that the presence of structural bias in novel metaheuristics may hamper their search abilities.     

Swarm cognition on off-road autonomous robots

This paper contributes with the first validation of swarm cognition as a useful framework for the design of autonomous robots controllers. The proposed model is built upon the authors’ previous work validated on a simulated robot performing local navigation on a 2-D deterministic world. Based on the ant foraging metaphor and motivated by the multiple covert attention hypothesis, the model consists of a set of simple virtual agents inhabiting the robot’s visual input, searching in a collectively coordinated way for obstacles. Parsimonious and accurate visual attention, operating on a by-need basis, is attained by making the activity of these agents modulated by the robot’s action selection process. A by-product of the system is the maintenance of active, parallel and sparse spatial working memories. In short, the model exhibits the self-organisation of a relevant set of features composing a cognitive system. To show its robustness, the model is extended in this paper to handle the challenges of physical off-road robots equipped with noisy stereoscopic vision sensors. Furthermore, an extensive aggregate of biological arguments sustaining the model is provided. Experimental results show the ability of the model to robustly control the robot on a local navigation task, with less than 1% of the robot’s visual input being analysed. Hence, with this system the computational cost of perception is considerably reduced, thus fostering robot miniaturisation and energetic efficiency. This confirms the advantages of using a swarm-based system, operating in an intricate way with action selection, to judiciously control visual attention and maintain sparse spatial memories, constituting a basic form of swarm cognition.     

Self-organized flocking in mobile robot swarms

In this paper, we study self-organized flocking in a swarm of mobile robots. We present Kobot, a mobile robot platform developed specifically for swarm robotic studies. We describe its infrared-based short range sensing system, capable of measuring the distance from obstacles and detecting kin robots, and a novel sensing system called the virtual heading system (VHS) which uses a digital compass and a wireless communication module for sensing the relative headings of neighboring robots. We propose a behavior based on heading alignment and proximal control that is capable of generating self-organized flocking in a swarm of Kobots. By self-organized flocking we mean that a swarm of mobile robots, initially connected via proximal sensing, is able to wander in an environment by moving as a coherent group in open space and to avoid obstacles as if it were a “super-organism”. We propose a number of metrics to evaluate the quality of flocking. We use a default set of behavioral parameter values that can generate acceptable flocking in robots, and analyze the sensitivity of the flocking behavior against changes in each of the parameters using the metrics that were proposed. We show that the proposed behavior can generate flocking in a small group of physical robots in a closed arena as well as in a swarm of 1000 simulated robots in open space. We vary the three main characteristics of the VHS, namely: (1) the amount and nature of noise in the measurement of heading, (2) the number of VHS neighbors, and (3) the range of wireless communication. Our experiments show that the range of communication is the main factor that determines the maximum number of robots that can flock together and that the behavior is highly robust against the other two VHS characteristics. We conclude by discussing this result in the light of related theoretical studies in statistical physics.     

A novel harmony search-K means hybrid algorithm for clustering gene expression data

Recent progress in bioinformatics research has led to the accumulation of huge quantities of biological data at various data sources. The DNA microarray technology makes it possible to simultaneously analyze large number of genes across different samples. Clustering of microarray data can reveal the hidden gene expression patterns from large quantities of expression data that in turn offers tremendous possibilities in functional genomics, comparative genomics, disease diagnosis and drug development. The k- ¬means clustering algorithm is widely used for many practical applications. But the original k-¬means algorithm has several drawbacks. It is computationally expensive and generates locally optimal solutions based on the random choice of the initial centroids. Several methods have been proposed in the literature for improving the performance of the k-¬means algorithm. A meta-heuristic optimization algorithm named harmony search helps find out near-global optimal solutions by searching the entire solution space. Low clustering accuracy of the existing algorithms limits their use in many crucial applications of life sciences. In this paper we propose a novel Harmony Search-K means Hybrid (HSKH) algorithm for clustering the gene expression data. Experimental results show that the proposed algorithm produces clusters with better accuracy in comparison with the existing algorithms.     

Optimal Gait for Bioinspired Climbing Robots Using Dry Adhesion:A Quasi-Static Investigation

Legged robots relying on dry adhesives for vertical climbing are required to preload their feet against the wall to increase contact surface area and consequently maximize adhesion force. Preloading a foot causes a redistribution of forces in the entire robot, including contact forces between the other feet and the wall. An inappropriate redistribution of these forces can cause irreparable detachment of the robot from the vertical surface. This paper investigates an optimal preloading and detaching strategy that minimizes energy consumption, while retaining safety, during locomotion on vertical surfaces. The gait of a six-legged robot is planned using a quasi-static model that takes into account both the structure of the robot and the characteristics of the adhesive material. The latter was modelled from experimental data collected for this paper. A constrained optimization routine is used, and its output is a sequence of optimal posture and motor torque set-points.