Exploring Behavior Discovery Methods for Heterogeneous Swarms of
Limited-Capability Robots
Connor Mattson, Jeremy C. Clark, and Daniel S. Brown
Kahlert School of Computing, University of Utah
Abstract
We study the problem of determining the emergent behaviors that are possible given a heterogeneous swarm of robots with limited capabilities. Prior work has considered behavior search for homogeneous swarms and proposed the use of novelty search over either a hand-specified or learned behavior space followed by clustering to return a taxonomy of emergent behaviors to the user. In this paper we seek to better understand the role of novelty search and the efficacy of using clustering to discover novel emergent behaviors. Through a large set of experiments and ablations, we analyze the effect of representations, evolutionary search, and clustering in the search for novel behaviors in a heterogeneous swarm. Our results indicate that clustering methods fail to discover many interesting behaviors and that an iterative human-in-the-loop discovery process finds the largest number of emergent behaviors. In the process of our experiments we discover 23 emergent behaviors. To the best of our knowledge, these are the first known emergent behaviors for heterogeneous swarms of computation-free agents.
Discovered Behaviors
Nested Cycles
Eye
Flower
Spiral
Nucleus
Flail
Containment
Dipole
Snake
Hurricane
Geometric Warp
Perimeter
Milling + Disp.
Aggregation + Disp.
Cyclic + Disp
Segments
Site Traversal
Mill-Followers
Aggregation
Dispersal
Cyclic Pursuit
Wall-Following
Milling
Results
This paper considers the behavior discovery problem where, given a robot's capability model, the complete set of emergent swarm behaviors can be efficiently discovered. We provide an analysis of prior swarm behavior discovery methods applied to heterogeneous swarms of limited-capability robots and find that a human-in-the-loop novelty search approach outperforms random search, fully-automatic behavior discovery, and Swarm Chemistry by 38.8%, 91.4%, and 28.15%, respectively. We show that local interactions between heterogeneous robot types can lead to 23 distinct behavioral patterns, 18 of which are novel discoveries for robots of the computation-free capability model.
Our results highlight the diminishing effectiveness of combining novelty search and clustering together as the dimensionality of the search space and rarity of interesting behaviors increases. We hypothesize that this is because novelty search will continue to pursue areas of the behavior space that produce random behaviors that, while uninteresting and/or incoherent to a human, appear distinct in terms of representation features. To address this problem, we propose a novel approach for using feedback from the human during novelty search to improve behavior discovery.
