基于强化学习的多Agent路径规划方法研究

王毅然 经小川 田 涛 孙运乾 从帅军

(中国航天系统科学与工程研究院 北京 100048)

0 引 言

随着科学技术的不断发展，路径规划技术的研究成果已经广泛应用人类生产和生活的各个方面。如在地震救灾中，无人机能够自主躲避障碍物，规划一组较优的路径到达指定灾区，完成灾情获取任务；在军事领域中，无人机和机器人在完成情报侦察以及作战打击任务过程中，要躲避敌方威胁和避免相撞，规划一条较优路径完成任务[1-4]。随着工作任务变得越来越复杂，往往需要多个智能体协同完成任务，每个智能体均是环境中的一部分，个体采取行动均会造成环境的改变，此时在动态环境中，单个智能体和其他智能体之间的协调与避障是多个智能体路径规划亟需解决的问题。路径规划的目标是寻找一条从给定的起始点到终止点的较优的运动路径。单智能体的路径规划在一个环境中的状态是有限的，目前解决的方法主要有Dijkstra算法[5]、粒子群算法[6]、A*算法[7]、遗传算法、模拟退火算法、蚁群算法[8]等。多智能体系统与单个智能体相比，往往能够完成复杂艰巨任务，且通常能够付出更小的代价收获更大的整体效益，因此多个智能体的路径规划研究具有十分重要的意义。

多智能体系统是由具有一定自主性、能够在共同目标窗口内协作、竞争和通信的协作智能Agent组成的[9]。单个Agent解决问题的能力是有限的，复杂任务需要多个Agent协同合作，共同完成整体或局部目标。如果在同一环境中存在多个Agent同时移动，对其进行路径规划将会变得十分困难。目前解决多智能体的路径规划问题取得了一些进展，文献[10]提出了免疫协同进化算法并仿真实现静态障碍物环境中多个机器人避障、避碰的最短路径；文献[11]提出了一种主从结构的并行多水下机器人协同路径规划算法，子层结构应用粒子群并行算法，生成各个机器人当前的最优路径，同时主层结构应用微分进化算法实时给出当前考虑机器人与障碍物、机器人与机器人之间避碰情况下，总系统运行时间最短的路径组合方案；文献[12]提出了一种基于分层强化学习及人工势场的多Agent路径规划算法，首先将多Agent的运行环境虚拟为一个人工势能场，根据先验知识确定每点的势能值，它代表最优策略可获得的最大回报，其次利用分层强化学习方法的无环境模型学习进行策略更新;文献[13]提出了首先利用A-Star算法启发式地得到多个智能体到达目标点的临时最短路径，同时计算访问节点的时间，通过动态地对时间窗进行精确计算和加锁来重置路线以避免冲突。

为解决未知环境下多个Agent路径规划问题，上述算法随着Agent的数量以及环境规模变大时，算法的效率会变得很低。本文提出了一种基于强化学习的多Agent路径规划方法(Multi-agent path planning based on reinforcement learning，MAPP-RL)，该方法中的多个Agent不断地与环境交互，当采取一个动作后，Agent会从环境中得到一个反馈，用来评估该动作的好坏，然后把评估结果作为历史经验，不断地进行优化决策，最后找到一个可以得到最大奖励的动作序列，完成复杂未知环境下的多Agent路径规划任务。

1 整体框架

多智能体的路径规划整体框架主要包括四个层次：环境建模层、算法层、任务分配层、多Agent系统层，如图1所示。

图1 整体框架图

在图1中，首先对环境进行建模，包括对环境中障碍、目标点等信息设置，其次通过任务分配层主要根据实际任务划分多个子任务，然后算法层接收环境信息以及多个Agent信息和任务分配情况，并进行计算，将结果返回给Agent。多Agent系统层与环境建模层、任务分配层、算法层进行交互，每个Agent均能执行动作与环境交互，同时也和任务分配模块的任务进行匹配，通过执行算法层，不断地更新策略，最后得到一组较优策略完成多个Agent的路径规划任务。

1.1 环境建模

对环境地图的建模常用的方法主要有三种：栅栏地图建模、拓扑地图建模和可视地图建模。本文采用的是栅栏建模法，如图2所示将环境分成n2个面积相同的方格，每个方格均携带不同0～3的参数信息，当格子参数为0时表示该区域无障碍物，当格子参数为1时表示该区域含有障碍物，当格子参数为2时表示智能体的位置信息，当格子参数为3时表示目标点的位置信息。通过构建栅栏地图，能够很好地获取环境的信息。

图2 栅栏环境图

1.2 任务分配

任务分配是多智能体协同合作中的一个重要研究内容。多Agent的路径规划的任务分配问题为：现假设系统环境中存在m个目标点，每个目标点至少一个Agent到达，所有目标点都有Agent到达时任务完成。该任务分配的目标是将多个目标点分别分配给Agent，以实现整体Agent到达目标点的路径总和最短。

1.3 多Agent路径规划算法

多Agent路径规划算法主要解决的问题是多个Agent的路径规划问题。本文采用的是基于强化学习的多Agent路径规划方法，多个Agent在同一环境中，不断与环境交互，根据环境的反馈进一步优化动作，完成整体的路径规划。对多个Agent进行路径规划主要有三个目标：一是对多个Agent进行路线规划时要考虑Agent间的路径冲突问题，避免多个Agent相撞；二是多个Agent进行路线选择时要避开障碍物；三是多个Agent到达目标点的路径总和尽可能的短。

2 基于强化学习的多Agent路径规划

2.1 强化学习相关理论

强化学习是一种无监督学习方法，Agent通过与动态环境的反复交互，学会选择最优或近最优的行为以实现其长期目标[14]。Sutton和Barto定义了强化学习方法的四个关键要素：策略、奖赏函数、价值函数、环境模型[15]。强化学习的基本模型主要包括环境和智能体两部分，如图3所示。

图3 强化学习基本模型

在图3中，Agent根据当前所处的环境状态，执行一个动作与环境交互，从环境中得到一个奖励，同时到达新的状态，进行学习更新策略，接着再执行一个动作作用于环境，不断重复此过程，优化策略完成任务。

很多强化学习问题可以形式化为马尔可夫决策过程(Markov decision process,MDP)。MDP是由〈S,A,P,R,γ〉构成的一个元组，其中：

S是一个有限状态集；

A是一个有限行为集；

P是集合中基于行为的状态转移概率矩阵：

R是基于状态和行为的奖励函数：

γ是一个衰减因子：γ∈[0,1]。

2.2 多Agent路径规划

在多Agent的强化学习过程中，每个Agent获得的奖励不仅仅取决于Agent自身的动作，同时还依赖于其他Agent的动作。因此本文将强化学习的MDP模型扩展为多马尔科夫决策过程(MDPs)。现假设有n个智能体，每个Agent可以选择的动作m个(即ai,i=1,2,…,m)，每个Agent的状态个数为k个(即sj,j=1,2,…,m)，则多个Agent采取的联合动作可以表示为Ai，多个Agent的联合状态可以表示为Si。基于强化学习的基本模型，结合本文的任务目标，本文定义了多Agent的路径规划学习框架，具体情况如图4所示。

图4 多Agent路径规划学习框架

在图4中，为了提高Agent的学习速度，本文中我们首先对多Agent所处的环境进行了预处理操作，剔除了一些无关的环境状态，同时将先验信息更新到知识库，提高了多Agent的学习效率。在该模型中，多个Agent基于当前所处的状态St，每个Agent根据知识库的历史经验，按照一定的策略规则采取动作集中的一个动作at，所有的Agent的动作组合成一次联合动作At作用于环境。当联合动作At执行完毕后，环境将转化为一个新的状态St+1，并且得到一个新的奖励值Rt+1。然后进行学习，更新历史经验，进一步完善知识库。接着根据Agen所处的新状态St+1和Rt+1选择新的联合动作At+1。多个Agent与环境进行周期性交互，不断重复“探索-学习-决策-利用”过程，从历史动作中进行学习更新自己的知识库，作为历史经验指导下次动作选择。

2.3 多Agent路径规划学习算法实现

2.3.1联合状态设定准则

2.3.2联合动作

2.3.3奖励函数

奖励函数定义了Agent的学习目标，并确定了Agent基于环境的感知状态即时行动的价值。由于Agent试图最大限度地获得总报酬，因此奖励函数本质上是用来指导Agent实现其目标的。奖励函数的设置会决定强化学习算法的收敛速度和程度。常用的奖励函数设置方法有：稀疏奖励、形式化奖励、奖励系数变化奖励等。本文采用的是稀疏奖励的形式定义奖励函数，设置情况如下式所示：

式中：a,b,c>0。

如式(1)所示，多Agent的路径规划目标是让多个Agent采取一组可以获得最大奖励的动作序列，到达指定的目标点。当Agent完成目标时，赋予一个正的奖励；当Agent碰到静态障碍物时，赋予一个负的奖励；当有两个或以上的Agent相互碰撞时，赋予一个负的奖励；其他情况的奖励值为0。

2.3.4价值更新函数

多Agent的路径规划采用的是Q-learning算法，在确定所有联合环境状态S和联合动作A后，要生成一个nm×km维的矩阵Q，矩阵中的元素Q(S,A)表示为多个Agent在环境状态St下选择动作At的价值。

更新的过程：当多个Agent在环境状态St下，按照既定的动作选择策略，选择一个联合动作At，执行完动作后Agent到达一个新的环境状态St+1，这时我们开始更新矩阵Q中的Q(S,A)值。Agent在状态St+1时选择Q矩阵对应Q值最大的Q(St+1,At+1)，然后把Q(St+1,At+1)乘上一个衰减值γ并加上到达St+1时所获取的奖励R作为现实中Q(S,A)的值,然后减去之前的Q(S,A)，接着乘以一个学习效率α累加上最初的Q(S,A)的值则更新为新的Q(S,A)。具体Q(S,A)值的更新公式如下式所示：

Q(St,At)←Q(St,At)+α[R+

γmaxAt+1Q(St+1,At+1)-Q(St,At)]

(2)

2.3.5动作选择策略

在强化学习问题中，探索和利用是一对矛盾：探索意味着Agent必须尝试不同的行为继而收集更多的信息，利用则是Agent做出当前信息下的最佳决定[15]。探索可能会牺牲一些短期利益，通过搜集更多信息而获得较为长期准确的利益估计；利用则侧重于根据已掌握的信息而做到短期利益最大化。探索不能无止境地进行，否则就牺牲了太多的短期利益进而导致整体利益受损；同时也不能太看重短期利益而忽视一些未探索的可能会带来巨大利益的行为。

目前，常用的探索方法有：ε-贪婪探索、不确定优先探索以及利用信息价值进行探索等。本文采用的是ε-贪婪探索，这里的ε是Agent随机选择的概率(0≤ε≤1)，在概率为1-ε的情况下，Agent使用贪婪的Q值方法选择Q值最大所对应的一个动作，当存在多个Q值相同的动作时随机选择一个；在概率为ε的情况下，Agent从动作集合中随机选择动作。

2.3.6多Agent路径规划算法步骤

在多Agent的路径规划中，多个Agent根据当前所处的环境状态，不断地与环境进行交互，在学习过程中对学习结果进行更新修正，用于指导Agent的动作选择，最终通过不断的学习，找到一组可以最大化奖励的动作序列，完成多Agent路径规划任务。该方法的伪代码如算法1所示。

算法1多Agent路径规划算法

Initialize：St,Q(s,a)

Repeat(for each episode): InitializeS

WhileStis notST

If (Probability<ε)

chooseAt=maxQ(St)

Else

Random chooseAt

Take actionAt，returnR和S’

UpdateQ(s,a)

S←S’

IfStisST

Break

该算法的具体学习过程的形式化描述如下：

(1) 初始化设置：地图生成，设置Agent和目标点的数量及初始位置，奖励函数设置，Q表初始化。

(2) 参数设置：终止学习周期Tmax，学习效率α、衰减度γ和探索度ε。

(3) 根据ε-贪婪策略选择动作At。

(4) 执行At，返回奖励值R和下一个状态St+1。

(5) 按式(2)更新Q值。

(6) 判断是否满足终止条件：若满足终止条件，执行(7)；否则，执行(3)。

(7)T：=T+1，判断T>Tmax：若成立，则学习结束；否则转(3)。

3 实验仿真与分析

3.1 实验设置

为了验证该方法的有效性，本文多个Agent的路径规划设置了一个虚拟的环境。与文献[16]一样，本文创造了不同大小的栅栏地图环境，其中障碍和目标点是随机生成的。如图5所示，我们设置了包含7个障碍、两个智能体、两个目标点的7×7大小的原始环境地图。

图5 实验环境

针对同一任务目标，将文献[16]的方法与本文方法进行实验对比。其中文献[16]智能体的动作集合为{U,D,L,R,S}，其中U代表向上，D代表向下，L代表向左，R代表向右，S代表静止不动。本文方法的两个Agent的联合动作集为：

其中文献[16]的奖励函数R′设置如式(3)所示，本文方法的奖励函数R具体设置如式(4)所示。

文献[16]和本文方法采用同一的学习更新函数的参数设置，如表1所示。

表1 更新函数的参数设置

本次实验假设两个智能体在环境中同时运动，不会出现故障情况，每次只能选择动作集合中的一个，环境是有边界的，当Agent选择超出边界的动作时，强制Agent留在环境内。任务目标是第2行第2列的Agent1到达第5行第6列的目标点，同时第2行第4列的Agent2到达第6行第4列的目标点，在Agent移动期间要避免相撞和避开障碍物。

3.2 实验结果与分析

为了验证本文方法的有效性，针对上述同一任务目标，进行两组实验，将本文方法与文献[16]方法进行对比，两组实验均训练4 000次。

本文运用文献[16]方法进行仿真实验，该方法分为两个阶段，首先分别对每个智能体进行路径规划，其次对发生碰撞的Agent进行动态调整。实验环境在图5基础上，分别进行单个智能体和目标点实验。首次实验时其中第2行第2列的Agent1运动轨迹如图6(a)所示。在图6(a)中，Agent1在第5个步长时与静态障碍物发生碰撞，Agent1的动作序列分别为：{D→R→R→D→D}，这是由于首次实验，Agent并没有历史经验作为决策依据，而是随机的选择动作，不断“试错”。经过Agent不断与环境交互，更新Q表，进行动作选择，Agent的最终路径规划路线结果如图6(b)所示，Agent1到达目标点的总步长为7。

(a) 首次实验轨迹 (b) 最终运动轨迹图6 Agent1实验结果图

类似地，第2行第4列的Agent2运动轨迹如图7(a)所示，Agent2在第4个步长时与静态障碍物发生碰撞，Agent2的动作序列为{L→U→R→R}，经过4 000次学习，得到的最终路径规划结果如图7(b)所示，Agent2到达目标点的总步长为6。

(a) 首次实验轨迹(b) 最终运动轨迹图7 Agent2首次实验运动轨迹

从图6(b)和图7(b)可以看出，当两个Agent在同一环境同时移动时，会在第2行第3列的位置相撞，运用动态规划思想对Agent的路径重新调整，最终的路径规划如图8所示。在图8中两个Agent在同一环境中同时移动，且能够躲避障碍物，两个Agent不会发生相撞，到达目标点路径最短。

图8 最终路径规划结果

运用本文的方法，在图5所示的环境中进行实验。首次实验时，两个Agent经过18个步长发生了相撞。这是由于本文的方法加入了先验信息，有历史经验作为决策支持，首次实验时避免了对障碍的学习，使Agent进行试错时避开了障碍。经过499次回合训练后，两个Agent第一次到达目标点，完成任务的总步长为50。训练4 000次后最终的路径规划结果如图9所示，总步长为14，其中联合动作序列为：

{DL→RS→DD→RD→RD→RD→DR}

图9 回合训练结果

为了验证本文的有效性，本文从总探索步数、完成任务的平均步数做了对比，具体情况如图10、图11所示。在图10中，文献[16]的总探索步数是65 810步，本文方法的总探索步数是54 375步，由于本文方法两个Agent采取动作时要考虑双方的位置信息，引入联合动作，避免了对单个Agent相撞后的路径重新规划，减少了17.4%的总探索步数。从图11得出，本文完成任务的平均步数与文献[16]相比减少了5步。

图10 总探索步数

4 结 语

为解决复杂任务下多个Agent路径规划问题，本文提出一种基于强化学习的多Agent路径规划方法。首先建立了多Agent路径强化学习模型，并详细描述了各个基本要素，以及多个Agent如何从历史数据中积累经验优化决策。通过仿真实验表明，该方法是可行、有效的。为了提高该方法的学习效率，本文提出了2种解决方案：(1) 环境预处理，根据实际任务以及多Agent的信息，剔除一些无关的环境状态；(2) 加入先验信息的Agent决策Q表，基于先验信息更新Q表，作为历史经验提供给Agent，大大提高了Agent的学习效率，与文献[16]方法相比，减少了17.4%的总探索步数。下一步将研究多Agent动态目标的路径规划问题，实现多Agent在复杂任务下的自主路径决策。