基于非合作博弈的多智能体覆盖问题动态规划

谢晨辉，谢能刚，王 璐，暴 伟

(1.安徽工业大学机械工程学院，安徽 马鞍山 243002；2.安徽工业大学管理科学与工程学院，安徽 马鞍山，243002)

1 引言

多智能体覆盖问题主要研究的是：针对具备一定范围内感知、通信和分辨能力以及分布计算性能的多个智能体，通过自组织的方式运动，使得多智能体系统在保持连通的同时，最终形成的网络状态能实现对特定环境的最大覆盖[1]。目前多智能体覆盖在很多实际任务中都有应用，如监视、搜救[2]、无线通信[3]、耕种等方面。多智能体覆盖问题中的关键是智能体的移动策略，一些初始位置随机的智能体在确定了策略后，经过多次移动，最后达到最理想的覆盖，获得最终的拓扑结构。因此，多智能体覆盖控制就是路径规划问题。此问题的评价指标主要有覆盖度与一致性，文献[4]就将一致性结合多智能体覆盖控制进行了研究，并在一维空间内进行了仿真，证明了算法的有效性。

目前计算动态路径的算法主要分为集中式和分布式两种。文献[5]描述了一种通过集中配置静态节点位置的算法，使整个网络拓扑结构满足全部连通和最大覆盖。但这种集中式算法要求环境已知且不够鲁棒。考虑到对环境的适应性，分布式算法就更加灵活可行。文献[6]提出了一种基于栅格法的集中式全覆盖路径规划算法，该算法有效地减少了栅格的密度，使得覆盖路径大大减少。Koenig等[7]提出了一种分布式的仿生覆盖算法，通过模仿蚂蚁在经过路程上释放信息素这一行为，利用提醒机制避免其它蚂蚁在该路程范围内(一定信息素浓度的区域)进行重复覆盖并最终达到最大覆盖。Batalin[8]等设计了一种智能体之间通过信息交换来互相排斥，并实现覆盖目标最大的分布式算法。

由于博弈论在多智能体协作问题上的广泛应用和良好表现，目前也被应用到多智能体覆盖问题中。Xu M[9]提出了一种基于非合作博弈的无线传感系统辅助拓扑控制算法，但算法仍有较大的冗余。钱凌[10]等将顺序博弈应用到覆盖控制当中，提出一种分布式算法，实现了无线传感网络中节点能量的均衡。刘昊然[11]等针对冗余造成能量效率低的问题，综合考虑网络节点覆盖率和节点剩余能量，提出了一种基于非合作博弈的无线传感器覆盖控制算法，增加了网络利用率和网络生命周期。Xin Ai[12]等基于非合作博弈模型，使用交互式算法来寻找博弈均衡解，利用多智能体之间重叠的感知面积最小化，来实现系统对环境的最大覆盖。丁晓燕[13]将非合作博弈引入到多智能体覆盖问题中，利用非合作博弈的个体理性来寻找最优解，每个智能体通过预测邻居智能体的行动来确定自己的最优移动策略，所有智能体的最优策略组合就构成系统的Nash均衡，经过多次移动后，整个系统就会达到一种平衡并实现最大的覆盖。但文献[13]只将智能体的移动方向作为博弈模型中的策略变量，通过多智能体博弈确定最佳方向后，再通过计算出最大可行步长的方式来保证多智能体系统的连通性。这种分两步走的方法不仅使计算量增加，同时无法解决智能体移动步长和移动方向之间可能出现的不协调问题，例如在第一步已经确定的各智能体最佳方向的基础上，在第二步各智能体移动步长的计算中，可能出现没有维持系统连通性的可行解的情形。

本文将多智能体系统对环境实现最优覆盖的任务视为分布式的动态规划问题，并针对动态规划过程进行博弈建模，同时针对文献[13]的不足，在非合作博弈模型中将智能体的移动步长和移动方向同时作为博弈的策略变量，将维持系统连通性作为博弈模型的约束条件，采用进化算法进行各个博弈方的策略寻优，通过谈判算法获得博弈均衡解，实现各个智能体在当前步下的最佳移动。智能体系统经过多次移动并达到稳定后，系统的网络拓扑既有连通性又可实现最佳覆盖度。本文算法的分布式控制模式可以克服鲁棒性不足的缺点。

2 多智能体覆盖控制问题描述与建模

2.1 问题描述

已知二维环境中有n个智能体，n个智能体的初始位置为(x1(0)，y1(0))、…、(xi(0)，yi(0))、…、(xn(0)，yn(0))，智能体之间的通信半径为Rc(与邻居交流半径)，智能体移动的最大可行步长为ρmax，智能体覆盖半径为Rf(智能体实际覆盖区域)；所有智能体已知邻居与自己的距离与方向。研究的问题是：在保持多智能体系统连通性的条件下(每个智能体至少有m个邻居)，对多智能体的移动路径进行规划，并使最终的分布状态实现对环境的最大覆盖，其中环境覆盖的评价指标为单位个体平均覆盖率λ，定义为

(1)

2.2 博弈建模

针对上述多智能体移动路径的动态规划问题，即已知k时刻(k=0，1，2，…)的n个智能体的位置(x1(k)，y1(k))、…、(xi(k)，yi(k))、…、(xn(k)，yn(k))，规划k+1时刻n个智能体的位置，本文建立非合作博弈模型进行求解。对任意k+1时刻：

1)n个智能体视为n个博弈方；

2)任意第i个博弈方的策略集Si={ρi，θi}，其中：ρi为第i个智能体的步长，θi∈[0，2π]为第i个智能体的方向。因此第i个博弈方在k+1时刻的位置坐标(xi(k+1)，yi(k+1))可表示为

xi(k+1)=xi(k)+ρicosθi

yi(k+1)=yi(k)+ρisinθi

(2)

3)在智能体的博弈得益上不仅考虑该智能体的覆盖性能，让其与邻居智能体之间的距离保持足够远以覆盖尽可能大的范围(减少冗余面积)，还考虑该智能体和邻居智能体之间的一致性指标(即该智能体尽量处于由其所有邻居组成的网络拓扑的中心，以使得相邻智能体间距离的方差尽量小)。任意第i个博弈方的得益函数为[9]

(3)

利用上述模型对k=0，1，2，…逐步进行博弈求解，以此获得所有智能体在每个移动步的坐标，完成多智能体移动路径的动态规划，覆盖问题规划成功的收敛判据为

(4)

式中：δ为给定的小值。

3 博弈模型求解

3.1 博弈均衡解的谈判求解算法

博弈均衡解的谈判求解算法步骤如下：

1)在各博弈方的策略空间S1，…，Sn中随机生成(或给定)初始可行策略，形成策略组合s0={s10，s20，…，sn0}；其中任意si0=(ρi0，θi0)。

3.2 单目标优化算法

对于3.1节中博弈均衡解求解算法的步骤2)，其中第i个(i=1，2，…，n)博弈方的单目标优化问题，基于进化算法[11]进行求解计算，具体计算步骤如下：

1)输入初始种群规模L，最大进化代数Tmax。置初始进化代t=0，随机产生L个初始设计变量的向量

2)取目标函数Fi为适应函数，值越大适应性越好。

3)调整方差向量ξ，让第tl代父本变异并选择个体进入第tl+1代。

在上述各步中，解向量si=(ρi，θi)和方差向量ξ=(ξ1，ξ2)的变异是进化计算中最关键的步骤，(si，ξ)变异的后代(s′i，ξ′)为

ξ′h=ξhexp(φ′·N(0，1)+φ·Nh(0，1))(h=1，2)，

ρ′i=ρi+N(0，ξ′1)，θ′i=θi+N(0，ξ′2)

4 仿真结果及分析

4.1 有界环境的仿真分析

有界环境取50×50的矩形区域，取7个智能体，通讯半径Rc取20，覆盖半径Rf取10，最大步长ρmax=0.5，关键邻居控制值m取1。覆盖问题动态规划中的参数δ取0.005，博弈求解中参数ε取0.002，单目标优化的进化算法参数设置为：种群规模L=60，最大进化代数Tmax=50，阈值μ=0.01。多智能体的初始位置分3种情形：集中在中心、集中在角点和随机分散。

图1-图3为不同初始位置时多智能体系统覆盖控制结果，图4为不同初始位置时系统覆盖度随移动步的变化情况，其中覆盖度定义为：覆盖度=系统已覆盖面积/环境总面积。从结果可以看出，不同初始位置的多智能体系统在本文博弈算法的动态规划下，最终都能达到一种稳定的较优的覆盖。从集中在中心、集中在角点和随机分散等3种初始位置出发，最终状态的系统覆盖度分别为：81.298%、80.402%和80.260%，均高于80%。同时，从图1-图3也可看出，多智能体之间存在重叠的覆盖面积(图中的阴影部分)以及超出环境边界的区域，定义：冗余度=(n×单个智能体覆盖面积-系统已覆盖面积)/n×单个智能体覆盖面积)，冗余度指标越小，表示多智能体系统的覆盖效率越高，经计算，从集中在中心、集中在角点和随机分散等3种初始位置出发，最终状态的系统冗余度分别为：8.616%、9.774%和9.957%，均在10%以下，说明系统效率较高。

图1 初始位置集中在中心时多智能体系统覆盖控制结果

图2 初始位置集中在角点时多智能体系统覆盖控制结果

图3 初始位置随机分散时多智能体系统覆盖控制结果

图4 系统覆盖度随移动步的变化情况

4.2 无界环境的仿真分析

取无界环境，智能体数取20，通讯半径Rc取20，覆盖半径Rf取20。初始位置为随机分布在一定区域内(如图5所示)，其它计算条件和参数同有界环境。

图5给出了终态时的网络拓扑结构。圆点为智能体，点与点之间的线为邻居之间的连线，可以看出整个网络是连通的。图6给出了单位个体平均覆盖率随移动步的变化情况，可以看出单位个体平均覆盖率在多智能体移动初期迅速上升，随后波动逐渐减小并渐趋稳定，最终达到最大覆盖48.6%。图7给出了系统中单个智能体的平均邻居数随移动步的变化情形，从中可看出，初始位置时每个智能体都有19个邻居(这个从图5也可得到，因为所有智能体初始集中在一个较小的通讯半径可以覆盖的区域内)，随着智能体逐渐移动，平均邻居数开始下降(智能体分散开，使得相互之间逐渐脱离通讯半径)，大约350步后平均邻居数目趋于小幅波动并逐渐稳定，基本维持在1.5左右。图8和图9显示了智能体系统中所有邻居对(互为邻居的两个智能体)之间距离的平均值和方差随移动步的变化情况，可以看出，随着智能体的移动，系统中邻居距离的平均值一直呈现单调上升的趋势，并逐渐趋向以通讯半径20为上限的值；同时，系统中邻居距离的方差随着智能体从初始位置分散开，首先呈现迅速增长的趋势(即不同邻居对之间的距离相差较大，此时对应图8中平均值迅速上升的阶段)，随着智能体系统的继续移动，一些距离超过通讯半径的邻居对解体，并且不同邻居对之间的距离也得到了一定的调整，使得差距变小，方差呈现为缓慢的下降趋势(对应图8中平均值平稳上升的阶段)，在240步以后，随着邻居对解体进程和不同邻居对之间的距离调整进程的加快(即不同邻居对之间的距离都逐渐趋向20，对应图8中平均值再次较快上升的阶段)，方差迅速下降并逐步趋向于0。

图5 智能体系统的初始位置和终态时的网络拓扑

图6 单位个体平均覆盖率随移动步的变化图

图7 平均邻居数随移动步的变化图

图8 系统中邻居距离的平均值随移动步的变化图

图9 系统中邻居距离的方差随移动步的变化图

5 结语

1)针对多智能体覆盖问题，基于第三代系统观(即复杂适应系统)，突破把系统元素看成“死”的、被动对象的观念，引进具有竞争能力的博弈方主体，将多智能体系统实现对环境覆盖的移动过程视为具有自组织能力的多个博弈方之间的动态规划。针对每一个动态规划步(所有智能体在每一动态规划步的移动都是同步的)，将n个智能体视为n个博弈方，将每个智能体的移动步长和移动方向作为该博弈方的策略变量，同时将维持系统连通性作为博弈模型的约束条件，每个博弈方通过预测邻居博弈方的行动来确定自己的最优移动策略(包括移动方向和移动步长)，通过各博弈方之间的多轮谈判以达到最优策略组合，获得系统中每个智能体在当前步的最佳移动方向和最佳移动步长，并得到下一步位置坐标，完成多智能体移动路径的动态规划，并最终实现对环境的最大覆盖。

2)利用本文算法对有界环境和无界环境下的多智能体覆盖问题进行了仿真分析，结果表明，本算法不仅能保证多智能体系统整体移动时的连通性，而且系统的最终位置状态可实现对环境的最大覆盖。在有界环境下，分析了不同初始位置对覆盖效果的影响，结果表明，无论是系统覆盖度指标还是冗余度指标，都是从集中在中心的初始位置出发，系统的最终状态最佳。表1显示了无界环境下本文计算结果与文献[13]的计算结果在性能指标上的对比。根据表1，可以发现，在同样的计算工况下，文献[13]经过500次的移动步，单位个体平均覆盖率为45.9%，本文算法经过370次左右的移动步，单位个体平均覆盖率为48.6%；文献[13]最终平均邻居数在2.2-2.5的区间内，而本文算法的最终平均邻居数在1.5左右，体现出更大的分散度。因此通过本文算法最终形成的多智能体系统拓扑网络能在保持整体连通的同时，实现对环境的更好覆盖，且算法效率更高。

表1 性能指标对比