# Large Scale Distributed Collaborative Unlabeled Motion Planning with Graph
Policy Gradients

Arbaaz Khan1, Vijay Kumar1, Alejandro Ribeiro1 1GRASP Lab, University of
Pennsylvania, USA<EMAIL_ADDRESS>
###### Abstract

In this paper, we present a learning method to solve the unlabelled motion
problem with motion constraints and space constraints in 2D space for a large
number of robots. To solve the problem of arbitrary dynamics and constraints
we propose formulating the problem as a multi-agent problem. We are able to
demonstrate the scalability of our methods for a large number of robots by
employing a graph neural network (GNN) to parameterize policies for the
robots. The GNN reduces the dimensionality of the problem by learning filters
that aggregate information among robots locally, similar to how a
convolutional neural network is able to learn local features in an image.
Additionally, by employing a GNN we are also able to overcome the
computational overhead of training policies for a large number of robots by
first training graph filters for a small number of robots followed by zero-
shot policy transfer to a larger number of robots. We demonstrate the
effectiveness of our framework through various simulations.

##  I Introduction

In robotics, one is often tasked with designing algorithms to coordinate teams
of robots to achieve a task. In this paper, we concern ourselves with
scenarios where a team of homogeneous or identical robots must execute a set
of identical tasks such that each robot executes only one task, but it does
not matter which robot executes which task. Concretely, this paper studies the
concurrent goal assignment and trajectory planning problem where robots must
simultaneously assign goals and plan motion primitives to reach assigned
goals. This is the unlabelled multi-robot planning problem where one must
simultaneously solve for goal assignment and trajectory optimization.

In the past, several methods have been proposed to achieve polynomial-time
solutions for the unlabelled motion planning problem [1, 2, 3]. The common
theme among these methods is the design of a heuristic best suited for the
robots and the environment. However, when additional constraints such as
constraints on dynamics, presence of obstacles in the space, desired goal
orientations; solving for a simple heuristic is no longer the optimal
solution. In contrast to previous literature that relies on carefully designed
but ultimately brittle heuristic functions, instead we hypothesize using
reinforcement learning (RL) to compute an approximate solution for the
assignment and planning problem without relaxing any constraints. When using
RL to learn policies for the robots, one can optimize a cost function that is
independent of any dynamics or constraints, i.e assign a high value if all
goals are covered and zero otherwise.

To achieve scalable multi-robot motion planning, we look to exploit the
inherent graph structure among the robots and learn policies using local
features only. We hypothesize that graph neural networks (GNNs) [4, 5] can be
a good candidate to parameterize policies for robots as opposed to the fully
connected networks used in [6]. GNNs work similar to convolutional neural
networks (CNNs) and can be seen as an extension of CNNs to data placed on
irregular graphs instead of a two dimensional grid such as an image. We define
a graph $\mathcal{G}=(\mathbf{V},\mathbf{E})$ where $\mathbf{V}$ is the set of
nodes representing the robots and $\mathbf{E}$ is the set of edges defining
relationships between them. These relationships can be arbitrary and are user
defined. In this work we define edges between robots based on the Euclidean
distance between them. This graph acts as a support for the data vector
${\mathbf{X}}=[{\mathbf{x}}_{1},\ldots,{\mathbf{x}}_{N}]^{\top}$ where
${\mathbf{x}}_{n}$ is the state representation of robot $n$. The GNN consists
of multiple layers of graph filters and at each layer the graph filters
extract local information from a node’s neighbors. The information is
propagated forward between layers after passing it through a non linear
activation function similar to how one would propagate information in a CNN.
The output of the final layer is given by $\Pi=[\pi_{1},\ldots,\pi_{N}]$,
where $\pi_{1},\ldots,\pi_{N}$ are independent control policies for the
robots. During training, each robot rolls out its own trajectory by executing
its respective policy. Each robot also collects a centralized reward and using
policy gradient methods [7] the weights of the GNN are updated. Further, since
the robots are homogeneous and the graph filters only learn local information,
we circumvent the computational burden of training many robots by training the
GNN on only a small number of robots but during inference use the same filter
across all robots.

###  I-A Related Work

The unlabeled motion planning is a relatively well studied problem in robotics
[1, 2, 3, 8]. Concurrent assignment and planning (CAPT) [3] is a provably
correct and complete algorithm but requires centralized information. Further,
CAPT makes assumptions about the dynamics and assumes the environment to be
obstacle free. The work of [9] proposes an algorithm for unlabeled motion
planning for disk like obstacles. The algorithm has a guaranteed solution with
a provable bound on runtime. It however requires the need to produce shortest
paths for a robot moving in an environment with static obstacles which can
prove to be a challenging problem in 3D. A recently emerging field of research
looks to approximate intractable multi-robot problems with a model-free
approach [10, 6] that provide significant benefits over analytic model based
methods. In our earlier work, [6], we proposed the use of RL to solve the
unlabeled motion planning problem with constraints on obstacles, dynamics of
robots etc. However, a key feature lacking from [6] was scalability. We were
only able to show unlabeled motion planning for 3-5 robots and this can mostly
be attributed to the sample inefficiency of online deep RL methods. In another
somewhat unrelated work, [11] we look to evaluate the use of a GNN to design
decentralized policies for consensus in robots and are able to achieve results
for a large number of robots. In this work, we look to combine the results
from both, i.e using RL for the unlabeled motion planning problem and achieve
large scalability by employing graph convolutional networks to parameterize
the decentralized policies. Through various simulations we demonstrate that
the methods proposed in this paper provide a suitable solution that extends
the learning formulation of the unlabeled motion planning algorithm to have
the ability to scale to many robots.

##  II Distributed Collaborative Unlabeled Motion Planning

We consider the problem of navigating $N$ disk-shaped robots to a set of $N$
goals of radius $R$. We say that the navigation problem is unlabeled because
there is no prior matching between robots and goals. Any robot can cover any
goal. The positions of the goals are fixed and we use ${\mathbf{g}}_{n}$ to
denote the position of goal $n$. The positions of robots change over discrete
time index $t$ and are denoted as ${\mathbf{r}}_{n}(t)$ for robot $n$. We
stack goal positions into the matrix
${\mathbf{G}}=[{\mathbf{g}}_{1}^{T};\ldots;{\mathbf{g}}_{N}^{T}]$ whose $n$th
row is the position of goal $n$ and robot positions into the matrix
${\mathbf{R}}(t)=[{\mathbf{r}}_{1}^{T}(t);\ldots;{\mathbf{r}}_{N}^{T}(t)]$
whose $n$th row is the position of robot $n$. We further group these two
matrices to define the system state

${\mathcal{S}}(t)\\!=\langle{\mathbf{R}}(t),{\mathbf{G}}\rangle\\!=\langle[{\mathbf{r}}_{1}^{T}(t);\ldots;{\mathbf{r}}_{N}(t)^{T}],[{\mathbf{g}}_{1}^{T};\ldots;{\mathbf{g}}_{N}^{T}]\rangle$
(1)

We assume that robot positions evolve according to a choice of action
${\mathbf{a}}_{n}(t)\in{\mathcal{A}}$ as determined by some stationary
distribution with conditional density
$p({\mathbf{r}}_{n}(t+1)|{\mathbf{r}}_{n}(t),{\mathcal{S}}_{n}(t))$. This
first order dynamical model implies that the state ${\mathcal{S}}(t)$ is a
complete description of the system at time $t$. We further assume operation in
open space. Both these choices are for simplicity of exposition. Incorporating
obstacles (Section 1) and high order complex dynamics is an easy extension.

The goal of the team of robots is to cover all goals in the sense that all
goals ${\mathbf{g}}_{n}$ have at least one robot within distance $R$ of its
location. To measure how well the configuration ${\mathcal{S}}(t)$ in (1)
accomplish this task, the reward $r({\mathcal{S}}(t))$ counts the number of
goals covered. This is equivalent to counting all the goals for which
$\|{\mathbf{g}}_{n}-{\mathbf{r}}_{m}\|\leq R$ for at least one robot $m$,
which we can write as the sum

$\displaystyle
r({\mathcal{S}}(t))=\sum_{n=1}^{N}{\mathbb{I}}\Big{[}\min_{m}\|{\mathbf{g}}_{n}-{\mathbf{r}}_{m}(t)\|\leq
R\Big{]}$ (2)

In (2) only the robots that are within distance $R$ of a goal contribute to
the reward. If there are several robots within $R$ of a goal, only the closest
contributes toward increasing $r({\mathcal{S}}(t))$. The maximum reward
$r({\mathcal{S}}(t))=N$ occurs when all goals are covered by one robot.
Therefore, the necessary and sufficient condition for all goals to be covered
at some time $t$ is for the reward to attain its maximum
$r({\mathcal{S}}(t))=N$.

Our interest here is designing policies to reach the maximum reward
$r({\mathcal{S}}(t))=N$ (Section III) with a distributed collaborative system.
The system is distributed because agents have access to local state
information only and collaborative because nearby agents communicate with each
other. To describe the locality of information and communication, consider
orderings of goals and robots relative to their distance to a given robot.
Formally, let ${\mathbf{r}}_{n[m]}(t)$ be the $m$th closest robot to robot $n$
other than $n$ itself so that for all $1\leq m\leq m^{\prime}\leq N-1$ it
holds

$\|{\mathbf{r}}_{n[m]}(t)-{\mathbf{r}}_{n}(t)\|\ \leq\
\|{\mathbf{r}}_{n[m^{\prime}]}(t)-{\mathbf{r}}_{n}(t)\|.$ (3)

Likewise, let ${\mathbf{g}}_{n[m]}$ be the $m$th closest goal to robot $n$ so
that for any $1\leq m\leq m^{\prime}\leq N$ we can write

$\|{\mathbf{g}}_{n[m]}(t)-{\mathbf{r}}_{n}(t)\|\ \leq\
\|{\mathbf{g}}_{n[m^{\prime}]}(t)-{\mathbf{r}}_{n}(t)\|.$ (4)

Observe that the position ${\mathbf{g}}_{n[m]}(t)$ of the $m$th closest goal
changes over time as robot $n$ moves through the environment.

We assume that each agent senses at most the $M$ goals and at most the $M$
robots that are closest to its location and that it can communicate with the
$M$ closest robots. We therefore define the state of robot $n$ at time $t$ as
a row vector concatenating its own location, the location of its $M$th closest
robots, and the location of its $M$th closest goals,

$\displaystyle{\mathbf{x}}_{n}(t)=\Big{[}{\mathbf{r}}_{n}^{T}(t);\
{\mathbf{r}}_{n[1]}^{T}(t);\ldots;$ $\displaystyle{\mathbf{r}}_{n[M]}^{T}(t);$
$\displaystyle{\mathbf{g}}_{n[1]}^{T}(t);\ldots;{\mathbf{g}}_{n[M]}^{T}(t)\Big{]}.$
(5)

For future reference we introduce $d$ to denote the number of entries of
${\mathbf{x}}_{n}(t)$. This number is $d=2(2M+1)$ for planar navigation and
$d=3(2M+1)$ for navigation in three dimensions. Communication between agents
is also restricted to local information exchanges. We model this with a
communication graph whose adjacency matrix we denote by
${\mathbf{S}}(t)\in{\mathbb{R}}^{N\times N}$. Entries of this matrix
$S_{nm}(t)$ are binary and are 1 only if robot $m$ is among the $M$th closest
robots to robot $n$. We write this formally as

$\displaystyle
S_{nm}(t)={\mathbb{I}}\Big{[}{\mathbf{r}}_{m}\in\big{\\{}{\mathbf{r}}_{n}(t),{\mathbf{r}}_{n[1]}(t),\ldots,$
$\displaystyle{\mathbf{r}}_{n[M]}(t)\big{\\}}\Big{]}$ (6)

where we point out that we also add self loops to ${\mathbf{S}}$ because we
have made $S_{nn}=1$. Observe that $M$ limits the number of robots that
communicate with each robot $n$, as well as the number of robots and goals
sensed by each robot $n$. These three parameters can be distinct in practical
implementations but we make them equal here to simplify notation.

Robots are given access to their local states ${\mathbf{x}}_{n}(t)$ as defined
in (II) and can exchange information with neighboring agents as dictated by
the graph ${\mathbf{S}}(t)$ whose entries are given by (6). Given their local
states and information received from neighbors, robot $n$ chooses an
$e$-dimensional action ${\mathbf{a}}_{n}(t)\in{\mathbb{R}}^{e}$ that controls
the transition into position ${\mathbf{r}}_{n}(t+1)$ according to the
dynamical model
$p({\mathbf{r}}_{n}(t+1)|{\mathbf{r}}_{n}(t),{\mathbf{a}}_{n}(t))$. We write
these stochastic policies as:

$\displaystyle{\mathbf{a}}_{n}(t)=\pi_{n}\big{(}{\mathbf{a}}_{n}(t){\,\big{|}\,}{\mathbf{x}}_{n}(t);{\mathbf{S}}(t)\big{)}.$
(7)

The notation in (7) signifies that ${\mathbf{S}}_{n}(t)$ is chosen according
to the local state ${\mathbf{x}}_{n}(t)$ – i.e., the policy is distributed –
and information exchanges with neighboring nodes as dictated by the graph
${\mathbf{S}}(t)$ – i.e., the policy is collaborative. We emphasize that the
graph ${\mathbf{S}}(t)$ affects the choice of action because it limits the
information accessible to robot $n$ and that it therefore is an important
component of the robots policy. Notwithstanding, these graph is not
necessarily known to robot $n$ and our policies will be executable without
this knowledge (Section III). The individual distributed collaborative
policies in (7) generate the product policy
$\Pi=\pi\big{(}{\mathbf{a}}_{1}(t){\,\big{|}\,}{\mathbf{x}}_{1}(t);{\mathbf{S}}(t)\big{)}\times\ldots\times\pi\big{(}{\mathbf{a}}_{N}(t){\,\big{|}\,}{\mathbf{x}}_{N}(t);{\mathbf{S}}(t)\big{)}$.
We want to jointly optimize over individual policies to maximize the
discounted reward

$J({\Pi})=\max_{\Pi}\mathbb{E}_{\Pi}\bigg{[}\sum_{t}^{T}\gamma^{t}r({\mathcal{S}}(t))\bigg{]}$
(8)

where the reward $r({\mathcal{S}}(t))$ is as given in (2). Our objective in
this paper is to learn policies having the form in (7) that maximize the
discounted reward in (8). We do so with the Graph Policy Gradient method that
we introduce next.

##  III Graph Policy Gradient

To find the policy $\Pi$ that maximizes the reward $J({\Pi})$ in (III) it is
customary to introduce a policy parameterization. Our key technical innovation
is to parameterize $\Pi$ with a graph neural network (GNN), which as we will
explain in Section IV not only respects but also leverages the locality of the
distributed collaborative motion planning problem we discussed in Section II.
GNNs are generalizations of convolutional neural networks (CNNs) built on the
definition of convolutional graph filters. Formally, define the state matrix
${\mathbf{X}}(t)\in{\mathbb{R}}^{n\times d}$ whose $n$th row is the state of
robot $n$ [cf. (II)],

$\displaystyle{\mathbf{X}}(t)=[{\mathbf{x}}_{1}(t);\ldots;{\mathbf{x}}_{N}(t)]\in{\mathbb{R}}^{N\times
d}.$ (9)

A graph convolutional filter to process ${\mathbf{X}}(t)$ on the graph
${\mathbf{S}}(t)$ is defined by a set of $K$ coefficient matrices
${\mathbf{H}}_{1k}\in{\mathbb{R}}^{d\times d_{1}}$. These matrices serve as
coefficients of a polynomial on ${\mathbf{S}}(t)$ that operates on the state
${\mathbf{X}}(t)$ to produce the output
${\mathbf{Y}}(t)\in{\mathbb{R}}^{d_{1}}$ given by

${\mathbf{Z}}_{1}(t)=\sum_{k=0}^{K-1}{\mathbf{S}}^{k}(t){\mathbf{X}}(t){\mathbf{H}}_{1k}.$
(10)

The output of the graph filter in 10 is further processed with a pointwise
nonlinearity to produce the layer 1 output signal

${\mathbf{X}}_{1}(t)=\sigma\Big{[}\ {\mathbf{Z}}_{1}(t)\
\Big{]}=\sigma\bigg{[}\sum_{k=0}^{K-1}{\mathbf{S}}^{k}(t){\mathbf{X}}(t){\mathbf{H}}_{1k}\bigg{]}.$
(11)

In a GNN with multiple layers the signal ${\mathbf{X}}_{1}(t)$ is further
processed with a graph filter with coefficients
${\mathbf{H}}_{1k}\in{\mathbb{R}}^{d_{1}\times d_{2}}$ and a pointwise
nonlinearity, to produce the output of Layer 2. In general, there are a total
of $L$ layers each of which is defined by a set of $K$ coefficients
${\mathbf{H}}_{1k}\in{\mathbb{R}}^{d_{l-1}\times d_{l}}$ which produce output
signals ${\mathbf{X}}_{l}(t)$ according to the recursion

${\mathbf{X}}_{l}(t)=\sigma\Big{[}\ {\mathbf{Z}}_{l}(t)\
\Big{]}=\sigma\bigg{[}\sum_{k=0}^{K-1}{\mathbf{S}}^{k}(t){\mathbf{X}}_{l-1}(t){\mathbf{H}}_{lk}\bigg{]}.$
(12)

The output of the $L$th layer is the output of the GNN and we propose here to
use it as the mechanism for generating robot actions. Specifically, stack the
individual actions of all agent into the action matrix
${\mathbf{A}}(t)=[{\mathbf{a}}_{1}^{T}(t);\ldots;{\mathbf{a}}_{N}^{T}(t)]\in{\mathbb{R}}^{n\times
e}$ and make

${\mathbf{A}}(t)={\mathbf{X}}_{L}(t)=\Phi({\mathbf{X}}(t),{\mathbf{S}}(t);{\mathbf{H}}).$
(13)

Notice that in (13) we have introduced the notation
$\Phi({\mathbf{X}}(t),{\mathbf{S}}(t);{\mathbf{H}})$ to represent the GNN’s
output. This output depends on the state input ${\mathbf{X}}(t)$, the graph
${\mathbf{S}}(t)$ and the filter tensor
${\mathbf{H}}:=\\{{\mathbf{H}}_{lk}\\}_{l,k}$ that groups the coefficient
matrices of all layers and all orders. The advantage of using a GNN to
parameterize actions ${\mathbf{A}}(t)$ is that they respect the structure of
the distributed collaborative policies in (7). The graph filters in (10) and
(12) are made up of diffusion operations that involve interactions between
neighbors only. Consider the product ${\mathbf{S}}(t){\mathbf{X}}(t)$ and
observe that the sparsity pattern of ${\mathbf{S}}(t)$ is such that the $n$th
row of this product is given by

$[{\mathbf{S}}(t){\mathbf{X}}(t)]_{n}=\sum_{m:S_{mn}=1}{\mathbf{x}}_{m}(t)$
(14)

If we interpret the row $\big{[}{\mathbf{A}}(t){\mathbf{X}}(t)\big{]}_{n}$ as
a quantity that is evaluated by robot $n$, it follows that robot $n$ can
evaluate this row by communicating with neighboring nodes only. Subsequent
entries in the graph filters in (10) can be recursively evaluated noticing
that ${\mathbf{S}}^{k}(t){\mathbf{X}}(t)={\mathbf{S}}^{k-1}(t){\mathbf{X}}(t)$
and that we can therefore write:

$[{\mathbf{S}}^{k}(t){\mathbf{X}}(t)]_{n}=\sum_{m:S_{mn}=1}[{\mathbf{S}}^{k-1}(t){\mathbf{X}}(t)]_{m}$
(15)

It follows that all of the summands in (10) can be computed exclusively
through local information exchanges. The pointwise nonlinearity in (11) can
also be locally implemented. Subsequent layers can be evaluated in a
distributed manner as well, because the argument in (14) and (15) is not
specific to Layer 1. Through this recursive distributed computations, robot
$n$ ends up computing the $n$th row of the GNN output
$[{\mathbf{X}}_{L}(t)]_{n}=[\Phi({\mathbf{X}}(t),{\mathbf{A}}(t);{\mathbf{H}})]_{n}$.
This row is used to define the local policy in (7) as

$\displaystyle{\mathbf{a}}_{n}(t)=[{\mathbf{A}}(t)]_{n}=[{\mathbf{X}}_{L}(t)]_{n}=[\Phi({\mathbf{X}}(t),{\mathbf{S}}(t);{\mathbf{H}})]_{n}$
(16)

The graph policy gradient method (GPG) is the search for a joint policy $\Pi$
that maximizes the cost in (III) over the space of policies
$\Pi({\mathbf{H}})$ that produce actions parameterized with a GNN of the form
in (12). The solution of this optimization is the optimal filter tensor

$\displaystyle{\mathbf{H}}^{*}=\mathop{\arg\max}_{{\mathbf{H}}}\ $
$\displaystyle\mathbb{E}_{\Pi({\mathbf{H}})}\bigg{[}\sum_{t}^{T}\gamma^{t}r({\mathcal{S}}(t))\bigg{]}$
$\displaystyle\Pi({\mathbf{H}}):{\mathbf{A}}(t)=\Phi({\mathbf{X}}(t),{\mathbf{S}}(t);{\mathbf{H}}).$
(17)

In (III), the filter tensor ${\mathbf{H}}$ along with the state
${\mathbf{X}}(t)$ and the graph ${\mathbf{S}}(t)$ determine the choice of
action ${\mathbf{A}}(t)$. This joint action controls the state transition as
dictated by the dynamical model
$p({\mathbf{r}}_{n}(t+1)|{\mathbf{r}}_{n}(t),{\mathbf{S}}_{n}(t))$. We want to
find a filter tensor ${\mathbf{H}}$ that results in the maximum reward
$J(\Pi({\mathbf{H}}))$.

The optimal filter can be computed through online policy gradient methods.
Robots roll out trajectories $\tau\sim\Pi$ and collect rewards
$r(\mathcal{S}(t))$ over a time horizon $t=0,\ldots,T$. Since the policies are
assumed to be independent, the policy gradient wrt $\mathbf{H}$,
$\nabla_{\mathbf{H}}J$ can be given as:

$=\mathbb{E}_{\tau\sim(\Pi)}\Bigg{[}\Big{(}\sum_{t=1}^{T}\nabla_{\mathbf{H}}\log[\pi_{1}\times\ldots\times\pi_{N}]\Big{)}\Big{(}\sum_{t=1}^{T}r(\mathcal{S}(t))\Big{)}\Bigg{]}$
(18)

This is called Graph Policy Gradients or GPG and was first proposed in [11] as
a method of taking gradients for RL policies parameterized by graph neural
networks. In parameterizing actions with a GNN we ensure the possibility of
having a distributed implementation. We will see in the upcoming Section IV
that GNNs also exhibit an invariance to the labeling that substantiates
transferability properties that we explore in the numerical experiments in
Section V.

##  IV Permutation Invariance of GNN Policy parameterizations

Let the GNN coefficients $\mathbf{H}^{*}$ be the solution that maximizes (III)
for a given ${\mathbf{S}}(t)$ and ${\mathbf{X}}(t)$. Consider another set of
graphs $\tilde{{\mathbf{S}}}(t)$ and state vectors $\tilde{{\mathbf{X}}}(t)$
that are produced by permuting ${\mathbf{S}}(t)$ and ${\mathbf{X}}(t)$. Let
the filter coefficients after training on $\tilde{{\mathbf{S}}}(t)$ and
$\tilde{{\mathbf{X}}(t)}$ be $\tilde{\mathbf{H}}^{*}$. To study the
relationship between $\mathbf{H}^{*}$ and $\tilde{\mathbf{H}}^{*}$ we first
define a set of permutation matrices of dimension ${N}$ such that
$\bm{\mathcal{P}}=\\{\mathbf{{P}}\in\\{0,1\\}^{{N}\times{N}}\
\mathbf{{P1=1}},\mathbf{{P}^{\top}1=1}\\}$

Such a permutation matrix $\mathbf{P}$ is one for which the product
$\mathbf{P}^{\top}{\mathbf{X}}(t)$ reorders the entries of any
${\mathbf{X}}(t)$ and the operation
$\mathbf{P}^{\top}{\mathbf{S}}(t)\mathbf{P}$ produces a reordering of the rows
and columns of any given ${\mathbf{S}}(t)$. The policy for system with
${\mathbf{S}}(t)$ is $\Pi=\Phi({\mathbf{X}}(t),{\mathbf{S}}(t);\mathbf{H})$.
Analogously, let the policy for the permuted system be given as:

$\displaystyle\begin{split}\tilde{\Pi}=\Phi({\tilde{{\mathbf{X}}}(t),\tilde{{\mathbf{S}}}(t)};\tilde{\mathbf{H}})\text{
where }\tilde{{\mathbf{S}}}(t)=\mathbf{P}^{\top}{\mathbf{S}}(t)\mathbf{P},\\\
\end{split}$ (19)

$\tilde{{\mathbf{X}}}$ is the permuted state of all robots and
$\tilde{\mathbf{H}}$ is the vector of filter coefficients that parameterizes
$\tilde{\Pi}$. This leads to:

######  Theorem 1.

Given a configuration of robots represented by ${\mathbf{X}}(t)$ that define
an underlying graph $\mathcal{G}$ with graph shift operator ${\mathbf{S}}(t)$
and another configuration of robots given by $\tilde{{\mathbf{X}}}(t)$ and
$\tilde{{\mathbf{S}}}(t)$ then the graph filter coefficients $\mathbf{H}^{*}$
and $\tilde{\mathbf{H}}^{*}$ which are the optimal solutions for the systems
$({\mathbf{S}}(t),{\mathbf{X}}(t))$ and
$(\tilde{{\mathbf{S}}}(t),\tilde{{\mathbf{X}}}(t))$ respectively are
equivalent,

$\mathbf{H}^{*}\equiv\tilde{\mathbf{H}}^{*}$ (20)

In order to prove Theorem 1, we must prove that both the unlabeled motion
planning problem and the GNNs parameterized by $\tilde{\mathbf{H}}^{*}\text{
and }\mathbf{H}^{*}$ are permutation equivariant.

###  IV-A Equivariance of GNNs for Unlabeled Motion Planning

######  Proposition 1.

Given a system of robots and goals
${\mathcal{S}}(t)=\\{{\mathbf{r}}(t),\,{\mathbf{g}}\\}$ and another system
where the robot states are permuted
$\tilde{\mathcal{S}}(t)=(\tilde{\mathbf{r}}(t),\mathbf{g})$ where
$\tilde{\mathbf{r}}(t)=\mathbf{P}^{\top}\mathbf{r}(t)$, the corresponding
robot states
${\mathbf{X}}(t)=[{\mathbf{x}}_{1}(t),\ldots,{\mathbf{x}}_{{N}}(t)]^{\top}$
and
$\tilde{{\mathbf{X}}}(t)=[\tilde{{\mathbf{x}}}_{1}(t),\ldots,\tilde{{\mathbf{x}}}_{{N}}(t)]^{\top}$
are permutation related, i.e
$\tilde{{\mathbf{X}}}(t)=\mathbf{P}^{\top}{\mathbf{X}}(t).$

Proof This is true because we have used ordering to construct the local robot
states in (II) and orderings are invariant to permutations. Formally, consider
indexes $n$ and ${\tilde{n}}$ with $[{\mathbf{P}}]_{n{\tilde{n}}}=1$. It
follows from ${\tilde{\mathbf{R}}}(t)={\mathbf{P}}^{T}{\mathbf{R}}(t)$ that
${\mathbf{r}}_{n}(t)={\mathbf{r}}_{\tilde{n}}(t)$; which means that robot $n$
has been mapped to robot ${\tilde{n}}$ in the permutation. Since orderings are
independent of labeling it follows that for all robots we must have
${\mathbf{r}}_{n[m]}(t)={\mathbf{r}}_{{\tilde{n}}[m]}(t)$ [cf. (3)]. Likewise,
for all goals we must have
${\mathbf{g}}_{n[m]}(t)={\mathbf{g}}_{{\tilde{n}}[m]}(t)$ [cf. (4)]. Given the
definition of the state row vector in (II) we therefore have that
${\mathbf{x}}_{n}(t)={\mathbf{x}}_{{\tilde{n}}}(t)$. Further recalling the
definition of the state matrix ${\mathbf{X}}(t)$ in (9) and the assumption
that $[{\mathbf{P}}]_{n{\tilde{n}}}=1$ we also have that
${\mathbf{x}}_{n}(t)=[{\mathbf{P}}^{T}{\mathbf{X}}(t)]_{\tilde{n}}$. Putting
the latter two statements together we conclude that
$[{\mathbf{P}}^{T}{\mathbf{X}}(t)]_{\tilde{n}}={\mathbf{x}}_{{\tilde{n}}}(t)$.
Since this is true for arbitrary ${\tilde{n}}$ we must have
${\mathbf{P}}^{T}{\mathbf{X}}(t)=\tilde{{\mathbf{X}}}(t)$. In order to show
that the GNN parameterization is equivariant for both settings, consider the
following proposition:

######  Proposition 2.

Given robots with states ${\mathbf{X}}(t)$ and $\tilde{{\mathbf{X}}}(t)$ and
underlying graphs ${\mathbf{S}}(t)$ and $\tilde{{\mathbf{S}}}(t)$ such that
$\tilde{{\mathbf{X}}}(t)=\mathbf{P}^{\top}{\mathbf{X}}(t)$ (from Proposition
1) and $\tilde{{\mathbf{S}}}(t)=\mathbf{P}^{\top}{\mathbf{S}}(t)\mathbf{P}$
for some permutation matrix $\mathbf{P}$, the outputs of a GNN policy $\Phi$
with filter coefficients $\mathbf{H}$ to the pairs
$({\mathbf{S}}(t),{\mathbf{X}}(t))$ and
$(\tilde{{\mathbf{S}}}(t),\tilde{{\mathbf{X}}}(t))$ are related by:

$\Phi(\tilde{{\mathbf{X}}}(t),\tilde{{\mathbf{S}}}(t);\mathbf{H})=\mathbf{P}^{\top}\Phi({\mathbf{X}}(t),{\mathbf{S}}(t);\mathbf{H})$
(21)

Proof The output of the GNN filter for the system
$(\tilde{{\mathbf{S}}}(t),\tilde{{\mathbf{X}}}(t))$ as given in (12) is:

$\Phi(\tilde{{\mathbf{X}}}(t),\tilde{{\mathbf{S}}}(t);\mathbf{H})=\sum_{k=0}^{K}h_{k}\tilde{{\mathbf{S}}}(t)^{k}\tilde{{\mathbf{X}}}(t)$
(22)

This can be expressed as:

$\sum_{k=0}^{K}h_{k}\tilde{{\mathbf{S}}}(t)^{k}\tilde{{\mathbf{X}}}=\sum_{k=0}^{\infty}h_{k}(\mathbf{P}^{\top}{\mathbf{S}}(t)^{k}\mathbf{P})\mathbf{P}^{\top}{\mathbf{X}}(t)$
(23)

Using the fact that $\mathbf{P}$ is an orthogonal matrix which in turn implies
that $\mathbf{P}^{\top}\mathbf{P}=\mathbf{P}\mathbf{P}^{\top}=\mathbf{I}$:

$\displaystyle\sum_{k=0}^{\infty}h_{k}(\mathbf{P}^{\top}{\mathbf{S}}(t)^{k}\mathbf{P})\mathbf{P}^{\top}{\mathbf{X}}(t)=\mathbf{P}^{\top}\sum_{k=0}^{\infty}h_{k}{\mathbf{S}}(t)^{k}{\mathbf{X}}(t)$
$\displaystyle=\mathbf{P}^{\top}\Phi({\mathbf{X}}(t),{\mathbf{S}}(t);\mathbf{H})$
(24)

Thus, proving Proposition 2. Intuitively, Proposition 2 tells us that
reordering the robots states and corresponding nodes in the graph
representation which is fed into the GNN policy, results in an appropriate
reordering of the outputs of the filter without any change in the weights of
the policy.

###  IV-B Equivariance of Unlabeled Motion Planning

In order to show that the unlabeled motion planning is permutation
equivariant, we look at the cost $J$.

######  Proposition 3.

The reward function $J$ is permutation equivariant. i.e for all permutation
matrices $\mathbf{P}\in\mathcal{P}$, $J_{\Pi}=J_{\tilde{\Pi}}$

Proof For the permuted system the reward is given as :

$\displaystyle
r(\tilde{{\mathcal{S}}}(t))=\sum_{n=1}^{N}{\mathbb{I}}\Big{[}\min_{m}\|{\mathbf{g}}_{n}-\tilde{{\mathbf{r}}}_{m}\|\leq
R\Big{]}$ (25)

Since the set of robots $\mathbf{r}$ and $\tilde{\mathbf{r}}$ are the same:

$\tilde{\mathbf{r}}_{i[1]}=\mathop{\arg\min}_{j}\text{
}\lvert\lvert\mathbf{g}_{i}-\tilde{\mathbf{r}}_{j}\rvert\rvert={\mathbf{r}}_{i[1]}$
(26)

Which leads us to $r({\mathcal{S}}(t))=r(\tilde{{\mathcal{S}}}(t))$ and
therefore
$\sum_{t}^{T}r({\mathcal{S}}(t))=\sum_{t}^{T}r(\tilde{{\mathcal{S}}}(t))$.
Now,

$\displaystyle
J_{\tilde{\Pi}}=\sum_{n=1}^{{N}}\max_{\theta}\mathbb{E}_{\tilde{\Pi}}\bigg{[}\sum_{t}^{T}r(\tilde{{\mathcal{S}}}(t))\bigg{]}$
(27)
$\displaystyle=\sum_{n=1}^{{N}}\max_{\theta}\int\sum_{t}^{T}r(\tilde{{\mathcal{S}}}(t))d\tilde{\Pi}$
(28)

Using the fact that $d\tilde{\Pi}=\mathbf{P}^{\top}d{\Pi}$ (from Proposition
2) and $r({\mathcal{S}}(t))=r(\tilde{{\mathcal{S}}}(t))$ we get;

$\sum_{n=1}^{{N}}\max_{\theta}\int\sum_{t}^{T}r(\tilde{{\mathcal{S}}}(t))d\tilde{\Pi}=\sum_{n=1}^{\mathbf{N}}\max_{\theta}\mathbf{P}^{\top}\int\sum_{t}^{T}r({\mathcal{S}}(t))d{\Pi}$
(29)

Since the set of robots is $\mathbf{N}$ for both $J_{\Pi}$ and
$J_{\tilde{\Pi}}$, we can conclude $J_{\tilde{\Pi}}=J_{\Pi}$ Thus, we conclude
that the unlabeled motion planning problem is permutation equivariant. With
these results, we construct the following proof:
Proof for Theorem 1 Let optimal coefficients $\mathbf{H}^{*}$ and
$\tilde{\mathbf{H}}^{*}$ induce a optimal reward $J^{*}$ and
$J_{\tilde{\Pi}}^{*}$ respectively. Consider the optimal filter coefficient
$\mathbf{H}$. From proposition 2, we have:

$\Phi(\tilde{{\mathbf{X}}}(t),\tilde{{\mathbf{S}}}(t);\mathbf{H})=\mathbf{P}^{\top}\Phi({\mathbf{X}}(t),{\mathbf{S}}(t);\mathbf{H})$
(30)

$\Phi(\tilde{{\mathbf{X}}}(t),\tilde{{\mathbf{S}}}(t);\mathbf{H})$ induces a
reward $J_{\tilde{\Pi}}$ while
$\mathbf{P}^{\top}\Phi({\mathbf{X}}(t),{\mathbf{S}}(t);\mathbf{H})$ induces
the optimal reward $J_{\Pi}^{*}$. However, as a result of Proposition 3, we
have:

$J_{\tilde{\Pi}}=J_{\Pi}^{*}$ (31)

Similarly by considering the optimal filter coefficient
$\tilde{\mathbf{H}}^{*}$:

$J_{\tilde{\Pi}}^{*}=J_{\Pi}$ (32)

If the cost $J_{\Pi}^{*}$ and $J_{\tilde{\Pi}}^{*}$ are the optimal costs,
then:

$\displaystyle J_{\Pi}^{*}\geq J_{\Pi}=J_{\tilde{\Pi}}$ (33) $\displaystyle
J_{\tilde{\Pi}}^{*}\geq J_{\tilde{\Pi}}=J_{\Pi}^{*}$ (34)

where the second equality follows from (31) and (32). From (33) and (34), we
can conclude that

$J_{\tilde{\Pi}}^{*}=J_{\Pi}^{*}$ (35)

Thus, we can conclude $\mathbf{H}^{*}\equiv\tilde{\mathbf{H}}^{*}$, completing
the proof for Theorem 1. One of the bottlenecks of RL for multi-robot systems
is the fact that it lacks the ability to scale to a large number of robots.
However, Theorem 1 and Proposition 2 offer us a valuable tool. When training,
we train only for a small number of robots with graph ${\mathbf{S}}(t)$ which
yields graph filters $\mathbf{H}$. By realizing that the bigger swarm consists
of smaller swarms that are permutations ${\mathbf{S}}(t)$ and the filter
coefficients for both are equivalent, we simply reuse the filter $\mathbf{H}$
on each of the smaller swarms. Thus, we are able to achieve large scale
unlabeled motion planning without the computational burden of having to train
a very large number of robots.

##  V Experiments

Figure 1: Training Curves for 3, 5 and 10 robots Policies trained by GPG are
able to converge on experiments with point mass robots, experiments where
robots follow single integrator dynamics and are velocity controlled as well
as experiments when disk shaped obstacles are present in the environment.

To test the efficacy of GPG on the unlabelled motion planning problem, we
setup a few experiments in simulation. We establish five main experiments. 1)
Unlabelled motion planning with three, five and ten robots where robots obey
point mass dynamics. 2) GPG is tested on three, five and ten robots but here
robots obey single integrator dynamics. 3) The robots follow single integrator
dynamics and additionally the environment is populated with disk shaped
obstacles. 4) The performance of GPG is tested against a model based provably
optimal centralized solution for the unlabelled motion planning problem. We
demonstrate empirically that the performance of GPG is almost always within a
small margin of that of the model based method but comes with the additional
advantage of being decentralized. 5) The learning formulation for the
unlabeled motion planning problem is agnostic to underlying robot dynamics or
operating conditions in the environment. To demonstrate this, we look to
execute the unlabeled motion planning problem in the higher order dynamics
simulator AirSim [12] equipped with quadrotors that model real world effects
such as downwash and wind. To establish relevant baselines, we compare GPG
with Vanilla Policy Gradients (VPG) where the policies for the robots are
parameterized by fully connected networks (FCNs). Apart from the choice of
policy parameterization there are no other significant differences between GPG
and VPG.

Figure 2: Transferring Learned GPG Filters for Large Scale Unlabelled Motion
Planning. (Left) A small number of robots are trained to cover goals and
follow point mass dynamics. During testing the number of robots as well as the
distance of the goals from the start positions are much greater than those
seen during training. (Center) A similar experiment is performed but now
robots have single integrator dynamics. (Right) In this experiment in addition
to single integrator dynamics, the environment also has obstacles that robots
must avoid.

###  V-A Experimental Details and Training

For GPG, we setup a L-layer GNN. For experiments involving 3 and 5 robots with
point mass experiments we find a 2 layer GNN, i,e a GNN that aggregates
information from neighbors that are at most 2 hops away to be adequate. For
experiments with 10 robots we find that GNNs with 4 layers work the best. For
the baseline VPG experiments, we use with 2-4 layers of FCNs. The maximum
episode length is $200$ steps and the discount factor $\gamma=0.95$. In
experiments with 3 robots, each robot senses 2 nearest goals and 1 nearest
robot. In experiments with 5 and more robots, robots sense 2 nearest goals and
2 nearest robots. The graph connects robots to their $1$,$2$ and $3$ nearest
neighbors in experiments with $3,5$ and $10$ robots respectively.

The behavior of GPG v/s VPG during training can be observed from Fig. 1. We
observe that in all cases GPG is able to produce policies that converge close
to the maximum possible reward (in all three cases maximum possible reward is
zero). When compared to the convergence plots of [6] who first proposed use of
RL for the unlabelled motion planning problem, this represents a large
improvement on just training. It can also be observed that GPG converges when
robot dynamics are changed or obstacles are added to the environment. While
this is not necessarily the optimal solution to the unlabelled motion problem,
it is an approximate solution to the unlabelled motion planning problem. The
FCN policies represented by VPG in Fig. 1 fail to converge even on the
simplest experiments.

###  V-B Experimental Results - Inference

The previous section shows the feasibility of GPG as a method for training a
large swarm of robots to approximately solve the unlabelled motion planning
problem. However, training a large number of robots is still a bottleneck due
to the randomness in the system. Training 10 robots with simple dynamics on a
state of the art NVIDIA 2080 Ti GPU with a 30 thread processor needs 7-8
hours. We see from our experiments that this time grows exponentially with an
increase in the number of robots. Thus, to overcome this hurdle and to truly
achieve large scale solutions for the unlabelled motion planning problem, we
hypothesize that since the graph filters learned by GPG only operate on local
information, in a larger swarm one can simply slide the same graph filter
everywhere in the swarm to compute policies for all robots without any extra
training. Intuitively, this can be attributed to the fact that while the
topology of the graph does not change from training time to inference time,
the size of the filter remains the same. As stated before, this is akin to
sliding a CNN filter on a larger image to extract local features after
training it on small images. To demonstrate the effect of GPG during inference
time, we setup three simple experiments where we distribute goals along
interesting formations. As described earlier, each robot only sees a certain
number of closest goals, closest robots and if present closest obstacles. Our
results can be seen in Fig. 2. The policies in Fig. 2(Left) and Fig. 2
(Center) are produced by transferring policies trained to utilize information
from 3-hop neighbors. In Fig. 2 the policies are transferred after being
trained to utilize information from 5-hop neighbors. Consider the formation
shown in Fig 2 (Left). Here each robot receives information about 3 of its
nearest goals and these nearest goals overlap with its neighbors. Further,
since the goals are very far away and robots are initialized close to each
other, a robot and its neighbor receives almost identical information. In such
a scenario the robots must communicate with each other and ensure that they
each pick a control action such that they do not collide into each other and
at the end of their trajectories, all goals must be covered. The GPG filters
learn this local coordination and can be extended to every robot in the swarm.
When training with obstacles, we extend the system state in Eqn. 1 to include
the positions of the obstacles ${\mathbf{O}}$ i.e
$\mathcal{S}(t)\\!=\\{{\mathbf{R}}(t),{\mathbf{G}},{\mathbf{O}}\\}$ and extend
the state of the robots in Eqn. II to observe $M$ nearest obstacles. The cost
itself is unchanged, and as such all results derived in this paper still hold
with the inclusion of the state of the obstacles. As before we train with the
GNN filters with a small number of robots and extend the filters to a larger
number. We observe in Fig 2 (Right) and attached video with this paper that
our solution is capable of covering goals even when obstacles are present.

We also study the effects of the choice of K and M on the performance of the
learned models. We observe that as the number of hops, i.e $K$ each robot
communicates with, the performance measured by looking at the success
percentage (number of times all goals are covered without collisions during
100 runs) during inference increases. However, this increases only to a
certain point after which there is a steep drop off in performance. This can
be explained to the increase in input dimensionality at each node, thus making
the problem more challenging. This result can be seen in Fig. 3 (Left). A
similar effect can be seen when the value of $M$, i.e direct neighbors and
goals that each robot senses. The increase in information only improves the
learning performance to a certain point after which there is a drop off in
performance as seen in Fig. 3(Right).

Figure 3: Success v/s choice of K and M. (L) During inference, we analyze
effects of choices for K and M.

###  V-C Comparison to Centralized Model Based Methods

To further quantify the performance of GPG, we compare with a model based
approach that uses centralized information, called concurrent assignment and
planning (CAPT), proposed in [3]. When used in an obstacle free environment,
it guarantees collision free trajectories. We direct the reader to [3] for
more details about the CAPT algorithm. We set up three different formations
F1, F2 and F3 similar to that in Fig 2 (Center). On average the goals in F3
are further away from the starting positions of the robots than those in F2
and those in F2 are further away from goals in F1. In this work, we treat CAPT
as the oracle and look to compare how well GPG performs when compared to this
oracle. We use time to goals as a metric to evaluate GPG against this
centralized oracle. Our results can be seen in Fig. 4 (Left). The key takeaway
from this experiment is that decentralized inference using GPG, performs
always within an $\epsilon$ margin (approximately 12-15 seconds) of the
optimal solution and this margin remains more or less constant even if the
goals are further away and if the number of robots are increased. However, GPG
outshines CAPT when the planning times for both are compared. CAPT employs the
hungarian algorithm to solve the task assignment and as a result has a time
complexity of $\mathcal{O}(n^{3})$ whereas GPG only requires a feedforward
pass during inference. The planning times for both methods can be seen Fig. 4
(Right). It is important to note that in the original CAPT method, the optimal
performance guarantees zero collisions. While the solution proposed in this
paper is a learned solution with the advantage of being decentralized, we
cannot guarantee collision free trajectories. Nevertheless, we analyze the
number of collisions between robots. This performance can be seen in Table .
We argue that while any learned method cannot guarantee collision free
trajectories, it has been shown in the past that simple model based backup
policies can be used in conjunction with learned policies to empirically
guarantee collision free trajectories[6]. To analyze this, we use velocity
obstacles [13] as a backup policy that intervenes every time a collision
between two robots executing GPG policies is imminent. We call this method
GPG+VO. It is important to note that in order to prevent GPG+VO from producing
degenerate solutions at the cost of collision free trajectories, we add a
penalty term to the cost function every time VO is called during training.

Figure 4: Time to Goals and Planning Time (Left) Time taken by CAPT to cover
all goals v/s time taken by GPG to cover all goals when robots follow velocity
controls. (Right) CAPT v/s GPG Planning Times.

.

We analyze these results in Table I for 30 robots over 3 line to circle
formations similar to the one seen in Fig 2 (Right). The formations R1 < R2 <
R3 differ from each other in the size of the radius of the circle on which the
goals are distributed. As in Fig 4 (Left) we observe that the difference
between CAPT and GPG is the same even with different number of formations. In
terms of number of collisions when the robots have more open space to operate,
the number of collisions are almost reduced to zero with just GPG. When the
room to operate is small as in R1 the GPG based policy tends to produce a
higher number of collisions. The backup model based policy in GPG+VO is able
to remove the number of collisions but results in an increase in time to cover
goals. Using the backup model based velocity obstacles, increases the time
required by an almost negligible amount when the robots have significant room
to operate such as in R3 and at the same time offers a decentralized solution.
Hence, we conclude that decentralized GPG is close in performance to the
provably optimal centralized solution.

| CAPT | GPG | GPG+VO
---|---|---|---
T(sec) | C | T(sec) | C | T(sec) | C
R1 | 68.27 | 0 | 85.31 | 11.4 | 94.9 | 0
R2 | 83.4 | 0 | 103.56 | 8.1 | 112.62 | 0
R3 | 98.16 | 0 | 122.15 | 2.3 | 124.15 | 0
TABLE I: CAPT vs GPG vs GPG+VO. Total time (T(sec)) and total number of
collisions (C) during inference for 30 robots over 3 line to circle formations
R1, R2 and R3 similar to the one seen in Fig 2 (Right). R1 < R2 < R3 differ
from each other in the size of the radius of the circle on which the goals are
distributed. Averaged over 20 runs.

###  V-D High Order Dynamics

In the previous experiments, we modeled the robots as ideal point mass systems
to study the feasibility of GNNs for the unlabeled motion planning problem. In
this experiment we test our learned policies in the AirSim simulator which
allows us to test our policies in the presence of higher order dynamics,
slower control rates and latency in observations thus mimicking a real world
robot swarm more realistically. In such a setting it is even more imperative
to be able to train with a smaller number of robots and be able to transfer to
a larger number without any additional training samples due to the increased
computational complexity associated with training a large number of robots
directly in the simulator. In this setting, the outputs from the policies are
interpreted as accelerations and are converted to desired roll and pitch
commands which are fed into the simulator. Further, since our proposed
framework is model free, it can still be trained directly as before with only
a sparse reward. Empirically, in Fig 5 and the attached video we observe our
The action ${\mathbf{S}}_{nt}$ chosen by the robot gives the change in
velocities. We execute the same paradigm as before. The unlabeled motion
planning is trained for a small number of robots. Then, during inference time
the filters learned for the small swarm are used across all the robots. A
snapshot of the performance of our algorithm can be seen in Fig 5.

Figure 5: Large Scale Unlabelled Motion Planning in AirSim using GPG. Control
to the training algorithm is handed after robots are at a certain altitude.
(L) During inference, we use the trained filters to cover goals spread on the
edges of a cube. (R) Goals to be covered are spread along a W.

##  VI Conclusion

In this paper, we look to achieve scalable decentralized solutions for the
full unlabelled motion planning problem. In this work, we propose connecting
the robots with a naive graph and utilize this graph structure to generate
policies from local information by employing GNNs. We show that these policies
can be transferred over to a larger number of robots and the solution computed
is close to the solution computed by a centralized oracle. One of the caveats
of this paper is that it is assumed nearest robots can always be sensed which
can potentially break down in a real world setting. Incorporating this is a
potential avenue we leave for future work.

## References

  * [1] A. Adler, M. De Berg, D. Halperin, and K. Solovey, “Efficient multi-robot motion planning for unlabeled discs in simple polygons,” in _Algorithmic Foundations of Robotics XI_. Springer, 2015, pp. 1–17.
  * [2] J. Yu and M. LaValle, “Distance optimal formation control on graphs with a tight convergence time guarantee,” in _Decision and Control (CDC), 2012 IEEE 51st Annual Conference on_. IEEE, 2012, pp. 4023–4028.
  * [3] M. Turpin, N. Michael, and V. Kumar, “Capt: Concurrent assignment and planning of trajectories for multiple robots,” _The International Journal of Robotics Research_ , vol. 33, no. 1, pp. 98–112, 2014.
  * [4] T. N. Kipf and M. Welling, “Semi-supervised classification with graph convolutional networks,” _arXiv preprint arXiv:1609.02907_ , 2016.
  * [5] Z. Wu, S. Pan, F. Chen, G. Long, C. Zhang, and P. S. Yu, “A comprehensive survey on graph neural networks,” _arXiv preprint arXiv:1901.00596_ , 2019\.
  * [6] A. Khan, C. Zhang, S. Li, J. Wu, B. Schlotfeldt, S. Y. Tang, A. Ribeiro, O. Bastani, and V. Kumar, “Learning safe unlabeled multi-robot planning with motion constraints,” _arXiv preprint arXiv:1907.05300_ , 2019.
  * [7] R. S. Sutton and A. G. Barto, _Reinforcement learning: An introduction_. MIT press Cambridge, 1998, vol. 1, no. 1.
  * [8] K. Solovey and D. Halperin, “On the hardness of unlabeled multi-robot motion planning,” _The International Journal of Robotics Research_ , vol. 35, no. 14, pp. 1750–1759, 2016.
  * [9] K. Solovey, J. Yu, O. Zamir, and D. Halperin, “Motion planning for unlabeled discs with optimality guarantees,” _arXiv preprint arXiv:1504.05218_ , 2015\.
  * [10] A. Faust, K. Oslund, O. Ramirez, A. Francis, L. Tapia, M. Fiser, and J. Davidson, “Prm-rl: Long-range robotic navigation tasks by combining reinforcement learning and sampling-based planning,” in _2018 IEEE International Conference on Robotics and Automation (ICRA)_. IEEE, 2018, pp. 5113–5120.
  * [11] A. Khan, E. Tolstaya, A. Ribeiro, and V. Kumar, “Graph policy gradients for large scale robot control,” _arXiv preprint arXiv:1907.03822_ , 2019.
  * [12] S. Shah, D. Dey, C. Lovett, and A. Kapoor, “Airsim: High-fidelity visual and physical simulation for autonomous vehicles,” in _Field and service robotics_. Springer, 2018, pp. 621–635.
  * [13] P. Fiorini and Z. Shiller, “Motion planning in dynamic environments using velocity obstacles,” _The International Journal of Robotics Research_ , vol. 17, no. 7, pp. 760–772, 1998.