GEESE: Grammatical Evolution Algorithm for Evolution of Swarm Behaviors

Simple organisms have evolved local interactions among individuals that produce useful collective behaviors: Bacteria interact with each other to move across cell surfaces efficiently by synthesizing a large number of flagella [1]; ant colonies have evolved collective behaviors for foraging, nest defense, path planning and construction [2]; bees are able to select best sites among many good sites at their disposal [8]; and fish are able to avoid predators by organizing themselves in collective shapes that deter predation [4]. Mimicking these collective behaviors in robots swarms would be beneficial for understanding social intelligence, collective cognition, and potential applications in engineering, artificial intelligence, and robotics. The problem of finding a set of individual behaviors to obtain a desired collective behavior is a hard problem. Conventionally, mimicking these behaviors with robots requires researchers to study actual behaviors, derive mathematical models, and implement these models as algorithms. There are different ways to obtain the desired behaviors in swarms such as artificial neural networks, genetic programming based structures, logic-based symbolic controllers and behaviorbased controllers. One approach to identifying individual behaviors that induce desirable collective behavior is to use Grammatical Evolution (GE), a type of Evolutionary Algorithm. GEs [6, 7] work by restricting the search space by "seeding" the solution space using domain-specific knowledge. Thus GEs seek to find solutions to the problems for which Genetic Programming (GP) [5] takes too long. We propose a distributed algorithm, Grammatical Evolution algorithm for Evolution of Swarm bEhaviors (GEESE), which uses grammatical evolution to evolve (a) a primitive set of human-provided rules into (b) productive individual behaviors that (c) exhibit desirable collective behaviors.