郑州大学徐明亮教授团队 | DPCN:一种高效解决多智能体路径规划冲突的新范式

研究团队

刘起东，李晓雯，展闯，徐明亮：郑州大学

张杰，龙程：南洋理工大学

本文工作

本文提出了一种新颖的“分散式规划–集中式协商”（Decentralized-Planning-Centralized-Negotiation, DPCN）范式，用于高效求解MAPF问题。如图1所示，DPCN将每个时间步划分为两个阶段：

规划阶段：每个智能体 i（如AGV）基于局部观测信息 o_i^t（视野为 3 * 3），独立生成一个动作意图 a ̃_i^t  ϵ A，其中。

协商阶段：系统检测所有潜在冲突（包括顶点冲突和交换冲突），并将涉及冲突的智能体动态聚合成“超级智能体”（super-agents）。每个超级智能体内部包含相互冲突的一组成员智能体。随后，通过本文提出的可学习的PNSE网络（Pointer Network Special Edition），根据当前环境状态，从该冲突集内部的成员智能体中选出一名“获胜者”执行其原始意图，其余智能体则保持静止或根据策略重新采样新动作。

图1 DPCN总体架构图

然而，该设计面临着两大挑战：

1. 动作集不一致：超级智能体的动作集由其内部成员智能体构成，不同冲突集拥有不同的成员智能体，因此无法使用固定动作集进行建模。

2. 动态训练困难：环境中的超级智能体会随着时间动态变化，这种动态性使得无法为每个超级智能体分配特定的策略网络 π_k 和动作价值函数 Q_k，从而导致训练困难。

为了应对上述挑战，本文受到指针网络的启发，设计了PNSE网络，它能够根据当前环境状态和冲突集内部关系，动态输出优先级分布，并选择最优执行者（即获胜者）。进一步地，本文提出一种定制化的策略梯度强化学习训练机制，采用平均场场近似（mean-field approximation）对全局回报进行公平分配，从而实现对动态超级智能体的有效训练。

本文的主要贡献如下：

1. 本文提出了分散式规划-集中式协商（DPCN）范式来解决多智能体路径规划（MAPF）问题。在该范式下，本文引入了一个新概念——超级智能体，它是代表一组智能体的概念性实体，而不是一个物理或独立的智能体。为了训练能够在动态且不断变化的超级智能体环境中有效运作的策略网络，本文设计了一种定制的多智能体强化学习（MARL）方法。

2. 本文设计了PNSE网络，其具备处理变长输入与不一致动作空间的能力，限制提升冲突解决效率。

实验结果