Abstract

Animals such as bees, ants, birds, fish, and others are able to efficiently perform complex coordinated tasks like foraging, nest-selection, flocking and escaping predators without centralized control or coordination. These complex collective behaviors are the result of emergence. Conventionally, mimicking these collective behaviors with robots requires researchers to study actual behaviors, derive mathematical models, and implement these models as algorithms. Since the conventional approach is very time consuming and cumbersome, this thesis uses an emergence-based method for the efficient evolution of collective behaviors. Our method, Grammatical Evolution algorithm for Evolution of Swarm bEhaviors (GEESE), is based on Grammatical Evolution (GE) and extends the literature on using genetic methods to generate collective behaviors for robot swarms. GEESE uses GE to evolve a primitive set of human-provided rules, represented in a BNF grammar, into productive individual behaviors represented by Behavior Tree (BT). We show that GEESE is generic enough, given an initial grammar, that it can be applied to evolve collective behaviors for multiple problems with just a minor change in objective function. Our method is validated as follows: First, GEESE is compared with state-of-the-art genetic algorithms on the canonical Santa Fe Trail problem. Results show that GEESE outperforms the state-of-the-art by a)~providing better solutions given sufficient population size while b)~utilizing fewer evolutionary steps. Second, GEESE is used to evolve collective swarm behavior for a foraging task. Results show that the evolved foraging behavior using GEESE outperformed both hand-coded solutions as well as solutions generated by conventional Grammatical Evolution. Third, the behaviors evolved for single-source foraging task were able to perform well in a multiple-source foraging task, indicating a type of robustness. Finally, with a minor change to the objective function, the same BNF grammar used for foraging can be shown to evolve solutions to the nest-maintenance and the cooperative transport tasks.

Degree

MS

College and Department

Physical and Mathematical Sciences; Computer Science

Rights

http://lib.byu.edu/about/copyright/

Date Submitted

2019-02-01

Document Type

Thesis

Handle

http://hdl.lib.byu.edu/1877/etd10561

Keywords

Swarms, Grammatical Evolution, Behavior Trees, Hub-based Colonies

Language

english

Download

Share

COinS