基于蚁群算法及博弈论的多Agent路径规划算法

郑延斌 王林林 席鹏雪 樊文鑫 韩梦云

摘 要：针对多Agent路径规划问题，提出了一个两阶段的路径规划算法。首先，利用改进的蚁群算法来为每个Agent规划出一条从起始点到目标点，不与环境中静态障碍物碰撞的最优路径。在蚁群算法的改进中引入反向学习方法来对蚂蚁位置进行初始化分布，提高了算法的全局搜索能力;利用粒子群算法中的自适应惯性权重因子来调节信息素强度Q值，使其自适应地变化，避免陷入局部最优;对信息素挥发因子ρ进行调节，提高算法的迭代速度。其次，若多Agent之间存在动态碰撞，利用博弈论构建多Agent之间的动态避障模型，并利用虚拟行动法来解决博弈的求解问题及多Nash均衡的选择问题，确保每个Agent能够快速学习到最优Nash均衡。仿真实验结果表明改进蚁群算法与传统蚁群算法相比在搜索精度与搜索速度上有明显的提高，与Mylvaganam的多Agent动态避障算法相比，所提算法减小了路径总长度并提高了收敛速度。

关键词：多Agent;路径规划;反向學习;蚁群算法;博弈论

中图分类号： TP24

文献标志码：A

文章编号：1001-9081（2019）03-0681-07

Abstract： A two-stage path planning algorithm was proposed for multi-Agent path planning. Firstly， an improved ant colony algorithm was used to plan an optimal path for each Agent from the starting point to the target point without colliding with the static obstacles in the environment. The reverse learning method was introduced to an improved ant colony algorithm to initialize the ant positions and increase the global search ability of the algorithm. The adaptive inertia weighted factor in the particle swarm optimization algorithm was used to adjust the pheromone intensity Q value to make it adaptively change to avoid falling into local optimum. The pheromone volatilization factor ρ was adjusted to speed up the iteration of the algorithm. Then， if there were dynamic collisions between multiple Agents， the game theory was used to construct a dynamic obstacle avoidance model between them， and the virtual action method was used to solve the game and select multiple Nash equilibria， making each Agent quickly learn the optimal Nash equilibrium. The simulation results show that the improved ant colony algorithm has a significant improvement in search accuracy and search speed compared with the traditional ant colony algorithm. And compared with Mylvaganam's multi-Agent dynamic obstacle avoidance algorithm， the proposed algorithm reduces the total path length and improves the convergence speed.

Key words： multi-Agent; path planning; reverse learning; ant colony algorithm; game theory

0 引言

多Agent路径规划问题是指在多Agent环境中为每个Agent找出一条从起点到终点的最优无碰路径[1]。路径规划问题是MAS （Multi-Agent System， MAS）研究的核心问题之一，受到国内外许多研究者的关注。蚁群算法[2]是一种基于仿生学的全局优化启发式正反馈算法，已成功应用于众多优化问题中，在路径规划问题中效果尤为显著[3-5]。然而蚁群算法应用规划问题中仍然存在收敛速度慢、易陷入局部最优的缺陷，为此国内外研究者提出了一些改进，如：裴振兵等[6]通过自适应地调整信息素启发因子及期望启发因子来提高蚁群算法的迭代速度，提出广义信息素更新规则使算法避免陷入局部最优;柳长安等[7]提出利用狼群分配原则的方法来对蚁群算法中最差路径上释放的信息素进行删除，从而提高了找到最短路径的速度;Yuan等[8]通过对启发式函数和路径选择策略进行改进来提高算法的迭代速度;Zouari等[9]将2-opt算法引入到蚁群算法中来减少找到最短路径的时间;屈鸿等[10]根据限定信息素强度的上下界，并使陷入死锁的蚂蚁采取回退策略来解决死锁问题，从而完成机器人路径规划。

多Agent环境中，受资源约束的影响，Agent在运动过程中相互之间可能发生碰撞。上述方法只考虑静态障碍的避碰问题，不能解决Agent之间的动态碰撞问题。由于在动态避障过程中，每个Agent的行为决策要受到环境中其他Agent行为决策的影响，研究者提出了基于博弈论的多Agent控制方法[11-12]，这些方法以避障为目的，规划出的路径可以确保不与静态障碍物或其他Agent发生碰撞，然而难以确保每个Agent的路径最优，另外当多个Nash平衡存在的情况下，会出现震荡现象。

本文提出一种多Agent路径规划方法，该方法分为两个阶段：第一阶段为静态避障，利用改进蚁群算法为每个Agent规划出一条无碰最优路径;第二个阶段为动态避障，是在前面得到最优路径的基础上所作的微调，用于解决Agent之间的碰撞问题。利用博弈论来构建多Agent动态避障模型，在求解该模型的过程中，利用虚拟行动法确保每个Agent都能快速學习到最优Nash均衡解，从而解决多Agent之间的动态避碰问题。

1 相关知识

1.1 蚁群算法

1.1.1 栅格间转移概率

在蚁群算法中，蚂蚁s会根据路径上的残留信息素浓度的大小来选择下一步要走的栅格，在时刻t蚂蚁s从点m转移到n的转移概率公式如下所示：

1.1.2 信息素更新规则

当迭代完成之后路径上的信息素需要更新，更新值由历史留下的信息素值与将要留下的信息素值所决定，更新公式为：

1.2 反向学习策略

Tizhoosh[13]在2005年基于相反数或对立点的概念提出了反向学习策略。在随后的发展中，该方法被应用于解决一些优化问题中。反向坐标定义如下。

定义1 假设x在一维空间中的坐标是-5，目标点的坐标为10，那么x反向点的坐标点为5，且点x到目标点的距离为15，点到目标点的距离为5。比较可得，反向点靠近目标点。x的反向坐标的计算公式为：

应用到优化的过程中，则反向机制的优化过程如定义3。

1.3 自适应惯性权重值

粒子在寻优过程中，惯性权重w应该是保持动态变化的。ω取值较大时，粒子的全局搜索能力较强;反之局部搜索的能力较强。由于粒子在寻优过程中，会逐渐靠近最优点，粒子的惯性权重应该随着迭代次数自适应的变化，因此粒子的自适应惯性权重更新公式[14]为：

1.4 博弈论基础

博弈论是研究相互影响、相互依存局中人理性行为的数学工具，是研究理性局中人如何交互的方法[15]。由于局中人的相互依存性，博弈中的决策必须建立在对其他局中人决策的预测之上。

Nash均衡是对博弈结局的一致性预测，如果所有局中人都预测某特定的Nash均衡会出现，则该Nash平衡就会出现，不会因为某个局中人认为不符合自己的利益而失败。达到Nash均衡后，任何局中人都不存在单方面提高自身的效用而降低其他局中人效用的动机，故Nash均衡是博弈的稳定解。

2 基于蚁群算法的多Agent规划方法

当每个Agent的起点和目标点确定后，就可以为每个Agent规划出一条不与环境中静态障碍物碰撞的路径。研究发现在路径寻优和自组织性方面蚁群算法存在很大的优势，然而传统蚁群算法存在易陷入局部最优及迭代速度慢的缺陷[10]，为此本文对传统蚁群算法作如下改进。

2.1 种群初始化

蚂蚁在解问题空间中找到最短路径的时间与蚂蚁初始化时在解空间中的分布存在正比关系，距离最佳位置近的蚂蚁找到最短路径的时间比距离最佳位置远的蚂蚁要短。

因此为了快速找到最短路径，在蚁群算法中引入反向学习策略对蚂蚁进行位置初始化，通过与当前种群与反向种群的位置进行对比找出较优的种群。

基于反向学习算法的种群位置初始化过程表述如下：

2.2 自适应信息素强度值

信息素强度Q为蚂蚁循环一周时在路径上所释放的信息总量，Q值越大，表示蚁群算法的收敛速度越快;但是一旦Q值过大时，蚂蚁会过多地集中于一条路径上从而导致算法的全局搜索能力变差，极易陷入局部最优。因此为了调整好二者之间的关系，本文引入粒子群算法中自适应惯性权重值来调节Q值的大小使其能够在搜索的过程中自适应的变化，从而兼顾好全局与局部搜索的关系。具体公式如下：

引入粒子群算法中的自适应惯性权重值的方法来调节信息素强度值可以使信息素强度值自适应地变化，避免蚂蚁陷入局部最优。

2.3 信息素挥发因子

信息素挥发因子ρ的大小也是影响路径信息素量大小的因素，从而影响蚁群算法的全局搜索能力和收敛速度。在传统的蚁群算法中挥发因子ρ是（0，1）上的一个常数，如果给定的ρ值过大，表明路径上的信息素量减少，从而导致算法收敛速度降低;若给定的ρ过小，路径上的信息素量会增大，导致算法快速收敛，虽然节约了算法的搜索时间，但可能导致算法陷入局部最优解。因此本文利用式（11）对挥发因子ρ作如下改进，使挥发因子ρ随着迭代次数的改变而自适应地变化，具体公式如下：

2.4 信息素更新规则

当迭代完成之后路径上的信息素需要更新，更新值由历史留下的信息素值与将要留下的信息素值所决定，更新公式为：

2.5 基于改进蚁群算法的多Agent路径规划算法

通过以上分析，引入反向学习策略可以增强算法的全局搜索能力，利用粒子群算法惯性权重值调节信息素强度Q值可避免蚂蚁陷入局部最优，对挥发因子进行调节提高了算法的迭代速度。改进后的蚁群算法流程如下：

步骤1 初始化蚁群算法中的参数，蚂蚁数量M、最大循环次数Kmax、启发因子、期望值β。

步骤2 利用反向学习方法即式（8）、（9）对蚂蚁的位置初始化。

步驟3 启动蚁群，蚂蚁根据状态转移规则选择下一个要途经的栅格，若该栅格移动至相邻栅格路径上的信息素值为0，则返回到上一个搜索的栅格，并将其设置为障碍栅格。

步骤4 重复步骤2，直到所有的蚂蚁都完成路径的搜索。

步骤5 计算并记录下各蚂蚁的路径长度Ls。

步骤6 依据式（12）、（13）、（14）进行信息素的全局更新。

步骤7 若蚁群全部收敛到一条路径或达到最大循环次数Kmax，则循环结束;否则转步骤2。

步骤8 输出全局最优路径，算法结束。

3 基于博弈论的多Agent动态避碰方法

利用改进的蚁群算法可以为每个Agent规划出一条与环境中静态障碍物之间无碰撞的最优路径。然而多Agent环境中，受资源的约束，Agent在运动过程中会相互发生碰撞，即动态碰撞的问题。由于每个Agent都是按照规划的路径前进，为了避免碰撞，每个Agent需要从行为集合{不变，改变运动方向，改变运动速度，等待}中选择一种行为来执行。碰撞发生在多个Agent之间，因此Agent的行为决策要受到环境中其他Agent的行为决策的影响，博弈论为这种相互影响的决策问题提供了很好的数学模型。本文利用博弈论来构建多Agent动态避障模型，把多Agent之间的避碰问题转换为求解该博弈模型的Nash均衡解问题，并利用虚拟行动法来确保每个Agent能够快速学习到最优Nash均衡解。

3.1 多Agent之间的碰撞检测

由于只有邻居中的Agent才有可能发生碰撞，因此为了便于计算，假设每个Agent都能获取其邻居集合中的Agent的速度信息v（包含大小和方向）等，Agent的半径为r。

3.2 多Agent动态避障博弈模型

定义9 由于只有邻居中的Agent才可能发生碰撞，因此局中人集合N定义为：

NC（No Change）表示Agent不作变化继续按照原始路径行走;ST（Stop）表示Agent停止等待;CV（Change Velocity）表示Agent速度产生加速减速变化;CD（Change Direction）表示Agent转变方向行走。

定义12 多Agent避碰博弈为G=（N，A，U），其中N表示局中人的集合，A是博弈过程Agent的行为集合，U是效用函数。

在避障过程中，如果Agent的行为选择为改变方向或改变速度，则当避障结束后，需要把方向和速度还原，不仅有一定的消耗，而且还需要一定的距离才能完成，因此设FL为Agent完成变化和还原需要的最短距离，当Agent和其目标点的距离小于FL时，就不能选择CV和CD行为。为此为Agent定义了优先级，表示Agent行为选择的优先级。

3.3 基于博弈论的多Agent动态避碰算法

由于多Agent之间的动态避障问题可以描述为一个博弈模型G，由Nash定理知，博弈G至少存一个Nash均衡解（定义5）。然而Nash定理只指出均衡的存在性，如何求得均衡解是一个比较复杂的问题。另外当博弈G中存在多个均衡时，如何确保博弈中每个Agent选择相同的均衡就尤为重要（即均衡的选择问题）。博弈学习中的虚拟行动方法[16]为博弈求解及均衡选择问题提供很好的解决方案，算法1给出了详细的描述。其中qaji（t））表示t时刻局中人i选择行为集合中某个行为aj的概率。

在重复博弈的过程中，每个局中人都知道其他参与人是在根据一个固定的混合策略分布q-i（t）来选取他们的行为组合，虽然该混合策略分布是不知道的，他可以从行为历史中学习到其他参与人的混合策略分布q-i（t）如式（20）、（21）。参与人i在学习时刻t实际行为选择是他在时刻t关于其他参与人行为策略的后验信念的最优反应如式（23）。故如果博弈G存在多个Nash均衡的话，算法1确保收敛到最优Nash均衡（详见文献[16-17]）。由于Nash均衡是多Agent的稳定解，一旦达到均衡，每个Agent都没有偏离该均衡解而去追求更高效用的意图，另外由式（19）知道，达到均衡后，Agent相互之间的距离都不会小于安全距离LL，故解决了多Agent之间的动态避障问题。

4 实验仿真与分析

分两阶段来验证本文所提出的算法的有效性。首先是对第一阶段，每个Agent的无静态碰撞的最优路径的验证（4.1节）;对多Agent之间的动态避障问题，第3章给出了理论说明，利用算法1和算法2能够得到最优的Nash均衡，解决Agent之间的动态碰撞问题。本章利用5个Agent之间的动态避障问题来验证算法的有效性（4.2节）。

4.1 Agent路径规划实验分析

为了验证本文算法的适用性分别在不同的环境下对本文算法进行实验验证，首先利用本文算法与文献[2]及文献[10]算法在20×20的栅格环境中对单个Agent的路径进行实验对比，使用文献[10]中同样的参数：迭代次数Kmax=200，期望值β=5.0，蚂蚁数量M=50，启发因子α=1.5，惯性权重的最大最小取值为：ωmax=0.9，ωmin=0.4，但是本文算法中信息素强度值Q及信息素蒸发因子ρ是自适应变化的，经过实验验证可以得到如图1所示多Agent的路径规划图以及图2所示的三种算法的迭代次数图，经过100次实验取得平均值得到表1所示对比结果。

通过表1中的数据可以看出，本文算法加入自适应惯性权重值调节信息素强度Q值及自适应的调节信息素蒸发因子ρ可以避免蚂蚁陷入局部最优值，从而提高算法的迭代速度。从三种算法的对比结果中可以看出，本文算法在时耗、最短路径长度及迭代次数方面都优于文献[2]与文献[10]中算法。

为了验证本文算法的适用性，随机生成20×20栅格环境利用本文算法及文献[2]与文献[6]中算法对单个Agent在路径规划上进行对比验证，得到的结果如图3所示路径规划图及图4所示的迭代次数对比图，实验中所用参数为：迭代次数Kmax=200，期望值β=7.0，蚂蚁数量M=30，启发因子α=1，惯性权重的最大最小取值为：ωmax=0.9，ωmin=0.4。经过100次实验取得平均值得到的结果如表2所示。

通過以上的对比结果可以看出，在最短路径的寻找过程中，本文算法在信息素挥发值上的改进能够明显提高算法的迭代速度，在最短路径长度上优于文献[2]以及文献[6]中算法。

4.2 多Agent动态避障分析

对5个Agent进行仿真，利用本文避障方法来解决多个Agent之间的碰撞问题，本文中所说的Agent的半径r根据经验值r=2，其中Agent1（A1）的起点与终点栅格为（1，179），Agent2（A2）的起点与终点栅格为（181，48），Agent3（A3）的起点与终点栅格为（101，180），Agent4（A4）的起点与终点栅格为（47，289），Agent5（A5）的起点与终点栅格为（364，55）。经过实验可以得到如图5所示为5个Agent的路径规划图，图6所示的加入博弈论的迭代次数图。

从图5中Agent之间的运行路线虽然存在交点，但是经过调用博弈论的多Agent动态避碰算法可以解决Agent之间的碰撞问题。如在图5中的B点Agent2与Agent3会利用碰撞检测方法检测到两者即将在B点处发生碰撞，则根据算法1及避障算法2两者产生一个博弈的过程，因此可以得到Agent2选择等待直到Agent3过去，这样避免了两者之间的碰撞;而在C点处Agent3、Agent4、Agent5同时检测到三者之间会在C点处发生碰撞，因此三者之间会产生一个博弈的过程，这时经过算法2可以得到由于Agent3距离目标点较近因此为了减少损失不必要作过多的行为变化，从而其有较高的优先级，这时只需微调方向后再回到原始蚁群算法规划好的路径就可以避免与Agent4与Agent5的碰撞;如图5中红色加粗虚线部分，而 Agent4与Agent5之间也会产生一个博弈的过程，利用算法2可以得到Agent4相比与Agent5会有较高的优先选择行为的权利，因此Agent5选择等待直到Agent3与Agent4过去，这样避免了三者之间的碰撞;在接下来的运动过程中虽然Agent之间的运行路线存在交点，但是Agent不是同时到达的，因此不会发生碰撞。因为本文考虑到对全局路径的规划，对比文献[12]中算法可以得到图6所示的5个Agent寻得最短路径的迭代次数对比，经过50次实验利用原始蚁群算法也即文献[2]中算法不考虑Agent之间碰撞的情况下及本文与文献[12]中的算法得到的平均路径长度的对比。

从图6中可以看出，本文引入博弈论的避障方法能够避免Agent之间的碰撞，使每个Agent快速收敛到最短路径。从图7中可以看出，本文算法与传统算法相比经过50次实验得到的平均路径长度较大，但是相比与文献[12]中的算法，本文算法的平均路径长度较优。此外为了验证本文算法的有效性，通过100次实验获得了如图8所示的本文算法与文献[12]中算法多Agent的Nash均衡值收敛曲线对比。

通过图8可以看出，本文算法在实验85次左右收敛到Nash均衡值而文献[12]中算法会出现震荡现象。

综合以上的对比实验，可以看出本文算法在寻找全局最优路径的过程中能够很好地解决Agent之间的碰撞，从而快速找到无碰路径。

5 结语

多Agent路径规划问题是MAS研究的核心问题之一，然而现有的方法着眼于静态障碍物的避碰问题，故不能解决Agent之间的动态避障问题。本文提出一个两阶段的多Agent路径规划方法：第一阶段，利用改进的蚁群算法为每个Agent规划出一条不与环境中静态障碍物碰撞的最优路径;第二阶段，如果在运动的过程中，Agent之间发生动态碰撞，利用博弈论方法建立多Agent动态避障博弈模型，并利用虚拟行动法使每个Agent能够快速学习到最优Nash均衡解。在多Agent的路径规划中具有较好的应用价值，仿真实验验证了该算法的有效性和合理性。

参考文献 （References）

[1] BENNET D J， MCINNES C R. Distributed control of multi-robot systems using bifurcating potential fields [J]. Robotics and Autonomous Systems， 2010， 58（3）： 256-264.

[2] DORIGO M， MANIEZZO V， COLORNI A. Ant system： optimization by a colony of cooperating Agents [J]. IEEE Transactions on Systems， Man， and Cybernetics， Part B： Cybernetics： A Publication of the IEEE Systems， Man， and Cybernetics Society， 1996， 26（1）： 29-41.

[3] KOVACS B， SZAYER G， TAJTI F， BURDELIS Met al. A novel potential field method for path planning of mobile robots by adapting animal motion attributes [J]. Robotics and Autonomous Systems， 2016， 82（C）： 24-34.

[4] QIAN W J， ZHOU L F，YANG L， et al. An improved ant colony algorithm of three dimensional path planning [C]// Proceedings of the 2017 10th International Symposium on Computational Intelligence and Design. Piscataway， NJ： IEEE， 2017，1： 119-122.