基于强化学习的多智能体路径规划研究与应用

Research and Application of Multi-Agent Path Planning Based on Reinforcement Learning

摘要: 研究聚焦于智能仓储中AGV的路径规划问题，构建了基于强化学习的多智能体寻路算法。每个AGV能从环境和以往经验中学习，利用不同行为产生的奖励机制，训练智能体自主选择更高效策略，以达到预定目标。本研究在ACTOR-CRITIC算法基础上加入经验回放机制并采用了中心化训练和去中心化决策的方法，以提高智能体的路径规划效率。同时，将ACTOR-CRITIC算法在智能仓的环境下进行模拟训练，验证AGV的路径规划效果。

Abstract: The research focuses on the path planning problem of AGV in intelligent warehousing, constructs a multi-agent path finding algorithm based on reinforcement learning. Each AGV can learn from the environment and previous experience, use the reward mechanism generated by different behaviors to train the agent to independently choose more efficient strategies to achieve the predetermined goal. In this research, an experience playback mechanism is added to the ACTOR-CRITIC algorithm, centralized training and decentralized decision-making methods are adopted to improve the path planning efficiency of the agent. At the same time, the ACTOR-CRITIC algorithm is simulated and trained in the environment of the smart warehouse to verify the path planning effect of the AGV.

1. 引言

近年来，多智能体系统由于能够提供灵活高效的解决方案而更多地应用于智能仓储管理。它们由多个可以相互通信和合作的自主智能体组成，能够共享资源和知识来解决复杂的任务 [1] [2] 。然而，这对智能体的有效控制和协调提出了重大挑战。智能体之间的有效沟通对于确保他们能够协作并到达预期目标至关重要，当处理在复杂环境中运行的多个智能体时尤其如此。前人提出了智能仓库中单智能体路径规划的几种方法，如A*搜索算法和Dijkstra算法 [3] 已被广泛使用并被证明是有效的。

终身多智能体路径规划是一个过程，使一组智能体能够在环境中移动时动态生成和更新路径。通过结合人工势场和分层规划等技术，智能体可以协作实时生成和更新路径，从而更有效地对环境变化做出反应。这种方法已被证明在各种应用中都是有效的，包括机器人、自动驾驶车辆和自主探索 [4] [5] 。然而它具有众多限制，首先，对多个智能体寻找最佳路径所涉及的计算复杂性非常高，随着智能体数量的增加，问题的解决难度呈指数级增长。其次，智能体之间缺乏沟通和协调，智能体对环境状态缺乏整体感知，这可能会严重影响规划路径的性能和可行性。以上问题导致传统的多智能体寻路算法难以高效的应对大型仓库环境或环境频繁变化的动态场景。目前，行业迫切需要在复杂场景和易变环境下使用先进的大面积导航方法。

强化学习是控制智能仓库中多个智能体的强大工具 [6] [7] 。智能体能够从环境和经验中学习，以最大限度地增强智能体的路径规划效果。通过利用智能体不同行为产生的奖励和惩罚，可以训练智能体优化其行为，以达到预期目标 [8] 。强化学习使用试错方法，允许智能体探索不同的策略，直到找到最成功的策略。这种类型的学习为智能体提供了从错误中总结经验并根据环境反馈调整其行为的机会 [9] 。此外，强化学习可用于教导智能体以无监督的方式工作，使它们无需人工干预即可学习。

本研究采用基于ACTOR-CRITIC的强化学习技术来训练智能体就其路径规划做出智能决策，加入了经验回放机制 [10] [11] 并采用了中心化训练和去中心化决策 [12] 的方法，以提高AGV的路径规划效率。同时，将ACTOR-CRITIC算法在仓储环境下进行模拟训练，验证本次研究中AGV之间的协作效果。

2. 多智能体强化学习算法

2.1. 系统模型

在路径规划领域，多智能体强化学习算法(MARL)的使用在提高运行效率和优化资源分配方面具有巨大潜力，这些算法的一个关键组成部分是马尔可夫决策过程(MDP) [13] 。MDP作为动态环境中决策问题建模的数学框架，能够捕获此类环境的不确定性和动态性质，适合智能仓储场景。

MDP的核心由一组状态空间、动作空间、状态转移函数、奖励函数、动作价值函数等组成，记为元组(S, A, P, R, Q)。本研究主要探索智能仓储中AGV的路径规划问题，设仓储环境中有n个智能体(AGV)。在每一时刻T，环境输出一个全局状态 $s_t\in S$ ，和n个观测状态 $\left[o_t^1,o_t^2,\cdots ,o_t^n\right]\in O$ 。其中，S代表全局状态空间，O代表全局观测空间。每个智能体根据自己的观测 $o_t^i$ 选择一个动作 $a_t^i\in A$ ，其中A表示每个智能体 $i\in \left\{1,\cdots ,n\right\}$ 的动作空间。系统根据状态转移函数 $P\left(s_{t+1}|s_t,a_t\right)$ 对所有智能体执行联合动作 $a_t\in A$ 。智能体得到各自的奖励 $r_t^i$ ，全局奖励 $R=\left[r_t^1,r_t^2,\cdots ,r_t^n\right]$ 。在这个过程中，每个智能体都试图增加自己的个人奖励以使全局奖励增大。动作价值函数 $Q\left(s,a\right)$ 会根据T时刻的奖励r、状态s和动作a输出一个评价智能体的动作a的值。

2.2. Actor-Critic

MARL提供了一种有效的方法来解决多智能体环境中遇到的复杂控制问题。Actor-Critic [14] 方法是一种常见的MARL算法，它汇集了基于策略和基于值的方法的优点。

Actor-Critic算法由两个主要部分组成：Actor和Critic。Actor负责根据当前情况选择动作，而Critic则检查所选择的动作并向Actor提供反馈。这种反馈使智能体能够随着时间的推移通过更新其策略来增强其决策过程。通过利用这种双组件架构，Actor-Critic算法可以有效地平衡决策和反馈，并在多智能体环境中学习最优策略。

在智能仓储的背景下，应用多智能体Actor-Critic算法来协调不同智能体(例如机器人或自动车辆)的动作，以实现高效可靠的仓库运营。Actor-Critic算法允许每个智能体学习自己的策略，同时考虑其他智能体的行为对整体系统性能的影响。这种协作学习过程使智能体能够实时适应和优化其行为，从而改善任务分配、资源利用率和整体仓库效率。总体而言，基于Actor-Critic的多智能体强化学习算法在彻底改变智能仓库控制机制方面具有巨大潜力。

策略网络 $\pi \left(a|s;\theta \right)$ 相当于一个参与者，它根据状态s做出动作a。价值网络 $q\left(s,a;\omega \right)$ 相当于法官，对行动者的表现进行打分，评价状态s下动作a的质量。Actor和Critic之间的关系如图1所示。

Figure 1. Actor-Critic algorithm framework

图1. Actor-Critic算法组织框架

Actor使用一个神经网络近似策略函数。这种神经网络称为策略网络，记为 $\pi \left(a|s;\theta \right)$ ，其中θ表示策略网络参数。策略网络的输入是当前环境的状态s。状态s经过卷积层、全连接层和softmax后，输出智能体将要执行的动作以及该动作的概率。这时，策略网络会随机采样一个动作并执行。图2描述了策略网络的结构。

Figure 2. Policy network

图2. 策略网络

Critic用一个神经网络来近似动作价值函数 $Q_{\pi }\left(s,a\right)$ 。这种神经网络被称为价值网络，记为 $q\left(s,a;\omega \right)$ ，其中ω表示价值网络参数。价值网络接收状态s作为输入并输出与每个动作相关的值。图3描绘了价值网络的组织结构。

Figure 3. Value network

图3. 价值网络

2.3. 训练

Actor-Critic算法中的两个神经网络不同时工作。如图4所示，每个Agent上分别定义了一个策略网络。中央控制器中有多个价值网络，每个价值网络对应一个策略网络。当训练算法时，中央控制器可以查看所有智能体的观察、动作和奖励，并把每一轮的 $o^i,r^i,a^i$ 依次存入经验回放数组。它被称为集中训练。

训练结束后，中央控制器上的价值网络被屏蔽，每个智能体根据策略网络进行决策，称为去中心化执行。如图5所示。在执行阶段，第一步，每个智能体从各自环境观察环境状态s。每个智能体都有一个独特的策略网络，可以生成概率分布。第二步，每个智能体根据自己的概率分布进行采样，得到动作a并执行。此时环境已经发生变化，重复步骤一和二，直到智能体到达目标位置。

Figure 4. Centralized training

图4. 中心化训练

Figure 5. Decentralized execution

图5. 去中心化执行

下面概述了Actor-Critic算法的训练过程。中央控制器从经验回放数组中随机抽取一个四元组 $\left(s_t,r_t,a_t,s_{t+1}\right)$ ，令当前策略网络变量为 ${\theta }_{now}$ ，价值网络变量为 ${\omega }_{now}$ 。执行以下步骤并更新参数 ${\theta }_{now}$ 和 ${\omega }_{now}$ 。

1) 观察当前状态 $s_t$ ，根据策略网络做决策： $a_t\text{~}\pi \left(\cdot |s_t;{\theta }_{now}\right)$ ，并让智能体执行动作 $a_t$ 。

2) 从环境中观察到奖励 $r_t$ 和新状态 $s_{t+1}$ 。

3) 根据策略网络做决策： ${\tilde{a}}_{t+1}\text{~}\pi \left(\cdot |s_{t+1};{\theta }_{now}\right)$ ，但不允许智能体执行动作 ${\tilde{a}}_{t+1}$ 。

4) 让价值网络打分：

${\hat{q}}_t\text{~}q\left(s_t,a_t;{\omega }_{now}\right)和{\hat{q}}_{t+1}\text{~}q\left(s_{t+！},{\tilde{a}}_{t+1};{\omega }_{now}\right)$

5) 计算TD目标和TD误差：

${\hat{y}}_t=r_t+\gamma \cdot {\hat{q}}_{t+1}和{\delta }_t={\hat{q}}_t-{\hat{y}}_t$

6) 更新价值网络：

${\omega }_{new}\leftarrow {\omega }_{now}-\alpha \cdot {\delta }_t\cdot {\nabla }_{w}q\left(s_t,a_t;{\omega }_{now}\right)$

7) 更新策略网络：

${\theta }_{new}\leftarrow {\theta }_{now}-\beta \cdot {\hat{q}}_t\cdot {\nabla }_{\theta }\ln \pi \left(a_t|s_t;{\theta }_{now}\right)$

3. 仿真

3.1. 仓储模型

为了便于理解智能仓库的操作流程，本研究总结了一个典型仓库的环境配置。该仓储系统的整个过程分为5个阶段。在第一阶段，当系统启动时，所有AGV都被分配货物的位置和拣选站的位置。第二阶段，AGV从充电区(起点)移动到目标货架底部并将其举起。第三阶段，AGV搬运货架至拣选工位入口。第四阶段，每位员工从货架上挑选产品。第五步，当拣选工作完成后，AGV将货架带到可用的货架位置并将其放下。AGV重复阶段二至五，直到系统停止。本次研究只涵盖第二阶段中的AGV路径规划。智能仓储系统的框图如图6所示。

Figure 6. Intelligent warehousing environment

图6. 智能仓储环境

本研究基于上述假设环境。使用以下四种情形进行模拟。他们是5个智能体和一张2 × 2的地图；10个智能体和一张2 × 2地图；5个智能体和一张5 × 5地图；10个智能体和一张5 × 5地图。其中，每个智能体占用面积为0.15 × 0.15，每个货架占用面积为0.08 × 0.08。将仓储作XY平面图，使整个仓储区域位于第一象限，智能体的起始区域(AGV充电区)为从x = 0到x = 0.3的所有区域内。

在训练策略网络和价值网络时，环境根据智能体在每个时间步长选择的动作返回全局奖励和单个奖励。单个奖励设定如下：

$r_t^i=\{\begin{array}{l}-d_t^i,d_t^i\ne 0\\ -d_t^i+2,d_t^i=0\end{array}$ (1)

其中 $d_t^i$ 是智能体i在第t个时间步长到目标位置的距离。为了让每个智能体在每个时间步中获得良好的奖励，智能体必须选择向目标位置移动的动作。另外，为了鼓励智能体尽可能向目标前进，设置了额外的激励奖励，即如果智能体到达目标架，则奖励额外增加2。全局奖励确定如下：

$r_t=\underset{i=0}{\overset{n}{{\displaystyle \sum }}}{r}_t^i$ (2)

其中n是环境中智能体的数量。全局奖励是对所有智能体动作的全面评估，它可表述为：每个智能体与目标书架之间的距离之和的负数。训练神经网时，中央控制器会根据全局奖励选择每个智能体的动作。在某些情况下，少数智能体的奖励减少会导致全局奖励增加。这种奖励设计在提高智能体的泛化性能方面是有利的。

仿真设定训练次数为5000，神经网络隐藏层维度为64，策略网络与价值网络的学习率均为1e-2。算法折扣因子设为0.95。

3.2. 仿真结果

本研究使用两个指标来衡量算法的有效性：(1) 累积奖励，即系统中所有智能体的累积奖励回报。(2) 到达目标点时，整个运动期间与目标点之间的平均距离。本研究还使用不同区域和不同智能体数量的四张地图进行仿真演示，以证明所用方法的可行性和泛化性。

3.2.1. 累积奖励

累积奖励与训练次数曲线如图7~10所示，随着训练次数的增加，算法的累积奖励逐渐收敛。依据本研究设置的奖励函数为每个智能体与目标书架之间的距离之和的负数。因此，当奖励收敛到设定的奖励值时，就可以确认智能体成功找到了目标。

当智能体数量相同时，累积奖励在较大地图环境中比在较小地图环境中收敛得更慢。这是因为地图尺寸变大，智能体需要走得更远才能找到各自的目标，因此需要更多的训练才能使曲线收敛。

当地图大小相同时，同时训练的智能体越多，累积奖励收敛的速度就越慢。这是因为同时参与的智能体越多，智能体之间就越容易出现阻塞，从而越难达到目标。

当有更多的智能体同时运行时，最终的累积奖励更大，因为更多的智能体获得额外的奖励值。

3.2.2. 平均距离

智能体到目标的平均距离与训练次数的关系如图11~14所示，随着训练次数的增加，相同时间步内智能体与目标之间的平均距离逐渐趋于0。可以证实，随着训练次数的增加，系统的性能随之提升，智能体的策略也越来越好，最终能够在规定的时间内成功找到目标。当智能体数量增加或地图尺寸增大时，需要更多的训练时间才能使智能体完美找到目标。随着地图尺寸的增大，曲线的收敛值会更大，这是因为在大地图下，智能体往往需要移动的更远才能到达目标。

Figure 7. Small layout with 5 agents

图7. 5个智能体与小空间

Figure 8. Small layout with 10 agents

图8. 10个智能体与小空间

Figure 9. Large layout with 5 agents

图9. 5个智能体与大空间

Figure 10. Large layout with 10 agents

图10. 10个智能体与大空间

Figure 11. Small layout with 5 AGVs

图11. 5个Agent与小空间

Figure 12. Small layout with 10 AGVs

图12. 10个Agent与小空间

Figure 13. Small layout with 5 AGVs

图13. 5个Agent与小空间

Figure 14. Large layout with 10 AGVs

图14. 10个Agent与大空间

4. 结论

本研究探讨了多智能体强化学习算法在智能仓储中的应用。得到如下结论：

(1) 通过利用强化学习技术，智能体可以从与环境的交互中学习并不断提高决策能力。在仓储环境中，区别于传统的固定路线的路径规划，智能体根据仓储环境状态而自主产生合适的路径，使仓库运营的效率、灵活性和适应性都显著提高。

(2) 模拟了基于Actor-Critic方法的多智能体强化学习算法，并利用该算法解决仓储环境下AGV的路径控制问题。仿真实验证实，在5000轮迭代下，10个以内的AGV已经具备能在一定范围内共同寻找目标的能力。AGV根据策略网络输出的动作策略自主规划每一时间步的动作并记录奖励与平均距离。所有AGV在3000轮迭代后的动作策略趋于稳定。最终，仿真的奖励函数曲线收敛稳定，AGV与目标的平均距离持续缩短并收敛。可以充分证实AGV能在实际仓储环境下根据自己的策略自主规划路径并找到目标。

(3) 根据真实的智能仓储场景，完成仓库环境的初步设计，为今后的算法实验提供了理想的环境。

总体而言，这项研究有助于探索MARL算法在提高智能仓库系统效率方面的能力。

基金项目

科学技术发展基金(0047/2021/A1)。