多智能体协作系统的一小步：合作奖励塑造（CoRS）方法提升路径规划（MAPF）效率的策略
多智能体协作系统的一小步，可能是AI 应用爆发的一大步。
多智能体路径规划（MAPF）在AI应用中扮演着越来越重要的角色，无论是在自动化仓库中协调机器人，还是在智能交通系统中管理无人驾驶汽车，MAPF 都是实现高效协作的关键技术。通过为每个智能体规划无冲突的路径，MAPF 不仅提高了系统的整体效率，还减少了资源浪费和潜在的安全隐患。
在物流、制造、交通等领域，MAPF 的应用前景广阔。例如，在一个大型仓库中，数百个机器人需要在狭小的空间内高效移动，避免碰撞并完成各自的任务。传统的路径规划方法难以应对如此复杂的场景，而 MAPF 提供了一种解决方案，使得这些机器人能够协同工作，显著提升了工作效率和安全性。
尽管传统的路径规划算法在单智能体环境中表现良好，但在多智能体环境中却面临诸多挑战。传统算法通常依赖于全局信息，通过集中式的方式为每个智能体规划路径。然而这种方法在处理大量智能体时，计算复杂度急剧增加，导致规划时间过长，难以实时应用。
此外，传统算法缺乏智能体之间的协作机制，容易导致路径冲突和资源竞争。例如，在一个复杂的交通系统中，多个无人驾驶汽车需要同时通过一个交叉路口。如果没有有效的协作机制，这些汽车可能会因为路径冲突而发生交通事故，影响整个系统的运行效率。
为了解决传统路径规划算法的局限性，研究人员开始探索将强化学习（RL）应用于 MAPF 问题。强化学习通过模拟智能体在环境中的行为，不断调整策略以最大化累积奖励，从而实现高效的路径规划和冲突避免。
在多智能体强化学习（MARL）中，每个智能体通过局部观测和与其他智能体的通信，学习分布式策略。这种方法不仅提高了系统的可扩展性，还增强了智能体在动态环境中的适应能力。例如，PRIMAL 算法利用异步优势演员评论（A3C）算法，通过行为克隆进行监督强化学习训练，显著提升了路径规划的效率。
尽管 MARL 在解决 MAPF 问题上表现出色，但由于缺乏全局信息，智能体之间的合作性仍然不足，影响了整体效率。为此新的研究提出了一种基于独立 Q 学习（IQL）的合作奖励塑造（CoRS）方法，通过评估智能体对其邻居的影响，促进智能体之间的主动合作。
7 月 15 日发表于国际学术交流平台arXiv的论文《Cooperative Reward Shaping for Multi-Agent Pathfinding》研究的目标是通过引入合作奖励塑造（CoRS）方法，提升多智能体路径规划（MAPF）的效率。具体而言，通过在 IQL 框架内设计合作性度量指标，将智能体之间的交互整合到奖励函数中，促进智能体之间的合作，从而提高系统的整体效率。
研究贡献
引入合作奖励塑造方法：论文提出了一种新的奖励塑造方法 CoRS，旨在在 IQL 框架内促进 MAPF 任务中智能体之间的合作。
提高系统效率：通过实验验证，CoRS 方法在多个场景中表现出色，尤其是在大量智能体的场景中，显著提高了路径规划的成功率和效率。
简化计算复杂度：论文还提出了一种近似计算方法，显著降低了奖励塑造方法的计算复杂度，使其在大规模系统中具有更好的可扩展性。
论文的作者团队包括 Zhenyu Song、Ronghao Zheng、Senlin Zhang 和 Meiqin Liu，他们在多智能体系统、强化学习和自主机器人探索等领域有着丰富的研究经验。团队成员在多个研究项目中都有贡献，涉及自主机器人探索、信息理论和多智能体系统等领域。
在多智能体路径规划（MAPF）领域，研究人员已经提出了多种方法来解决路径冲突和提高系统效率。我们将从基于强化学习的MAPF和奖励塑造在多智能体系统中的应用两个方面进行详细解读。
强化学习（RL）在多智能体路径规划中的应用已经取得了显著进展。RL规划器通过模拟智能体在环境中的行为，不断调整策略以最大化累积奖励，从而实现高效的路径规划和冲突避免。RL规划器通常将MAPF问题视为多智能体强化学习（MARL）问题，通过部分观测学习分布式策略。这种方法特别适用于大量智能体的环境，因为它能够在不依赖全局信息的情况下，利用局部观测和智能体间的通信来实现高效的路径规划。
例如，PRIMAL算法利用异步优势演员评论（A3C）算法，通过行为克隆进行监督强化学习训练。PRIMAL算法在训练过程中使用了集中式规划器ODrM*的经验，这种方法在一定程度上提高了路径规划的效率。然而，PRIMAL算法依赖于集中式规划器，这限制了其在复杂环境中的效率，因为解决MAPF问题可能需要大量时间，特别是在智能体数量较多的情况下。
PRIMAL算法是基于强化学习和模仿学习的多智能体路径规划方法。它利用A3C算法和行为克隆技术，通过从集中式规划器ODrM*中获取经验进行训练。尽管这种方法在一定程度上提高了路径规划的效率，但其依赖于集中式规划器的特性限制了其在大规模和复杂环境中的应用。
具体来说，PRIMAL算法在处理大量智能体时，计算复杂度急剧增加，导致规划时间过长，难以实时应用。此外，集中式规划器需要全局信息，这在动态和不确定的环境中难以获取。因此，PRIMAL算法在处理大规模多智能体系统时，面临着显著的挑战。
为了克服集中式算法的局限性，研究人员提出了多种分布式算法，如分布式启发式协调（DHC）和决策因果通信（DCC）算法。这些算法不需要集中式规划器，通过分布式的方式实现路径规划和冲突避免。
DHC算法通过将所有可能的最短路径选择纳入模型的启发式输入，而不是强制智能体选择特定路径，从而提高了算法的灵活性。此外，DHC算法收集邻居智能体的数据来辅助决策，并使用多头注意力机制计算智能体间的交互。这种方法不仅提高了系统的可扩展性，还增强了智能体在动态环境中的适应能力。
DCC算法则通过选择性与邻居通信来提高智能体的性能。在训练和执行阶段，智能体仅在邻居对其决策产生影响时进行通信，从而减少了不必要的通信开销。DCC算法引入了复杂的决策因果单元，帮助智能体确定在训练和执行阶段的适当通信对象。这种方法不仅提高了智能体的合作性，还显著提升了系统的整体效率。
在多智能体系统中，奖励函数的设计对强化学习算法的性能有着重要影响。一个合理的奖励函数可以显著提高算法的学习效率和智能体的性能。研究人员不断探索如何设计奖励函数，以优化算法的学习过程和智能体的行为。
奖励函数的设计不仅需要考虑个体智能体的目标，还需要促进智能体之间的合作。在多智能体路径规划中，智能体之间的合作对于避免路径冲突和提高系统效率至关重要。因此，设计能够激励合作行为的奖励函数成为了研究的重点。
亲社会奖励塑造是一种通过设计奖励函数来增强智能体合作行为的方法。例如，在两人猎鹿游戏中，通过引入亲社会系数，奖励函数可以激励智能体进行合作，从而提高系统的整体性能。实验表明，亲社会奖励塑造方法在具有静态网络结构的多智能体系统中表现出色。
因果影响评估则通过反事实推理来评估智能体行为对其他智能体的影响。具体来说，每个智能体在每个时间步模拟替代动作，并计算这些动作对其他智能体行为的影响。那些对其他智能体行为产生显著变化的动作被认为是有影响力的，并因此获得奖励。这种方法通过奖励显著影响行为的动作，促进了智能体之间的合作。
Shapley值分解方法是一种用于计算或重新分配智能体合作收益的方法。Shapley值源自合作博弈论，用于衡量每个参与者对合作收益的贡献。在多智能体系统中，Shapley值分解方法可以用于奖励分配，以确保智能体之间的稳定和有效合作。
例如，在自主驾驶场景中，基于Shapley值的奖励重分配方法可以显著提高智能体的合作性和系统的整体效率。然而，Shapley值的计算过程复杂且耗时。为了解决这一问题，研究人员提出了近似方法，如边际贡献的近似和蒙特卡罗采样，以简化Shapley值的计算。
协调策略优化（CoPO）算法引入了“合作系数”的概念，通过加权平均智能体及其邻居的奖励来塑造奖励。具体来说，合作系数用于调整智能体的奖励函数，使其既考虑自身利益，又考虑邻居的利益。这种方法证明了通过合作系数塑造的奖励满足个体全局最大化（IGM）条件。
在交通模拟实验中，CoPO算法显著提高了系统的整体性能和安全性。然而，这种方法将智能体的奖励不仅与其自身的动作相关，还与其邻居的动作相关，这可能会影响训练过程的稳定性和收敛效率。
在多智能体路径规划（MAPF）中，环境设置是实现高效路径规划和冲突避免的基础。下面我们详细介绍论文中对MAPF环境的定义、奖励函数的设计以及奖励塑造方法的具体实现。
图1：现实世界中的多智能体场景和包含众多移动机器人的网格地图。在网格地图中，蓝色单元格表示智能体，黄色单元格表示其目标，绿色单元格表示已实现其目标的智能体。
论文采用了标准的多智能体路径规划环境，具体为一个 (w \times h) 的无向网格图 (G(V, E))，其中 (V) 是图中的顶点集合，(E) 是边集合。网格图中的每个顶点 (v(i, j)) 表示一个位置，所有智能体和障碍物都位于这些顶点上。顶点之间遵循4邻域规则，即每个顶点与其上下左右四个方向的邻居相连。
在这个环境中，有 (n) 个智能体和 (m) 个障碍物。每个智能体 (A_i) 有一个唯一的起始顶点 (s_i) 和目标顶点 (g_i)，其在时间步 (t) 的位置为 (x_i^t)。障碍物的位置用 (b_k) 表示。智能体的动作空间为 ({“上”, “下”, “左”, “右”, “停”})。
在每个时间步，智能体可以选择一个动作来改变其位置。可能出现的冲突包括：
顶点冲突：两个智能体或智能体与障碍物占据同一顶点（(x_i^t = x_j^t) 或 (x_i^t = b_k)）。
边冲突：两个智能体在同一时间步交换位置（([x_i^{t-1}, x_i^t] = [x_j^t, x_j^{t-1}])）。
当发生冲突时，相关智能体的位置保持不变，以避免实际的碰撞。MAPF问题的目标是为所有智能体找到一组无冲突的路径，使每个智能体从起始点 (s_i) 移动到目标点 (g_i)。具体来说，路径 (P_i = [s_i, x_i^1, \ldots, x_i^t, \ldots, g_i]) 是智能体 (A_i) 的位置序列。最终目标是找到一组路径 (P = {P_1, P_2, \ldots, P_n})，确保所有智能体在最短时间内到达各自的目标点，并且在移动过程中不发生冲突。
为了激励智能体朝目标移动并避免冲突，论文设计了一个奖励函数。奖励函数的具体设置如下：
这种奖励函数设计旨在鼓励智能体尽快到达目标点，同时避免与其他智能体或障碍物发生冲突。
为了进一步提高智能体之间的合作性，论文提出了一种合作奖励塑造（CoRS）方法。该方法通过评估一个智能体对其邻居的影响，并将这种交互整合到奖励函数中，从而促进智能体之间的主动合作。
具体来说，合作性度量指标被定义为在给定状态和动作下，智能体的动作对其邻居的最大影响。公式如下：
图 2：CoRS 和 DHC 算法的组合框架。CoRS 组件主要塑造奖励。DHC 组件由通信块和对决 Q 网络组成。值得注意的是，通信块采用多头注意力机制。该框架利用并行训练作为一种有效的解决方案。此过程涉及同时生成多个参与者以生成经验数据并将其上传到全局缓冲区。然后，学习者从全局缓冲区中检索此数据以进行训练，从而允许频繁更新参与者的网络。
通过这种奖励塑造方法，智能体在最大化自身奖励的同时，也会考虑其动作对其他智能体的影响，从而促进智能体之间的合作，提高系统的整体效率。
在多智能体路径规划（MAPF）中，智能体之间的合作性是实现高效路径规划和避免冲突的关键。论文提出了一种合作奖励塑造（CoRS）方法，通过设计合作性度量指标和调整奖励函数，促进智能体之间的合作。
独立Q学习（IQL）是一种常用于多智能体系统的强化学习方法。在IQL框架下，每个智能体独立地学习和优化其策略，目标是最大化自身的累积奖励。然而，这种方法存在一个显著的问题：由于每个智能体只关注自身的奖励，缺乏对其他智能体行为的考虑，导致智能体之间的合作性较差。
在多智能体路径规划中，这种缺乏合作性的行为可能会导致路径冲突和资源竞争。例如，一个智能体可能会选择一条最优路径，但这条路径可能会与其他智能体的路径发生冲突，导致整体效率下降。因此，如何在IQL框架下增强智能体之间的合作性，成为了一个亟待解决的问题。
为了提高智能体之间的合作性，奖励塑造成为了一种有效的方法。奖励塑造通过设计合理的奖励函数，引导智能体的行为，使其不仅关注自身的奖励，还考虑其行为对其他智能体的影响。通过这种方式，可以促进智能体之间的合作，减少路径冲突，提高系统的整体效率。
在多智能体路径规划中，奖励塑造的必要性尤为突出。通过设计合作性奖励函数，可以激励智能体在选择路径时考虑其他智能体的行为，从而避免冲突，实现高效的路径规划。
为了实现奖励塑造，首先需要定义一个合作性度量指标，用于评估智能体行为的合作性。论文提出的合作性度量指标通过评估一个智能体对其邻居的影响来衡量其合作性。具体公式如下：
通过最大化操作，消除了其他智能体动作对合作性度量的影响，同时反映了智能体 (A_i) 的动作对其他智能体的影响。
在定义了合作性度量指标之后，需要将其整合到奖励函数中，以实现奖励塑造。论文提出的奖励函数调整公式如下：
通过调整，可以在自私和合作之间找到一个平衡点，从而实现智能体之间的有效合作。
为了更好地分析奖励塑造方法的效果，论文引入了虚拟智能体的概念。将所有其他智能体视为一个虚拟智能体 ，其动作为 (a{-i})，奖励为平均奖励。通过这种方式，可以简化智能体之间的交互分析。
这种方法确保了智能体 和虚拟智能体处于平等地位，有助于分析奖励塑造方法对智能体行为的影响。
合作系数 是奖励塑造方法中的关键参数，它直接影响智能体的行为。当 较小时，智能体更倾向于自私行为，关注自身的奖励；当较大时，智能体更倾向于合作行为，考虑其动作对其他智能体的影响。
通过实验验证，论文发现当 (\alpha = 0.5) 时，智能体的行为能够较好地平衡自私和合作，实现系统的整体最优。具体来说，智能体在选择路径时，不仅考虑自身的最优路径，还会考虑其他智能体的路径，从而避免冲突，提高系统的整体效率。
在多智能体路径规划（MAPF）中，计算复杂度是一个关键问题。为了提高算法的可扩展性和效率，论文提出了一种近似方法，通过简化计算过程来实现高效的合作奖励塑造。
在多智能体系统中，每个智能体都有自己的动作空间。当智能体数量增加时，联合动作空间的大小呈指数级增长。例如，对于每个智能体有5个可能动作的情况，(n) 个智能体的联合动作空间包含 (5^n) 个状态。这种指数级增长的计算复杂度使得在大规模系统中直接计算联合动作空间变得不可行。
在MAPF问题中，计算联合动作空间的复杂度不仅影响路径规划的效率，还直接影响奖励塑造方法的实现。为了在大规模系统中实现高效的奖励塑造，必须简化联合动作空间的计算过程。
为了简化计算过程，论文引入了邻居的概念。在网格图中，如果两个智能体之间的曼哈顿距离不超过 (d_n)，则认为它们是邻居。选择合适的邻居半径 (d_n) 可以在保证智能体间有效交互的同时，最大限度地简化计算过程。
在论文的实验中，选择 (d_n = 2) 作为邻居半径。这意味着如果两个智能体之间的曼哈顿距离不超过2，它们就被视为邻居。这个选择不仅简化了智能体间的交互，还充分考虑了潜在的冲突。
在定义了邻居之后，可以通过近似计算方法来简化合作性度量指标的计算。具体来说，将智能体与所有其他智能体的交互简化为智能体与其邻居的交互。这种近似方法意味着我们考虑智能体与其一个邻居的交互，而不是所有邻居的联合动作。通过这种方式，可以显著降低计算复杂度。
这种方法不仅简化了计算过程，还确保了奖励函数的稳定性和收敛性。
通过引入邻居和近似计算方法，论文提出的奖励塑造方法在计算复杂度上得到了显著简化。这种简化不仅提高了算法的效率，还增强了奖励函数的稳定性和收敛性。具体来说，奖励函数 仅依赖于智能体自身的动作，不依赖于其他智能体的动作，从而减少了计算过程中的不确定性。
实验结果表明，使用近似计算方法的奖励塑造方法在训练过程中表现出较低的训练损失和较快的收敛速度。这表明该方法在大规模多智能体系统中具有良好的适用性。论文提出的奖励塑造方法适用于邻居关系随时间变化的多智能体路径规划场景。通过考虑智能体与其邻居的交互，可以在保证有效合作的同时，显著降低计算难度。
大规模多智能体系统：在智能体数量较多的情况下，近似计算方法可以显著降低计算复杂度，提高系统的整体效率。
动态环境：在智能体位置和邻居关系不断变化的动态环境中，论文的方法能够快速适应变化，实现高效的路径规划和冲突避免。
论文提出的近似方法通过简化计算过程，提高了奖励塑造方法的效率和稳定性，为大规模多智能体路径规划提供了一种有效的解决方案。
在多智能体路径规划（MAPF）研究中，实验验证是评估算法性能的重要环节。论文通过一系列实验，验证了合作奖励塑造（CoRS）方法在提高智能体合作性和路径规划效率方面的有效性。
实验在标准的多智能体路径规划环境中进行。具体来说，实验环境为一个 (w \times h) 的无向网格图，每个智能体有一个 9×9 的视野（FOV），并且可以与最多两个最近的邻居通信。网格图中的每个顶点表示一个位置，所有智能体和障碍物都位于这些顶点上。智能体的动作空间为 ({“上”, “下”, “左”, “右”, “停”})。
训练过程采用了课程学习方法，逐步引入更具挑战性的任务。训练从一个简单的任务开始，即在 10×10 的环境中只有一个智能体。当成功率超过 0.9 时，逐步增加智能体数量或环境大小，最终在 40×40 的环境中处理 10 个智能体。
图5：在10×10的地图上，使用10个代理训练两种不同奖励塑造方法的损失。
每个回合的最大步数为 256，批量大小为 192，序列长度为 20，动态学习率从 (10^{-4}) 开始，在 100,000 和 300,000 步时减半，最大训练步数为 500,000。微调期间，学习率保持在 (10^{-5})。使用分布式训练提高效率，16 个独立环境并行运行生成智能体经验，这些经验被上传到全局缓冲区，学习器从缓冲区中检索数据并在GPU上训练智能体策略。
在训练过程中，通过多轮网络微调和合作系数 (\alpha) 的调整，最终获得了 (\alpha = 0.1675) 和策略 (\pi)。为了评估奖励塑造方法的效果，将CoRS-DHC训练的策略与原始DHC算法进行比较。
实验在不同规模的地图（40×40 和 80×80）和不同数量的智能体（4, 8, 16, 32, 64）上进行测试。为了获得更多的见解，还在80×80的地图上引入了128个智能体的场景。每个实验场景包括200个独立的测试案例，障碍物密度保持在0.3。40×40和80×80地图的最大时间步数分别为256和386。
实验结果表明，CoRS-DHC在所有测试集中显著优于现有的DHC算法，尤其是在高密度智能体场景中，路径规划成功率提高了20%以上。此外，CoRS方法有效减少了所有智能体到达目标点所需的步数。
尽管DHC算法结合了启发式函数和智能体间的通信，但在智能体合作性方面仍存在问题。相比之下，CoRS-DHC通过奖励塑造促进了智能体间的合作，从而显著提升了DHC算法在高密度场景中的性能。值得注意的是，这一显著改进是在不改变算法结构或网络规模的情况下实现的，突显了CoRS方法的有效性。
图6：通过CoRS增强DHC。该图显示了CoRS DHC和DHC在不同测试场景下的成功率。该表提供了在不同测试环境中完成任务所需的平均步骤。
为了进一步验证CoRS-DHC的性能，将其与其他先进的MAPF算法进行比较。选择了当前最先进的DCC算法作为主要比较对象，同时以集中式MAPF算法ODrM*和基于RL和IL的PRIMAL作为参考。
DCC算法通过选择性与邻居通信来提高智能体性能，引入了复杂的决策因果单元，帮助智能体确定在训练和执行阶段的适当通信对象。PRIMAL算法通过模仿ODrM并结合强化学习，实现了分布式MAPF。ODrM作为集中式算法，旨在为多个智能体生成最优路径，是目前最好的集中式MAPF算法之一。
实验结果表明，CoRS-DHC算法在大多数场景中的成功率均超过DCC算法。此外，除了40×40网格中有64个智能体的场景外，CoRS-DHC算法训练的策略的完成时间与DCC算法相当或更短。这些结果清楚地表明，CoRS-DHC算法在性能上与DCC相当，但DCC在训练和执行期间采用了更复杂的通信机制，而CoRS算法仅在训练阶段使用简单的奖励塑造。
- 合作奖励塑造的有效性：CoRS方法通过设计合理的合作性度量指标和调整奖励函数，显著提高了智能体之间的合作性和路径规划效率。
- 计算复杂度的降低：通过引入邻居和近似计算方法，CoRS方法在计算复杂度上得到了显著简化，适用于大规模多智能体系统。
- 与先进算法的比较：CoRS-DHC算法在大多数场景中的性能均优于或相当于当前最先进的MAPF算法，突显了其在多智能体路径规划中的应用潜力。
后面的工作可以将CoRS方法扩展到其他多智能体任务中，如多智能体协作、资源分配和任务调度等。通过设计合理的合作性度量指标和调整奖励函数，可以进一步提高智能体之间的合作性和任务执行效率。论文通过实验验证了合作系数(\alpha)对智能体行为的影响。未来的研究可以进一步优化合作系数的选择，探索不同任务和环境下的最优合作系数，以提高系统的整体效率。未来的研究可以将CoRS方法与其他强化学习方法结合，如深度强化学习（DRL）和模仿学习（IL），以进一步提高多智能体路径规划的效率和智能体之间的合作性。
可以将CoRS方法应用于实际场景，如自动化仓库、智能交通系统和无人机编队等。通过在实际场景中验证CoRS方法的有效性，可以进一步推动多智能体系统和强化学习技术的发展。总的来说，论文通过一系列实验验证了合作奖励塑造方法在多智能体路径规划中的有效性和优势。希望这些研究成果能够为相关领域的研究人员提供有价值的参考，推动多智能体系统和强化学习技术的发展。（END）
参考资料：https://arxiv.org/pdf/2407.10403
波动世界（PoppleWorld)是噬元兽数字容器的一款AI应用，是由AI技术驱动的帮助用户进行情绪管理的工具和传递情绪价值的社交产品，基于意识科学和情绪价值的理论基础。波动世界将人的意识和情绪作为研究和应用的对象，探索人的意识机制和特征，培养人的意识技能和习惯，满足人的意识体验和意义，提高人的自我意识、自我管理、自我调节、自我表达和自我实现的能力，让人获得真正的自由快乐和内在的力量。波动世界将建立一个指导我们的情绪和反应的价值体系。这是一款针对普通人的基于人类认知和行为模式的情感管理Dapp应用程序。
粤ICP备17114055号
支持私有云部署
