Exploring communication protocols and centralized critics in multi-agent deep learning

Abstract

Tackling multi-agent environments where each agent has a local limited observation of the global state is a non-trivial task that often requires hand-tuned solutions. A team of agents coordinating in such scenarios must handle the complex underlying environment, while each agent only has partial knowledge about the environment. Deep reinforcement learning has been shown to achieve super-human performance in single-agent environments, and has since been adapted to the multi-agent paradigm. This paper proposes A3C3, a multi-agent deep learning algorithm, where agents are evaluated by a centralized referee during the learning phase, but remain independent from each other in actual execution. This referee’s neural network is augmented with a permutation invariance architecture to increase its scalability to large teams. A3C3 also allows agents to learn communication protocols with which agents share relevant information to their team members, allowing them to overcome their limited knowledge, and achieve coordination. A3C3 and its permutation invariant augmentation is evaluated in multiple multi-agent test-beds, which include partially-observable scenarios, swarm environments, and complex 3D soccer simulations.

Keywords

Multi-agent systems neural networks emergent communication deep reinforcement learning

1. Introduction

A multi-agent system (MAS) is, by definition, an environment where multiple entities (i.e., agents) are interacting. Most complex systems can be modeled as a MAS, from an ant colony to the solar system. It can also be useful to describe a problem as a MAS when a group of agents can solve it, but the problem would otherwise be difficult or impossible for a single monolithic system. Research shows, indeed, that multiple fields explore interactions of agents in MAS, including distributed target tracking [1], autonomous robots [2], and spacecraft formation [3], where a team of agents must coordinate to spatially arrange themselves; traffic monitoring [4] and distributed sensor networks [5], where sensing agents are geographically spread and coordinate to achieve meaningful information; competitive negotiation [6, 7] or decision-support systems [8], where agents interact with other, possibly human, agents; competitions or games [9, 10], where robotic and software agents compete for supremacy, demonstrating the strength and applicability of machine learning algorithms, by achieving agents that surpass the best human players in the world; and even in crowd-modeling areas [11, 12], where MAS can be used to detect anomalies, predict flow, and improve the interactions between robots and humans in real-life scenarios.

Essentially, MAS form the basis of most complex systems around us, and its agents include both software agents, physical robots, and humans. Coordination is considered a key characteristic of MAS, and an agent’s capability of coordinating with others constitutes one of its major qualities. In cooperative environments, coordination consists on harmonizing the interactions of multiple agents, such that a global plan can be carried out. The global plan, composed of the sum of each agent’s individual actions, will ideally fulfill the agent’s individual goals or the global objective of the MAS, as efficiently as possible. However, for multiple systems, defining by hand how an agent should behave in all possible situations and with all possible interactions with others may be prohibitively difficult, time-consuming, or expensive. Ideally, agents would learn their own behaviors without human guidance, and develop their own policies to coordinate with others in the MAS and complete the required task. This is known as multi-agent learning.

Various research efforts [13, 14, 15] have shown, however, that achieving coordination in MAS remains a complex challenge with open questions. A popular technique for multi-agent learning is to apply single-agent machine learning algorithms to each independent agent and demonstrate that successful policies can be learned with implicit coordination. However, theoretical convergence guarantees offered by single-agent algorithms are lost, as the vast majority of algorithms assumes a stationary environment [16]. In a MAS, agents must take into account the remaining agents’ policies, which can also adapt their behavior (known as a moving target problem [17]). In other words, each agent must handle all the complexity that exists in a single-agent environment, as well as the additional issues that arise in the multi-agent paradigm. Single-agent challenges include the underlying environment’s complexity (where a task may be very complex to learn), the partial-observability of the environment (where an agent observes only a small local section of the entire environment), or high-dimensional state- or action-spaces (video games like Starcraft II present millions of pixel screen combinations and hundreds of possible actions at any given point). Multi-agent challenges include the moving target problem[17], where multiple independent agents learning simultaneously causes each agent’s perspective on the environment to appear non-stationary, as well as the structural credit assignment problem, where the actions of agents that contribute to a task’s completion may be rewarded in an inadequate manner (e.g., in a soccer match, each agent gets a point when a goal is scored, but not all agents contributed to that goal equally).

To achieve coordination, exchanging information has been shown to be a helpful solution. However, when agents can exchange information between them, learning or defining a communication protocol that best improves the team’s performance remains an open problem. Communication allows agents to share different types of information [18, 19], which helps compensate for the partial observability of the environment, reducing the complexity of the task. However, there is no consensus on how best to determine the communication protocol for any given environment.

Another helpful solution for coordination is for a central referee to evaluate the entire team’s performance and contribution to the task, instead of each agent evaluating this locally, lessening the structural credit assignment problem. However, such solutions often suffer from poor scalability with large amounts of agents, as the referee’s complexity scales with the team size. Methods that can improve the scalability of these referees become valuable in such cases. These include, among others, pre-processing the referee’s input, simplifying information at the cost of requiring a priori domain knowledge, and permutation invariance techniques, which reduce the complexity of the referee by allowing it to ignore the order in which agents are deployed.

This article proposes Asynchronous Advantage Actor-Centralized-Critic with Communication (A3C3), previously introduced in Simões et al. [20], a multi-agent deep learning algorithm. Agents are executed independently, but a centralized critic is used in the learning phase for agents to learn implicit coordination. Agents also learn to communicate through learned communication protocols. Our contributions are three-fold. Firstly, A3C3 is described and evaluated more thoroughly, being compared in multiple complex and partially-observable environments against other state-of-the-art approaches. Secondly, the complexity of A3C3’s critic increases with the amount of agents in the environment, so a network architecture is proposed to alleviate the problem. This architecture focuses on allowing permutation invariance in a deep neural network, which A3C3 can benefit from when the amount of agents in the team is large. It allows A3C3 to be used in swarm-like scenarios with tens of agents. Finally, A3C3 agents learn a communication protocol tabula rasa, through which they share relevant information for other team members. The interpretation of each communication protocol is not trivial, and an analysis of the learned protocols in four environments is presented in this paper. Direct correlations between local observations (e.g., each agent’s location) and the sent messages can be found, demonstrating the meaning behind the protocol.

The remainder of this paper is organized as follows. Section 2 describes related work and current state of the art in the field. Section 3 states the problem, Section 4 describes our main contribution, the A3C3 algorithm, and Section 5 describes a network architecture that can be integrated with A3C3 to increase its scalability through permutation invariance. Section 6 lists the used test-beds, and Section 7 the results obtained in them, with A3C3 and multiple other state-of-the-art algorithms. Finally, Section 8 draws conclusions and lists future work directions.

2. Related work

Deep Neural Networks are powerful non-linear function approximators and form the basis of Deep Learning (DL) algorithms. At its core, a neural network is a directed graph where nodes represent neurons and are divided into an input layer, an output layer, and one or more hidden layers [21], as can be seen in Fig. 1. How many hidden layers are necessary to distinguish between deep and shallow neural networks is not clearly defined. Each edge of the graph between nodes $i$ and $j$ has a weight $w_{ij}$ and each node $j$ outputs value $x_{j}=\sigma(x_{j}^{-})$ , where $\sigma$ is a predetermined activation function, and $x_{j}^{-}=\sum_{i=1}^{I}w_{ij}\times x_{i}$ is the weighted sum of the node $j$ ’s $I$ input synapses. These input synapses, in a fully connected layer for example, consist on all the nodes of the previous layer, and possibly an additional node with value $1$ called the bias, all multiplied by their corresponding weight.

Figure 1.

An example of a deep neural network with a fully-connected architecture and $N$ hidden layers. Each node is connected to all the nodes in the next layer.

Neural networks and DL algorithms have recently emerged as a popular solution in a multitude of different areas. These include time series forecasting in big data scale [22], which rely on sequences of samples of information to predict events, like flash floods [23] or seismic activity [24, 25], allowing systems to warn humans in a timely manner. Other applications of DL are based on image classification [26, 27], useful for extracting information from images [28], detecting and identifying vehicles in traffic surveillance cameras [29], or structural failure risk in bridges [30, 31], roads [32], and other structures [33, 34]. Neural networks show tremendous potential across tasks where mapping an input (like an image) to a result (like a classification of “dog” or “cat”) is useful. This is partly due to the universal approximation theorem [35], which states that deep neural networks with at least one hidden layer and a non-linear activation function can provably approximate any function with arbitrary precision.

DL is now commonly used across many different fields, and its potential has been taken advantage of for medical purposes, analyzing patient data [36, 37], predicting physical properties of materials [38], and to achieve super-human results in multi-agent learning problems based on video games [39, 40]. In the latter scenario, DL maps pixel values or game information into game controls (like moving or attacking). These multi-agent learning algorithms rely on Reinforcement Learning, a machine learning category where at least one agent, which behaves as the learner, interacts with the environment. Agents select and perform actions on the environment, which then reaches a new state, from which agents take an observation, and possibly a reward associated with that transition. This can be seen in Fig. 2.

Figure 2.

The RL cycle for single-agent systems [41]. At time-step $t$ , the agent executes action $a_{t}$ upon the environment, and obtains reward $r_{t+1}$ and observation $o_{t+1}$ . This process is repeated until the environment reaches a terminal state.

A rational agent is trained until it can output a policy $\pi(a_{t}|o_{t})$ , which is a probability distribution over its possible actions for each observation taken. In Deep Reinforcement Learning, artificial neural networks are used to approximate the policy that the agent follows. The agent is trained in order to maximize its obtained rewards, also known as its returns. Value-based reinforcement learning has an agent approximating the optimal value function, a mapping between state-action pairs and the expected returns of choosing that action on that state. Higher returns implies higher rewards will be obtained, and indicate the best action. Policy-based reinforcement learning has an agent directly finding the optimal policy, without using a value function.

Actor-Critic algorithms merge both value- and policy-based methods. They use an actor to control the agent by learning the optimal policy, and a critic that evaluates the agent’s actions by approximating the optimal value function. DL actor critic methods use two artificial neural networks, one representing the actor, and another the critic. The actor network with weights $\theta_{a}$ outputs a probability distribution $\pi(a_{t}|o_{t};\theta_{a})$ at time-step $t$ , where each action $a_{t}$ is given a probability of being sampled when the agent observes $o_{t}$ . The critic network with weights $\theta_{v}$ outputs a value estimation $V(o_{t};\theta_{v})$ at time-step $t$ when the agent observes $o_{t}$ .

Asynchronous Advantage Actor-Critic (A3C) [42] is an asynchronous DL actor-critic algorithm. Global critic and actor networks are asynchronously updated by $N$ workers, in parallel. Despite its many advantages, DL often requires long computational times or specialized hardware (like computer clusters, GPU boards, FPGA boards, among others) [43], and A3C can be horizontally scaled by increasing its amount of workers. Each worker has its own agent, environment, and local actor and critic (copied from the global networks). It interacts with its environment, calculates updates based on local networks, and applies them on global networks. Proximal Policy Optimization (PPO) [44] is a policy search-based method largely inspired on A3C. The policy network uses a new update function which clips policy updates to prevent very large update steps. It has been shown to achieve state-of-the-art results in multiple single-agent environments, with less hyper-parameters and a simpler implementation.

Multi-agent deep reinforcement learning proposals introduce new techniques to enforce agent coordination, such as agent communication or centralized learning.

The Counterfactual Multi-Agent Policy Gradients (COMA) algorithm [45] is a centralized training, distributed execution algorithm where the value network is augmented with the observations and actions of the entire team. Agents still run independently, but the centralized value network now models a value function for a stationary environment. The algorithm tackles the credit assignment problem by using its value estimations to evaluate the benefits of specific actions by specific agents. However, COMA does not support heterogeneous reward functions.

The CommNet algorithm [46] is a joint-action algorithm [47], where an artificial neural network outputs the actions for all agents simultaneously, thus not supporting distributed execution. However, the algorithm allows agents to share messages during the feedforward passes of the network, allowing agents to learn policies and a continuous communication protocol simultaneously. CommNet’s joint-action approach leads to poor scalability (as the joint-action space scales exponentially with the amount of agents), and has uncommon and unintuitive hyper-parameters (agents share an arbitrary amount of messages before committing to each joint-action).

Value-Decomposition Networks (VDN) [48] allow agents to learn a factorized joint-action value function based on their independent observations, and the sum of each agent’s estimation approximates the centralized joint-action function. Agents can communicate by concatenating the output of their layers at some points. VDN disregards any additional information available from the environment, and limits the complexity of the centralized joint-action function to a simple sum. QMIX [49] is a VDN-extension, where each agent’s value function is no longer summed to approximate the centralized joint-action function. Instead, an additional mixing network is used to combine each individual value function in a more complex manner, which is also able to incorporate additional environment information.

Other proposals learn communication using a pre-determined vocabulary. The Mordatch algorithm [50] uses recursive neural networks for agents to learn how to maintain a meaningful conversation in cooperative scenarios. Agents communicate through a discrete set of symbols and are optimized with a joint-reward function. REINFORCE [51] is extended with Hierarchical Recurrent Encoder-Decoder by Das et al. [52], such that agents can learn to communicate with a set of natural-language symbols while learning to complete tasks. Lazaridou et al. [53] replace agents’ action-space with an alphabet so that agents learn to communicate in a cooperative task. However, this is no different from learning a cooperative policy.

In conclusion, many deep reinforcement learning algorithms feature undesirable properties for an independent MAS. Algorithms like COMA, CommNet, VDN, and QMIX use centralized critics or output joint-actions, and scale poorly with the amount of agents in the environment. Research has shown that environments with only four agents can be too complex for joint-action approaches like CommNet [54], and centralized critics used by COMA, VDN, and QMIX incorporate all agent observations and may require additional solutions (such as a Permutation Invariant Network architecture, discussed below) when working with large teams. COMA and QMIX also do not take advantage of inter-agent communication, a flexible way for agents to share information. Communication can help compensate for local information and improve the team coordination. A3C3 features a centralized critic with a scalable architecture for large teams, and learns a communication protocol where agents share relevant information to complete the task.

3. Problem statement

The scope of our work encompasses cooperative multi-agent environments with limited observability. A team of $J$ agents has to coordinate, with each agent being executed in an independent manner, having sole access to its own local observations of the environment. The team size $J$ is expected to range from a simple pair to tens of agents. An observation $o_{t}^{j}$ by agent $j$ at time-step $t$ represents an incomplete and local representation of the environment’s current state $s_{t}$ . Agent $j$ interacts with the environment through a set of discrete actions $\mathcal{A}^{j}$ , and the joint-action output by the team is executed simultaneously, placing the environment in a new state. At each state transition, environments either provide team-wide rewards (e.g., when a task is accomplished, all agents in the team receive a point) or individual rewards (only the agent that completed the task is rewarded). Agents have limited communication capabilities, and can use a communication protocol to share information and coordinate. Formally, an environment can be described as a Decentralized Partially-Observable Markov Decision Process [55].

As an analogy, consider a group of $J=$ 5 human workers transporting supplies from a factory to a truck. Each worker’s local observation $o_{t}^{j}$ comprises its own location and carried cargo, while the environment state $s_{t}$ is composed of all worker’s locations, cargo, and the remainder of supplies left at the factory. Workers have a set of actions $\mathcal{A}^{j}$ that include picking up cargo, dropping it, and moving in a direction. The workers all receive a team reward in the form of a fixed payment when all the cargo has been delivered, regardless of their individual performance. They can also learn a unique language with which to talk to each other, within ear-range, in order to decide the best way to transport cargo without hampering each other.

We consider a centralized learning, distributed execution paradigm [56], where an algorithm has access to all agents’ observations and actions during the training phase, acting as a centralized controller, but where agents behave independently during the execution phase. This allows an algorithm to take advantage of centralized architectures, and incorporate additional information from the environment or from the agents into their policies. We also assume that the amount of agents $J$ can vary throughout each episode, depending on the environment (e.g., a race can initially have three vehicle agents, but only two remain active after one finishes the track). The team’s size can include, at any given moment, tens of agents (considered a swarm by some authors [57, 58]), therefore requiring scalable models. Given that the scope of our work is based in DL and the input of an artificial neural network is not permutation invariant, standard network architectures may be unable to scale adequately.

We also model agent communication as message transmission, where agents can send vectors of continuous values to others. Messages may be limited by range (e.g., agents can only communicate with other geographically close agents), size and value (a message can range from multiple values within [ $-$ 1, 1] to a single bit {0, 1} of information), or by target (messages can be broadcast to the entire team, or sent to specific agents). We also assume imperfect communication mediums, where messages can be late, lost, noisy, or otherwise interfered with.

4. Asynchronous advantage actor centralized-critic with communication

This section describes the Asynchronous Advantage Actor Centralized-Critic with Communication (A3C3) algorithm, a multi-agent actor-critic algorithm. A3C3 uses an actor network with weights $\theta_{a}^{j}$ and a centralized critic with weights $\theta_{v}^{j}$ for each agent $j$ . The actor for agent $j$ takes only local information (like its observation $o_{t}^{j}$ ) as input, allowing agents to be executed in an independent manner. The centralized critic for agent $j$ takes global information (like a concatenation of all agent observations) as input, thus making A3C3 require a centralized learning process where all agents have access to all observations. During execution, the critic is not necessary, only the actor. Despite being centralized, each agent trains its own critic, given that agents may have distinct reward functions. With homogeneous team rewards (e.g., an agent scores a goal in a soccer match and the entire team gets a point), the same centralized critic with a single value estimation can be used for all agents. However, if the environment does not provide team rewards (e.g., only the agent that scored a goal gets a point, instead of the entire team), a single centralized critic can be used, but it must output the value estimation for each individual agent. Because the centralized critic incorporates all agent observations, using a standard network architecture may not be scalable with large team sizes.

In addition to actor and centralized critic networks for each agent $j$ , A3C3 also models a communicator network with weights $\theta_{c}^{j}$ . The communicator for agent $j$ takes only local information, similar to its actor, allowing it to be used during an independent execution phase. The network outputs continuous-valued messages of length CC (the amount of communication channels). A communicator network with $\text{CC}=$ 2 has two output nodes, each of which outputs the value for one of the channels. We use a hyperbolic tangent activation function in the communicator’s output, such that the value of each channel is within $[-1,1]$ , but other activation functions are supported (like sigmoid or binary). Exemplary messages with $\text{CC}=$ 2 and a hyperbolic tangent activation include $\{0,0\}$ , $\{-1,1\}$ , $\{\frac{1}{2},\frac{1}{2}\}$ , or $\{-\frac{1}{2},0\}$ . An agent $j$ sends generated messages $sc_{t}^{j}$ at time-step $t$ to its team members based on environmental constraints (e.g., range or reliability). These are received as $rc_{t+1}^{j}$ in the following time-step, and are concatenated to the input of the actor networks. When a message is delayed or lost, a standard value $rc_{0}$ is used.

Formally, for agent $j$ at time-step $t$ , the centralized critic’s input comprises a centralized observation $O_{t}$ that concatenates all agent observations and any additional state information provided by the environment. For example, some environments provide access to the complete underlying state (all information that describes the current time-step, without noise) for debug purposes. A3C3 can incorporate this information when available. The centralized critic is not necessary during execution, and outputs a value estimation $V(O_{t}^{j},\theta_{v}^{j})$ , representing the expected returns if all agents follow their policies at that time-step. The actor’s input comprises the agent’s local observation $o_{t}^{j}$ and any messages $rc_{t}^{j}$ received from other agents. The network outputs a probability distribution $\pi(a_{t}^{j}|o_{t}^{j},rc_{t}^{j},\theta_{a}^{j})$ from which that time-step’s action $a_{t}^{j}$ is sampled. The communicator’s input is the agent’s local observation $o_{t}^{j}$ , and outputs a message $sc_{t}^{j}$ (a vector of CC continuous-valued elements), which is received by other agents in the following time-step. Both the actor and the communicator require solely local information, allowing agents to be executed in an independent manner.

A3C3 is also an asynchronous algorithm. This class of algorithms runs multiple parallel workers in multi-core CPU and has been shown to outperform single-threaded GPU-based algorithms [42]. It allows algorithms to scale horizontally, an increase the amount of updates over time by increasing the amount of workers, and without requiring specialized hardware. Asynchronous algorithms keep global networks which are updated by multiple workers, each worker keeping local copies of the networks, and updating the global networks with mini-batches of samples. In the case of single-agent actor-critic algorithms, each worker has a local actor and critic networks, copies of the global actor and critic networks. In multi-agent actor-critic, there are $J$ global actor networks and $J$ global critic networks, and each worker keeps local copies of all those networks. With homogeneous agents, this can be simplified by using inter-agent parameter sharing (agents all train the same actor network, for example). Networks with similar output can also benefit from intra-agent parameter sharing [59, 60], where the networks are combined, and a single feedforward pass yields multiple outputs.

The pseudo-code for an A3C3 worker is described in Algorithm 1. Workers create local copies of the global networks, and sample the environment. They compute a message and an action for each agent, execute them, and re-sample the environment. After a mini-batch is collected or a terminal state is found, the loss of local networks is calculated and the corresponding gradients are applied to the global networks. This loop is repeated until agents’ policies have converged. When using inter-agent parameter sharing (i.e., homogeneous agents share the same networks), the optimization steps of each agent’s mini-batch optimize the same global network, thus making the learning phase more efficient.

Algorithm 1: Pseudo-code for A3C3’s worker threads. See https://github.com/bluemoon93/A3C3 for implementation details.
Input: Learning rate $\eta$ , number of agents $J$ , global actor $\theta_{a}^{j}$ , centralized critic $\theta_{v}^{j}$ , and communicator $\theta_{c}^{j}$ networks for each agent $j$ .
1. $t\leftarrow 0$
2. repeat
3. Copy global network weights into local copies of networks
4. Sample observation $o_{t}^{j}$ for each agent $j$
5. Sample or derive centralized observation $O_{t}$
6: repeat
7: for each agent $j$ do
8: Send message $sc_{t}^{j}$ given by communicator network,
execute action $a_{t}^{j}$ given by actor network
9: Sample new observation $o_{t+1}^{j}$ and reward $r_{t}^{j}$
10: end for
11: Sample or derive centralized observation $O_{t+1}$
12: $t\leftarrow t+1$
13: until terminal state or mini-batch of state-action pairs
collected
14: for each state-action pair $i$ in the reversed mini-batch do
15: for each agent $j$ do
16: Calculate expected return $R$ given actual returns of
the subsequent states in the mini-batch
17: Calculate critic loss $L_{v_{i}}^{j}$ based on expected returns
and the critic’s value estimation
18: Calculate actor loss $L_{a_{i}}^{j}$ based on an advantage
estimator and an entropy factor to encourage
exploration
19: Calculate error $L_{rc_{i}}^{j}$ of messages received by agent
$j$ , based on actor loss
20: Calculate communicator loss $L_{sc_{i}}$ based on error
of messages sent by agent $j$ and received by others
21: end for
22: end for
23: Use local losses of all networks to optimize global
networks
24: until training completed
Oupput: Converged global actor $\theta_{a}^{j}$ , centralized critic $\theta_{v}^{j}$ , and communicator $\theta_{c}^{j}$ networks.

After $t_{\text{max}}$ time-steps, or if a terminal state is reached, all networks are optimized with the collected mini-batch of interactions with the environment, by calculating the loss for each interaction. The centralized critic’s loss $L_{v_{i}}^{j}$ is calculated using the squared difference between the actual returns and the value network’s output $(R-V(O_{i}^{j},\theta_{v}^{j}))^{2}$ . When a terminal state has not been reached, the centralized critic’s estimation is used to bootstrap next state’s expected value. The actor network’s loss $L_{a_{i}}^{j}$ is defined as the difference between the actual returns and the value network’s output $(R-V(O_{i}^{j},\theta_{v}^{j}))$ , and the logarithm of the policy network’s output strategies $\log\pi(a_{i}^{j}|o_{i}^{j},rc_{t}^{j},\vartheta_{a}^{j})$ . An entropy factor $H(\pi(a_{i}^{j}|o_{i}^{j},rc_{i}^{j},\vartheta_{a}^{j}))$ is also used, to discourage premature convergence. The communicator network’s loss takes an additional step to calculate. In the actor network, gradients are calculated with respect to the received messages $L_{rc_{i+1}}$ (representing the error of those messages), and mapped as loss of sent messages $L_{sc_{i}}$ for the communicator network, which is then minimized. In other words, agent $j$ informs other agents (through the error of its received messages) about how those messages can improve its own policy. Agent $j$ is also informed about how its messages can help other agents. By doing this for the entire team, all agents learn to output relevant information for each other, enforcing coordination between them. The loss of all three networks is minimized through backpropagation with every mini-batch of interactions. The gradients are calculated based on the loss of each worker’s local networks, and asynchronously applied on the global networks.

As an example of an optimization cycle, consider two vehicles learning to cross an intersection. Vehicles (the agents) know whether they wish to turn or not, and can either move forward, turn, or wait (three possible actions). They can signal each other by turning a light on or off (a binary message with a single value). A3C3 simulates multiple intersections (one per worker), each intersection with two agents trying to cross. Each simulation defines random goals for agents, and agents get heavily penalized for crashing or following the wrong direction, and lightly penalized for waiting at the intersection. As simulations are completed, agents learn a value function, and understand that they get a small penalty for waiting and a large penalty for going the wrong way. When they advance towards their intended destination, they are penalized only on occasion, when the other vehicle also went that direction. The centralized critic learns that agents could avoid large penalties if they did not collide, and so vehicles learn to share the direction they wish to move. By turning on their light when wishing to turn (just like humans turn on a blinker light), both vehicles understand where the other is headed, and the vehicle with priority can advance while the other awaits. Both vehicles realize that it is better to wait while the priority vehicle crosses instead of crashing both. After some thousands of simulations, the agents’ policies stabilize and the environment is successfully completed.

5. Permutation invariant network architecture

Like previously stated, as the amount of agents in the environment increases, the scalability of A3C3 is hindered by the centralized critic. Since this network commonly aggregates observations from all agents (although it is not necessary to), its complexity is directly proportional to the amount of agents on the team. An additional issue, found with homogeneous teams, is that exchanging agents’ identifiers (and therefore the order with each each agent’s observation is fed to the critic) should also not affect the value estimation. However, a neural network approximator is not permutation invariant with respect to each agent’s observation. In an environment with at least two homogeneous agents, the order with which each agent’s observation is aggregated to the input of the network affects its value estimation. The problem is further accentuated when the amount of agents grows to large values.

For example, consider a team of two homogeneous agents, that observe their own positions as $o_{1}$ , and $o_{2}$ . Consider two positions, $A$ and $B$ , where agents are standing. Two equivalent options arise here: either agent $j=$ 1 is at position $A$ , observing $o_{1}=A$ , and agent $j=$ 2 is at position $B$ , observing $o_{2}=B$ ; or they are switched, with $o_{1}=B$ and $o_{2}=A$ . Both options are equivalent because agents are homogeneous, and so should behave in the same way regardless of which agent is where. The centralized critic concatenates both observations as $\{o_{1},o_{2}\}$ and, again because agents are homogeneous, should output the same value estimation $V$ when its input is $\{A,B\}$ or $\{B,A\}$ . However, common feedforward architectures are not invariant to this permutation, and $V(A,B)\neq V(B,A)$ . The amount of possible permutations scales exponentially with the amount of agent observations, making the value function’s complexity intractable with large teams.

In swarm scenarios, where there are usually tens of homogeneous agents [61], a critic must derive a value function $V$ using a very large input layer, and it must also learn that agents’ inputs are permutation invariant. It is possible for algorithms to learn permutation invariant policies in MAS with a small amount of agents simply based on randomness and on the algorithm’s ability to explore similar states where agents are in opposite locations. This is, in fact, a common technique used in most joint-action based algorithms [46] and also used by A3C3 in the previous section. With only two to four agents, A3C3 learns to output similar value estimations for agents in the same positions but listed in different orders. However, once the amount of agents grows large, this becomes exponentially more difficult to learn for a network, since the amount of possible permutations $P=J!$ .

The question then becomes how to allow a critic network whose input contains a set of agent observations to become permutation invariant to the order of this set. We have demonstrated that it is possible to learn some kind of permutation invariance by feeding a network enough data that it learns to be robust to agent permutations. This is a slow method, and does not scale well.

Another possible option is to maintain the same network structure, and pre-process its input. By ordering the set of agents based on their observations, the network will output the same value estimation regardless of the original set’s order. When each agent’s observation is 1-dimensional, this is a trivial task. However, even in the simple case of a 2-dimensional observation of $(x,y)$ coordinates, defining a proper ordering metric can be complex. With $(x,y)$ , agents can be ordered by the average of their coordinates, their sum, their $L^{2}$ norm, or by prioritizing a coordinate and using the other to resolve ties. Different methods will likely yield different results. If the agents’ 2-dimensional observation is not coordinates, but unrelated values, this task becomes even more complex and entirely problem-dependent. While in some cases is will probably be an adequate technique, it is not general enough.

This section describes a technique where the network architecture is itself permutation invariant, which has been independently researched as Deep M-Embeddings (DME) [62]. DMEs consist on an initial network $\theta_{p}$ that extracts $F$ features from each agent’s observation, and then apply a permutation invariant filter on these features. From there, the remainder of the network is permutation invariant to the order of agents and estimates the value function as before. The feature extraction network must use the same weights $\theta_{p}$ for all agents $j$ , in order to maintain its permutation invariance properties, and outputs a set of features $\lambda$ with dimensions $[J,F]$ . The permutation invariant filter is essentially an operation that reduces the dimensionality of the feature extraction network’s output into a single vector $\Lambda$ of length $F$ , like a mean function

$\displaystyle\Lambda_{f}=\frac{\sum_{j=1}^{J}\lambda_{j,f}}{J},\text{for all % features}\ f$ (1)

across agent observations. Other possible functions include the maximum function

$\displaystyle\Lambda_{f}=\max_{j}\lambda_{j,f},\text{for all features}\ f$ (2)

or the weighted softmax function

$\displaystyle\Lambda_{f}=\sum_{j=1}^{J}w_{j,f}\lambda_{j,f},$ $\displaystyle\text{with}\ w_{j,f}=\frac{e^{\beta_{f}\lambda_{j,f}}}{\sum_{j=1}% ^{J}\beta_{f}\lambda_{j,f}},\text{for all features}\ f,$ (3)

where $\beta$ is a set of weights, each for its corresponding feature, which is also optimized. The reduced vector $\Lambda$ can then be used as a regular network layer in the centralized critic network $\theta_{v}^{j}$ . Figure 3 shows an example of the proposed architecture.

Figure 3.

The architecture of a permutation invariant Central Critic for agent $j$ . The critic takes as input the set of observations from all agents as well as any other relevant information that is available from the environment. Every agent’s observation is processed by a DME layer, which extracts a set of permutation invariant features. These are then concatenated with the information from the environment which did not belong to agent observations (if any) and connected with the remainder of the layers in the critic network.

Figure 4.

The POC suite. (a) Agents (black) have access to their own coordinates and must locate a reward zone (red). That location should be shared with other agents to maximize the team reward. (b) At intersections, purple vehicles wish to turn and white vehicles wish to go forward. They should signal their intent to turn or not, and cross without colliding by following road rules. (c) Predators (squares) observe a small local area, and try to surround and capture prey (circles), which run from the closest predator. (d) Drones know beacon locations and their own position. They should share their positions and decide which drone covers which beacon.

Popular DL frameworks [63, 64] do not feature DME layers, and implementing them by hand can lead to unoptimized or incorrect code. Therefore, we take advantage of pre-existing architectures, specifically convolutional layers, to emulate the behavior of DME. Convolutional layers use a kernel, usually with $[P_{x},P_{y},C]$ dimensions, with $P_{x}$ and $P_{y}$ corresponding to pixels, and $C$ being the amount of color channels in the image. This kernel is repeatedly slided across the input image, with a given stride, representing the amount of pixels the kernel is slided. A stride of $1$ means the kernel is moved one pixel at a time. As the kernel is slided, it analyses small parts of the original input image, with dimensions $[P_{x},P_{y}]$ , and generates an output of depth $f$ for each one, which corresponds detected features (like edges, or geometric shapes).

We can take advantage of the optimized convolutional layer implementations and shape them to act like DME layers. If each agent observation has a length of $O$ , and the set of agent observations being fed to the centralized critic has a shape of $[J,O]$ , a convolutional layer with a kernel of $[1,O,1]$ dimensions, with stride $1$ and depth $f$ , will extract features from each agent observation into a vector of size $f$ . The set of these $J$ vectors can then be reduced with permutation invariant functions to create a single $f$ -sized vector, which acts as a standard hidden layer in the network (with the exception of being permutation invariant to the set of agent observations). This behaves like the architecture shown in Fig. 3, and it remains an end-to-end differentiable architecture, which can still be fully optimized through backpropagation. Multiple convolutional layers with non-linear activation functions can be chained as desired, to extract non-linear features from each agent observation.

While we integrate this network architecture within A3C3’s critic, it can be used elsewhere. For example, A3C3’s actor networks can benefit from this architecture if agents received broadcast messages from all their teammates. The architecture can also be used outside of A3C3, and algorithms with centralized critics (like COMA, QMIX, or VDN) can benefit from its incorporation.

6. Environment suites

A3C3 is tested in three environment suites with partially-observable state-spaces, represented as Dec-POMDP, where agents can only sample incomplete, noisy, or incorrect observations of the underlying state.

Figure 5.

Three scenarios of the KiloBots environment. Agents (grey) know their own poses and the relative polar coordinates of other agents and objects (green). (a) Agents must push the object towards the yellow area. (b) Agents must push and join the objects together at any point in the map. (c) Agents must push and separate the objects as far away from each other as possible.

6.1 Partially-observable with communication suite

We use a set of diverse multi-agent environments, the Partially-Observable with Communication (POC) suite [65], each requiring information sharing between agents in order to overcome their partial observability. The four environments are shown in Fig. 4.

The Hidden Reward is a classical robotics exploration challenge. Agents explore the map until a target area is found or the time-limit is reached. Agents observe their own location and a sensor indicating whether they’re in the reward zone. The central observation is the concatenation of all agent observations. Ideally, agents spread out to explore the map as fast as possible, and alert teammates once the reward zone is found.

The Traffic environment simulates multiple intersections for a large amount of vehicles which must adhere to priority road rules and avoid crashes or traffic jams. Each vehicle senses cars immediately around themselves, and knows their preferred route. Vehicles can only communicate with the cars within their vision range. The central observation for each agent is its local observations concatenated with its neighbors preferred routes. Ideally, vehicles inform each other of their intent to turn, and the one with priority moves.

The Predator/Prey environment has two teams of agents. Predators with local partial observations must surround and capture intelligent prey, which always run form the closest predator. Predators know their location and can observe a small local area (less than 10% of the full map). Collisions are penalized, and predators are randomly placed when one occurs. The central observation is a global observation of predator and prey coordinates. Ideally, predators explore until a prey is seen, and they quickly converge on that prey, until all are caught.

The Navigation environment has multiple beacons which must be covered, and the team must decide which agent covers which beacon. Agents observe the beacon’s locations, as well as their own. Ideally, they communicate their own location with each other and coordinate to cover both as fast as possible.

Figure 6.

The RCSSServer3d Soccer Simulator environment. (a) The Passing scenario, where agents maximize their reward by passing the ball as many times as possible. (b) The Keep-Away scenario, where agents maximize their reward by keeping the ball away from the opponent for as long as possible. (c) The 3dSSL framework, which deploys an RCSS Simulator and $J$ agents, all of which connect to the deployed simulator. Both the simulator and agents remain connected to the framework, which informs agents of what actions they will execute upon the environment. Agents then report their new observations.

6.2 KiloBots

The KiloBots environment [57] is a set of local continuous observation- and action-space scenarios with simulated physics, emulating the KiloBot robot [66]. Each robot has a diameter of 3 centimeters and moves using two vibration motors. The environment is a great testbed for swarm learning algorithms, whose policies can later be applied to physical KiloBots. The scenarios, shown in Fig. 5, include:

•
Push – Agents push an object to a target location.
•
Assemble – Agents push and assemble multiple objects together.
•
Segregate – Agents push and separate multiple objects apart.

Each KiloBot observes its own pose, as well as the position of the obstacles in the environment (although not their shape or orientation). KiloBots can communicate with the two other closest agents. The central observation concatenates all agent positions, and thus scales linearly with the amount of agents in the environment. The swarm must coordinate to complete the task as fast as possible. In the Segregation and Assembly tasks, a divide and conquer approach is ideal, where the swarm splits in multiple groups.
6.3 3d Soccer Simulation League

The 3D Soccer Simulation League is part of the RoboCup initiative [67], an annual international robotics competition, whose goal is to have a team of fully-autonomous physical robots winning a soccer match against the world-champion human team, using FIFA standard rules, by the year 2050. It is a complex multi-agent environment where two teams of humanoid simulated robots play a ten-minute soccer match using realistic rules. Each team is comprised of eleven NAO robots [68] with multiple different models, each with different physical characteristics. Each agent perceives the environment through local partial observations consisting on spherical coordinates of other elements in the environment. These include landmarks like the goal posts, field lines, other agents, and the ball. Agents then act upon their own local joints, by sending commands to the environment simulator.

Table 1
The hyper-parameters used for the tests conducted in this section. This table lists the amount of agents $J$ , the amount of workers $N$ , the future reward discount $\gamma$ , the learning rate $\eta$ , the amount of communication channels (CC), the layer size modifier $x$ , and the amount of training episodes. Critic and actor networks used two fully connected hidden layers of $20x$ and $10x$ nodes activated with a ReLU function. When using DME, the central critic had used two convolutional layers of $40x$ and $20x$ nodes activated with a ReLU function. The communicator network used a single hidden layer with $10x$ nodes activated with a ReLU function, and an output layer of CC nodes, activated with a hyperbolic tangent function. The non-received message $rc_{0}$ default value is all zeros

Environment	$J$	$N$	$\gamma$	$\eta$	CC	$x$	Episodes
POC Hidden Reward	4	3	0.90	$10^{-4}$	20	2	$2\times 10^{5}$
POC Traffic Simulator	40	3	0.10	$10^{-4}$	1	2	$2\times 10^{3}$
POC Pursuit	3	12	0.95	$5\times 10^{-5}$	10	6	$2\times 10^{5}$
POC Navigation	2	3	0.95	$10^{-4}$	20	4	$1.5\times 10^{5}$
KiloBots Light	17	12	0.95	$10^{-4}$	2	4	$3\times 10^{5}$
KiloBots Join	17	12	0.95	$10^{-4}$	2	4	$4.5\times 10^{5}$
KiloBots Split	17	12	0.95	$10^{-4}$	2	4	$4\times 10^{5}$
3dSSL Passing	3	6	0.90	$10^{-3}$	0	4	$1.6\times 10^{3}$
3dSSL Keep-Away	3	6	0.90	$10^{-3}$	0	4	$6\times 10^{3}$

Table 2

Comparison of multiple algorithms and a heuristic baseline for the tested environments. The average reward (over 100 test runs) obtained by the team after each algorithm trained for the amount of episodes shown in Table 1. Each algorithm tries to maximize the obtained reward, and the best results are shown in bold. A3C3 is able to match or surpass the baseline heuristic in all environments

	A3C	A3C2	A3C3	Heur.	COMA	PPO	QMIX	VDN
POC H.R.	24	67	84	71	14	27	19	19
POC T.S.	$-$ 93	$-$ 16	$-$ 14	$-$ 13	$-$ 257	$-$ 122	$-$ 255	$-$ 259
POC Pursuit	$-$ 42	$-$ 19	$-$ 19	$-$ 27	$-$ 50	$-$ 50	$-$ 50	$-$ 44
POC Nav.	0.94	1.97	1.99	2	0.68	0.93	0.38	0.92

Using low-level controllers that abstract simple tasks, like kicking or walking, has been the de facto standard in the league, controllers which are then used by high-level decision-making modules. In other words, agents have a set of behaviors which are chosen according to their strategy. The behavior acts upon the agent’s joints, and the strategy defines which behavior to execute and with which parameters.

The 3D Soccer Simulation League features multiple game types, as shown in Fig. 6. One is the Passing game, where agents pass the ball between them, while receiving a reward for each successful pass. Another game type is the Keep-Away game, where three players keep the ball away from a single opponent for as long as possible, getting points for each pass and a large penalty if the opponent reaches the ball.

We propose the 3d Soccer Simulation Learning (3dSSL) framework, as shown in Fig. 6c, which models the 3D Soccer Simulation League with a Gym interface, and allows multiple environments to run simultaneously with fault-tolerance mechanisms enabled. It supports parallel learning with asynchronous DL or genetic algorithms, through socket communication implemented within the FCPortugal3D team [69], an award winning team in the League.

Agents observe the estimated positions of all players and the ball, as well as the estimated location the ball will stop at, their orientation, and the distances of all players to the ball. All estimated information is sampled by the mechanisms used in FCPortugal3D. The action-space is no longer a low-level continuous joint-control, but instead a discrete selection of high-level behaviors used in the team. The behaviors used were standing, where an agent simply stands in the same place, getting up, used when the agent falls on the ground, kicking to an ally, with the choice of which teammate to kick the ball towards, and using a kick for the adequate distance to the target, moving to position, where each agent has a specific default location based on the team’s formation. Agents may fall when changing behaviors abruptly, and all behaviors take multiple time-steps to complete. 3dSSL also provides additional information to be used by learning algorithms or on tests, but which is not normally accessible by agents in regular play. This includes the agent’s real position, orientation, acceleration, as well as the ball’s real current position. This information can be used during the learning phase of algorithms that benefit from data that are usually unaccessible to agents.

7. Results

A3C3’s performance is evaluated in the three multi-agent environment suites described in the previous section. The first suite comprises multiple partially-observable environments, and requires agents to share information in order to successfully complete the task. The second is a swarm simulator, where many simple agents must coordinate to achieve the task. The third is a humanoid soccer simulator, where a team must learn a high-level strategy based on low-level behaviors to win the game.

In the conducted tests, the initial choice of network architecture was based on prior experience in deep reinforcement learning [60], where actor and critic networks had one to three layers of width 10 to 120. A grid-parameter search [22] was then conducted to find the best width (we tested layers of 10, 20, 40, 80, 120 nodes) and an adequate activation function (Logistic, Rectifier Linear Units [70], or Exponential Linear Units [71]). We chose, for each environment, the simplest architecture we found that consistently converged to proper policies. The Glorot initializer [72] is used with default parameters to compute the networks’ initial weights, the Adam optimizer [73] with default parameters to optimized them, and an entropy weight $\beta=$ 0.01 to discourage premature convergence [42]. We chose the highest learning rate $\eta$ that reliably allowed convergence, and a future reward discount factor $\gamma$ dependent on the horizon of each scenario and its importance of future rewards. A list of the final hyper-parameters for our tests is shown in Table 1.

Figure 7.

Color-coded $\text{CC}=$ 20 protocol learned in the hidden reward environment. Five different colored messages exemplify messages sent at different locations. Two messages in the same location are also showcased, demonstrating the case where the Reward zone has not yet been found and when the agent has found it and is signaling its position. It is clear that the learned communication protocol allows agents to signal others when the target has been found, which in turn allows the remainder of the team to converge on that location and successfully complete the task.

7.1 State-of-the-art comparison in the POC suite

This section evaluates A3C3 against other algorithms, using the environments described in the POC suite. All algorithms were executed with similar parameters, to achieve a fair basis of comparison, and were trained for the same amount of steps. A3C and PPO are single-agent DL algorithms, and are run as independent agents, as if each agent were in a single-agent non-stationary environment. COMA, QMIX, and VDN are multi-agent DL algorithms that rely on a centralized critic to achieve coordination in a team. An ablation of A3C3 without a centralized critic, called A3C2 [65], is also evaluated here.

The results are shown in Table 2. For all environments in the POC Suite, A3C3 is consistently able to overcome partial-observability and learn optimal policies with relevant communication protocols. It also consistently outperforms other similar algorithms without specific over-tuning. Independent algorithms like A3C and PPO are unable to make agents coordinate and underperform in all scenarios. COMA, QMIX, and VDN also behave poorly, and show poor scalability in the Traffic Simulator environment. These algorithms are based in Q-Learning, and often perform worse than single-agent actor-critic algorithms like A3C or PPO. Only A3C2 and A3C3 achieve successful results in these environments, being the only algorithms that learn communication protocols between agents. A3C3’s centralized critic improves the speed and quality of achieved policies.

A3C3 either outperformed or matched our heuristic baselines. These baselines were achieved with a hard-coded centralized controller that output a joint-action for the entire team, with access to all agent observations. In the Traffic Simulator and Navigation environments, which require little map exploration, A3C3’s behavior closely follows the baseline. In the Hidden Reward and Pursuit environments, A3C3 optimized a better map exploration policy than the baseline, and completed the challenges faster, thus achieving a higher score.

7.2 Communication analysis in the POC suite

This section analyses the learned communication protocols in the partially-observable suite. While the protocol may not be fully understood by humans, it is possible to extract some interesting conclusions on what agents are actually communicating and how those messages can be interpreted by teammates.

For easier analysis, we convert the protocol channels into colors (each channel representing one of three RGB values composing a pixel). For example, a $\text{CC}=$ 21 protocol can be represented in seven pixels. When the channels are not a multiple of three, the last pixel does not have all Red, Green or Blue components.

Figure 7 shows a protocol learned in the Hidden Reward environment. Four messages are shown, representing the message an agent outputs in a corresponding location on the map. For instance, the top message is the message sent by an agent to its teammates when at the top right corner of the map. The policy learned by the team consisted on agents forming a vertical line and moving across the $X$ axis to explore the map. The learned communication protocol facilitates this by having distinct patterns across the $Y$ axis, so that agents can clearly understand which rows are being explored. The differences on the $X$ axis are more subtle, but are noticeable enough that agents can align in the proper formation during exploration. Figure 7 also shows a clear difference between the exploration (when the target zone has not been found) and the exploitation (when the target zone is known) protocols. This difference represents the alert signal agents emit when the reward zone has been found. When receiving an alert message, agents know to converge to the sent coded-coordinates, instead of maintaining their exploration protocol.

Figure 8.

The evolution of two separate $\text{CC}=$ 1 protocols learned in the traffic simulator environment, using two separate agent populations. The plots represent the output message’s single channel value across training episodes, when two agents stand at an intersection. The values are averaged over possible intersection situations (vehicles behind or in front of the agent), and split based on whether the agent intends to turn or move forward. In Population A, agents broadcast a value close to 1 when they wish to move forward at an intersection, and a value close to $-$ 1 when they wish to turn. In Population B, the opposite happens, and agents signal 1 when they desire to turn. This is equivalent to a real world vehicle that turns on a blinker light at an intersection. Both Populations’ protocols are shown here to demonstrate that artificial populations may learn different protocols, some of which may not be intuitive to humans.

Figure 8 shows the evolution of two protocols learned in the Traffic environment. Both populations learn to clearly distinguish the intention of turning or going forward. Interestingly, different populations learn opposite protocols, where population A signals their intention of going forward, and population B signals their intention of turning.

Figure 9.

The $\text{CC}=$ 20 protocol in the navigation environment, (a) before and (b) after convergence has been achieved. The plots represent the average value of each channel in a message as the agent’s $X$ coordinate changes. Initially, we can observe that the communication protocol is chaotic and random, agents are just communicating noise to each other. By the end of the training phase, we see clear correlations between the agent’s $X$ -axis position and the sent message. A similar behavior is seen for the $Y$ -axis, and this allows agents to infer each other’s positions based on communication and decide which agent covers which target, successfully completing the navigation task.

Figure 9 showcases, for the Navigation environment, the difference between the initial random protocol that agents use, and the final protocol that is used after policies converge. Initially, each channel behaves without much correlation regarding the agent’s location. In other words, agents cannot properly decide which agent covers which beacon, as they cannot interpret the other agents’ locations from their messages. However, the protocol evolves in a way that agent coordinates can be extracted from their sent messages. When convergence is achieved, some channels have very obvious correlations with the $X$ coordinate of the agents’ locations (and a similar behavior is seen for the $Y$ coordinate). This in turn allows agents to cooperate and coordinate their coverage of the beacons.

Figure 10.

Color-coded $\text{CC}=$ 10 protocol learned in the predator/prey environment. On the right, a predator (red) can see the map around itself, and broadcasts messages based on whether a prey (green) is at that location. On the left, messages are arranged geographically, representing an agent’s output message when a prey is found in the corresponding location of its local observation. An example is shown, where a prey is found in the upper right corner of the predator’s vision range, and the predator broadcasts the corresponding message.

Figure 11.

The evolution of policies in the three tasks of the KiloBots environment. The plots represent the average reward and standard deviation (over $N$ workers) obtained by the team across training steps, using different architectures to handle permutations in the Centralized Critic. Each team tries to maximize the obtained reward, and by the end of the training phase, all architectures achieve the maximum reward and are able to successfully complete the task. Some architectures enable the teams to reach this point earlier in training, thanks to their permutation-invariant properties, than the original fully connected architecture, which has a harder time adapting to large amounts of agents.

Figure 10 shows a protocol learned in the Predator/Prey environment. Messages are shown and arranged geographically, representing the message an agent outputs when a prey is found at a corresponding location in its local observation, while the agent is at the center of the map. The center position is the predator itself, and no prey can be there. The policy learned by the team shows distinct patterns for each location, which alerts other predators to the prey’s location. At this point, predators then converge and surround the prey until it is captured. This effectively allows agents to handle the partial-observability of the environment.

7.3 Permutation invariance in the KiloBots suite

This section describes the tests conducted to evaluate the scalability of A3C3 with large teams in the KiloBots environment, described in Section 6.2. The continuous action-space of the KiloBots is discretized into a simple set of actions, including rotation, stopping and moving forward. Communication is geographically limited, and agents can only broadcast their messages to the two closest agents.

The performance of teams is evaluated by comparing different methods to handle the large amount of agents, as described in Section 5. A3C3’s centralized critic concatenates the observations of all $J=$ 17 agents in the swarm, and can benefit from the permutation invariant architecture. The tests include an unordered method, with the original fully-connected A3C3 architecture used on other environments; an ordered method, where agent observations are pre-processed and ordered by an average of their $X$ and $Y$ coordinates; and the mean Eq. (1), max Eq. (2), and softmax Eq. (5) DME methods, for permutation invariance through convolutional architectures.

Figure 11 shows the evaluation conducted on all five architectures and on all three scenarios. The analysis of the performance of the teams shows that all architectures can converge to successful solutions. In other words, even with a large amount of states, the centralized critic can learn an accurate value estimation for the team. Pre-processing and ordering the input helped in two of the three scenarios, which further demonstrates that it is not a generally applicable solution. However, the DME methods accelerated the learning phase by a large amount in all scenarios, and shortened the time taken for the teams to achieve optimal policies. The mean and softmax DME show the best results, and the mean DME is the fastest due to simpler optimizations.

Table 3
The average reward (over $100$ test runs) obtained by three different teams in the 3dSSL Framework. A3C3 was trained for the amount of episodes shown in Table 1, and is compared against the hard-coded FCPortugal3D team and a team of random agents. A3C3 tries to maximize the obtained reward and surpasses the original FCPortugal3D implementation in the Passing scenario. However, it is not as effected in the Keep-Away Scenario, where the heuristic baseline carefully calculates the expected time for the enemy to reach the ball and uses that information to better adjust and improve its behavior

	Random	A3C3	Heuristic
Passing scenario	1.5	8.5	7.9
Keep-Away scenario	$-$ 9	$-$ 3	$-$ 1.3

7.4 High-level strategy learning in the 3dSSL framework

This section describes the tests conducted in the 3dSSL framework, described in Section 6.3. As previously stated, a sub-set of FCPortugal3D’s behaviors was used, such that A3C3 learns a high-level policy that takes advantage of the low-level behaviors already existing in the team.

The team’s performance is shown in Table 3, where agents learn effective strategies to complete each scenario. In the Passing challenge, agents group together such that passes are quicker and more accurate. On the Keep-Away scenario, agents do the opposite, and remain in corners of the field, such that the opponent takes a long time to reach the ball. They successfully keep the ball away from the opposite team until the episode reaches a given time-limit. When compared with the hard-coded policies used by the team in competition, the learned policies matched the performance of the Passing scenario, but did not outperform FCPortugal3D’s Keep-Away behavior, likely due to a smaller flexibility on the available behaviors.

Interestingly, agents learn to take advantage of the implementation details of the scenarios, and exploited the environments. In the Passing challenge, agents converged in the center of the map and learned to alternately move towards and away from the ball, which would make the environment score a successful pass (as a different agent was now closer to the ball). In the Keep-Away challenge, agents discovered that the opponent would not move beyond the field lines, so they converged to a policy where they just kicked the ball outside the field and would no longer need to move. Both scenarios were fixed with regards to these exploitations, by correctly evaluating a successful pass, and preventing the ball from leaving the field. After doing so, agents learn to perform actual passes and to play a fair game of keep-away soccer.

8. Conclusion

This manuscript proposes A3C3, a multi-agent deep reinforcement learning algorithm. It uses a centralized critic to implicitly share information during the learning stage, and can benefit from a permutation invariant network architecture to scale to large team sizes. A3C3 agents learn a communication protocol, where they share relevant information to team members. The protocols learned by each population are unique, and agents from different populations may be unable to coordinate with one another. All source-code, experiments, environments, and hyper-parameters have been published at https://github.com/bluemoon93/A3C3.

A3C3 is shown to outperform other state-of-the-art algorithms, and is able to match or outperform centralized heuristic controllers in a wide variety of environments. Agents learn high-level policies to complete the task, and their communication protocol is analyzed. Our analysis shows that agents share local information, allowing them to compensate for partial observability. A3C3 is also shown to be able to scale to swarm-size teams, and can be integrated with existing software agents to derive strategies from available behaviors. Given its robustness and generality, A3C3 represents a solid first step into multi-agent reinforcement learning, where independent agents learn to communicate with each other and coordinate to complete a cooperative task.

Future work directions include a distributed implementation protocol where agents and worker threads can be run on different machines, which will further increase the scalability of A3C3. Recursive neural networks can also be explored, such that agents can further handle partially-observable environments and also learn multi-step communication protocols. Exploring the effects of noise in the communication protocols can also help demonstrate the robustness of A3C3.

Footnotes

Acknowledgments

This work is supported by: Portuguese Foundation for Science and Technology (FCT) under grant PD/BD/113963/2015; Institute of Electronics and Informatics Engineering of Aveiro – IEETA (UIDB/ 00127/2020); Artificial Intelligence and Computer Science Laboratory – LIACC (UIDB/00027/2020).

References

Yang

Cappelle

Ruichek

El Bagdouri

. Multi-object tracking with discriminant correlation filter based deep learning tracker. Integrated Computer-Aided Engineering. 2019; 26(3): 273-284.

Yim

Zhang

Lamping

Mao

. Distributed control for 3D metamorphosis. Autonomous Robots. 2001; 10(1): 41-56.

Skobelev

Simonova

Zhilyaev

. Using multi-agent technology for the distributed management of a cluster of remote sensing satellites. Complex Systems: Fundamentals & Applications. 2016; 90: 287.

Mannion

Duggan

Howley

. An experimental review of reinforcement learning algorithms for adaptive traffic signal control. In: Autonomic Road Transport Support Systems. Springer, 2016. pp. 47-66.

Gutierrez Soto

Adeli

. Multi-agent replicator controller for sustainable vibration control of smart structures. J Vibroeng. 2017; 19: 4300-4322.

Korczak

Hernes

Bac

. Risk avoiding strategy in multi-agent trading system. Computer Science and Information Systems (FedCSIS), 2013 Federated Conference on. IEEE, 2013, pp. 1131-1138.

Baarslag

Fujita

Gerding

Hindriks

Ito

Jennings

, et al. Evaluating practical negotiating agents: Results and analysis of the 2011 international competition. Artificial Intelligence. 2013; 198: 73-103.

Lin

Descamps

Gaud

Hilaire

Koukam

. Multi-Agent System for intelligent Scrum project management. Integrated Computer-Aided Engineering. 2015; 22(3): 281-296.

Lau

Pereira

Melo

Neves

Figueiredo

. Ciber-rato: A simulation environment for mobile and autonomous robots. Electrónica e Telecomunicações. 2002; 3(7): 647-650.

10.

Silver

Hubert

Schrittwieser

Antonoglou

Lai

Guez

, et al. A general reinforcement learning algorithm that masters chess, shogi, and Go through self-play. Science. 2018; 362(6419): 1140-1144.

11.

Schrom-Feiertag

Stubenschrott

Regal

Schrammel

Settgast

. Using cognitive agent-based simulation for the evaluation of indoor wayfinding systems. arXiv preprint arXiv161102459, 2016.

12.

Szymanezyk

Duckett

Dickinson

. Agent-based crowd simulation in airports using games technology. In: Transactions on Computational Collective Intelligence VIII. Springer, 2012, pp. 192-213.

13.

Hernandez-Leal

Kaisers

Baarslag

de Cote

. A survey of learning in multiagent environments: Dealing with non-stationarity. arXiv preprint arXiv170709183, 2017.

14.

Albrecht

Stone

. Autonomous agents modelling other agents: A comprehensive survey and open problems. Artificial Intelligence. 2018; 258: 66-95.

15.

Hernandez-Leal

Kartal

Taylor

. Is multiagent deep reinforcement learning the answer or the question? A brief survey. arXiv preprint arXiv181005587, 2018.

16.

Kober

Bagnell

Peters

. Reinforcement learning in robotics: A survey. The International Journal of Robotics Research. 2013; 32(11): 1238-1274.

17.

Bowling

Veloso

. Rational and Convergent Learning in Stochastic Games. In: Proceedings of the 17th International Joint Conference on Artificial Intelligence – Volume 2. IJCAI’01. San Francisco, CA, USA: Morgan Kaufmann Publishers Inc., 2001, pp. 1021-1026. Available from: http//dl.acm.org/citation.cfm?id=1642194.1642231.

18.

Lau

Reis

. FC Portugal-high-level coordination methodologies in soccer robotics. In: Robotic Soccer. InTech, 2007.

19.

Velagapudi

Prokopyev

Scerri

Sycara

. A token-based approach to sharing beliefs in a large multiagent team. In: Optimization and Cooperative Control Strategies. Springer, 2009, pp. 417-429.

20.

Simões

Lau

Reis

. Multi-agent Neural Reinforcement-Learning System with Communication. In: Rocha

Adeli

Reis

Costanzo

, editors. New Knowledge in Information Systems and Technologies. Springer International Publishing, 2019, pp. 3-12.

21.

Wang

. Artificial neural network. In: Interdisciplinary Computing in Java Programming. Springer, 2003, pp. 81-100.

22.

Torres

Galicia

Troncoso

Martínez-Álvarez

. A scalable approach based on deep learning for big data time series forecasting. Integrated Computer-Aided Engineering. 2018; (Preprint): 1-14.

23.

Bui

Hoang

Martínez-Álvarez

Ngo

PTT

Hoa

Pham

, et al. A novel deep learning neural network approach for predicting flash flood susceptibility: A case study at a high frequency tropical storm area. Science of The Total Environment. 2020; 701: 134413.

24.

Rafiei

Adeli

. NEEWS: a novel earthquake early warning model using neural dynamic classification and neural dynamic optimization. Soil Dynamics and Earthquake Engineering. 2017; 100: 417-427.

25.

Nabian

Meidani

. Deep learning for accelerated seismic reliability analysis of transportation networks. Computer-Aided Civil and Infrastructure Engineering. 2018; 33(6): 443-458.

26.

Rafiei

Adeli

. A new neural dynamic classification algorithm. IEEE Transactions on Neural Networks and Learning Systems. 2017; 28(12): 3074-3083.

27.

Koziarski

Cyganek

. Image recognition with deep neural networks in presence of noise – dealing with and taking advantage of distortions. Integrated Computer-Aided Engineering. 2017; 24(4): 337-349.

28.

Manzanera

Meles

Leenders

Renken

Pagani

Arnaldi

, et al. Scaled subprofile modeling and convolutional neural networks for the identification of Parkinson’s disease in 3d nuclear imaging data. International Journal of Neural Systems. 2019; 29(9): 1950010.

29.

Molina-Cabello

Luque-Baena

López-Rubio

Thurnhofer-Hemsi

. Vehicle type detection by ensembles of convolutional neural networks operating on super resolved images. Integrated Computer-Aided Engineering. 2018; (Preprint): 1-13.

30.

Liang

. Image-based post-disaster inspection of reinforced concrete bridge systems using deep learning with Bayesian optimization. Computer-Aided Civil and Infrastructure Engineering. 2019; 34(5): 415-430.

31.

Zhang

Chen

. Zernike-moment measurement of thin-crack width in images enabled by dual-scale deep learning. Computer-Aided Civil and Infrastructure Engineering. 2019; 34(5): 367-384.

32.

Bang

Park

Kim

. Encoder-decoder network for pixel-level road crack detection in black-box images. Computer-Aided Civil and Infrastructure Engineering. 2019; 34(8): 713-727.

33.

Zhao

Zhou

. Automatic pixel-level multiple damage detection of concrete structure using fully convolutional network. Computer-Aided Civil and Infrastructure Engineering. 2019; 34(7): 616-634.

34.

Gao

Kong

Mosalam

. Deep leaf-bootstrapping generative adversarial network for structural image data augmentation. Computer-Aided Civil and Infrastructure Engineering. 2019; 34(9): 755-773.

35.

Csáji

. Approximation with artificial neural networks. Faculty of Sciences, Etvs Lornd University, Hungary. 2001; 24: 48.

36.

Ansari

Cherian

Caicedo

Naulaers

De Vos

Van Huffel

. Neonatal seizure detection using deep convolutional neural networks. International Journal of Neural Systems. 2019; 29(4): 1850011.

37.

Antoniades

Spyrou

Martin-Lopez

Valentin

Alarcon

Sanei

, et al. Deep neural architectures for mapping scalp to intracranial EEG. International Journal of Neural Systems. 2018; 28(8): 1850009.

38.

Nguyen

Kashani

Ngo

Bordas

. Deep neural network with high-order neuron for the prediction of foamed concrete strength. Computer-Aided Civil and Infrastructure Engineering. 2019; 34(4): 316-332.

39.

Arulkumaran

Cully

Togelius

. Alphastar: An evolutionary computation perspective. In: Proceedings of the Genetic and Evolutionary Computation Conference Companion, 2019, pp. 314-315.

40.

Berner

Brockman

Chan

Cheung

Debiak

Dennison

, et al. Dota 2 with Large Scale Deep Reinforcement Learning. arXiv preprint arXiv191206680, 2019.

41.

Sutton

Barto

, et al. Introduction to reinforcement learning. vol. 135, MIT press Cambridge, 1998.

42.

Mnih

Badia

Mirza

Graves

Lillicrap

Harley

, et al. Asynchronous methods for deep reinforcement learning. In: International conference on machine learning, 2016, pp. 1928-1937.

43.

Ortega-Zamorano

Jerez

Gómez

Franco

. Layer multiplexing FPGA implementation for deep back-propagation learning. Integrated Computer-Aided Engineering. 2017; 24(2): 171-185.

44.

Schulman

Wolski

Dhariwal

Radford

Klimov

. Proximal policy optimization algorithms. arXiv preprint arXiv170706347, 2017.

45.

Foerster

Farquhar

Afouras

Nardelli

Whiteson

. Counterfactual multi-agent policy gradients. In: Thirty-Second AAAI Conference on Artificial Intelligence, 2018.

46.

Sukhbaatar

Fergus

, et al. Learning multiagent communication with backpropagation. In: Advances in Neural Information Processing Systems, 2016, pp. 2244-2252.

47.

Claus

Boutilier

. The Dynamics of Reinforcement Learning in Cooperative Multiagent Systems. In: Proceedings of the Fifteenth National/Tenth Conference on Artificial Intelligence/Innovative Applications of Artificial Intelligence. AAAI ’98/IAAI ’98. Menlo Park, CA, USA: American Association for Artificial Intelligence; 1998. pp. 746-752. Available from: http//dl.acm.org/citation.cfm?id=295240.295800.

48.

Sunehag

Lever

Gruslys

Czarnecki

Zambaldi

Jaderberg

, et al. Value-Decomposition Networks For Cooperative Multi-Agent Learning Based On Team Reward. In: Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems. AAMAS ’18. Richland, SC: International Foundation for Autonomous Agents and Multiagent Systems; 2018, pp. 2085-2087. Available from: http//dl.acm.org/citation.cfm?id=3237383.3238080.

49.

Rashid

Samvelyan

de Witt

Farquhar

Foerster

Whiteson

. QMIX: Monotonic Value Function Factorisation for Deep Multi-Agent Reinforcement Learning. CoRR. 2018abs/1803.11485. Available from: http//arxiv.org/abs/1803.11485.

50.

Mordatch

Abbeel

. Emergence of grounded compositional language in multi-agent populations. In: Thirty-Second AAAI Conference on Artificial Intelligence, 2018.

51.

Williams

. Simple statistical gradient-following algorithms for connectionist reinforcement learning. Machine Learning. 1992 May; 8(3): 229-256. Available from: 10.1007/BF00992696.

52.

Das

Kottur

Moura

Lee

Batra

. Learning cooperative visual dialog agents with deep reinforcement learning. In: Proceedings of the IEEE International Conference on Computer Vision, 2017, pp. 2951-2960.

53.

Lazaridou

Peysakhovich

Baroni

. Multi-agent cooperation and the emergence of (natural) language. Proceedings of the International Conference on Learning Representations, 2017.

54.

Simões

Lau

Reis

. Multi-agent Double Deep Q-Networks. In: Oliveira

Gama

Vale

Lopes Cardoso

, editors. Progress in Artificial Intelligence. Lecture Notes in Computer Science, vol. 10423. Springer International Publishing, 2017, pp. 123-134.

55.

Bernstein

Givan

Immerman

Zilberstein

. The complexity of decentralized control of Markov decision processes. Mathematics of Operations Research. 2002; 27(4): 819-840.

56.

Foerster

Assael

de Freitas

Whiteson

. Learning to Communicate with Deep Multi-Agent Reinforcement Learning. CoRR. 2016abs/1605.06676, Available from: http//arxiv.org/abs/1605.06676.

57.

Gebhardt

Daun

Schnaubelt

Neumann

. Learning robust policies for object manipulation with robot swarms. In: 2018 IEEE International Conference on Robotics and Automation (ICRA). IEEE, 2018, pp. 7688-7695.

58.

Saska

Chudoba

Precil

Thomas

Loianno

Tresnak

, et al. Autonomous deployment of swarms of micro-aerial vehicles in cooperative surveillance. In: Unmanned Aircraft Systems (ICUAS), 2014 International Conference on. IEEE, 2014, pp. 584-595.

59.

Reyes

Ventura

. Performing multi-target regression via a parameter sharing-based deep network. International Journal of Neural Systems. 2019; 1950014-1950014.

60.

Simões

Lau

Reis

. Guided Deep Reinforcement Learning in the GeoFriends2 Environment. In: IJCNN 18: International Joint-Conference on Neural Networks, 2018, pp. 375-381.

61.

Ducatelle

Di Caro

Förster

Bonani

Dorigo

Magnenat

, et al. Cooperative navigation in robotic swarms. Swarm Intelligence. 2014; 8(1): 1-33.

62.

Gebhardt

GHW

Hüttenrauch

Neumann

. Using M-Embeddings to Learn Control Strategies for Robot Swarms. Submitted to Swarm Intelligence. submitted; Available from: https://www.ias.informatik.tu-darmstadt.de/uploads/Team/GregorGebhardt/UsingMEmbeddingsToLearnControlStrategiesForRobotSwarms.pdf.

63.

Theano Development Team. Theano: A Python framework for fast computation of mathematical expressions. arXiv e-prints. 2016 May; abs/1605.02688. Available from: http//arxiv.org/abs/1605.02688.

64.

Abadi

Agarwal

Barham

Brevdo

Chen

Citro

, et al.. TensorFlow: Large-Scale Machine Learning on Heterogeneous Systemss 2015. Software available from tensorflow.org. Available from: https://www.tensorflow.org/.

65.

Simões

Lau

Reis

. Multi-Agent Deep Reinforcement Learning with Emergent Communication. In: 2019 International Joint Conference on Neural Networks (IJCNN). IEEE, 2019.

66.

Rubenstein

Ahler

Hoff

Cabrera

Nagpal

. Kilobot: A low cost robot with scalable operations designed for collective behaviors. Robotics and Autonomous Systems. 2014; 62(7): 966-975.

67.

Kitano

Asada

Kuniyoshi

Noda

Osawa

. Robocup: The robot world cup initiative. In: Proceedings of the first international conference on Autonomous agents. ACM, 1997, pp. 340-347.

68.

Shamsuddin

Ismail

Yussof

Zahari

Bahari

Hashim

, et al. Humanoid robot NAO: Review of control and motion exploration. In: 2011 IEEE International Conference on Control System, Computing and Engineering, IEEE, 2011, pp. 511-516.

69.

Reis

Lau

. FC Portugal team description: RoboCup 2000 simulation league champion. In: Robot Soccer World Cup. Springer, 2000, pp. 29-40.

70.

Nair

Hinton

. Rectified linear units improve restricted boltzmann machines. In: Proceedings of the 27th international conference on machine learning (ICML-10), 2010, pp. 807-814.

71.

Clevert

Unterthiner

Hochreiter

. Fast and accurate deep network learning by exponential linear units (elus). International Conference for Learning Representations, 2016.

72.

Glorot

Bengio

. Understanding the difficulty of training deep feedforward neural networks. In: Teh

Titterington

, editors. Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics. vol. 9 of Proceedings of Machine Learning Research. Chia Laguna Resort, Sardinia, Italy: PMLR, 2010, pp. 249-256. Available from: http//proceedings.mlr.press/v9/glorot10a.html.

73.

Kingma

. Adam: A method for stochastic optimization. 3rd International Conference for Learning Representations, San Diego, 2015.