第2期 张文旭，等：强化学习的地-空异构多智能体协作覆盖研究 ·203· 构的假设前提，而异构多智能体与覆盖问题的结合 盖执行者，UAV则作为引导者。利用UAV观测范 相对薄弱，比如，文献「6]在一阶动态异构覆盖问题 围广和移动速度快的优势对UGV的覆盖行动进行 中，考虑不同的速度对应不同的控制输入，设计了 指导，以扩大UGV的观测视野和提高团队对位置 种分布式覆盖控制策略；文献[7☑研究了非凸环境 环境的获取准确性，UGV不断移动直到栅格被覆盖 下的覆盖问题，提出了一种梯度环境分割算法；文 到指定的程度。智能体的路径以栅格序号进行表 献[8]在异构无线传感器网络中研究了覆盖与消耗 示，便于算法中地图信息和智能体状态的更新。 的控制算法；文献[9]介绍了一种基于加权Voronoi 1.2分布式马尔可夫模型 图的异构机器人覆盖框架，根据异构覆盖代价进行 分布式控制是多智能体系统的一个重要特性， 加权，实现代价最小的覆盖任务。针对异构多智能 由于智能体携带的传感器存在精度误差，且覆盖环 体的覆盖问题，目前多智能体的异构性多体现在传 境复杂多变，智能体的局部观测性和环境的不确定 感器的异构上，即感知范围的不同，少有研究从智 性将难以避免。针对以上问题，考虑采用分布式 能体运动方式的异构性上进行考虑。另一方面，无 局部可观测马尔可夫模型(DEC-POMDPs)),其由 人机(unmanned aerial vehicle,UAV)和无人车(un- 一个八元组构成： manned ground vehicle,.UGV)的异构特性协作是多 ,S,{4l,P{2l,O,R,b）》 (1) 智能体的前沿性研究课题，它们在速度、负载、通 式中：1表示有限的智能体集合；S表示一个有限的 信、观测能力等方面具有很强的互补性，二者协作 系统状态集合；{A}表示智能体可采取的动作的集 可以有效拓宽应用范围，其应用价值受到了世界各 合；P表示系统的转移；{2}表示智能体i的观测集 国学者的广泛关注，现有的工作主要集中在路径 合；O表示观测函数；R表示回报函数；b为初始状态 规划、搜索定位、跟踪追逃等方面，比如，文献[12]提 分布。求解DEC-POMDPs的目的是找到一个联合 出了一种UAV和UGV的合作导航策略，利用UAV 策略元=（π1，π2，，πn)使回报函数R最大化。 的大视野特性引导UGV避障；文献[13]研究了多 1.3Q学习 UAV和UGV的合作监控，通过二者的观测数据融 文献[14]提出了一类通过引入期望的延时回 合完成对目标的侦查；文献[14]基于UAV和UGV 报，求解无完全信息的马尔可夫决策过程的方法， 的合作框架研究了人群跟踪的决策和监控。但是， 针对UAV和UGV互补特性的协作覆盖问题尚未 称为Q-学习(Q-learning)。Q-学习是一种与模型无 得到研究。 关的基于瞬时策略的强化学习方法，通过对状态-动 本文提出了一种地-空异构多智能体的协作覆 作对的值函数进行估计，以求得最优策略。Q学习 盖模型，针对未知环境下的动态覆盖问题，依靠 算法的基本形式如下： UAV机动性能与观测范围的优势，在覆盖过程中 2s,a)=k0+y∑rPa)maxg'6,a0(②) 对UGV的动作进行指导，同时考虑了智能体的观 式中：Q(s,a)表示智能体在状态s下采用动作a所获 测局部性和不确定性，基于分布式局部可观测马尔 得的奖赏折扣总和，y为折扣因子，P(s,a,s)表示概 可夫(DEC-POMDPs)模型建立栅格地图覆盖环境， 率函数。对于一个动态覆盖问题而言，强化学习算 根据UAV和UGV的异构特性设计覆盖场景，并利 法的优势在于，智能体无需提前了解环境模型，它 用多智能体强化学习算法完成对地图的覆盖。 可以通过与环境的交互来获得状态信息，并通过反 馈的覆盖效果对所采取的行动进行评价，利用不断 1问题描述 的试错和选择，逐步改进和完善覆盖策略，达到覆 1.1多智能体覆盖问题 盖重复路径少、覆盖时间短等优化目标。 覆盖问题大体上可分为静态与动态覆盖两类， 2覆盖问题设计 静态覆盖主要关注传感器位置的优化，动态覆盖则 要求智能体群组遍历区域内所有兴趣点。动态覆盖 2.1异构多智能体设计 包含了导航与避障的研究内容，目的是利用移动机 对于异构多智能体系统，首先需要对单个智能 器人或固定传感器，在物理接触或传感器感知范围 体的特性进行分析。UGV能够装载大容量动力装 内遍历目标环境区域，并尽可能地满足时间短、重 置和大型精密仪器，具备较高的数据处理运算能 复路径少和未遍历区域小的优化目标四。 力，但移动速度慢，视野范围小，在障碍物密集的区 本文考虑带有观测不确定性的异构多智能体动 域，行动能力受到极大限制；相比之下，UAV具有较 态覆盖问题，以栅格地图为覆盖环境，UGV作为覆 高的移动速度和空间灵活性，移动过程中不需要考构的假设前提，而异构多智能体与覆盖问题的结合 相对薄弱，比如，文献[6]在一阶动态异构覆盖问题 中，考虑不同的速度对应不同的控制输入，设计了 一种分布式覆盖控制策略；文献[7]研究了非凸环境 下的覆盖问题，提出了一种梯度环境分割算法；文 献[8]在异构无线传感器网络中研究了覆盖与消耗 的控制算法；文献[9]介绍了一种基于加权 Voronoi 图的异构机器人覆盖框架，根据异构覆盖代价进行 加权，实现代价最小的覆盖任务。针对异构多智能 体的覆盖问题，目前多智能体的异构性多体现在传 感器的异构上，即感知范围的不同，少有研究从智 能体运动方式的异构性上进行考虑。另一方面，无 人机 (unmanned aerial vehicle, UAV) 和无人车 (un￾manned 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] ，其由 一个八元组构成： ⟨ I,S,{Ai},P,{Ωi},O,R,b 0 ⟩ (1) I S {Ai} i P {Ωi} i O R b 0 ⃗π = (π1, π2,···, πn) R 式中： 表示有限的智能体集合； 表示一个有限的 系统状态集合； 表示智能体 可采取的动作的集 合； 表示系统的转移； 表示智能体 的观测集 合； 表示观测函数； 表示回报函数； 为初始状态 分布。求解 DEC-POMDPs 的目的是找到一个联合 策略 使回报函数 最大化。 1.3 Q 学习 文献[14]提出了一类通过引入期望的延时回 报，求解无完全信息的马尔可夫决策过程的方法， 称为 Q-学习 (Q-learning)。Q-学习是一种与模型无 关的基于瞬时策略的强化学习方法，通过对状态–动 作对的值函数进行估计，以求得最优策略。Q-学习 算法的基本形式如下： Q ∗ (s,a) = R(s,a)+γ ∑ s ′∈S P(s,a,s ′ )maxQ ∗ (s ′ ,a ′ ) (2) Q ∗ (s,a) s a γ P(s,a,s ′ ) 式中： 表示智能体在状态 下采用动作 所获 得的奖赏折扣总和， 为折扣因子， 表示概 率函数。对于一个动态覆盖问题而言，强化学习算 法的优势在于，智能体无需提前了解环境模型，它 可以通过与环境的交互来获得状态信息，并通过反 馈的覆盖效果对所采取的行动进行评价，利用不断 的试错和选择，逐步改进和完善覆盖策略，达到覆 盖重复路径少、覆盖时间短等优化目标。 2 覆盖问题设计 2.1 异构多智能体设计 对于异构多智能体系统，首先需要对单个智能 体的特性进行分析。UGV 能够装载大容量动力装 置和大型精密仪器，具备较高的数据处理运算能 力，但移动速度慢，视野范围小，在障碍物密集的区 域，行动能力受到极大限制；相比之下，UAV 具有较 高的移动速度和空间灵活性，移动过程中不需要考 第 2 期 张文旭，等：强化学习的地–空异构多智能体协作覆盖研究 ·203·