In this work we consider a generalization of the well-known multivehicle
routing problem: given a network, a set of agents occupying a subset of its
nodes, and a set of tasks, we seek a minimum cost sequence of movements subject
to the constraint that each task is visited by some agent at least once. The
classical version of this problem assumes a central computational server that
observes the entire state of the system perfectly and directs individual agents
according to a centralized control scheme. In contrast, we assume that there is
no centralized server and that each agent is an individual processor with no a
priori knowledge of the underlying network (including task and agent
locations). Moreover, our agents possess strictly local communication and
sensing capabilities (restricted to a fixed radius around their respective
locations), aligning more closely with several real-world multiagent
applications. These restrictions introduce many challenges that are overcome
through local information sharing and direct coordination between agents. We
present a fully distributed, online, and scalable reinforcement learning
algorithm for this problem whereby agents self-organize into local clusters and
independently apply a multiagent rollout scheme locally to each cluster. We
demonstrate empirically via extensive simulations that there exists a critical
sensing radius beyond which the distributed rollout algorithm begins to improve
over a greedy base policy. This critical sensing radius grows proportionally to
the $\log^*$ function of the size of the network, and is, therefore, a small
constant for any relevant network. Our decentralized reinforcement learning
algorithm achieves approximately a factor of two cost improvement over the base
policy for a range of radii bounded from below and above by two and three times
the critical sensing radius, respectively.

本文提出了一种完全分布式、在线和可扩展的增强学习算法，用于解决多车辆路径规划问题，代理定期聚集在本地簇中，独立地在每个簇中应用多智能体扩展方案，动态地在代理之间协调任务并共享其局部信息。通过较大规模的模拟，证明了分布式滚动算法比贪婪基础策略具有近两倍的成本优势。