Learning NEAT Emergent Behaviors in Robot Swarms

Emergent behavior is a phenomenon observed in swarms of agents. It is generally defined as a complex swarm behavior which occurs as a consequence of each individual agent following a relatively simple control scheme [16, 18]. Examples of this can be found in the behavior of groups of animals, such as how some species of fire ants have been observed to create rafts out of their bodies to survive flooding [14]. Emergent behavior is also exhibited in migrating swarms of some species of caterpillars, which walk on top of each other in order to create a ‘rolling swarm’ [22]. This allows the caterpillars to migrate quicker than simply walking. Similar instances of complex emergent behavior have been observed in the field of swarm robotics.

Though there are various definitions of swarm robotics, it is generally agreed that robot swarms are multi-agent systems where each agent is autonomous and has low complexity [3, 10, 15]. They are used for various tasks, including exploration and surveillance. They are characterized by using locally communicating distributed systems as opposed to a central controller. Due to this, they remain functional as the swarm size is increased. However, they do not have a central controller, so careful fine tuning of the individual policies is required to achieve a desired swarm behavior.

It is well known that emergent behavior can arise in robot swarms, and past studies have explored this. Pagello et al. [19] study how to make a robot swarm perform a cooperative task by creating emergent behaviors. They implement this by dynamically assigning predefined roles to each robot. A function $Q$ is learned for each agent, which takes in local information and outputs the best role for the agent to adopt. After refining their $Q$ functions, they observe cooperative emergent behavior in their chosen task, robot soccer.

In a more recent study, Oliveri et al. [17] use a Monte Carlo scheme to continuously refine the behavior of individual agents in a swarm. They tested their method on robots connected in a line, which were each able to push away from their neighbors. Their study concluded that training each agent to optimize its individual velocity resulted in the entire group of connected robots crawls forward.

Evolutionary algorithms are algorithms inspired by biological evolution, where a user defined fitness function is optimized by repeatedly transforming a ‘population’ of solutions by spawning new members similar to members with the best fitness. We inspect NeuroEvolution (NE), a type of evolutionary algorithm that evolves neural networks. In early NE algorithms, the topology¹¹1The topology of a neural network refers to the graph structure of the nodes and the connections between them of the neural network is fixed, and the mutations take place in the weights of the connections [24]. However, using the Neuroevolution of Augmenting Topologies (NEAT) algorithm, the topolocy of the neural network can evolve as well, theoretically allowing generalization to problems of arbitrary complexity [25].

The rest of the paper is organized as follows: Section II discusses related work. Section III details our proposed learning algorithm, as well as common sensing and output schemes we use. We present our experiments in Section IV, and discuss the results in Section V. The conclusions we draw are in Section VI.

We propose NEAT as a candidate for learning emergent behavior in robot swarms. We will evolve a population of neural networks, evaluated through the performance of a homogeneous²²2Each agent is controlled with a copy of the same neural network robot swarm in one episode.

Our algorithm requires as input a user-defined fitness function. This function acts on a full episode of a robotic swarm’s behavior, and returns a real number evaluating the swarm behavior.

The proposed algorithm does the following in a loop:

• •

  For each network $x$ in a population of neural networks, a robot swarm is initialized such that each member contains a copy of $x$ for control.

• •

  A full episode is run, and the output of the fitness function is used as the fitness of $x$.

• •

  After fitnesses are collected, the next generation of networks is evaluated with NEAT.

We implement this on model robot swarms in a CoppeliaSim simulator [21]. For learning, we use the NEAT-Python package [13]. We use ROS2 Foxy to handle transferring sensing and actuation messages between CoppeliaSim and Python [12]. Our full implementation is available on Github [20].

The primary method for control of robot swarms is to have each agent act independently on local information. This method allows generalization of learned policies to varied swarm sizes. Thus, we generally use local observations of the environment and of nearby agents for inputs to each agent’s policy.

Since the position of other agents in the swarm is usually vital to training a good policy, we specify two sensing schemes that we use for our experiments.

We define $k$-tant sensing, where we split the environment into $k$ regions based on direction relative to the agent that is sensing. We allow the agent to either sense the distance to the nearest neighbor³³3We invert the distance so that an empty region corresponds to a sensor value of 0 or the number of neighbors in each region, as displayed in Fig. 1. Although we only use 2-D experiments, this sensing scheme very easily generalizes to 3-D (and $N$-D) sensing by discretizing the relative angles to each neighboring agent.

Since the NEAT algorithm outputs vectors of any specified dimension, this algorithm can very easily be fed into a velocity controller, or even into a low-level motor controller. In our experiments, we use both methods to verify the robustness of our algorithm to output scheme.

In this task, we simulate a ‘search and rescue’ scenario. The environment we use is a square arena with the agents spawned randomly near the center (displayed in Fig. 5). For the fitness function, we adapt deployment entropy, a measure of how well distributed the agents become in the environment [8]. Deployment entropy is defined by discretizing the environment into a grid, and measuring the entropy of the distribution of agents in that grid. In the example of Fig. 3, we would calculate this value as $\sum\limits_{i}-p_{i}\log(p_{i})\approx 2.05$. Since entropy is maximized by a uniform distribution, we believe using this as a fitness function would encourage the agents to spread out in the environment, the desired behavior for a ‘search and rescue’ mission. We implement this task for the both the Anki robots and the GT-MABs.

For the GT-MABs, we use 20 agents and divide the environment into a grid with 16 units for calculating deployment entropy. We chose $\lfloor 20\rfloor^{2}=16$ as this makes 1-2 agents per square optimal. For input, we use $k$-tant Distance Sensing with $k=8$. We also allow the walls to be sensed on each $k$-tant, since this lets the agents avoid crashing into them.

For the Anki Vectors, we use 10 agents (as this number would comfortably fit in our environment) and divide the environment into $\lfloor\sqrt{10}\rfloor^{2}=9$ units for deployment entropy. For input, we use $k$-tant Distance Sensing ($k=8$) along with of the Anki’s onboard proximity sensor.

For both agents, we define a designed policy where each agent moves away from the closest neighbors. We expect this to cause the agents to distribute themselves evenly, producing the desired swarm behavior.

In previous research we established that a swarm of GT-MABs was able to climb a wall that was much taller than the altitude they were assigned to hold [23]. Upon closer inspection, we realized that that collisions were resulting in the agents registering each other as the floor, effectively stacking their desired heights. A stack of three agents would allow the top one to pass over the wall.

We also note that the ‘wall climbing’ behavior is susceptible to the sensing angle of the GT-MAB’s ultrasound-based range sensor. With a large sensing angle, the GT-MABs are able to sense the wall itself when they are next to it, which results in a single agent being able to climb the wall on its own. To avoid this, we use a narrow ultrasound angle so that the agents must stack in order to climb the wall.

We design the Wall Climb task to replicate this scenario. The environment we use is an arena with a 3 meter tall wall on the $y$ axis. A swarm of 20 GT-MABs spawn randomly on the right side, as shown in Fig. 8. For the fitness function, we use the number of agents that end the experiment on the other side of the wall. If no agents succeed, we subtract a penalty of the distance of the closest blimp to the wall, to speed up initial exploration. We believe using this as a fitness function will encourage the emergent ‘aggregation’ behavior, since this is the only way the agents can climb the wall.

For our input scheme, we experiment with both $k$-tant Distance Sensing and $k$-tant Neighbor Sensing, with $k=8$. We compare the two experiments to display robustness of our algorithm to input scheme.

We define a designed policy where each agent moves towards either their closest neighbor or the direction with the most neighbors (depending on the input scheme), as well as slightly towards the direction of the wall. We expect this to cause the GT-MABs to flock and stack on top of one another, producing the desired swarm behavior of flocking over the wall. For our designed policy, we expect that Neighbor Sensing will perform slightly better, as this will encourage the agents to seek the largest group of neighbors.

After training in CoppeliaSim, we observe that the evolved behavior for both GT-MABs and Ankis seems to be for each agent to move in a direction away from its close neighbors. The GT-MABs accomplish this directly through the velocity controller, while the Ankis learned to spin in circles and reverse whenever their proximity sensor sensed an agent in front of them. For both experiments, the result seems to be a well distributed swarm (Fig. 5). From Fig. 4, we can see that both experiments generated agents that achieved close to the theoretic maximal entropy⁴⁴42.718 for GT-MABs from placing one agent in 12 of the squares, and two agents in 4 of the squares; 2.16 for Ankis by placing one agent in 8 of the squares and two agents in 1 square, with the Ankis achieving it almost immediately.

The result of the designed policy (Fig. 5(b, d)) also had the swarm distribute in the environment. Comparing these results in Table I, we can see that for GT-MABs, the designed policy outperforms the evolved behavior by about one standard deviation. For the Anki experiment, the opposite is true, with the evolved behavior outperforming the designed policy by about one standard deviation. This seems to be due to the designed policy favoring sending agents to the edges of the environment.

Overall, we show that in this task, our algorithm learns a local behavior that closely approximated the desired ‘search and rescue’ emergent swarm behavior. The evolved behavior greatly outperforms the designed policy, which shows that our evolutionary algorithm performs comparably to designing the behavior with knowledge of the task.

After training the GT-MAB models in CoppeliaSim, we observe that the evolved behavior for both experiments seems to be for each agent to move in a direction towards its closest neighbors, in addition to moving in the direction to climb the wall. The result of this behavior does seem to be a flock of agents stacked on top of each other, climbing the wall. From Fig. 6, we can see that after a few generations, the best genome of each generation achieved having about 18 GT-MABs make it over the wall.

We noticed that both sensing methods achieved similar population fitness values across generations Fig. 6. From Table I, we see there is no statistically significant difference between the two fitness results.⁵⁵5We perform a two sample $t$-test with unequal variance on the fitnesses obtained from the evolved Neighbor Sensing and Distance Sensing experiments. Using their respective means and standard deviations of (16.70,1.12) and (16.72,1.32) with a sample size of 60 for both, we arrive at a $p$-value of $p>.9$, which is much larger than $.05$, the accepted value for statistical significance. This shows that with our sample size, there is no significant difference between the fitnesses obtained from the different sensing methods.

The result of the designed policy in both of these experiments similarly causes the agents to flock together and climb the wall. However, in this case we do notice a difference in the two modes of sensing. In the Distance Sensing experiments, the designed policy seems to be more likely to cause the agents to form several smaller groups as opposed to one large one. This results in a lower fitness due to more agents being left behind, as shown in Table I. Comparing this with our evolved behavior, we can see in both experiments, the evolved behavior outperforms the best designed policy by at least one standard deviation.

Overall, we show that in this task, our algorithm learns a local behavior that closely approximated the desired ‘flocking’ emergent swarm behavior. We can further see that although the different sensing modes has an effect on our designed policy, the evolutionary algorithm is robust to these variations.