近年来，多智能体覆盖问题得到了越来越多的关注^[1]，并作为多智能体协调控制的一个重要研究方向，有着重要的理论和应用价值，在服务保障、工业制造、军事侦察、安全保卫、灾后搜救、星球探索、资源勘察等方面都有着广阔的应用前景^[2]，其主要研究包括路径规划、动态避障、任务分配等方面^[3-4]。

对于一个多智能体系统，智能体的异构特性可以更大地发挥多智能体的优势，更好地完成协作任务^[5]。目前，大多数的覆盖研究都基于智能体为同构的假设前提，而异构多智能体与覆盖问题的结合相对薄弱，比如，文献[6]在一阶动态异构覆盖问题中，考虑不同的速度对应不同的控制输入，设计了一种分布式覆盖控制策略；文献[7]研究了非凸环境下的覆盖问题，提出了一种梯度环境分割算法；文献[8]在异构无线传感器网络中研究了覆盖与消耗的控制算法；文献[9]介绍了一种基于加权Voronoi图的异构机器人覆盖框架，根据异构覆盖代价进行加权，实现代价最小的覆盖任务。针对异构多智能体的覆盖问题，目前多智能体的异构性多体现在传感器的异构上，即感知范围的不同，少有研究从智能体运动方式的异构性上进行考虑。另一方面，无人机(unmanned aerial vehicle, UAV)和无人车(unmanned ground vehicle, UGV)的异构特性协作是多智能体的前沿性研究课题^[10]，它们在速度、负载、通信、观测能力等方面具有很强的互补性，二者协作可以有效拓宽应用范围, 其应用价值受到了世界各国学者的广泛关注^[11]，现有的工作主要集中在路径规划、搜索定位、跟踪追逃等方面，比如，文献[12]提出了一种UAV和UGV的合作导航策略，利用UAV的大视野特性引导UGV避障；文献[13]研究了多UAV和UGV的合作监控，通过二者的观测数据融合完成对目标的侦查；文献[14]基于UAV和UGV的合作框架研究了人群跟踪的决策和监控。但是，针对UAV和UGV互补特性的协作覆盖问题尚未得到研究。

本文提出了一种地–空异构多智能体的协作覆盖模型，针对未知环境下的动态覆盖问题，依靠UAV机动性能与观测范围的优势，在覆盖过程中对UGV的动作进行指导，同时考虑了智能体的观测局部性和不确定性，基于分布式局部可观测马尔可夫(DEC-POMDPs)模型建立栅格地图覆盖环境，根据UAV和UGV的异构特性设计覆盖场景，并利用多智能体强化学习算法完成对地图的覆盖。

1 问题描述 1.1 多智能体覆盖问题

覆盖问题大体上可分为静态与动态覆盖两类，静态覆盖主要关注传感器位置的优化，动态覆盖则要求智能体群组遍历区域内所有兴趣点。动态覆盖包含了导航与避障的研究内容，目的是利用移动机器人或固定传感器，在物理接触或传感器感知范围内遍历目标环境区域，并尽可能地满足时间短、重复路径少和未遍历区域小的优化目标^[2]。

本文考虑带有观测不确定性的异构多智能体动态覆盖问题，以栅格地图为覆盖环境，UGV作为覆盖执行者，UAV则作为引导者。利用UAV观测范围广和移动速度快的优势对UGV的覆盖行动进行指导，以扩大UGV的观测视野和提高团队对位置环境的获取准确性，UGV不断移动直到栅格被覆盖到指定的程度。智能体的路径以栅格序号进行表示，便于算法中地图信息和智能体状态的更新。

1.2 分布式马尔可夫模型

分布式控制是多智能体系统的一个重要特性，由于智能体携带的传感器存在精度误差，且覆盖环境复杂多变，智能体的局部观测性和环境的不确定性将难以避免^[12]。针对以上问题，考虑采用分布式局部可观测马尔可夫模型(DEC-POMDPs)^[13]，其由一个八元组构成：

$\left\langle {I, S, \left\{ {{A_i}} \right\}, P, \left\{ {{\varOmega _i}} \right\}, O, R, {b^0}} \right\rangle $

(1)

式中： $I$ 表示有限的智能体集合； $S$ 表示一个有限的系统状态集合； $\left\{ {{A_i}} \right\}$ 表示智能体 $i$ 可采取的动作的集合； $P$ 表示系统的转移； $\left\{ {{\varOmega _i}} \right\}$ 表示智能体 $i$ 的观测集合； $O$ 表示观测函数； $R$ 表示回报函数； ${b^0}$ 为初始状态分布。求解DEC-POMDPs的目的是找到一个联合策略 $\vec \pi = \left( {{\pi _1}, {\pi _2}, \cdots \!, {\pi _n}} \right)$ 使回报函数 $R$ 最大化。

1.3 Q学习

文献[14]提出了一类通过引入期望的延时回报，求解无完全信息的马尔可夫决策过程的方法，称为Q-学习(Q-learning)。Q-学习是一种与模型无关的基于瞬时策略的强化学习方法，通过对状态–动作对的值函数进行估计，以求得最优策略。Q-学习算法的基本形式如下：

${Q^*}(s, a) = R(s, a) + \gamma \sum\nolimits_{s' \in S} {P(s, a, s')} \max {Q^*}(s', a') $

(2)

式中： ${Q^*}(s, a)$ 表示智能体在状态 $s$ 下采用动作 $a$ 所获得的奖赏折扣总和， $\gamma $ 为折扣因子， $P(s, a, s')$ 表示概率函数。对于一个动态覆盖问题而言，强化学习算法的优势在于，智能体无需提前了解环境模型，它可以通过与环境的交互来获得状态信息，并通过反馈的覆盖效果对所采取的行动进行评价，利用不断的试错和选择，逐步改进和完善覆盖策略，达到覆盖重复路径少、覆盖时间短等优化目标。

2 覆盖问题设计 2.1 异构多智能体设计

对于异构多智能体系统，首先需要对单个智能体的特性进行分析。UGV能够装载大容量动力装置和大型精密仪器，具备较高的数据处理运算能力，但移动速度慢，视野范围小，在障碍物密集的区域，行动能力受到极大限制；相比之下，UAV具有较高的移动速度和空间灵活性，移动过程中不需要考虑地面复杂的障碍环境，然而它的实时运算能力、负载能力和电量荷载受到较大限制。

根据UGV和UAV的上述特性，在地–空异构多智能体覆盖问题中，如图1所示，UAV以五角星表示，定义UAV采取类似于摄像头抽象环境扫描算法，在环境中的观测范围为一个扫描半径为2个栅格的圆形区域，如虚线区域所示，其中12个阴影栅格为UAV的观测，并据此获得相关观测矩阵。

UAV获得的观测信息不仅用于决策UAV的下一步移动动作，还需要向UGV提供额外的地图环境信息。其次，考虑到UAV的速度异构特性，定义其移动速度为每步2个栅格，图中箭头表示智能体的移动方向。UGV以圆圈表示，不同于UAV具备广阔的高空视野，UGV的观测范围较小，定义其观测为前、后、左、右4个栅格，即周围的阴影栅格，设定移动速度为每步1个栅格。UGV的优势在于对环境信息的测量精度要高于UAV。

2.2 覆盖场景设计

定义1　基于DEC-POMDPs的覆盖环境需要体现出多智能体的异构性、分布式和不确定性，其组成类似于式(1)，可以抽象为一个8元组 $\left\langle {I, {{S}}, \left\{ {{A_i}} \right\}, P, \left\{ {{\varOmega _i}} \right\}, O, R, {b^0}} \right\rangle $ 结构，其中：

$I$ 为智能体数量集合： $I = \left\{ {1, 2, 3} \right\}$ ，异构多智能体系统包含3个智能体，其中编号为1和2的智能体为UGV，编号为3的智能体是UAV。

${{S}}$ 为状态矩阵：用来描述整张地图上各栅格被访问的情况，即各智能体自身的状态，状态集合为 ${{S}}:J \times L$ 。其中 $J$ 表示地图被覆盖的情况，地图上每个栅格的状态信息又可表示为尚未访问状态 ${s_1}$ 、已访问状态 ${s_2}$ 、障碍物状态 ${s_3}$ 3类情况。 $L$ 包含第 $i$ 个智能体在地图上的位置 ${P_i}$ 。

${\varOmega _i}$ 为观测集合：表示第 $i$ 个智能体的观测集合。对UGV而言， ${\varOmega _i}\left( t \right) = \left\{ {{{{env}}_i}\left( t \right), {{po}}{{{s}}_i}\left( t \right), {{po}}{{{s}}_j}\left( t \right)} \right\}$ , $i \in \left[{1, 2} \right]$ ，依次描述 $t$ 时刻第 $i$ 个UGV的自身局部观测信息 ${{{env}}_i}\left( t \right)$ 、自身的位置信息 ${{{pos}}_i}\left( t \right)$ 以及根据通信获得的其他UGV位置信息 ${{{pos}}_j}\left( t \right)$ ，设定UGV无法观测到UAV的位置；对于UAV而言，观测集合 ${\varOmega _3}\left( t \right) =$ $ \left\{ {{{{env}}_3}\left( t \right), {{{pos}}_1}\left( t \right), {{{pos}}_2}\left( t \right), {{{pos}}_3}\left( t \right)} \right\}$ ，依次描述 $t$ 时刻UAV自身对环境的观测、各个UGV的相对位置(当UGV处于UAV传感范围时)、UAV自身的位置。在环境观测矩阵 ${{{env}}_i}\left( t \right)$ 中，包含智能体观测范围内 $n$ 个点的环境观测信息集合 $j\left( t \right) = \left\{ {{\varepsilon _1},{\varepsilon _2},} \right.$ $\left. {{\varepsilon _3},{\varepsilon _4}} \right\}$ , 其中 ${\varepsilon _1}$ 表示尚未访问的栅格， ${\varepsilon _2}$ 表示已经访问的栅格， ${\varepsilon _3}$ 表示障碍物栅格， ${\varepsilon _4}$ 表示UGV。智能体的传感器感应范围内出现其他UGV时，能根据该UGV对环境的状态感知获取其相对位置，对于一辆UGV而言，其观测范围内的其他UGV，作为障碍物进行考虑。

$O$ 为观测概率函数：体现了智能体观测的不确定性， $O\left( {o|s, a} \right)$ 表示智能体执行 $a$ 后转移到状态 $s$ 时获得观测 $o$ 的概率。智能体从所处环境中获取观测信息可以用概率矩阵进行表示，假设栅格地图上观测点的观测函数相同，定义其观测–状态概率分布函数如表1所示。

$O\left( {{s_1}|{\varepsilon _1}, a} \right) = 0.9$ 表示在执行 $a$ 后，到达真实状态 ${s_1}$ 时， ${s_1}$ 为 ${\varepsilon _1}$ 的观测概率为0.9。

${A_i}$ 为动作集合：表示第 $i$ 个智能体的动作。对于UGV和UAV， $t$ 时刻可能产生的动作为 ${A_i}\left( t \right) =\{ {up}, $ $ {{{ down, left, right}}} \}$ 。

$R$ 为回报函数：表示环境对智能体的行动给出的评价。对于UGV，执行一次行动后存在着“没走过”、“走过”和“障碍物”3个状态，分别对应着30、–5和–10的回报值，栅格的边界作为障碍物考虑。在覆盖问题中，UAV对UGV的观测起指导作用，所以UAV的回报由两部分组成，第1部分为UAV自身的回报，和UGV的回报定义相同，第2部分为UGV反馈的回报，其定义为

${R_{{UAV}}} = \mu \cdot {R_{{UAV}}} + \left( {1 - \mu } \right) \cdot \sum {{R_{{UGV}}}}$

(3)

式中： $\mu $ 为权重系数，当UAV的观测范围里没有UGV时 $\mu = 1$ 。

${b^0}$ 为初始信念状态：智能体根据初始信念状态和初始Q值函数获取当前应选择的动作向量。其更新公式为

${b^t}\left( {s\left( {t + 1} \right)} \right) = O\left( {{s_1}|\varepsilon, a} \right)\sum\limits_{s \in S} {{b^t}\left( {s\left( t \right)} \right)} P\left( {s\left( {t + 1} \right)|s\left( t \right), a} \right)$

(4)

3 基于强化学习的覆盖算法 3.1 异构多智能体学习决策

在覆盖场景中，我们将UGV设定为任务执行者，负责访问地图上尚未被探索的栅格，而将UAV设定为作团队中的督导者，通过通信向UGV提供更广阔的视野信息，配合UGV建立更精确的信念状态，实现更高效的覆盖。

考虑到智能体的结构异构性和局部观测性，假设UAV可以向观测范围内的UGV进行单向通信，并发送UAV的观测信息，而UGV之间不能进行通信。UAV的强化学习一步策略更新的流程如图2所示。

UGV获得的观测能够被分为两类：1)根据智能体自身传感器获得的局部观测信息 ${\varOmega _{{{local}}}}$ ；2)依赖通信行为获得的UAV的观测信息 ${\varOmega _{{{other}}}}$ ，则联合观测表示为 ${\varOmega _{{{joint}}}} = \{ {\Omega _{{{local}}}},{\Omega _{{{other}}}} \cup $ Ø}， ${\varOmega _{{{local}}}} \in {\varOmega _{{{joint}}}}$ 。

由于局部观测性的存在，UGV不一定在所有时刻都能获得UAV的观测信息，本文用类似文献[15]所提通讯受限的多智能体在线规划算法的思想，将学习过程分为可以通信与不能通信两种情况。在DEC-POMDPs 模型中嵌入多个局部可观察马尔可夫决策过程(partially observable Markov decision processes, POMDP)模型作为辅助学习单元，在POMDP模型中使用最大似然算法，如表1所示，并将局部状态近似看作全局状态。当执行策略更新时，依照观测来源将观测划分为局部观测 ${\varOmega _{{{local}}}}$ 和联合观测 ${\varOmega _{{{joint}}}}$ 两类，强化学习框架如图3所示。

当智能体团队执行联合行动，并获取联合观测 ${\varOmega _{{{joint}}}}$ 后，也获得相应的局部观测 ${\varOmega _{{{local}}}}$ 信息，此时从POMDP对应的Q值表中获取局部观测 ${\varOmega _{{{local}}}}$ 对应的动作 ${a_k}$ , 并将其作为策略倾向在联合观测中扩充观测矩阵。另外，在智能体获取环境反馈后，更新DEC-POMDPs模型相应的Q值表的同时，由于 ${\varOmega _{{{local}}}} \!\in\! {\varOmega _{{{joint}}}}$ ，同步更新POMDP模型Q值表中与 ${\varOmega _{{local}}}$ 对应的键值。当UAV和UGV的观测范围出现重叠时，考虑到智能体观测精度的异构特性，栅格地图的联合观测状态为 ${O_{{{joint}}}} = \beta \cdot {O_{{{UAV}}}} + \left( {1 - \beta } \right) \cdot {O_{{{UGV}}}}$ ，其中， $\beta $ 为权重系数。

3.2 基于强化学习的覆盖算法

解决强化学习问题主要是找到一个策略使智能体团队最终达到最大的奖励信号。如果在所有状态下，策略 $\pi $ 都大于或等于策略 $\pi '$ 的期望回报值，那么称这个策略为最优策略，记作 ${\pi ^*}$ 。而最优策略对应的状态–联合动作对 $\left( {s, {{a}}} \right)$ 也有相同的最优值函数，记作 ${Q^*}$ 。在POMDP模型下，智能体 $i$ 在 $s$ 状态下执行行动 $a$ 获得的Q值为

$\begin{array}{c}{Q_i}\left( {s(t),a} \right) = R\left( {s(t),a} \right) + \\ \sum\limits_{s \in S} {\sum\limits_{o \in \varOmega } {P\left( {s(t + 1)\left| {s(t),a} \right.} \right)O\left( {o\left| s \right.(t + 1),a} \right)V\left( {s(t + 1),a} \right)} } \end{array}$

(5)

Q学习更新公式为

$\begin{array}{c}{Q_t}\left( {s(t),a} \right) = (1 - \alpha ){Q_t}\left( {s(t),a} \right) + \\ \alpha \left[ {R\left( {s(t),a} \right) + \mathop {\max }\limits_a \left\{ {{Q_t}\left( {s(t + 1),a} \right)} \right\}} \right]\end{array}$

(6)

DEC-POMDPs与POMDP的唯一区别在于智能体的数量由单个变为多个，其Q-学习迭代表达式与POMDP类似，智能体的行动由单独行动 $a$ 变为联合行动 ${{a}}$ ：

$\begin{array}{c}{Q_t}\left( {s(t),{{a}}} \right) = (1 - \alpha ){Q_t}\left( {s(t),{{a}}} \right) + \\ \alpha \left[ {R\left( {s(t),{{a}}} \right) + \mathop {\max }\limits_a \left\{ {{Q_t}\left( {s(t + 1),{{a}}} \right)} \right\}} \right]\end{array}$

(7)

4 仿真结果

仿真实验考虑一个 $20 \times 20$ 大小的栅格地图环境，如图4所示，最外围是地图边界，黑色区域表示障碍物，智能体的初始位置固定，五角星表示UAV，圆圈表示UGV。智能体团队的任务为尽可能多地访问到所有栅格，即完成对格子世界的覆盖。当走过的栅格超过95%以上时，认为此次覆盖任务成功；当智能体在1 500步仍不能完成95%的覆盖时，认为此次任务失败。定义学习率为0.6，折扣因子为0.2， $\mu {{ = }}0.4$ ， $\beta {{ = }}0.3$ 。仿真实验在MATLAB 2012b环境下进行，并利用Mysql数据库存储Q值表。

执行1 000幕覆盖实验后的学习效果如图5所示，可以看出随着学习幕数的增加，经过700幕左右学习后，智能体团队完成地图覆盖所需步数逐渐收敛到较稳定的值，其中虚线为覆盖步数拟合曲线，图中覆盖步数存在的毛刺原因为智能体的观测带有不确定性，当观测信息出现错误时，可能使智能体当前学习幕的覆盖完成步数出现波动。

图6对比了UAV加入任务时的覆盖成功率，图中实线表示一个UAV和两个UGV组成的异构多智能体团队，虚线表示只有两个UGV组成的团队。从图中可以看出，两种智能体团队对地图的覆盖成功率都随着强化学习算法的迭代不断得到提高。但是，在存在UAV的团队中，因为UAV可以对UGV的覆盖行动进行指导，所以在经过700幕左右学习时，团队覆盖成功率就开始趋于稳定，而只有UGV的团队，需要900幕左右的学习才开始趋于稳定，因此体现出UAV与UGV协作覆盖的优势。

最后，在地图左上角设置了一个影响整体覆盖效果的“陷阱”区域，用以进一步的验证在强化学习过程中，UAV对UGV的引导效果。陷阱区域如图4中虚线圈区域所示，为边界与障碍物所夹的6个栅格，访问此区域的回报 $R = 0.3$ ，低于访问其他空旷区域的回报。当覆盖率达到95%时，认为本次覆盖任务成功，但陷阱区域属于不应该访问的5%部分，每幕覆盖实验结束后，记录陷阱区域被访问的次数，每20个学习幕进行一次采样。

图7对比了UAV加入覆盖任务时对陷阱区域的访问效果，由图中可以看出，两种智能体团队对陷阱区的访问次数，都将随着学习幕数的增加而逐渐减少，最终将不再访问陷阱区，体现了强化学习算法对于覆盖问题的有效性。但是，在只有两个UGV组成的团队进行覆盖任务时，由于UGV的观测范围较小，团队需要更多的学习幕数后，才能减少对陷阱区域的访问。

5 结束语

本文探讨了异构多智能体与动态覆盖问题的结合，以UAV和UGV的异构协作任务为背景，提出了一种地–空异构多智能体协作覆盖模型。根据UAV和UGV的异构特性，设计了UAV和UGV互补的覆盖观测方法，同时考虑到智能体观测的局部性和不确定性，以DEC-POMDPs为模型建立覆盖场景，并利用多智能体强化学习算法完成了对环境的覆盖。进一步工作主要包括：1)在强化学习动作选择中考虑UAV和UGA的动力学模型；2)在UAV与UGV的互补特性中考虑分布式系统的信息融合问题，以提高学习收敛速度。