强化学习的地–空异构多智能体协作覆盖研究

张文旭，马磊，贺荟霖，王晓东

近年来，多智能体覆盖问题得到了越来越多的关注[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]，其由一个八元组构成：

1.3 Q学习

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

2 覆盖问题设计

2.1 异构多智能体设计

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

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

图1 UAV and UGV的异构观测Fig. 1 The heterogeneous observation of UAV and UGV

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

2.2 覆盖场景设计

定义1 基于DEC-POMDPs的覆盖环境需要体现出多智能体的异构性、分布式和不确定性，其组成类似于式(1)，可以抽象为一个 8元组结构，其中：

表1 观测-状态概率分布函数Table 1 The probability distribution function of observation-state

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

3.1 异构多智能体学习决策

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

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

图2 UAV强化学习一步策略更新流程Fig. 2 The one-step strategy update flow of reinforcement learning of UAV

UGV获得的观测能够被分为两类：1)根据智能体自身传感器获得的局部观测信息；2)依赖通信行为获得的UAV的观测信息，则联合观测表示为Ø}，。

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

图3 异构多智能体强化学习框架Fig. 3 The frame of reinforcement learning of heterogeneous multi-agent

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

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

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

4 仿真结果

图4 多智能体覆盖环境Fig. 4 The coverage environment of multi-agent

图5 异构多智能体覆盖完成步数Fig. 5 The coverage steps of heterogeneous multi-agent

执行1 000幕覆盖实验后的学习效果如图5所示，可以看出随着学习幕数的增加，经过700幕左右学习后，智能体团队完成地图覆盖所需步数逐渐收敛到较稳定的值，其中虚线为覆盖步数拟合曲线，图中覆盖步数存在的毛刺原因为智能体的观测带有不确定性，当观测信息出现错误时，可能使智能体当前学习幕的覆盖完成步数出现波动。图中实线表示一个UAV和两个UGV组成的异构多智能体团队，虚线表示只有两个UGV组成的团队。从图中可以看出，两种智能体团队对地图的覆盖成功率都随着强化学习算法的迭代不断得到提高。但是，在存在UAV的团队中，因为UAV可以对UGV的覆盖行动进行指导，所以在经过700幕左右学习时，团队覆盖成功率就开始趋于稳定，而只有UGV的团队，需要900幕左右的学习才开始趋于稳定，因此体现出UAV与UGV协作覆盖的优势。

图6 覆盖试验成功率Fig. 6 The success rate of coverage

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

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

图7 陷阱区域访问次数统计Fig. 7 The count of visits to the trap

5 结束语

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

[1]KANTAROS Y, ZAVLANOS M M. Distributed communication-aware coverage control by mobile sensor networks[J]. Automatica, 2016, 63: 209–220.

[2]蔡自兴, 崔益安. 多机器人覆盖技术研究进展[J]. 控制与决策, 2008, 23(5): 481–486, 491.CAI Zixing, CUI Yi’an. Survey of multi-robot coverage[J].Control and decision, 2008, 23(5): 481–486, 491.

[3]MAHBOUBI H, MOEZZI K, AGHDAM A G, et al. Distributed deployment algorithms for improved coverage in a network of wireless mobile sensors[J]. IEEE transactions on industrial informatics, 2014, 10(1): 163–174.

[4]TAO Dan, WU T Y. A survey on barrier coverage problem in directional sensor networks[J]. IEEE sensors journal,2015, 15(2): 876–885.

[5]TIAN Yuping, ZHANG Ya. High-order consensus of heterogeneous multi-agent systems with unknown communication delays[J]. Automatica, 2012, 48(6): 1205–1212.

[6]SONG Cheng, LIU Lu, FENG Gang, et al. Coverage control for heterogeneous mobile sensor networks on a circle[J].Automatica, 2016, 63: 349–358.

[7]KANTAROS Y, THANOU M, TZES A. Distributed coverage control for concave areas by a heterogeneous robotswarm with visibility sensing constraints[J]. Automatica,2015, 53: 195–207.

[8]WANG Xinbing, HAN Sihui, WU Yibo, et al. Coverage and energy consumption control in mobile heterogeneous wireless sensor networks[J]. IEEE transactions on automatic control, 2013, 58(4): 975–988.

[9]SHARIFI F, CHAMSEDDINE A, MAHBOUBI H, et al. A distributed deployment strategy for a network of cooperative autonomous vehicles[J]. IEEE transactions on control systems technology, 2015, 23(2): 737–745.

[10]CHEN Jie, ZHANG Xing, XIN Bin, et al. Coordination between unmanned aerial and ground vehicles: a taxonomy and optimization perspective[J]. IEEE transactions on cybernetics, 2016, 46(4): 959–972.

[11]ZHOU Yi, CHENG Nan, LU Ning, et al. Multi-UAV-aided networks: aerial-ground cooperative vehicular networking architecture[J]. IEEE vehicular technology magazine,2015, 10(4): 36–44.

[12]PAPACHRISTOS C, TZES A. The power-tethered UAVUGV team: a collaborative strategy for navigation in partially-mapped environments[C]//Proceedings of 22nd Mediterranean Conference of Control and Automation.Palermo, Italy, 2014: 1153–1158.

[13]GROCHOLSKY B, KELLER J, KUMAR V, et al. Cooperative air and ground surveillance[J]. IEEE robotics and automation magazine, 2006, 13(3): 16–25.

[14]KHALEGHI A M, XU Dong, WANG Zhenrui, et al. A DDDAMS-based planning and control framework for surveillance and crowd control via UAVs and UGVs[J]. Expert systems with applications, 2013, 40(18): 7168–7183.

[15]马磊, 张文旭, 戴朝华. 多机器人系统强化学习研究综述[J]. 西南交通大学学报, 2014, 49(6): 1032–1044.MA Lei, ZHANG Wenxu, DAI Chaohua. A review of developments in reinforcement learning for multi-robot systems[J]. Journal of southwest Jiaotong university, 2014,49(6): 1032–1044.

[16]PUTERMAN M L. Markov decision processes: discrete stochastic dynamic programming[M]. New York: John Wiley and Sons, 1994.

[17]WATKINS C J C H, DAYAN P. Q-learning[J]. Machine learning, 1992, 8(3/4): 279–292.

[18]WU Feng, ZILBERSTEIN S, CHEN Xiaoping. Online planning for multi-agent systems with bounded communication[J]. Artificial intelligence, 2011, 175(2): 487–511.