GEESE: Grammatical Evolution Algorithm for Evolution of Swarm Behaviors

One of the researcher I admire on Twitter said that with every paper you publish write a blog post about it. People might not read you full paper but there are higher chances that they will read the blog post on it. So this blog post is about my paper “GEESE: Grammatical Evolution Algorithm for Evolution of Swarm Behaviors” which describes about an algorithm to automatically generate collective behaviors for swarms.

Introduction

Social animals like bees, ants, birds, fish, and others are able to perform a complex task like foraging, nest selection, flocking and escaping predictors efficiently without any central control and coordination. Mimicking these behaviors onto robots swarms would be beneficial for understanding social intelligence, collective cognition, and potential applications in engineering, artificial intelligence, and robotics. It requires researchers to spend a lot of time studying the actual behaviors and derive mathematical equations which govern them. This approach is cumbersome to apply for all the animals that exhibit collective behaviors. Instead, we purpose a framework, GEESE, that will generate collective behaviors for swarms of robots through an evolutionary approach. This framework usages grammatical evolution technique to evolve a primitive set of rules into rich individual behaviors. The interaction between individual behaviors gives rise to the collective behaviors in different sets of the environment. We show this framework/algorithm performs great on Santa Fe trail problem and also on Single source foraging problem.

The above figure is the mathematical model for the Best-of-N site selection process employed by honeybees. To establish this model, researcher spent collectively more than 10 years observing honeybees and collecting data. Using those data, they established this model. According to this model, the best-of-N process takes five states: Resting, Observing, Exploring, Accessing and Dancing. In each state, the behaviors of the bees are different. For more details on this model please refer to this paper “Stability of choice in the honey bee nest-site selection process” by Passino et al. The take away point here is that mimicking the behaviors of biological swarms onto robots is time consuming and daunting task. There should be another way to impart the behaviors into robot swarms. The rest of this blog post with talk in detail about one of the method to learn the collective behaviors in robot swarms using evolutionary computing.

Grammatical Evolution

Since this paper deals with variant of Grammatical Evolution (GE), we first need to understand the basic of Grammatical Evolution to understand the impact of this paper. GE is a context-feee grammar-based GP paradigm that is capable of evolving programs or rules in many languages. GE adopts a population of genotypes represented as binary strings, which are transformed into functional phenotype programs through a genotype-to-phenotype transformation. The transformation uses a BNF grammar, which specifies the language of the produced solutions.

BNF Grammar

It is a notation technique to describe the syntax of language. It is represented by four tuples N, T, P and S

N -> Represents the set of all non-terminals
T -> Represents the set of all terminals
P -> Represents the set of productions that map N to T
S -> Initial start symbol

Below is the BNF grammar used for Santa Fe Trail problem.

<code> ::= <code> | <progs>
<progs> ::= <condition> | <prog2> | <prog3> |

<condition> ::= if_food_ahead(<progs>, <progs>)
<prog2>    ::= prog2(<progs>, <progs>)
<prog3>    ::= prog3(<progs>, <progs>, <progs>)
<op>    ::= left | right | move

$a^* = argmax_a \bar{u}(a) = argmax_a \sum_{s} u(s, a)p(s)$

Genome

It is a fixed length sequence of number. It is grouped usually in 4 or 8 called codon. It defines the proceedings of left-derivation of the BNF grammar.

Genome

The figure above represents a genome of length 24 which is grouped into size of 4. Since this genome is represented by binary string, each codon can be converted into decimal value. These values are used in genotype-to-phenotype mapping.

Mapping

Let c be the codon value, A denotes the left-most non-terminal in the derivation (grammar) and r_A denotes the number of right-hand side rules associated with the production of A. Then the rule is

RHSRule = c % r_A

Phenotype

The output from the mapping process is the phenotype. Phenotypes are the actual programs output. It represents a valid expansion of the BNF grammar. If we use the BNF grammar and genotype specified earlier then the phenotype would be if_food_ahead(move, left) from the mapping process. The figure below summaries the process that we discussed so far.

The the above figure we present a simple BNF grammar. The mapping process converts the genotype population to phenotype using the RHSRule specified earlier.

Example

At first, we start with the Start symbol of the BNF grammar which is <code>. The first codon value is 3, the number of right hand side for this first rule is 2. Then using the RHSRule we get 1 from applying 3%2. So we choose last non-terminal symbol <progs>. Similarly, we move to second production rule <progs>. Similarly, following the above table, we finally get the phenotype if_food_ahead(move, left).

GE Pipeline

Above figure represents simple GE work-flow. At first, a random population based on the parameters is initialized. Then for each generation, n best individuals are selected then genetic operators are applied.

GEESE

When the environment is huge, its really hard for single agents to explore and exploit the environment efficiently with a strict time constraint. When multiple agents are distributed in different spatial regions, the search for high-quality solutions can be accelerated if all the agents start in a different spatial location and interact with each other, sharing their knowledge of the search space accumulated so far. Distributed evaluation of fitness and searching different parts of the spatial domain suggest that a mult-agent GE may generate effective solutions. Traditionally, Grammatical Evolution (GE) algorithms are operated in centralized fashion. Though some variants of GE are distributed still they use the centralized population.

GEESE is inspired from “odNEAT”, a distributed and decentralized neuroevolution algorithm for online learning in groups of autonomous robots. Instead of evolving weights and network topology as of “odNEAT”, GEESE evolves executable programs based on the BNF grammar. Each agent has its own unique genetic instance and can run GE operators on its own, GEESE computation can be distributed. This algorithm has three main function: sense, act and update which are executed consecutively. During the sense step, the agents uses the sensors to gather information about the environment. If the sensors detect any neighboring agents, it will communicate with the agents to receive the genome from others. Thus, sense function will use sensor inputs to detect agents and gather genome from nearby agents. In the act step, the will check its memory to look for stored genomes. If the memory is greater than a threshold, then genetic operators like Selection, Crossover and Mutation are applied. During the update step, the current genome is replaced with the geneome with highest fitness value obtained after applying genetic operators if it exists. The overall pipeline for GEESE algorithm is shown in figure below.

Experiments

We compare GEESE with variants of GE on the Santa Fe Trail problem and single source foraging problem. The graph below shows the results of GEESE and GE on Santa Fe trail problem.

Above figure demonstrates that GEESE converges to solution faster than standard GE. The solid line is the mean fitness. The shared region represents one standard deviation across the 50 trails. GEESE required fewer generations with a smaller effective population size to solve the Santa Fe Trail in comparison with Standard GE. The hit rate for GE is just 6% where as the its 57% for GEESE. One of the program evolve from GEESE was able to solve Santa Fe Trail problem in 324 steps which is fewer steps than any other known solution so far. Thus, GEESE outperforms standard GE in the Santa Fe Trail problem.

The above figure shows the performance of three different behaviors in single source foraging problem. The handcoded solution was able to collect 77 units of food where as the behavior evolved using GE was only able to collect 56 units of food. GEESE outperformed both of them by collecting 83 units of food. One of the reason for the GE to perform poorly is to the fact that the evolved program lacked communication behaviors, even though the grammar was capable of expression it.

Aadeshnpn