Evolutionary Algorithms to Investigate Self-Organising Swarms

Self-organised drone swarms have always been a challenge in swarm robotics. One of the best approaches for achieving collective drone behavior (swarm) is to use evolutionary algorithms. In such algorithm, an agent uses a gene type approach to improve the performance towards a fitness function.

In the real world, applying such algorithm is a quite risky process – especially if the drone swarm is designed automatically and considered as optimisation problem. That is why John Page, Senior Lecturer and Faqihza Mukhlish, PhD Candidate of SAVE Laboratory, University of New South Wales have published a paper named “Simulation: The Only Way To Investigate Self-Organising Swarms” as a way to use selection methods with minimum financial and social risk.

Low-Level Distributed Intelligence as a Method to Control Complex Drone Systems

The idea of low-level distributed intelligence as a method to control complex systems has been used by many researchers over the past couple of years. This idea is mainly inspired by the behavior of social animals while completing tasks such as foraging in colony of ants, flocking birds or schooling fish.

In the field of robotics, an application of a self-organising swarm can be found in search and rescue missions using multiple UAVs which are actually the main topic of the paper. Speaking of, the paper considers search and rescue (SAR) missions as a complex problem that must be tackled despite of many difficulties such as minimum of information and harsh environments. Still, designing a self-organising swarm to tackle SAR mission is a non-trivial risk in both real implementation and self performance analysis.

Simulation is the Only Way One Can Investigate Swarm Strategies Safely

As the authors of the papers concluded, simulation is the only way to investigate swarm strategies safely, especially when solving a problem such as a SAR mission. Developing a new strategy that will use UAVs is not cost-effective. Therefore, the main aim of their paper is to investigate the evolutionary approaches such as breeding techniques and clonal reproduction to control a self-organising swarm in SAR mission through simulation.

Flow diagram of the use of evolutionary
algorithm (Holland, 1975)

One of the most important criteria for success, according to the authors, is the role of breeding age to evolutionary algorithm. Speaking of, breeding age is an interesting aspect of natural evolution because individuals must reach an age of maturity in order to reproduce.

“The individual require time to prove its fitness therefore the amount of time that the individual experienced from birth to sexual maturity is of importance. This initial time allows each individual to prove its fitness is the highest among the group and is then given the opportunity to pass its genetics to next generation. However, to investigate this kind of scenario, it is difficult to observe and get a robust result analytically.”

Flow Diagram of Clonal Reproduction (de Castro and Von Zuben, 2002)

The Simulation and its Results

The simulation in this paper is set to run 10 evolutions, involving 8 UAVs and the age of their maturity varies. Every time the UAVs find the lost victim, they would continue their path for search of the next lost victim. This simulation is set to evolve to find victims which are placed randomly.

As a result of this, some operations of the genetic algorithm produced high performance individuals, but the clonal selection consistently achieved a much higher average fitness. Clonal selection was found to produce swarm with a much lower diversity than the genetic algorithm.

As the authors concluded:

“Simulation plays a significant role to investigating self- organised swarms cheaply and safely. Several evolutionary approaches are detailed in this paper and have demonstrated the importance of simulation. The measurement of the success of this approach is very dependent on high quality simulation as physical testing is not only expensive but also may involve unacceptable risks.”

One of the main weaknesses of the approach, however, was the fact that the efficiency of the system very much depends on the selection of the fitness function – but this does not have to be a constant and can itself evolve.

Citation: Page, John & Mukhlish, Faqihza. (2017). “Simulation The Only Way to Investigate Self-Organising Swarms”. Conference: Australasian Simulation Congress (ASC 2017), At Sydney, Australia, Volume: http://proceedings.simulationaustralasia.com/content/2017/44-paper.pdf