  In this paper we tackle the problem of routing multiple agents in a
coordinated manner. This is a complex problem that has a wide range of
applications in fleet management to achieve a common goal, such as mapping from
a swarm of robots and ride sharing. Traditional methods are typically not
designed for realistic environments hich contain sparsely connected graphs and
unknown traffic, and are often too slow in runtime to be practical. In
contrast, we propose a graph neural network based model that is able to perform
multi-agent routing based on learned value iteration in a sparsely connected
graph with dynamically changing traffic conditions. Moreover, our learned
communication module enables the agents to coordinate online and adapt to
changes more effectively. We created a simulated environment to mimic realistic
mapping performed by autonomous vehicles with unknown minimum edge coverage and
traffic conditions; our approach significantly outperforms traditional solvers
both in terms of total cost and runtime. We also show that our model trained
with only two agents on graphs with a maximum of 25 nodes can easily generalize
to situations with more agents and/or nodes.
