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.

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

未被映射环境中多车路径规划的分布式在线发布

Distributed Online Rollout for Multivehicle Routing in Unmapped  Environments

Multi-agent settings remain a fundamental challenge in the reinforcement
learning (RL) domain due to the partial observability and the lack of accurate
real-time interactions across agents. In this paper, we propose a new method
based on local communication learning to tackle the multi-agent RL (MARL)
challenge within a large number of agents coexisting. First, we design a new
communication protocol that exploits the ability of depthwise convolution to
efficiently extract local relations and learn local communication between
neighboring agents. To facilitate multi-agent coordination, we explicitly learn
the effect of joint actions by taking the policies of neighboring agents as
inputs. Second, we introduce the mean-field approximation into our method to
reduce the scale of agent interactions. To more effectively coordinate
behaviors of neighboring agents, we enhance the mean-field approximation by a
supervised policy rectification network (PRN) for rectifying real-time agent
interactions and by a learnable compensation term for correcting the
approximation bias. The proposed method enables efficient coordination as well
as outperforms several baseline approaches on the adaptive traffic signal
control (ATSC) task and the StarCraft II multi-agent challenge (SMAC).

本文提出了一种基于局部通信学习的新方法来解决存在大量代理并存的多代理强化学习挑战，其中我们设计了一种利用深度卷积提取局部关系和在邻近代理之间学习局部通信的新通信协议，在此基础上，我们显式地学习联合动作的影响，并引入均场近似来减少代理之间的交互规模，可以更有效地协调邻近代理的行为，并在不同任务中表现良好。