Abstract

Resilience is essential for long-term autonomous agents. Swarm behaviors seen in bees, ants, birds, fish, and others are interesting because they resiliently perform complex coordinated tasks like foraging, nest-selection, flocking and escaping predators without centralized control or coordination. Conventionally, mimicking swarm behaviors with robots requires researchers to study actual behaviors, derive mathematical models, and implement these models as state machines. Since the conventional approach is time-consuming and cumbersome, this dissertation uses a grammatical evolution algorithm with Behavior Trees (BTs) to evolve behaviors that are resilient to different perturbations for foraging and nest maintenance tasks. The modular, reactive, and readable properties of BTs make it an excellent controller for implementing swarm behaviors. Our method is based on the author's master's thesis work on a core algorithm called Grammatical Evolution algorithm for Evolution of Swarm bEhaviors using Behavior Trees (GEESE-BT). The GEESE-BT algorithm can be used to evolve swarm behaviors for interesting multiagent problems, but the solutions require ad hoc fitness functions tailored to the specific problems. This dissertation presents the BeTr-GEESE algorithm, which replaces ad hoc fitness functions with direct feedback from the BT modules. BeTr-GEESE learns more efficiently than GEESE-BT. The modular, subtask-specific programs produced by BeTr-GEESE can be exchanged through lateral transfer to perform missions that require sequential execution of subtasks. Lateral transfer produces resilient performance in divisible and additive group tasks like foraging and nest maintenance. However, the behaviors of successful groups must exhibit temporal locality, meaning that an agent must persist in behavior long enough to perform essential functions but also means that agents cannot persist too long or evolution is too slow. A biologically inspired enhancement of using multiple genes with BeTr-GEESE allowed a fixed population of heterogeneous agents to accomplish tasks with high resilience power and efficiency. The last part of the dissertation complements the empirical approach used in designing resilient swarms using grammatical evolution. Goal specification and verification are vital to designing resilient artificial agents. Finite trace Linear Temporal Logic ($LTL_f$) is a potent way of specifying goals, but synthesizing planners that guarantee the goals are satisfied can be computationally prohibitive. This dissertation shows that goals specified using a subset of finite trace Linear Temporal Logic ($LTL_f$) can be decomposed into an equivalent BT that leads to a relaxed behavior synthesis problem in which a wide range of planners can be used to generate effective behaviors that satisfy the goal specification.

Degree

PhD

College and Department

Physical and Mathematical Sciences; Computer Science

Rights

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

Date Submitted

2023-04-14

Document Type

Dissertation

Handle

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

Keywords

Behavior Trees, Grammatical Evolution, Finite Trace Linear Temporal Logic, Swarm, Goals

Language

english

Download

Share

COinS