ifaamas [AAMAS ’23]Proc. of the 22nd International Conference on Autonomous
Agents and Multiagent Systems (AAMAS 2023)May 29 – June 2, 2023 London, United
KingdomA. Ricci, W. Yeoh, N. Agmon, B. An (eds.) 2023 2023 767 1 Tsinghua
University, 2 Shanghai Artificial Intelligence Laboratory, 3 Tongji
University, 4 Shanghai Qi Zhi Institute
∗ Equal Contribution † Corresponding Author

# Asynchronous Multi-Agent Reinforcement Learning for
Efficient Real-Time Multi-Robot Cooperative Exploration

Chao Yu1,2∗, Xinyi Yang1∗, Jiaxuan Gao1∗, Jiayu Chen1,2, Yunfei Li1, Jijia
Liu3, Yunfei Xiang1,
Ruixin Huang1, Huazhong Yang1, Yi Wu1,2,4†, Yu Wang1†
<EMAIL_ADDRESS>
###### Abstract.

We consider the problem of cooperative exploration where multiple robots need
to cooperatively explore an unknown region as fast as possible. Multi-agent
reinforcement learning (MARL) has recently become a trending paradigm for
solving this challenge. However, existing MARL-based methods adopt _action-
making steps_ as the metric for exploration efficiency by assuming all the
agents are acting in a fully synchronous manner: i.e., _every_ single agent
produces an action _simultaneously_ and _every_ single action is executed
_instantaneously_ at each time step. Despite its mathematical simplicity, such
a synchronous MARL formulation can be problematic for real-world robotic
applications. It can be typical that different robots may take slightly
different wall-clock times to accomplish an atomic action or even periodically
get lost due to hardware issues. Simply waiting for every robot being ready
for the next action can be particularly _time-inefficient_. Therefore, we
propose an asynchronous MARL solution, _Asynchronous Coordination Explorer
(ACE)_ , to tackle this real-world challenge. We first extend a classical MARL
algorithm, multi-agent PPO (MAPPO), to the asynchronous setting and
additionally apply action-delay randomization to enforce the learned policy to
generalize better to varying action delays in the real world. Moreover, each
navigation agent is represented as a team-size-invariant CNN-based policy,
which greatly benefits real-robot deployment by handling possible robot lost
and allows bandwidth-efficient intra-agent communication through low-
dimensional CNN features. We first validate our approach in a grid-based
scenario. Both simulation and real-robot results show that ACE reduces over
10% actual exploration time compared with classical approaches. We also apply
our framework to a high-fidelity visual-based environment, Habitat, achieving
$28\%$ improvement in exploration efficiency.

###### Key words and phrases:

Multi-Agent Reinforcement Learning, Asynchronous Decision Making, Cooperative
Exploration

##  1\. Introduction

Exploration is a fundamental task for building intelligent robot systems,
which has been applied in many application domains, including rescue Kleiner
et al. (2006), autonomous driving Bresson et al. (2017), drone von Stumberg et
al. (2017), and mobile robots Rubio et al. (2019). In this paper, we consider
a multi-robot cooperative exploration task, where multiple homogeneous robots
simultaneously explore an unknown spatial region in a cooperative fashion.
Learning the optimal cooperative strategies can be challenging due to the
existence of multiple robots. These robots must effectively distribute the
exploration workload so that they can always navigate towards different
spatial regions to avoid trajectory conflicts, which accordingly leads to a
remarkably higher exploration efficiency than the single-robot setting.

Multi-agent reinforcement learning (MARL) has been a trending approach to
tackle this cooperative exploration challenge. RL-based methods directly learn
neural policies end to end by interacting with a simulated environment for
policy improvement. Compared with planning-based solutions Savinov et al.
(2019); Burgard et al. (2005); Umari and Mukhopadhyay (2017) which require
non-trivial implementation heuristics and expensive inference computation at
execution time, RL-based methods Savinov et al. (2019); Chen et al. (2019)
provide strong representation capabilities of complex strategies and
negligible inference overhead once the policies are trained.

Classical multi-agent RL algorithms typically adopt a synchronous algorithmic
framework, i.e., all the agents are making actions at the same time, and all
the actions will be executed immediately at each time step, leading to the
next action-making step for future actions. This process is mathematically
formulated as a decentralized Markov decision process, which is widely adopted
in multi-agent RL literature. Although such a mathematical framework is simple
and elegant, it can be problematic for real-world multi-robot exploration
tasks. For real robot systems, each actual action is never atomic and may take
varying times to finish. These action delays can be more severe due to
unexpected network communication traffic or hardware failure. Simply following
the synchronous setting, i.e., waiting until every robot is ready before
making new actions, can be particularly real-time inefficient. Therefore, an
ideal RL framework for real-world use should be asynchronous, i.e., whenever
an agent finishes action execution, it should immediately generate the next
action, and the learned strategy should effectively enable such an
asynchronous action-making process.

In this paper, we propose a novel asynchronous multi-agent RL-based solution,
_Asynchronous Coordination Explorer (ACE)_ , to tackle the real-world multi-
robot exploration task. We first extend a classical MARL algorithm, multi-
agent PPO (MAPPO), to the asynchronous setting to effectively train the multi-
agent exploration policy, and additionally leverage an action-delay
randomization technique to enable better simulation to real-world
generalization. Moreover, we design a communication-efficient Multi-tower-CNN-
based Policy (MCP) for each agent. In MCP, a CNN module is applied to each
agent’s local information to extract features, and a fusion module combines
each agent’s features to produce an action. During execution time, efficient
intra-agent communication can be achieved via directly exchanging low-
dimensional features extracted by the weight-sharing CNN module. Another
benefit of MCP is to tackle varying team sizes, which may occur when agents go
offline in real-world applications.

We conduct experiments in a grid-based multi-room scenario both in simulation
and our real-world multi-robot laboratory, where strategies learned by ACE
significantly outperform both classical planning-based methods and neural
policies trained by synchronous RL methods. In particular, _ACE reduces
$10.07\%$ real-world exploration time_ than the synchronous RL baseline and
_reduces $33.86\%$ real-world exploration time_ than the fastest planning-
based method with 2 Mecanum steering robots. Besides, we extend ACE to a
vision-based environment, Habitat, verifying the effectiveness of the
asynchronous training mechanism when applied to more complicated environments.
More demonstrations can be seen on our website:
https://sites.google.com/view/ace-aamas.

##  2\. Related Work

###  2.1. Cooperative Exploration

Multi-agent cooperative exploration is an important task for building
intelligent mobile robot systems. There are a large number of works developing
planning-based methods for this problem Dornhege and Kleiner (2013); Umari and
Mukhopadhyay (2017); Yamauchi (1997a), but they typically rely on manually
designed heuristics Wurm et al. (2008); Cohen (1996); Burgard et al. (2005)
and are limited in expressiveness to learn more complex cooperation
strategies. Another popular line of research is deep MARL-based methods which
leverage the expressiveness power of neural networks to learn non-trivial
cooperative exploration skills Wang et al. (2021); Zhu et al. (2021); Wang* et
al. (2020); Long et al. (2020); Yang et al. (2020); Wang et al. (2020a). Note
that most existing MARL-based methods assume synchronous action execution
among all the agents or consider atomic actions, which we believe is due to
the synchronous design of most simulated RL environments. However, such
synchronous design does not reflect the real-world multi-agent systems, where
agents take actions at different real times due to network delay and
unexpected hardware take-downs. We propose an _asynchronous_ MARL exploration
framework in this work to better match real-world applications. Omidshafiei et
al. (2015) considers an asynchronous decision-making mechanism for large-scale
problems and proposes an improved Monte Carlo Search method to solve this
problem. A concurrent work formulates a set of asynchronous multi-agent actor-
critic methods that allow agents to directly optimize asynchronous policies
Xiao et al. (2022), while we design an asynchronous MARL training framework
combined with action-delay randomization. We also notice a recent trend of
developing asynchronous simulation Jia et al. (2020); Yao et al. (2021), which
we hope can further accelerate the advances in applying MARL methods to the
real world.

###  2.2. Sim2real Transfer

It is often challenging to directly deploy policies trained in simulation to
the real world since there is always a mismatch between simulation and
reality. Domain randomization is a simple but effective technique to fill the
reality gap, which creates a variety of simulated environments with randomized
properties such as physical dynamics Tobin et al. (2017a); Peng et al. (2017)
and visual appearances Tobin et al. (2017b); OpenAI et al. (2018), and tries
to train RL that can perform well among all of them. We also adopt the idea of
domain randomization, and randomly delay the execution of each agent in
simulation to model the uncertain delay between policy computation and actual
action execution in the real world. The action delay technique is also adopted
in other domains such as model-based RL Chen et al. (2021a) and reactive RL
Travnik et al. (2018).

###  2.3. Multi-Agent Communication

Most works in MARL only consider perfect communication where agents can
receive messages from all other agents Zhang et al. (2021); Godoy et al.
(2015); Ding et al. (2018), but the requirements on communication bandwidth
and transmission rate are costly. Recent works have begun to focus on learning
efficient communication. Foerster et al. (2016); Sukhbaatar et al. (2016)
learn communication protocols in limited-bandwidth communication channels.
Some works propose to learn which agent to communicate with using attention
mechanisms Jiang and Lu (2018); Niu et al. (2021) or weight-based schedulers
Kim et al. (2019). In our work, we focus on how to efficiently communicate
with other agents with limited information to maintain perfect decision
performance. We propose an extraction module to obtain essential features from
high-dimensional information, which is much more efficient than delivering
observation information directly.

###  2.4. Size-Invariant Representation

Attention mechanism Vaswani et al. (2017b) is widely used in RL policy
representation to capture object-level information Duan et al. (2017); Wang et
al. (2018); Zhang et al. (2019b, a) and represent relations Zambaldi et al.
(2018); Savinov et al. (2019). In MARL, attention-based policy can also be
applied for generalization to an arbitrary number of input entities Long et
al. (2020); Wang et al. (2020b); Hsu et al. (2020); Duan et al. (2017); Jiang
et al. (2018); Ryu et al. (2020); Wang et al. (2018). There are some other
generalization settings in MARL, such as other-play Hu et al. (2020a),
population-based training Osindero et al. (2017); Jaderberg et al. (2019) and
zero-shot team formation Baker (2020). In addition, some training techniques
are used to better deal with varying sizes of agents, such as evolutionary
learning Long et al. (2020); Czarnecki et al. (2018) and curriculum learning
Chen et al. (2021b). In our work, we design a Multi-tower-CNN-based Policy
based on an attention mechanism to tackle varying team sizes. Parameter-
sharing is a commonly used paradigm for varying team sizes in MARL with
homogeneous agents, which is also adopted in this work. It learns an identical
policy for each agent and helps to reduce nonstationarity and improve training
efficiency Chu and Ye (2017); Terry et al. (2020).

##  3\. Preliminary

###  3.1. Task Setup

We study the task of real-time multi-robot cooperative exploration, where a
team of robots aims to explore an unknown environment exhaustively as fast as
possible. Robots can transmit local information to each other to avoid
duplicate exploration for better efficiency. The real-time multi-robot task is
with an asynchronous nature, i.e., different robots do not take actions and
receive the next-step observations at the same time. A real robot often
requires non-fixed time to execute an action, and unexpected hardware failure
can cause random delays. Besides, under the standard bi-level control setting
in robot navigation Juliá et al. (2012); Yamauchi (1997a); Yu et al. (2021a);
Umari and Mukhopadhyay (2017), each action is a goal position to reach and
typically requires varying number of atomic steps to accomplish, thus
exacerbating the asynchronous issue. The asynchronous execution is not
considered by classical multi-agent reinforcement learning (MARL) works. It is
typically assumed all agents take actions at the same _action-making step_ and
do not take the action execution time into account. In the traditional MARL
literature Yu et al. (2021c), the task is usually formulated as a
decentralized partially observable Markov decision process (Dec-POMDP), which
is unable to capture the asynchronous property in our setting.

###  3.2. Problem Formulation

Figure 1. Comparison of _asynchronous_ and _synchronous_ action making.

We model the asynchronous multi-agent cooperative exploration task as a
decentralized partially observable Semi-Markov decision process (Dec-POSMDP)
Omidshafiei et al. (2015) with shared rewards. We adopt a modular action
execution scheme Chaplot et al. (2020); Loquercio et al. (2021) which consists
of bi-level actions for robust deployment in real-world robot systems. A macro
action (MA), i.e., global goal, is generated in the action-making step.
Several atomic actions, i.e., execution actions, are followed to perform under
the guidance of the MA.

To avoid notation ambiguity, we use $p^{(i)}$ to denote a parameter $p$
related to the i-th agent, and $\bar{p}=(p^{(1)},p^{(2)},\cdots,p^{(n)})$ to
denote joint parameters for multiple agents thereafter. A Dec-POSMDP is
defined by a set of elements $\langle
D,\bar{U},\bar{B},P,\bar{R}^{\tau}\rangle$.
$D=\langle\bar{S},\bar{A},\bar{\Omega},\bar{O},\bar{R},P,n,\gamma\rangle$
defines the decentralized partially observable Markov decision processes (Dec-
POMDP), where $\bar{S}$ is the joint state space, $\bar{A}$ is joint atomic
action space, $\bar{\Omega}$ is the observation space,
$O^{(i)}(o^{(i)}|s,a^{(i)})$ denotes the observation probability function for
agent $i$, $\bar{R}:\bar{S}\times\bar{A}\rightarrow\mathbb{R}$ is the joint
reward function, $n$ is the number of agents, $P$ is the state transition
probability. $\bar{U}$ is joint macro-action space. A macro action $u^{(i)}$
is a high-level policy that can generate a sequence of atomic actions
$a_{t}\sim u^{(i)}(H_{t}^{(i)})$ for any $t$ when $u^{(i)}$ is activated,
where $H_{t}^{(i)}$ is the individual action-observation history till $t$.
$\bar{B}$ denotes the stop condition of MA and $B^{(i)}(u^{(i)})$ is
represented as a set of action-observation histories of an agent $i$. If
$H_{t}^{(i)}\in B^{(i)}(u^{(i)}_{t})$ holds, $u_{t}^{(i)}$ terminates and the
agent generates a new MA. $\bar{R}^{\tau}$ is the macro joint reward function:
$\bar{R}^{\tau}(\bar{s},\bar{u})=\mathbb{E}\left[\sum_{t=0}^{\bar{\tau}_{end}}\gamma^{t}\bar{R}(\bar{s}_{t},\bar{a}_{t})|\bar{a}_{t}\sim\bar{u}(\bar{H}_{t})\right]$
where $\bar{\tau}_{end}=\min_{t}\\{t:H_{t}^{(i)}\in B^{(i)}(u^{(i)})\\}$.

The solution of a Dec-POSMDP is a joint high-level decentralized policy
$\bar{\phi}=(\phi^{(1)},\cdots,\phi^{(n)})$ where each $\phi^{(i)}$ produces
an MA $\phi^{(i)}(H_{t}^{(i)})\in U^{(i)}$ given individual action-observation
history $H_{t}^{(i)}$. In the beginning of an episode, an initial MA is
computed as: $u_{t_{0}}^{(i)}=\phi^{(i)}(H_{t_{0}}^{(i)})$. At action-making
step $k>0$, the agent generates a new MA
$u_{t_{k}}^{(i)}=\phi^{(i)}(H_{t_{k}}^{(i)})$ if the stop condition is met,
i.e. $H_{t_{k}}^{(i)}\in B^{(i)}(u_{t_{k-1}}^{(i)})$. Otherwise, the agent
continues to use the previous MA: $u_{t_{k}}^{(i)}=u_{t_{k-1}}^{(i)}$. In the
time range $[t_{k},t_{k+1})$, the agent interacts with the environment with
atomic actions sampled from MA: $a_{t}^{(i)}\sim u^{(i)}(H_{t}^{(i)})$.
Finally, the goal of Dec-POSMDP is to maximize the accumulative discounted
reward:
$\mathbb{E}\left[\sum_{k=0}^{\infty}\gamma^{t_{k}}\bar{R}^{\tau}(\bar{s}_{t_{k}},\bar{u}_{t_{k}})|\bar{\phi},\bar{s}_{0}\right]$
where $t_{0}=0$ and $t_{k}=\min_{t}\\{t>t_{k-1}:H_{t}^{(i)}\in
B^{(i)}(u^{(i)}_{t_{k-1}})\\}$ for $k\geq 1$. A more detailed definition can
be found in Omidshafiei et al. (2015).

In our _asynchronous_ setting, $t$ is the real time, not the discrete time
step as in common _synchronous_ RL. Our setting is more time-efficient and
robust to hardware faults. Take a 2-agent case as an example (see Fig. 1), in
the synchronous setting, the agents can only transmit data (blue and green
arrows) and perform policy inference (orange arrow) after both of them have
finished the previous action execution. The system execution speed is bottle-
necked by the agent with the longest execution time. Worse still, the whole
system will get stuck if one agent goes offline unexpectedly. By contrast,
agents take actions in a distributed manner in an asynchronous setting. Each
agent can request data from other agents and conduct policy inference
immediately after it finishes its own action execution. This asynchronous
setting is more time-efficient for multi-agent exploration tasks, and will not
be blocked by dynamic changes such as agents going offline.

###  3.3. Connection to Conventional MARL

In the conventional MARL literature Yu et al. (2021c), the problem formulation
is typically under decentralized partially observable Markov decision process
(Dec-POMDP), which assumes synchronized actions. In this work, we also focus
on the multi-agent setting and assume a shared reward function and dynamic
transitions. However, different from synchronous MARL which assumes all agents
execute actions simultaneously, we consider the asynchronous nature in the
practical multi-robot scenarios.

We will adapt a popular MARL algorithm, Multi-Agent Proximal Policy
Optimization (MAPPO) Yu et al. (2021c), from the conventional setting to our
asynchronous setting. Conventional MAPPO follows the Centralized Training and
Decentralized Execution (CTDE) paradigm, in which agents make decisions with
individual observations and update the joint policy with global information in
a centralized manner. Under the framework of Dec-POMDP, MAPPO requires all
agents taking actions synchronously at each discrete time step, and the state
transits according to actions from all agents: $s_{t}\sim
P(\cdot|s_{t-1},\bar{a}_{t-1})$. It aims to find a joint policy $\bar{\pi}$
that maximizes the accumulated discounted reward
$\mathbb{E}\left[\sum_{t=0}^{\infty}\gamma^{t}\bar{R}(s_{t},\bar{a}_{t})|a_{t}^{(i)}\sim\pi^{(i)}(H_{t}^{(i)})\right]$.
Different from MAPPO, Async-MAPPO is designed for the asynchronous setting,
where there are no centralized environment steps.

##  4\. Methodology

To better model the asynchronous nature of real-world multi-agent exploration
problems, we present Asynchronous Coordination Explorer (ACE). ACE consists of
3 major components: (1) Async-MAPPO for MARL training, (2) action-delay
randomization for zero-shot generalization in the real world, and (3) multi-
tower-CNN-based policy representation for efficient communication.

###  4.1. Async-MAPPO

We extend an on-policy MARL algorithm MAPPO Yu et al. (2021b) to our
asynchronous setting, which we call Async-MAPPO. The pseudo-code of Async-
MAPPO is shown in Algo. 1. Compared with the setting of MAPPO, both policy
execution and data collection are not necessarily time-aligned among different
agents, and we implement the asynchronous action-making and replay buffer as
follows.

  1. $\bullet$

We design a bi-level execution scheme. In ACE, agents perform atomic actions
under the guidance of global goals (macro actions). Instead of receiving the
reward, local observation, and states immediately after executing an atomic
action, Async-MAPPO accumulates the reward between action-making steps and
only takes observation and states at each macro action.

  2. $\bullet$

We implement asynchronous buffer insertion, in contrast to the synchronous
scheme in original MAPPO as shown in Fig. 1. The original MAPPO assumes
synchronous execution of all the agents; in each time step, all the agents
take actions simultaneously, and the trainer waits for all the new transitions
before inserting them into a centralized data buffer for RL training. In
Async-MAPPO, different agents may not take actions at the same time (some
agents may even get stuck and cannot return new observations at all), which
makes it infeasible for the trainer to collect transitions in the original
synchronous manner. Therefore, we allow each agent to store its own transition
data in a separate cache and periodically push the cached data to the
centralized data buffer. We can then run the standard MAPPO training algorithm
over this buffer.

1 Initialize the policy $\pi$;

2 while  _$step\leq step_{max}$_ do

3 set data buffer $D=\\{\\}$;

4 for  _$i=1$ to $batch\\_size$_ do

5 Reset the environment;

6 Create $N$ empty caches $C=[[],\dots,[]]$;

7 for  _$t=1$ to $T$_ do

8 for  _all agents $i=1$ to $N$_ do

9 if  _agent $i$ replans macro action_ then

10 $b\leftarrow$ agent $i$’s $b$-th macro actions;

11 $s_{b}^{(i)}\leftarrow State,o_{b}^{(i)}\leftarrow Observation$;

12
$C_{i}+=[s_{b-1}^{(i)},o_{b-1}^{(i)},u_{b-1}^{(i)},\hat{R}_{b}^{\tau(i)},s_{b}^{(i)},o_{b}^{(i)}]$;

13 $p_{b}^{(i)}=\pi(o_{b}^{(i)})$;

14 Update macro action $u_{b}^{(i)}\sim p_{b}^{(i)}$;

15

16 end if

17 Execute atomic action $a_{t}^{(i)}\sim u_{b}^{(i)}$;

18

19 end for

20

21 end for

22 Compute reward-to-go and insert data into $D$;

23

24 end for

25 Update $\pi$ on MAPPO loss;

26

27 end while

Algorithm 1 Async-MAPPO

###  4.2. Action-Delay Randomization

When training in traditional simulators, agents can always take execution
steps synchronously without considering different action execution costs.
Moreover, real-world action delays such as hardware failure and network
blocking are not simulated. These problems cause a large gap for deploying
trained agents from simulation to reality. To reduce this gap, we apply
action-delay randomization during simulation. In the end of each action-making
step, we force each agent to wait for a random period from $3$ to $5$
execution steps in grid-based environments, and from $10$ to $15$ execution
steps in Habitat before querying the next macro action.

Figure 2. Overview of Asynchronous Coordination Explorer (ACE).

###  4.3. Multi-Tower-CNN-Based Policy

The Multi-tower-CNN-based Policy (MCP) is utilized to generate macro actions,
i.e., global goals in ACE. As illustrated in Fig. 3, MCP consists of 3 parts,
i.e., a CNN-based local feature extractor, an attention-based relation
encoder, and an action decoder.

The local feature extractor is a weight-sharing 3-layer CNN and can extract a
$G\times G\times 4$ feature embedding from each agent’s $S\times S\times 7$
local information, which includes one obstacle channel, one explored region
channel, one-hot location channel, one trajectory channel to represent the
history trace, and three agent-view channels of the agent’s local observation.

The agents transmit extracted feature embedding instead of the raw local
information, which greatly reduces communication traffic by $1-\frac{G\times
G\times 4}{S\times S\times 7}=1-\frac{4}{7\alpha^{2}}$ times where
$\alpha=S/G$. For example, we adopt $G=5$ in grid-based environments, thus the
communication traffic reduces $\sim 97\%$ in $S=25$ maps and $\sim 93\%$ in
$S=15$ maps.

The relation encoder aims to aggregate the extracted feature maps from
different agents to better capture the intra-agent interactions. In team-based
exploration, an agent should not only spot undiscovered areas but also inter-
teammates’ movement for better scheduling among agents. We adopt a simplified
Transformer Vaswani et al. (2017b) block as the team-size-invariant relation
encoder. Inspired by the vision transformer model Dosovitskiy et al. (2020),
we apply multi-head cross-attention Vaswani et al. (2017a) to derive a single
team-size-invariant representation of size $G\times G\times 4$, as shown in
Fig. 3.

Finally, the action decoder predicts the agent’s policy from the aggregated
representation as a multi-variable Categorical distribution to select a grid
cell $g$ from a plane as the global goal $(u_{x},u_{y})$. Note that in
Habitat, in order to produce accurate global goals, we adopt a spatial action
space with three separate action heads, i.e., two discrete region heads for
choosing a grid cell $g$, which are the same as grid-based environments, and
two additional continuous point heads for outputting a coordinate
$(\Delta_{x},\Delta_{y})$, indicating the relative position of the global goal
within the selected region $g$. Details of MCP in Habitat can be found in
Appendix A.2.

Figure 3. Workflow of _Multi-tower-CNN-based Policy_ (MCP), including a CNN-
based local feature extractor, a relation encoder, and an action decoder.

###  4.4. Overall Architecture

As shown in Fig. 2, each agent observes the local information and requests the
latest feature embedding from other agents, which is output by the weight-
sharing local feature extractor, at each action-making step. That is, agents
only need to transfer the low-dimensional feature embedding, instead of the
entire local information. The multi-tower-CNN-based policy, which is trained
by Async-MAPPO, generates the next macro action, i.e., global goal, at each
action-making step, and the agent performs path planning on the local map
according to the global goal, outputting the atomic action at each time step.
Note that agents could go offline in multi-agent tasks due to unexpected
network communication traffic or hardware failure.

Figure 4. The illustration of the grid-based simulator and real-world robot
system.

##  5\. Environment Details

Here we give details of the environments we adopted in this work, including
the environment setting, the observation space and the action space of ACE, as
well as the designed reward function.

###  5.1. Environment Setting

Grid-based scenario: As shown in Fig. 4, we implement a multi-agent
exploration task based on the GridWorld simulator Chevalier-Boisvert et al.
(2018), which was originally designed for synchronous settings. We consider
two different map sizes, which are $15\times 15$ with $4\sim 9$ random rooms
and $25\times 25$ with $4\sim 25$ random rooms. All the agents are uniform
randomly spread over the map in the beginning. The local information of each
robot is fed to the RL-trained policy or planning-based methods to generate a
global goal and $A^{\star}$ algorithm is utilized to plan 5 atomic actions on
the local map to follow the global goal.

We also set up a $15\times 15$ real-world grid map which is the same as the
grid-based simulation, and each grid is 0.31m long, as shown in Fig. 4. Our
robots are equipped with Mecanum steering and an NVIDIA Jetson Nano processor.
The locations and poses of robots are tracked by OptiTrack cameras and the
Motive motion capture software. After training a policy in the grid-based
simulator under $15\times 15$ map with random rooms, we directly deploy it to
the real-world robot system. Each real robot executes in a distributed and
asynchronous manner. The robot adopts a request-send mechanism to obtain the
newest feature embedding of other agents through ROS topic upon finishing all
atomic actions.

Habitat: We adopt map data from the Gibson dataset Xia et al. (2018) while the
visual signals and dynamics are simulated by Habitat Savva et al. (2019). We
follow the same environment configuration in Yu et al. (2021d) and use a pre-
trained neural SLAM model to predict the robot pose and the local map. Full
details of Habitat can be found in Appendix A. We also make sure that the
birthplaces of agents are set to be close enough, i.e., agents are randomly
scattered in a circle with a radius of 1 meter, so that the exploration task
would be sufficiently challenging for learning.

###  5.2. Observation Space

The input of RL-trained MCP is an $S\times S$ image with 7 channels, where $S$
is the max size of the map. The channels represent obstacles, the explored
mask, the agent location, the trajectory, and three $H\times W$ agent-view.
Note that each agent only maintains its locally observed information, which is
memory and communication-efficient for real-world deployment.

###  5.3. Action Space

The overall exploration framework is hierarchical, with a global goal (macro
action) followed by several atomic actions towards the goal. The action of the
policy is to generate a global goal $(u_{x},u_{y})$ chosen in the map,
representing a discrete grid in grid-based environments or a continuous
location in Habitat Savva et al. (2019). The available atomic actions are
moving forward, turning left, and turning right provided by the simulator.

###  5.4. Reward Function

The team-based reward function is the sum of the coverage reward, success
reward, and overlap penalty. Let $Ratio^{t}$ denote the total coverage ratio
at time $t$, $Exp_{a}^{t}$ be the explored map by agent $a$ and $Exp^{t}$
denote the merged explored map by all agents. Both $Exp^{t}$ and $Exp^{t}_{a}$
are sets of explored areas. The reward terms are defined as follows.

  * •

Coverage Reward: It is proportional to the size of the newly discovered region
by the team $Exp^{t}\backslash Exp^{t-1}$.

  * •

Success Reward: Agent $a$ gets a success reward of $Ratio^{t}$ when $C\%$
coverage ratio is reached, which $C=98$ in the grid-like simulator and $C=90$
in Habitat111Maps in Habitat are harder than in the grid-based simulator,
leading to differences in the success rate threshold..

  * •

Overlap Penalty: The overlap penalty $r_{overlap}$ is designed to penalize
repetitive exploration and encourage cooperation with others. It is defined as

$\begin{array}[]{l}r_{overlap}=\left\\{\begin{array}[]{l}\begin{array}[]{l}-A_{overlap}\times
0.01,\;Ratio^{t}\;<0.9\\\ 0,\;Ratio^{t}\geq
0.9\end{array}\end{array}\right.\\\ \end{array},$

where $A_{overlap}$ is the increment of the overlapped explored area between
agent $a$ and other agents. The overlapped area between agent $a$ and agent
$w$ is $Overlap^{t}_{a,w}=Exp^{t}_{a}\cap Exp^{t}_{w}$, and
$A_{overlap}=\sum_{w\in\\{1,\cdots,n\\}\backslash\\{a\\}}Overlap^{t}_{a,w}\backslash
Overlap^{t-1}_{a,w}$.

Map Size | Methods | Synchronous Action Making | Asynchronous Action Making
---|---|---|---
Time $\downarrow$ | Overlap $\downarrow$ | Coverage $\uparrow$ | ACS $\uparrow$ | Time $\downarrow$ | Overlap $\downarrow$ | Coverage $\uparrow$ | ACS $\uparrow$
$15\times 15$ | Utility | 40.81(0.94) | 0.45(0.02) | 1.00(0.00) | 88.80(0.08) | 35.75(0.99) | 0.42(0.01) | 1.00(0.00) | 90.01(0.14)
Nearest | 25.44(0.53) | 0.17(0.01) | 1.00(0.00) | 91.60(0.17) | 22.59(0.34) | 0.17(0.01) | 1.00(0.00) | 92.47(0.17)
RRT | 28.86(0.99) | 0.18(0.01) | 1.00(0.00) | 91.46(0.03) | 25.85(0.36) | 0.19(0.01) | 1.00(0.00) | 92.36(0.08)
APF | 24.95(0.76) | 0.17(0.01) | 1.00(0.00) | 91.57(0.39) | 21.56(0.43) | 0.17(0.01) | 1.00(0.00) | 92.52(0.37)
Voronoi | 48.57(3.64) | 0.33(0.01) | 1.00(0.00) | 86.43(0.33) | 42.94(4.05) | 0.20(0.01) | 1.00(0.00) | 88.16(0.57)
MAPPO | 24.75(0.45) | 0.08(0.02) | 1.00(0.00) | 92.39(0.19) | 21.92(0.90) | 0.09(0.01) | 1.00(0.00) | 93.18(0.17)
| ACE | 21.76(0.79) | 0.07(0.00) | 1.00(0.00) | 92.54(0.21) | 18.66(0.79) | 0.07(0.01) | 1.00(0.00) | 93.39(0.14)
$25\times 25$ | Utility | 189.38(0.93) | 0.46(0.05) | 0.93(0.01) | 139.31(1.56) | 183.71(1.59) | 0.50(0.04) | 0.95(0.01) | 144.64(1.42)
Nearest | 113.48(1.73) | 0.24(0.01) | 1.00(0.00) | 161.40(0.63) | 99.52(2.00) | 0.24(0.01) | 1.00(0.00) | 166.53(0.91)
RRT | 120.15(2.29) | 0.20(0.01) | 1.00(0.00) | 164.35(0.64) | 105.64(1.69) | 0.21(0.01) | 1.00(0.00) | 168.33(0.27)
APF | 101.41(0.78) | 0.23(0.01) | 1.00(0.00) | 162.46(0.64) | 90.00(1.48) | 0.23(0.01) | 1.00(0.00) | 166.82(0.81)
Voronoi | 131.65(0.41) | 0.23(0.01) | 1.00(0.00) | 160.92(0.33) | 117.14(0.13) | 0.20(0.01) | 1.00(0.00) | 165.35(0.27)
MAPPO | 90.15(1.08) | 0.08(0.01) | 1.00(0.00) | 168.54(0.58) | 82.55(2.70) | 0.09(0.01) | 1.00(0.00) | 171.72(0.27)
| ACE | 83.34(0.44) | 0.06(0.00) | 1.00(0.00) | 170.03(0.49) | 74.36(2.93) | 0.06(0.00) | 1.00(0.00) | 173.16(0.72)
Table 1. Performances of different methods under 2-agent synchronous and asynchronous settings in the grid-based simulator. | Metrics | Utility | Nearest | RRT | APF | ACE
---|---|---|---|---|---|---
3 $\Rightarrow$ 2 | Time $\downarrow$ | 139.33(1.79) | 76.53(1.16) | 81.86(1.14) | 74.80(2.11) | 67.50(1.42)
Overlap $\downarrow$ | 0.48(0.03) | 0.30(0.01) | 0.27(0.00) | 0.32(0.01) | 0.22(0.00)
Coverage $\uparrow$ | 0.94(0.01) | 1.00(0.00) | 1.00(0.00) | 1.00(0.00) | 1.00(0.00)
ACS $\uparrow$ | 110.56(1.11) | 126.03(0.39) | 126.75(0.18) | 125.15(0.58) | 128.49(0.37)
4 $\Rightarrow$ 3 | Time $\downarrow$ | 96.15(0.46) | 53.68(1.01) | 55.33(0.82) | 52.26(0.68) | 48.88(1.82)
Overlap $\downarrow$ | 0.40(0.03) | 0.36(0.00) | 0.34(0.01) | 0.38(0.01) | 0.33(0.07)
Coverage $\uparrow$ | 0.92(0.01) | 1.00(0.00) | 1.00(0.00) | 1.00(0.00) | 1.00(0.00)
ACS $\uparrow$ | 73.28(1.55) | 84.05(0.57) | 84.08(0.41) | 83.60(0.41) | 84.78(0.77)
Table 2. Performance of different methods with decreased team size on $25\times 25$ maps in the grid-based simulator. Methods | Utility | Nearest | RRT | APF | MAPPO | ACE
---|---|---|---|---|---|---
Time(s) | 60.25(0.16) | 38.72(0.12) | 55.89(0.24) | 52.64(0.23) | 28.48(0.12) | 25.61(0.10)
Table 3. Running time of different methods when the coverage ratio reaches
100% in the real-world robot system.

##  6\. Experiment Results

###  6.1. Training Details

In the simulation, every RL policy is trained with $50M$ steps in the grid-
based simulator and $100M$ steps in Habitat over 3 random seeds. All results
are averaged over a total of 300 testing episodes (100 episodes per random
seed). As for real-world testing, we randomly generate $10$ maps of size
$15\times 15$ and test $5$ times for each map. In synchronous action-making
cases, agents perform action-making at the same time and wait for all other
agents to finish. In asynchronous action-making cases, agents do not wait for
others and perform both macro and atomic actions independently.

###  6.2. Evaluation Metrics

The most important metric in our experiment is _Time_ , which is the running
time for the agents to reach a $C\%$ coverage ratio. We report wall-clock time
in the real world, and report an estimated statistical running time in
simulation: turning left or right takes $0.5s$; stepping forward takes $1s$.
Policy inference time is fixed to $0.1s$ for both RL and planning-based
methods thus the results can better reflect the difference between
asynchronous and synchronous settings.

We also consider 3 additional statistics metrics to capture different
characteristics of a particular exploration strategy. These metrics are only
for analysis, and we primarily focus on Time as our performance criterion.

  * •

_Accumulative Coverage Score_ (ACS): The overall exploration progress
throughout an episode computed as $A_{T}=\int_{t=0}^{T}Ratio^{t}$, where $T$
is the max running time. Higher _ACS_ implies faster exploration.

  * •

_Coverage_ : the _final_ ratio of explored area when an episode terminates.
Higher implies more exhaustive exploration.

  * •

_Overlap_ : the ratio of the overlapped region explored by _multiple_ agents
to the current explored area when C% coverage is reached. Lower _Overlap_
implies better credit assignment.

All metrics are calculated with the running time $t$, i.e., the estimated
statistical time in simulation and wall-clock time in the real world. Each
score is reported as ”mean (standard deviation)”.

###  6.3. Baselines

We consider 4 popular planning-based competitors, including a utility-
maximizing method (_Utility_) Juliá et al. (2012), a search-based nearest-
frontier method (_Nearest_) Yamauchi (1997a), a rapid-exploring-random-tree-
based method (_RRT_) Umari and Mukhopadhyay (2017), and an artificial
potential field method (_APF_) Yu et al. (2021a) which applies resistance
forces among agents as a cooperation mechanism. Note that APF is a multi-agent
baseline while the other three are commonly used for single-agent tasks.
Moreover, all baselines use global information to do planning after every
macro action. Different from ACE, they are not learning-based and are all
designed for asynchronous execution.

###  6.4. Grid-Based Scenario

####  6.4.1. Main Results

Experiment results with 2 agents in the grid-based simulator under synchronous
and asynchronous training are provided in Table 1. In both settings, ACE
outperforms planning-based baselines with $\geq 10\%$ less Time, full
Coverage, and higher ACS. Although APF encourages cooperation, its Overlap is
still higher than ACE, demonstrating ACE’s superiority in discovering
efficient cooperation strategies. Comparing ACE with MAPPO, which is trained
in a synchronous manner, ACE demonstrates similar $ACS$ to MAPPO with less
Time and Overlap, which indicates the robustness of ACE to realistic execution
with randomized action delay. Results of 3 agents can be found in appendix D.

####  6.4.2. Generalization to Agent Lost

We further consider another setting where the team size decreases within an
episode on map size $25\times 25$ to emulate the real-world scenarios with
hardware failure and to examine whether our learned policies can generalize to
these extreme cases during execution. “$N_{1}\Rightarrow N_{2}$” denotes a
scenario with $N_{1}$ agents at the beginning and only $N_{2}$ agents alive
after $50\%$ coverage. As shown in Table 2, ACE demonstrates $10\%$ less Time
than other baselines and obtains the highest ACS and lowest Overlap,
indicating ACE’s effective zero-shot adaptation to extreme situations where
some agents go offline.

####  6.4.3. Real-World Robot System

In this part, we present the running time of different methods with 2 agents
in real-world exploration tasks on $15\times 15$ maps, which are running in an
asynchronous manner. The deployment pipeline is described in Sec. 5.1. As
shown in Table 3, two RL-based methods, MAPPO and ACE, outperform the
planning-based baselines with a large margin according to the total
exploration time. In particular, ACE reduces 33.86% real-world exploration
time than the fastest planning-based method _Nearest_. Besides, ACE reduces
10.07% running time compared with MAPPO, proving that combining action-delay
randomization with Async-MAPPO indeed improves the efficiency of multi-agent
exploration.

###  6.5. Habitat Results

####  6.5.1. Main Results

We extend ACE to a vision-based environment, Habitat. Table 4 shows the
performance of different methods under 2-agent asynchronous action-making
settings. Despite having higher Overlap due to more exhaustive exploration,
ACE outperforms planning-based baselines with $\geq 28\%$ less Time, higher
Coverage and ACS. Compared with synchronous MAPPO, ACE still shows higher
Coverage and ACS with less Time, demonstrating the effectiveness of ACE in
more complicated vision-based tasks.

####  6.5.2. Generalization to Agent Lost

We also consider the setting of decreased team sizes in Habitat, and we follow
the same experimental setup as for the grid-based simulations. Table 5 shows
the performance of different methods with decreased team size (2 $\Rightarrow$
1). ACE demonstrates $5.3\%$ less Time than other baselines and obtains the
highest Coverage and ACS with comparable Overlap, which indicates the ACE’s
ability to generalize to agent lost.

Methods | Time $\downarrow$ | Overlap $\downarrow$ | Coverage $\uparrow$ | ACS $\uparrow$
---|---|---|---|---
Utility | 273.83(37.80) | 0.84(0.03) | 0.83(0.08) | 186.17(17.43)
Nearest | 220.25(30.23) | 0.59(0.04) | 0.94(0.03) | 180.05(7.37)
RRT | 177.29(17.16) | 0.63(0.06) | 0.97(0.02) | 187.35(6.86)
APF | 218.45(24.64) | 0.67(0.04) | 0.94(0.02) | 188.62(7.67)
MAPPO | 133.23(17.72) | 0.68(0.09) | 0.97(0.01) | 201.33(7.98)
ACE | 127.62(8.55) | 0.78(0.07) | 0.98(0.01) | 213.81(9.33)
Table 4. Performance of different methods under 2-agent asynchronous action-making settings in Habitat. Methods | Time $\downarrow$ | Overlap $\downarrow$ | Coverage $\uparrow$ | ACS $\uparrow$
---|---|---|---|---
Utility | 281.09(32.25) | 0.48(0.05) | 0.84(0.08) | 153.02(12.38)
Nearest | 309.76(9.83) | 0.40(0.03) | 0.85(0.05) | 149.43(4.55)
RRT | 260.31(27.92) | 0.35(0.03) | 0.92(0.02) | 155.23(6.04)
APF | 309.88(6.63) | 0.42(0.01) | 0.79(0.01) | 143.54(0.83)
MAPPO | 262.92(19.84) | 0.35(0.04) | 0.90(0.03) | 160.90(6.68)
ACE | 246.38(19.26) | 0.36(0.03) | 0.92(0.03) | 164.32(8.23)
Table 5. Performance of different methods with decreased team size in Habitat.

###  6.6. Ablation Studies

In this section, we analyze the sensitivity of communication size and action-
delay randomization based on the grid-like simulator through ablation studies.

####  6.6.1. Sensitivity Analysis of Communication Size

We study the exploration performances in different communication traffic
scenarios, including:

  * •

No Comm.: The attention-based relation encoder is removed. Therefore, agents
can only use their own local information to perform macro actions. This is the
lower bound of different communication traffic.

  * •

Comm. (0.25x): The number of channels output by the CNN local feature
extractor is set to $1$, which is a quarter of the original $4$ channels.

  * •

Comm. (0.5x): The number of CNN local feature extractor output channels is set
to $2$.

  * •

Perf. Comm.: Agents use merged observation from all the agents as the input of
the CNN local feature extractor.

Table 6 summarizes the performances on different communication traffic with 2
agents on $25\times 25$ maps. More communication between agents generally
leads to better exploration efficiency, as is shown by the decreasing Time and
increasing ACS from “No Comm.” to “Comm. (0.25x)”, “Comm. (0.5x)” and “Perf.
Comm.”. Moreover, the behavior metric Overlap in these four scenarios shows
better cooperation efficiency with more communication. Note that ACE performs
even better than “Perf. Comm.” with strictly less communication, demonstrating
the effectiveness of the feature embedding extracted from our CNN policy for
decision-making.

Methods | Time $\downarrow$ | Overlap $\downarrow$ | Coverage $\uparrow$ | ACS $\uparrow$
---|---|---|---|---
No Comm. | 159.26(2.18) | 0.37(0.01) | 0.93(0.01) | 151.87(1.82)
Comm. (0.25x) | 110.92(1.33) | 0.11(0.01) | 0.99(0.00) | 167.60(0.71)
Comm. (0.5x) | 83.77(1.38) | 0.09(0.00) | 1.00(0.00) | 170.90(0.60)
Perf. Comm. | 75.62(0.84) | 0.06(0.01) | 1.00(0.00) | 173.15(0.53)
ACE | 74.36(2.93) | 0.06(0.00) | 1.00(0.00) | 173.16(0.72)
Table 6. Performance with different communication traffic. Intervals | Time $\downarrow$ | Overlap $\downarrow$ | Coverage $\uparrow$ | ACS $\uparrow$
---|---|---|---|---
Rand (1-10) | 60.24(0.35) | 0.51(0.00) | 1.00(0.00) | 82.44(0.31)
Rand (5-10) | 56.41(1.51) | 0.47(0.01) | 1.00(0.00) | 83.46(0.35)
Rand (1-5) | 55.69(1.23) | 0.43(0.01) | 1.00(0.00) | 83.57(0.45)
ACE (3-5) | 48.88(1.82) | 0.33(0.07) | 1.00(0.00) | 84.78(0.77)
Table 7. Performance of different action-delay intervals.

####  6.6.2. Sensitivity Analysis of Action-Delay Randomization

We further study the impact of the different random action-delay intervals.
Besides the randomization interval stated in Sec. 4.2, we consider 3 different
choices of action-delay intervals during training, “Rand (1-10)”, “Rand
(5-10)”, and “Rand (1-5)”. “Rand ($M_{1}-M_{2}$)” means each macro action
execution is delayed for a random number of simulation steps uniformly sampled
from $[M_{1},M_{2}]$. We empirically find that these variants have similar
performance in most simple test settings, while ACE outperforms them in some
extreme cases. To better illustrate the effect of different action-delay
choices, we present the results in the “$4\Rightarrow 3$” setting, an extreme
scenario with agent loss. As shown in Table 7, ACE consumes the least Time and
achieves the highest ACS. The results show that action-delay randomization
works best with a proper randomization interval, while a large randomization
interval adds high uncertainty during training and hurts the final
performance.

##  7\. Conclusion

To bridge the gap between synchronous simulator and asynchronous action-making
process in real-world multi-agent exploration task, we propose a novel real-
world multi-robot exploration solution, _Asynchronous Coordination Explorer
(ACE)_ to tackle this challenge. In ACE, Multi-agent PPO (MAPPO) is extended
to the asynchronous action-making setting for effective training, and an
action-delay-randomization technique is applied for better generalization to
the real world. Besides, each agent equipped with a team-size-invariant Multi-
tower-CNN-based Policy (MCP), extracts and broadcasts the low-dimensional
feature embedding to accomplish efficient intra-agent communication. Both
simulation and real-world results show that ACE improves $10\%$ exploration
efficiency compared with classical approaches in grid-based environments. We
also extend ACE to a vision-based testbed Habitat, where ACE outperforms
planning-based baselines with $\geq 28\%$ less exploration time. Although we
aim at the sim-to-real problem caused by multiple agents executing tasks
asynchronously, there are still many issues that have not been fully
considered, such as communication errors, localization errors, and sensor
errors. we leave these issues as our future work.

## ACKNOWLEDGMENT

This research was supported by National Natural Science Foundation of China
(No.U19B2019, 62203257, M-0248), Tsinghua University Initiative Scientific
Research Program, Tsinghua-Meituan Joint Institute for Digital Life, Beijing
National Research Center for Information Science, Technology (BNRist), and
Beijing Innovation Center for Future Chips and 2030 Innovation Megaprojects of
China (Programme on New Generation Artificial Intelligence) Grant No.
2021AAA0150000.

We would suggest to visit https://sites.google.com/view/ace-aamas for more
information.

##  Appendix A Habitat Details

###  A.1. Pipeline

In Habitat experiments, we use Neural SLAM to represent the scene with a top-
down mapping, and thus the explored regions and discovered obstacles are
expressed with a top-down 2D mapping. Then the planner, MCP, schedules a
global goal according to the explored information. Finally, the agent uses a
local policy that guides the agent to the chosen global goal.

###  A.2. MCP Details

####  A.2.1. Input Representation

In MCP, each CNN-based feature extractor’s input map, i.e. one feature
extractor per agent, is a $240\times 240$ map with 7 channels, including

  * •

Obstacle channel: Each pixel value denotes the probability of being an
obstacle.

  * •

Explored region channel: A probability map for each pixel being explored.

  * •

One-hot location channel: The only non-zero grid denotes the position of the
agent.

  * •

Trajectory channel: This is used to represent the agent’s history trace. To
reflect time-passing, this channel is updated in an exponentially decaying
weight manner. More precisely, an agent’s trajectory channel $V^{t}$ at
timestep $t$ is updated as following,

$\begin{array}[]{l}V_{x,y}^{t}=\left\\{\begin{array}[]{l}\begin{array}[]{l}1\quad\quad\quad\text{if
agent is near }(x,y)\\\ \varepsilon
V^{t-1}_{x,y}\quad\text{otherwise}\end{array}\end{array}\right.\\\
\end{array}$

where the agent is regarded as near $(x,y)$ when the grid-level distance
between them is less than $3$.

  * •

Three local observations channels: the RGB images of agent-view local
observations.

All mapping-related channels are transformed into a world-view to save MCP
from learning to align all agents’ information, which might involve rotation
and translation.

####  A.2.2. Action Space

Through MCP, every agent chooses a long-term goal (a point) from the whole
space. A natural choice is to model the agent’s policy as a multi-variable
Gaussian distribution to select points from a plane. However, in our
exploration setting, an agent’s policy could be extremely multi-modal
especially during early stage of exploration since many points could induce
similar effects on the agent’s path. To fix this issue, we adopt a
hierarchical design. We first divide the whole map into $8\times 8$ regions,
from which the agent chooses a desired region. Then, similar to previous
choice, a point in this region is selected as the long-term goal. Formally,
the policy of agent $k$, could be described as,

$\displaystyle g_{r},g_{c}$ $\displaystyle\sim\leavevmode\nobreak\
\text{Cat}(r_{\theta,r}),\text{Car}(r_{\theta,c})$ $\displaystyle x_{l},y_{l}$
$\displaystyle\sim\leavevmode\nobreak\
\mathcal{N}(\mu_{\theta},\Sigma_{\theta})$ $\displaystyle
x^{\prime}_{l}=\text{sigmoid}(x_{l})$ $\displaystyle,\leavevmode\nobreak\
\leavevmode\nobreak\ y^{\prime}_{l}=\text{sigmoid}(y_{l})$ $\displaystyle
x_{g}=(g_{r}+x^{\prime}_{l})/8$ $\displaystyle,\leavevmode\nobreak\
\leavevmode\nobreak\ y_{g}=(g_{c}+y^{\prime}_{l})/8$

where $\theta$ is the model parameter,
$\text{Cat}(r_{\theta,r}),\text{Car}(r_{\theta,c})$ represent two categorical
distributions for choosing the region, $g_{r},g_{c}$ are the row and column
indexes of the sampled region, $\mu_{\theta},\Sigma_{\theta}$ are the mean and
covariance matrix of the Gaussian distribution to choose the local point
within the region and $(x_{g},y_{g})$ is the final sampled long-term goal.

####  A.2.3. Network Architecture

Our models are trained and implemented using Pytorch Paszke et al. (2017). We
reuse the neural SLAM module and local policy from Savinov et al. (2019), and
we briefly summarize their architectures here. Neural SLAM module has two
components, a Mapper and a Pose Estimator. The Mapper is composed of ResNet18
convolutional layers, 2 fully-connected layers, and 3 deconvolutional layers.
The Pose Estimator consists of 3 convolutional layers and 3 fully connected
layers. Similarly, the local policy has Resnet18 convolutional layers, fully-
connected layers, and a recurrent GRU layer.

Table 8. CNN Block Hyperparameter in Habitat. Layer | Out Channels | Kernel Size | Stride | Padding
---|---|---|---|---
1 | 32 | 3 | 1 | 1
2 | 64 | 3 | 1 | 1
3 | 128 | 3 | 1 | 1
4 | 64 | 3 | 1 | 1
5 | 32 | 3 | 2 | 1

The Multi-tower-CNN-based Policy (MCP) has three main components, including
CNN-based feature extractors, a transformer-based relation encoder, and an
action decoder.

  1. (1)

Each CNN-based feature extractor contains 5 consecutive CNN blocks. Their
corresponding parameters are shown in tab. 8. We use ReLU as the activation
function. After each of the front four CNN blocks, we attach a 2D max pooling
layer with 2 kernel sizes.

  2. (2)

The transformer-based relation encoder is used to better capture spatial
information. The attention layer has 4 heads, with 32 dimension sizes for each
head.

  3. (3)

The action decoder simply uses a CNN projector and linear transformations to
turn the feature map output from the transformer-based relation encoder to
corresponding logits for Categorical distribution (region head) and means and
standard deviations of the Gaussian distribution (point heads).

The critic also utilizes a similar architecture as MCP, except for replacing
the action decoder with fully-connected layers to output value predictions.

##  Appendix B Training Details

###  B.1. Reward Function

We use 3 kinds of team-based rewards, including a coverage reward, a success
reward, and an overlap penalty. In the following part, $Ratio^{t}$ denotes the
total coverage ratio at timestep $t$. Let $Exp^{t}$ be the merged explored map
at timestep $t$ and $Exp_{k}^{t}$ be the explored map of agent $k$. Ideally,
both $Exp^{t}$ and $Exp^{t}_{k}$ can be considered as sets of explored points.
Then define $\Delta Exp^{t}=Exp^{t}\backslash Exp^{t-1}$ as the newly
discovered region at timestep $t$ by the whole team with regard of the merged
explored area. Specially, we model an individual’s effort by $\Delta
Exp^{t}_{k}=Exp^{t}_{k}\backslash Exp^{t-1}$, that is agent $k$’s contribution
at timestep $k$ based on the whole team’s previous exploration. Note that
$\Delta Exp^{t}_{k}$ is not defined based on the agent’s previous exploration,
i.e. $\Delta Exp^{t}_{k}\neq Exp^{t}_{k}\backslash Exp^{t-1}_{k}$.

  * •

Coverage Reward: The coverage reward consists of two parts, a team coverage
reward, and an individual coverage reward. The team coverage reward is
proportional to the area of the exploration increment $\Delta Exp^{t}$. The
individual coverage reward, as the name suggests, is proportional to the
individual contribution, i.e., the area of $\Delta Exp^{t}_{k}$.

  * •

Success Reward: Agent $a$ gets a success reward of $Ratio^{t}$ when $C\%$
coverage rate is reached, which $C=98$ in the grid-based simulator and $C=90$
in Habitat222Maps in Habitat are harder than in the grid-based simulator,
leading to differences in the success rate threshold..

  * •

Overlap Penalty: The overlap penalty $r_{overlap}$ is designed to encourage
agents to reduce repetitive exploration and learn to cooperate with others.

$\begin{array}[]{l}r_{overlap}=\left\\{\begin{array}[]{l}\begin{array}[]{l}-A_{overlap}\times
0.01,\;Ratio^{t}\;<0.9\\\ 0,\;Ratio^{t}\geq
0.9\end{array}\end{array}\right.\\\ \end{array},$

where $A_{overlap}$ is the increment of the overlapped explored area between
agent $a$ and other agents. The overlapped area between agent $a$ and agent
$w$ is $Overlap^{t}_{a,w}=Exp^{t}_{a}\cap Exp^{t}_{w}$, and
$A_{overlap}=\sum_{w\in\\{1,\cdots,n\\}\backslash\\{a\\}}Overlap^{t}_{a,w}\backslash
Overlap^{t-1}_{a,w}$.

The final team-based reward is simply the sum of all these terms. In Habitat,
all the explored and obstacle maps are represented under discretization of
$5cm$, and all the area computations are taken in $m^{2}$.

###  B.2. Hyperparameters

The hyperparameters for Async-MAPPO are as shown in Table 9.

common hyperparameters | value
---|---
gradient clip norm | 10.0
GAE lambda | 0.95
gamma | 0.99
value loss | huber loss
huber delta | 10.0
mini batch size | batch size / mini-batch
optimizer | Adam
optimizer epsilon | 1e-5
weight decay | 0
network initialization | Orthogonal
use reward normalization | True
use feature normalization | True
learning rate | 2.5e-5
Table 9. Async-MAPPO hyperparameters

##  Appendix C Planning-based Baselines

We demonstrate some details about the 5 planning-based baselines here.

Utility: A method that always chooses frontier that maximizes information gain
Burgard et al. (2005).

Nearest: A method that always chooses the nearest frontier as global goal
Yamauchi (1997b). The distance to a frontier is computed using the breadth-
first search on the occupancy map.

APF: Artificial Potential Field (APF) Yu et al. (2021a) plans a path for each
agent based on a computed potential field. The end of the path, which is a
frontier, is the selected goal. For every agent, an artificial potential field
$F$ is computed in the discretized map, with consideration of distance to
frontiers, presence of obstacles, and potential exploration reward. APF also
introduces resistance force as a simple mechanism. Finally, the path is
generated along the fastest decreasing direction of $F$, starting from the
agent’s current position.

RRT: This baseline is adopted from Umari and Mukhopadhyay (2017). Rapid-
exploring Random Tree (RRT) is originally a path-planning algorithm based on
random sampling and is used as a frontier detector in Umari and Mukhopadhyay
(2017). After collecting enough frontiers through random exploration, RRT
chooses frontier $p$ with the largest utility $u(p)=IG(p)-N(p)$, where $IG(p)$
and $N(p)$ are respectively the normalized information gain and navigation
cost of $p$.

Voronoi Hu et al. (2020b) The voronoi-based method first partitions the map
via voronoi partition and assigns components to agents so that each agent owns
parts that are closest to it. Then each agent finds its own global goal by
finding a frontier point with largest potential as in Utility within its own
partition.

In Habitat experiment, to avoid visually blind areas and ensure that selected
frontiers are far enough, the area within $2.5m$ from each agent is considered
explored when making global planning. The information gain of a frontier $p$
is computed as the number of unexplored grids within $1.5m$ to $p$. All these
baselines do re-planning every $15$ environment steps.

Pseudocode of APF is shown in 3. Line 6-12 computes the resistance force
between every pair of agents where $D$ is the influence radius. In lines
13-18, distance maps starting from cluster centers are computed, and the
corresponding reciprocals are added into the potential field so as one agent
approaches the frontier, the potential drops. Here $w_{c}$ is the weight of
cluster $c$, which is the number of targets in this cluster. Consequently, an
agent would prefer to seek frontiers that are closer and with more neighboring
frontiers. Lines 20-25 show the process of finding the fastest potential
descending path, at each iteration, the agent moves to the cell with the
smallest potential among all neighboring ones. $T$ is the maximum number of
iterations, and $C_{repeat}$ is the repeat penalty to avoid agents wandering
around cells with the same potentials.

Pseudocode of RRT is shown in Algo. 2. In each iteration, a random point $p$
is drawn and a new node $t$ is generated by expanding from $s$ to $p$ with
distance $L$, where $s$ is the closest tree node to $p$. If segment $(s,t)$
has no collision with obstacles in $M$, $t$ is inserted into the target list
or the tree according to whether $t$ is in the unexplored area or not.
Finally, the goal is chosen from the target list with the largest utility
$u(c)=IG(c)-N(c)$ where $IG(c)$ is the information gain and $N(c)$ is the
navigation cost. $IG(c)$ is computed by the number of unexplored grids within
$1.5m$ to $c$, as mentioned above. $N(c)$ is computed as the Euclidean
distance between the agent location and point $c$. To keep these two values at
the same scale, we normalize $IG(\cdot)$ and $N(\cdot)$ to $[0,1]$ w.r.t all
cluster centers.

0: Map $M$ and agent location $loc$.

0: Selected frontier goal

1: $NodeList\leftarrow\\{loc\\},Targets\leftarrow\\{\\}$

2: $i\leftarrow 0$

3: while $i<T$ and $|Targets|<N_{target}$ do

4: $i\leftarrow i+1$

5: $p\leftarrow$ a random point

6: $s\leftarrow\arg\min_{u\in NodeList}||u-p||_{2}$

7: $t\leftarrow Steer(s,p,L)$

8: if $No\\_Collision(M,s,t)$ then

9: if $t$ lies in unexplored area then

10: $Targets\leftarrow Targets+\\{t\\}$

11: else

12: $NodeList\leftarrow NodeList+\\{t\\}$

13: end if

14: end if

15: end while

16: $C\leftarrow$ clusters of points in $Targets$.

17: $goal\leftarrow\arg\min_{c\in C}IG(c)-N(c)$

18: return $goal$

Algorithm 2 Rapid-exploring Random Tree

0: Map $M$, number of agents $n$ and agent locations $loc_{1}\dots loc_{n}$.

0: Selected goals

1: $P\leftarrow$ frontiers in $M$

2: $C\leftarrow$ clusters of frontiers $P$

3: $goals\leftarrow$ an empty list

4: for $i=1\rightarrow n$ do

5: $F\leftarrow$ zero potential field, i.e., a 2d array

6: for $j=1\rightarrow n$ do

7: for empty grid $p\in M$ do

8: if $j\neq i$ and $||p-loc_{j}||_{2}<D$ then

9: $F_{p}\leftarrow F_{p}+k_{D}\cdot(D-||p-loc_{j}||_{2})$

10: end if

11: end for

12: end for

13: for $c\in C$ do

14: Run breadth-first search to compute distance map $dis$ starting from $c$

15: for empty grid $p\in M$ do

16: $F_{p}\leftarrow F_{p}-dis_{p}^{-1}\cdot w_{c}$

17: end for

18: end for

19: $u\leftarrow loc_{i},cnt\leftarrow 0$

20: while $u\notin M$ and $F_{u}$ is not a local minima and $cnt<T$ do

21: $cnt\leftarrow cnt+1$

22: $F_{u}\leftarrow F_{u}+C_{repeat}$

23: $u\leftarrow\arg\min_{v\in Neigh(u)}F_{v}$

24: end while

25: append $u$ to the end of $goals$

26: end for

27: return $goals$

Algorithm 3 Artificial Potential Field(APF)

##  Appendix D Additional Results

###  D.1. Ablation Studies in Habitat

We conduct ablation studies on MCP and report the training ACS performances on
two maps in Habitat.

####  D.1.1. MCP w.o. RE

We consider the MCP without the relation encoder. The output feature maps from
the CNN-based feature extractors are channel-wise concatenated and directly
fed into the action decoder.

####  D.1.2. MCP w.o. AD

We remove discrete heads from the action decoder so that the global goal is
directly generated via two Gaussian action distributions.

Figure 5. Ablation studies on MCP components. Map Size | Methods | Synchronous Action Making | Asynchronous Action Making
---|---|---|---
Time $\downarrow$ | Overlap $\downarrow$ | Coverage $\uparrow$ | ACS $\uparrow$ | Time $\downarrow$ | Overlap $\downarrow$ | Coverage $\uparrow$ | ACS $\uparrow$
$25\times 25$ | Utility | 144.13(1.23) | 0.44(0.05) | 0.94(0.01) | 108.0(1.3) | 137.2(3.3) | 0.5(0.0) | 0.95(0.01) | 112.53(0.88)
Nearest | 79.55(0.94) | 0.33(0.02) | 1.00(0.00) | 125.54(0.39) | 64.65(2.76) | 0.32(0.02) | 1.00(0.00) | 129.6(0.6)
RRT | 80.42(1.86) | 0.36(0.02) | 1.00(0.00) | 126.89(0.50) | 70.64(2.02) | 0.33(0.05) | 1.00(0.00) | 130.20(0.53)
APF | 75.67(1.94) | 0.31(0.03) | 1.00(0.00) | 124.98(0.33) | 63.26(2.82) | 0.33(0.06) | 1.00(0.00) | 129.02(0.41)
Voronoi | 80.63(1.89) | 0.23(0.04) | 1.00(0.00) | 126.23(0.32) | 68.58(1.53) | 0.23(0.01) | 1.00(0.00) | 129.57(0.13)
MAPPO | 64.8(0.33) | 0.13(0.02) | 1.00(0.00) | 129.7(0.14) | 57.1(0.02) | 0.12(0.01) | 1.00(0.00) | 132.03(0.10)
| ACE | 60.7(0.02) | 0.12(0.01) | 1.00(0.00) | 131.23(0.02) | 55.4(0.03) | 0.10(0.02) | 1.00(0.00) | 134.7(0.02)
Table 10. Performances of different methods under 3-agent synchronous and
asynchronous settings in the grid-based simulator.

As shown in Fig. 5, the full MCP module produces both the highest ACS while
_MCP w.o. AD_ produces the lowest ACS. This suggests that a simple Gaussian
representation of actions may not be able to fully capture the distribution of
good global goals, which can be highly multi-modal in the early exploration
stage. _MCP w.o. RE_ performs slightly worse than the full MCP, indicating
that the relation encoder could encourage cooperation and improve exploration
efficiency.

###  D.2. 3-agent Results

We additionally report the result of 3 agents in a map with size $25\times 25$
in the grid-based simulator under both synchronous and asynchronous settings,
shown in Tab. 10. Among all methods, ACE achieves the best exploration
efficiency, with the lowest time, overlap ratio and the highest ACS.

## References

  * (1)
  * Baker (2020) Bowen Baker. 2020\.  Emergent Reciprocity and Team Formation from Randomized Uncertain Social Preferences.  _arXiv preprint arXiv:2011.05373_ (2020).
  * Bresson et al. (2017) Guillaume Bresson, Zayed Alsayed, Li Yu, and Sébastien Glaser. 2017.  Simultaneous localization and mapping: A survey of current trends in autonomous driving.  _IEEE Transactions on Intelligent Vehicles_ 2, 3 (2017), 194–220.
  * Burgard et al. (2005) Wolfram Burgard, Mark Moors, Cyrill Stachniss, and Frank E Schneider. 2005.  Coordinated multi-robot exploration.  _IEEE Transactions on robotics_ 21, 3 (2005), 376–386.
  * Chaplot et al. (2020) Devendra Singh Chaplot, Dhiraj Gandhi, Saurabh Gupta, Abhinav Gupta, and Ruslan Salakhutdinov. 2020.  Learning to explore using active neural slam. In _International Conference on Learning Representations_. ICLR.
  * Chen et al. (2021a) Baiming Chen, Mengdi Xu, Liang Li, and Ding Zhao. 2021a.  Delay-aware model-based reinforcement learning for continuous control.  _Neurocomputing_ 450 (2021), 119–128.  https://doi.org/10.1016/j.neucom.2021.04.015
  * Chen et al. (2021b) Jiayu Chen, Yuanxin Zhang, Yuanfan Xu, Huimin Ma, Huazhong Yang, Jiaming Song, Yu Wang, and Yi Wu. 2021b.  Variational Automatic Curriculum Learning for Sparse-Reward Cooperative Multi-Agent Problems.  arXiv:2111.04613 [cs.LG]
  * Chen et al. (2019) Tao Chen, Saurabh Gupta, and Abhinav Gupta. 2019.  Learning exploration policies for navigation. In _International Conference on Learning Representations_. ICLR.
  * Chevalier-Boisvert et al. (2018) Maxime Chevalier-Boisvert, Lucas Willems, and Suman Pal. 2018\.  Minimalistic Gridworld Environment for OpenAI Gym.  https://github.com/maximecb/gym-minigrid.
  * Chu and Ye (2017) Xiangxiang Chu and Hangjun Ye. 2017.  Parameter Sharing Deep Deterministic Policy Gradient for Cooperative Multi-agent Reinforcement Learning.  _CoRR_ abs/1710.00336 (2017).  arXiv:1710.00336
  * Cohen (1996) William W Cohen. 1996\.  Adaptive mapping and navigation by teams of simple robots.  _Robotics and autonomous systems_ 18, 4 (1996), 411–434.
  * Czarnecki et al. (2018) Wojciech Czarnecki, Siddhant Jayakumar, Max Jaderberg, Leonard Hasenclever, Yee Whye Teh, Nicolas Heess, Simon Osindero, and Razvan Pascanu. 2018.  Mix & match agent curricula for reinforcement learning. In _International Conference on Machine Learning_. PMLR, 1087–1095.
  * Ding et al. (2018) Wenhao Ding, Shuaijun Li, Huihuan Qian, and Yongquan Chen. 2018\.  Hierarchical reinforcement learning framework towards multi-agent navigation. In _2018 IEEE International Conference on Robotics and Biomimetics (ROBIO)_. IEEE, 237–242.
  * Dornhege and Kleiner (2013) Christian Dornhege and Alexander Kleiner. 2013.  A frontier-void-based approach for autonomous exploration in 3d.  _Advanced Robotics_ 27, 6 (2013), 459–468.
  * Dosovitskiy et al. (2020) Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, et al. 2020\.  An image is worth 16x16 words: Transformers for image recognition at scale.  _arXiv preprint arXiv:2010.11929_ (2020).
  * Duan et al. (2017) Yan Duan, Marcin Andrychowicz, Bradly C Stadie, Jonathan Ho, Jonas Schneider, Ilya Sutskever, Pieter Abbeel, and Wojciech Zaremba. 2017\.  One-Shot Imitation Learning. In _NIPS_.
  * Foerster et al. (2016) Jakob Foerster, Ioannis Alexandros Assael, Nando de Freitas, and Shimon Whiteson. 2016\.  Learning to Communicate with Deep Multi-Agent Reinforcement Learning. In _Advances in Neural Information Processing Systems_ , D. Lee, M. Sugiyama, U. Luxburg, I. Guyon, and R. Garnett (Eds.), Vol. 29. Curran Associates, Inc.  https://proceedings.neurips.cc/paper/2016/file/c7635bfd99248a2cdef8249ef7bfbef4-Paper.pdf
  * Godoy et al. (2015) Julio E Godoy, Ioannis Karamouzas, Stephen J Guy, and Maria Gini. 2015.  Adaptive learning for multi-agent navigation. In _Proceedings of the 2015 International conference on autonomous agents and multiagent systems_. 1577–1585.
  * Hsu et al. (2020) Christopher D. Hsu, Heejin Jeong, George J. Pappas, and Pratik Chaudhari. 2020.  Scalable Reinforcement Learning Policies for Multi-Agent Control.  _CoRR_ abs/2011.08055 (2020).  arXiv:2011.08055
  * Hu et al. (2020a) Hengyuan Hu, Adam Lerer, Alex Peysakhovich, and Jakob Foerster. 2020a.  “Other-Play” for Zero-Shot Coordination. In _Proceedings of the 37th International Conference on Machine Learning_ _(Proceedings of Machine Learning Research, Vol. 119)_ , Hal Daumé III and Aarti Singh (Eds.). PMLR, 4399–4410.
  * Hu et al. (2020b) Junyan Hu, Hanlin Niu, Joaquin Carrasco, Barry Lennox, and Farshad Arvin. 2020b.  Voronoi-based multi-robot autonomous exploration in unknown environments via deep reinforcement learning.  _IEEE Transactions on Vehicular Technology_ 69, 12 (2020), 14413–14423.
  * Jaderberg et al. (2019) Max Jaderberg, Wojciech M. Czarnecki, Iain Dunning, Luke Marris, Guy Lever, Antonio Garcia Castañeda, Charles Beattie, Neil C. Rabinowitz, Ari S. Morcos, Avraham Ruderman, Nicolas Sonnerat, Tim Green, Louise Deason, Joel Z. Leibo, David Silver, Demis Hassabis, Koray Kavukcuoglu, and Thore Graepel. 2019\.  Human-level performance in 3D multiplayer games with population-based reinforcement learning.  _Science_ 364, 6443 (2019), 859–865.  https://doi.org/10.1126/science.aau6249
  * Jia et al. (2020) Hangtian Jia, Yujing Hu, Yingfeng Chen, Chunxu Ren, Tangjie Lv, Changjie Fan, and Chongjie Zhang. 2020.  Fever basketball: A complex, flexible, and asynchronized sports game environment for multi-agent reinforcement learning.  _arXiv preprint arXiv:2012.03204_ (2020).
  * Jiang et al. (2018) Jiechuan Jiang, Chen Dun, Tiejun Huang, and Zongqing Lu. 2018\.  Graph convolutional reinforcement learning.  _arXiv preprint arXiv:1810.09202_ (2018).
  * Jiang and Lu (2018) Jiechuan Jiang and Zongqing Lu. 2018.  Learning Attentional Communication for Multi-Agent Cooperation. In _Advances in Neural Information Processing Systems_ , S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett (Eds.), Vol. 31. Curran Associates, Inc.  https://proceedings.neurips.cc/paper/2018/file/6a8018b3a00b69c008601b8becae392b-Paper.pdf
  * Juliá et al. (2012) Miguel Juliá, Arturo Gil, and Oscar Reinoso. 2012\.  A comparison of path planning strategies for autonomous exploration and mapping of unknown environments.  _Autonomous Robots_ 33, 4 (2012), 427–444.
  * Kim et al. (2019) Daewoo Kim, Sangwoo Moon, David Hostallero, Wan Ju Kang, Taeyoung Lee, Kyunghwan Son, and Yung Yi. 2019.  Learning to Schedule Communication in Multi-agent Reinforcement Learning. In _International Conference on Learning Representations_.  https://openreview.net/forum?id=SJxu5iR9KQ
  * Kleiner et al. (2006) Alexander Kleiner, Johann Prediger, and Bernhard Nebel. 2006\.  RFID technology-based exploration and SLAM for search and rescue. In _2006 IEEE/RSJ International Conference on Intelligent Robots and Systems_. IEEE, 4054–4059.
  * Long et al. (2020) Qian Long, Zihan Zhou, Abhinav Gupta, Fei Fang, Yi Wu, and Xiaolong Wang. 2020\.  Evolutionary Population Curriculum for Scaling Multi-Agent Reinforcement Learning. In _International Conference on Learning Representations_.
  * Loquercio et al. (2021) Antonio Loquercio, Elia Kaufmann, René Ranftl, Matthias Müller, Vladlen Koltun, and Davide Scaramuzza. 2021.  Learning high-speed flight in the wild.  _Science Robotics_ 6, 59 (2021), eabg5810.  https://doi.org/10.1126/scirobotics.abg5810 arXiv:https://www.science.org/doi/pdf/10.1126/scirobotics.abg5810
  * Niu et al. (2021) Yaru Niu, Rohan Paleja, and Matthew Gombolay. 2021.  Multi-agent graph-attention communication and teaming. In _Proceedings of the 20th International Conference on Autonomous Agents and MultiAgent Systems_. 964–973.
  * Omidshafiei et al. (2015) Shayegan Omidshafiei, Ali-akbar Agha-mohammadi, Christopher Amato, and Jonathan P. How. 2015\.  Decentralized Control of Partially Observable Markov Decision Processes using Belief Space Macro-actions.  _CoRR_ abs/1502.06030 (2015).  arXiv:1502.06030 http://arxiv.org/abs/1502.06030
  * OpenAI et al. (2018) OpenAI, Marcin Andrychowicz, Bowen Baker, Maciek Chociej, Rafal Józefowicz, Bob McGrew, Jakub W. Pachocki, Jakub Pachocki, Arthur Petron, Matthias Plappert, Glenn Powell, Alex Ray, Jonas Schneider, Szymon Sidor, Josh Tobin, Peter Welinder, Lilian Weng, and Wojciech Zaremba. 2018\.  Learning Dexterous In-Hand Manipulation.  _CoRR_ abs/1808.00177 (2018).  arXiv:1808.00177 http://arxiv.org/abs/1808.00177
  * Osindero et al. (2017) Max Jaderberg Valentin Dalibard Simon Osindero, Wojciech M Czarnecki, Jeff Donahue Ali Razavi Oriol Vinyals, Tim Green Iain Dunning, and Karen Simonyan Chrisantha Fernando Koray Kavukcuoglu. 2017.  Population Based Training of Neural Networks.  _arXiv preprint arXiv:1711.09846_ (2017).
  * Paszke et al. (2017) Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang, Zachary DeVito, Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer. 2017\.  Automatic differentiation in PyTorch. In _NIPS-W_.
  * Peng et al. (2017) Xue Bin Peng, Marcin Andrychowicz, Wojciech Zaremba, and Pieter Abbeel. 2017.  Sim-to-Real Transfer of Robotic Control with Dynamics Randomization.  _CoRR_ abs/1710.06537 (2017).  arXiv:1710.06537 http://arxiv.org/abs/1710.06537
  * Rubio et al. (2019) Francisco Rubio, Francisco Valero, and Carlos Llopis-Albert. 2019\.  A review of mobile robots: Concepts, methods, theoretical framework, and applications.  _International Journal of Advanced Robotic Systems_ 16, 2 (2019), 1729881419839596\.
  * Ryu et al. (2020) Heechang Ryu, Hayong Shin, and Jinkyoo Park. 2020\.  Multi-agent actor-critic with hierarchical graph attention network. In _Proceedings of the AAAI Conference on Artificial Intelligence_ , Vol. 34. 7236–7243.
  * Savinov et al. (2019) Nikolay Savinov, Anton Raichuk, Raphaël Marinier, Damien Vincent, Marc Pollefeys, Timothy Lillicrap, and Sylvain Gelly. 2019\.  Episodic curiosity through reachability. In _International Conference on Learning Representations_. ICLR.
  * Savva et al. (2019) Manolis Savva, Abhishek Kadian, Oleksandr Maksymets, Yili Zhao, Erik Wijmans, Bhavana Jain, Julian Straub, Jia Liu, Vladlen Koltun, Jitendra Malik, et al. 2019\.  Habitat: A platform for embodied ai research. In _Proceedings of the IEEE/CVF International Conference on Computer Vision_. 9339–9347.
  * Sukhbaatar et al. (2016) Sainbayar Sukhbaatar, arthur szlam, and Rob Fergus. 2016\.  Learning Multiagent Communication with Backpropagation. In _Advances in Neural Information Processing Systems_ , D. Lee, M. Sugiyama, U. Luxburg, I. Guyon, and R. Garnett (Eds.), Vol. 29. Curran Associates, Inc.  https://proceedings.neurips.cc/paper/2016/file/55b1927fdafef39c48e5b73b5d61ea60-Paper.pdf
  * Terry et al. (2020) Justin K. Terry, Nathaniel Grammel, Ananth Hari, Luis Santos, Benjamin Black, and Dinesh Manocha. 2020\.  Parameter Sharing is Surprisingly Useful for Multi-Agent Deep Reinforcement Learning.  _CoRR_ abs/2005.13625 (2020).  arXiv:2005.13625
  * Tobin et al. (2017a) Josh Tobin, Rachel Fong, Alex Ray, Jonas Schneider, Wojciech Zaremba, and Pieter Abbeel. 2017a.  Domain randomization for transferring deep neural networks from simulation to the real world. In _2017 IEEE/RSJ international conference on intelligent robots and systems (IROS)_. IEEE, 23–30.
  * Tobin et al. (2017b) Joshua Tobin, Rachel Fong, Alex Ray, Jonas Schneider, Wojciech Zaremba, and Pieter Abbeel. 2017b.  Domain Randomization for Transferring Deep Neural Networks from Simulation to the Real World.  _CoRR_ abs/1703.06907 (2017).  arXiv:1703.06907 http://arxiv.org/abs/1703.06907
  * Travnik et al. (2018) Jaden B. Travnik, Kory W. Mathewson, Richard S. Sutton, and Patrick M. Pilarski. 2018.  Reactive Reinforcement Learning in Asynchronous Environments.  _Frontiers in Robotics and AI_ 5 (2018).  https://doi.org/10.3389/frobt.2018.00079
  * Umari and Mukhopadhyay (2017) Hassan Umari and Shayok Mukhopadhyay. 2017.  Autonomous robotic exploration based on multiple rapidly-exploring randomized trees. In _2017 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_. 1396–1402.  https://doi.org/10.1109/IROS.2017.8202319
  * Vaswani et al. (2017a) Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin. 2017a.  Attention is all you need. In _Advances in neural information processing systems_. 5998–6008.
  * Vaswani et al. (2017b) Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Ł ukasz Kaiser, and Illia Polosukhin. 2017b.  Attention is All you Need. In _Advances in Neural Information Processing Systems_ , I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (Eds.), Vol. 30. Curran Associates, Inc.
  * von Stumberg et al. (2017) Lukas von Stumberg, Vladyslav Usenko, Jakob Engel, Jörg Stückler, and Daniel Cremers. 2017.  From monocular SLAM to autonomous drone exploration. In _2017 European Conference on Mobile Robots (ECMR)_. IEEE, 1–8.
  * Wang et al. (2021) Haiyang Wang, Wenguan Wang, Xizhou Zhu, Jifeng Dai, and Liwei Wang. 2021.  Collaborative Visual Navigation.  _arXiv preprint arXiv:2107.01151_ (2021).
  * Wang* et al. (2020) Tonghan Wang*, Jianhao Wang*, Yi Wu, and Chongjie Zhang. 2020\.  Influence-Based Multi-Agent Exploration. In _International Conference on Learning Representations_.
  * Wang et al. (2020a) Weixun Wang, Tianpei Yang, Yong Liu, Jianye Hao, Xiaotian Hao, Yujing Hu, Yingfeng Chen, Changjie Fan, and Yang Gao. 2020a.  From Few to More: Large-Scale Dynamic Multiagent Curriculum Learning. In _The Thirty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2020, The Thirty-Second Innovative Applications of Artificial Intelligence Conference, IAAI 2020, The Tenth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2020, New York, NY, USA, February 7-12, 2020_. AAAI Press, 7293–7300.
  * Wang et al. (2020b) Weixun Wang, Tianpei Yang, Yong Liu, Jianye Hao, Xiaotian Hao, Yujing Hu, Yingfeng Chen, Changjie Fan, and Yang Gao. 2020b.  From Few to More: Large-Scale Dynamic Multiagent Curriculum Learning. In _Proceedings of the AAAI Conference on Artificial Intelligence_ , Vol. 34. 7293–7300.
  * Wang et al. (2018) Xiaolong Wang, Ross Girshick, Abhinav Gupta, and Kaiming He. 2018.  Non-local neural networks. In _Proceedings of the IEEE conference on computer vision and pattern recognition_. 7794–7803.
  * Wurm et al. (2008) Kai M Wurm, Cyrill Stachniss, and Wolfram Burgard. 2008\.  Coordinated multi-robot exploration using a segmentation of the environment. In _2008 IEEE/RSJ International Conference on Intelligent Robots and Systems_. IEEE, 1160–1165.
  * Xia et al. (2018) Fei Xia, Amir R Zamir, Zhiyang He, Alexander Sax, Jitendra Malik, and Silvio Savarese. 2018\.  Gibson env: Real-world perception for embodied agents. In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_. 9068–9079.
  * Xiao et al. (2022) Yuchen Xiao, Weihao Tan, and Christopher Amato. 2022.  Asynchronous Actor-Critic for Multi-Agent Reinforcement Learning.  https://doi.org/10.48550/ARXIV.2209.10113
  * Yamauchi (1997a) Brian Yamauchi. 1997a.  A frontier-based approach for autonomous exploration. In _Proceedings 1997 IEEE International Symposium on Computational Intelligence in Robotics and Automation CIRA’97.’Towards New Computational Principles for Robotics and Automation’_. IEEE, 146–151.
  * Yamauchi (1997b) Brian Yamauchi. 1997b.  A frontier-based approach for autonomous exploration. In _Proceedings 1997 IEEE International Symposium on Computational Intelligence in Robotics and Automation CIRA’97.’Towards New Computational Principles for Robotics and Automation’_. IEEE, 146–151.
  * Yang et al. (2020) Jiachen Yang, Alireza Nakhaei, David Isele, Kikuo Fujimura, and Hongyuan Zha. 2020.  CM3: Cooperative Multi-goal Multi-stage Multi-agent Reinforcement Learning. In _International Conference on Learning Representations_.
  * Yao et al. (2021) Meng Yao, Qiyue Yin, Jun Yang, Tongtong Yu, Shengqi Shen, Junge Zhang, Bin Liang, and Kaiqi Huang. 2021\.  The Partially Observable Asynchronous Multi-Agent Cooperation Challenge.  _arXiv preprint arXiv:2112.03809_ (2021).
  * Yu et al. (2021b) Chao Yu, Akash Velu, Eugene Vinitsky, Yu Wang, Alexandre Bayen, and Yi Wu. 2021b.  The surprising effectiveness of mappo in cooperative, multi-agent games.  _arXiv preprint arXiv:2103.01955_ (2021).
  * Yu et al. (2021c) Chao Yu, Akash Velu, Eugene Vinitsky, Yu Wang, Alexandre Bayen, and Yi Wu. 2021c.  The Surprising Effectiveness of PPO in Cooperative, Multi-Agent Games.  https://doi.org/10.48550/ARXIV.2103.01955
  * Yu et al. (2021d) Chao Yu, Xinyi Yang, Jiaxuan Gao, Huazhong Yang, Yu Wang, and Yi Wu. 2021d.  Learning Efficient Multi-Agent Cooperative Visual Exploration.  _arXiv preprint arXiv:2110.05734_ (2021).
  * Yu et al. (2021a) Jincheng Yu, Jianming Tong, Yuanfan Xu, Zhilin Xu, Haolin Dong, Tianxiang Yang, and Yu Wang. 2021a.  SMMR-Explore: SubMap-based Multi-Robot Exploration System with Multi-robot Multi-target Potential Field Exploration Method. In _2021 IEEE International Conference on Robotics and Automation (ICRA)_.
  * Zambaldi et al. (2018) Vinicius Zambaldi, David Raposo, Adam Santoro, Victor Bapst, Yujia Li, Igor Babuschkin, Karl Tuyls, David Reichert, Timothy Lillicrap, Edward Lockhart, et al. 2018\.  Relational deep reinforcement learning.  _arXiv preprint arXiv:1806.01830_ (2018).
  * Zhang et al. (2019b) Chuxu Zhang, Dongjin Song, Chao Huang, Ananthram Swami, and Nitesh V Chawla. 2019b.  Heterogeneous graph neural network. In _Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_. 793–803.
  * Zhang et al. (2021) Kaiqing Zhang, Zhuoran Yang, and Tamer Başar. 2021\.  Multi-agent reinforcement learning: A selective overview of theories and algorithms.  _Handbook of Reinforcement Learning and Control_ (2021), 321–384.
  * Zhang et al. (2019a) Yan Zhang, Jonathon Hare, and Adam Prugel-Bennett. 2019a.  Deep set prediction networks.  _Advances in Neural Information Processing Systems_ 32 (2019), 3212–3222.
  * Zhu et al. (2021) Fengda Zhu, Siyi Hu, Yi Zhang, Haodong Hong, Yi Zhu, Xiaojun Chang, and Xiaodan Liang. 2021.  MAIN: A Multi-agent Indoor Navigation Benchmark for Cooperative Learning.  (2021).