多智能体动态目标协同搜索策略研究

赵梓良，刘 洋，李博伦，马力超，张志彦

（北京机械设备研究所，北京 100039）

0 引言

随着建图定位、目标识别、机器学习和通信组网等技术的成熟，无人智能体以其运算速度快、运动速度快、能长时间作业、能在极端环境下作业等特点，在目标搜索课题中受到青睐，被期望替代人类在危险、恶劣环境中高效长时间执行巡逻、侦察和搜救任务[1]。而多智能体的集群协作作业又能大大提升目标搜索任务的完成效率。

多智能体集群搜索策略是多机器人领域中一个重要的研究课题，通过一个显示控制平台和多个智能单体（如无人机）之间的协同策略规划，完成对一定区域内的静止、运动目标的搜索任务[2−7]。多智能体集群搜索策略设计主要包括2个步骤，一是智能体对待搜索环境场景的理解与建图，二是智能体对待搜索环境场景的协同搜索策略设计。

目前环境地图的典型表示方法包括尺度地图和拓扑地图2种。其中尺度地图基于直接度量信息表示环境细节，为地图中最小单位区域（栅格）赋值，如用0表示自由空间而用1表示障碍物。拓扑地图则是提取自由空间中的关键节点，并用边连接相邻的节点，形成拓扑网络结构[8]。与尺度地图相比，拓扑地图表示相同环境地图所需的数据信息更少，因此更适合在大型、复杂环境下执行目标搜索和巡逻等任务[8−10]。

图2 由示例场景尺寸地图提取出的拓扑地图

目前在多智能体对环境区域进行协同搜索的研究成果中，2种典型的搜索策略为：基于贪心算法的路径规划策略[11−13]与基于拓扑地图区域划分和分区最优回路求解的多级子图巡逻(MSP)策略[14−16]。基于贪心算法的路径规划策略将路径点尽量平均地分配给每个智能体，使完成各自路径需要耗费的时间中最长的智能体的时间最短。应用该类方法的搜索系统在理论上能完成对区域的快速覆盖搜索，但由于各智能单体的规划路径中首末位置距离较远，在搜索环境较复杂、搜索场景中障碍物较多的情况下，智能体返回起点过程容易宕机，因此不适用于长时间复杂环境的区域搜索和巡逻。基于拓扑地图划分和分区最优回路求解的多级子图巡逻策略首先根据多层k划分法折叠顶点和边来减小图的大小，对较小的图进行k划分、再分解和细化后构建原始图的k路区域划分，最后对划分后的子拓扑地图求解最优回路问题，依次判定是否存在欧拉回路、哈密顿回路、非哈密顿回路与最长搜索路径，并作为子拓扑地图内单体的搜索路线。应用该类方法的搜索系统解决了贪心算法规划的路径不闭合、巡逻过程易宕机问题，能长时间循环执行搜索、巡逻任务，并在搜索静态目标时有良好的表现。但该策略仍然存在在各智能单体负责的区域边界地带搜索效果不佳、巡逻路线过于规律、容易被目标人或具有感知和决策能力的目标智能体掌握并学习规避的问题。并且在实际场景中，智能体的故障会导致其负责巡逻的区域的搜索失效，该区域成为盲区。

目前搜索场景中动态目标的躲避策略方面的研究较少，动态目标多采取随机运动策略或规律性巡线运动策略。而在被广泛研究的追捕−逃跑模型课题中，模型中目标的逃跑策略则能为搜索场景下目标人或具有感知和决策能力的目标智能体的躲避策略设计提供参考。

基于上述目标搜索方法的启发，本文提出了一种防具备躲避策略的动态目标的协同搜索策略。运用强化学习框架使多智能体和具备躲避策略的目标进行对抗性的搜索训练，让多智能体集群搜索系统不断训练、修正和优化搜索策略，提高针对动态目标的搜索效率和应对单体宕机问题的鲁棒性。

1 协同搜索策略

1.1 拓扑地图提取

如前文所述，拓扑地图相比于尺度地图，表示环境所需的数据信息更少，更适用于目标搜索任务，其数据信息可以表示为G=(V，E)，其中V表示地图中的关键节点集合，而E表示连接关键节点的边以及该条边的长度[8]。而实际建图的激光雷达等传感器获取的是占据栅格地图，因此首先需要将原始的栅格地图转换成拓扑地图[17]。图1−2展示了从尺度地图提取出拓扑地图的示例效果。

图1 gmapping算法建图获得的场景尺寸地图

上述拓扑地图提取的方法是通过对环境区域进行广度优先搜索，先计算地图中自由空间的连通区域，根据智能体的尺寸对栅格地图中的障碍物边缘轮廓进行填充扩展，确保智能体既能在最终拓扑地图相邻的节点间通行又不会与障碍物边缘碰撞；再通过扩展泰森多边形图（EVG）的方法以均匀的节点和边表示环境地图的拓扑信息[8，17]。

1.2 基于强化学习的协同搜索策略

对于优化具有躲避策略的动态目标的协同搜索效率问题，难点在于智能体对环境场景的搜索经验的缺失。而Q-learning强化学习框架可以不要求先验数据，通过训练不断优化搜索策略。在该强化学习系统中，决策者通过观察环境，根据当前状态下的观测信息做出动作尝试，并接受环境对动作尝试的奖励和惩罚反馈来获得学习信息并不断更新搜索策略的Q值表。Q值表的行索引对应决策者所处的状态，列索引对应在某一状态下执行的动作尝试，更新对应行列的Q值会不断修正决策者进行动作尝试的概率。在这个过程中符合设计目的的动作会获得奖励，决策者再次遇到同样场景会更倾向于采取这一动作，而与设计目的不符的动作则会得到惩罚，决策者会尽量避免这样的动作。经过若干次尝试，决策者对其所处的环境有了充分的理解，知道在某一状态下获得尽可能大的奖励的动作[18−20]。Q-learning强化学习框架中策略的更新可以表示为：

式中，S表示智能体当前状态，A表示智能体在S状态下采取的动作，Q(S,A)表示在S状态下采取A动作的Q值，R(S,A)表示在S状态下采取A动作的即时奖励，S′表示在S状态采取A动作后的下一状态，α为学习率，γ为折扣因子。

在本文提出的协同搜索策略中，智能体所处状态的集合（状态空间）为拓扑地图中关键节点集合V。而智能体在每一状态下可采取的动作集合（动作空间）为拓扑地图中与该状态对应的节点相连通的节点，表示由当前状态对应的节点向可通行的下一节点运动的动作。初始策略设置为随机搜索，智能体随机选择在各个状态下的动作，该策略表示为值均为0的Q值表。奖励在一次搜索完成后反馈给智能体搜索到目标必要路径上的所有状态，以激励决策者在后续到达这些状态时尽可能选择发现目标概率更大的动作。在多智能体系统中，智能单体在各个状态下选择动作的策略具有共通性，因此设计系统中的智能体共用一个Q值表，增加训练效率。而为了避免所有智能单体根据Q值表采取相同动作，参考基于节点空闲时间的巡逻策略[18,21]对即时策略做出调整。基于节点空闲时间的巡逻策略提出由主控平台发布拓扑地图中各节点的空闲时间信息，各智能体自由抢占附近空闲时间长的节点作为目标点。参照此方法中节点空闲时间设置方式，对任一智能体，将空闲时间不超过某一阈值的节点，即刚被访问过的节点的Q值即时调整为0，以避免多智能体互相跟随或在局部回路转圈等问题。

2 动态目标的躲避策略

人工势场法[22]及其优化方法在局部路径规划和追捕−逃跑研究课题中被广泛应用，该类方法根据物体当前位置及其周围的障碍物、追捕者和目标点的位置关系，在目标周围设置虚拟力场，其中障碍物、追捕者在物体的感知范围内对物体产生斥力，而目标点对物体产生引力，且力场强度由物体之间相对距离决定。物体在该虚拟力场影响下进行局部路径规划，避开障碍物和追捕者向目标点移动。但在多智能体集群搜索策略研究中，上述基于相对位置关系的人工势场法并不适用。与追捕−逃跑问题中追捕者根据逃跑者的位置进行包围不同，搜索场景下搜索者在搜索到目标前并不能获知目标的位置和与目标的距离。因此以与搜索者的距离作为影响动态目标的躲避策略的依据与实际情况不符。

考虑在实际搜索场景中，目标人物与作为搜索者的智能单体（如无人机）观测、识别距离相近，而目标人物可以依据无人机运行过程中旋翼的桨叶发出的声音判断其感知范围内有无搜索者靠近或远离，然后进行躲避的行为，设置了一种基于动作（位置变化）的人工势场法的躲藏策略。该策略中目标不仅感知一定范围内的搜索者的位置，同时感知该范围内的搜索者较自己执行的动作（靠近或远离），仅计算靠近的搜索者施加的斥力作为躲避动作的决策依据。目标感知范围内搜索者对目标的斥力场[23]可以表示为：

式中，U rep表示该位置的斥力场大小，ST为目标位置，SN为N号搜索者位置，η为斥力尺度因子，ρ为2点之间的距离，ρ0为搜索者影响半径。目标受斥力大小则是其感知范围内斥力场的梯度,可以表示为：

式中，F rep表示目标在ST位置受到的斥力。

图3给出了该躲避策略的示意图。目标当前所处位置为ST，圆内区域为目标ST的当前感知范围，S1—S5表示其周围搜索者的位置，实线箭头方向为目标感知的搜索者动作方向。在该状态下，目标ST仅考虑观测范围内向其靠近的搜索者S2和S3的动作进行躲避，图中虚线表示的向量示意了这一躲避策略的决策过程。

图3 动态目标基于动作的躲避策略示意图

3 仿真校验

为验证动态目标躲避策略的效果和经过对抗训练得到的协同搜索策略的有效性，在三维仿真平台Gazebo中分别设置静态目标搜索和动态目标搜索仿真实验，校验选用图1的场景进行，场景总面积为450.0 m2，其中可通行区域约317.9 m2，障碍物区域面积约132.1 m2。图4展示了场景和场景中4个初始状态的智能体、1个随机目标的仿真可视化实景。

图4 Gazebo平台中仿真场景和场景中4个位于初始区域的智能体（左上黑点）及1个位于随机位置的目标（右上蓝点）

对于静止目标搜索，在环境地图中同一初始区域（搜索出发区）内，分别加载1—10个配置有定位、感知与识别、决策与驱动等功能模块的无人机模型作为搜索者，以及1个初始位置随机的目标人物模型作为目标。搜索者同时从搜索出发区出发，分别对整个区域按照文献[14]提出的多级子图巡逻策略和本文提出的训练后协同策略（Q值表）展开搜索。当目标人物位置与任一搜索者距离小于1 m且不被遮挡时，视为发现目标并完成一个校验回合，同时记录本次校验的搜索时间。由于在本文校验中选用的拓扑地图边长相近（平均边长0.499 m，标准差0.031 m）、智能体在各节点停留的时间相近但难以测算，因此统计搜索者搜索的节点数量（即步数）表示搜索时间，提高训练速度。搜索者数量从1个依次增加至10个，分别重复10 000个校验回合。

对于动态目标搜索，只需在上述静态目标搜索仿真校验的基础上为初始位置随机的目标人物配置定位、感知与识别、躲避策略与驱动功能。同样地将搜索者数量从1个依次增加至10个，重复10 000个校验回合。

图5展示了不同数量智能体应用文献[14]提出的多级子图巡逻策略，对静止目标和具备本文提出的躲避策略的动态目标搜索的平均步数。校验结果表明，本文提出的基于动作的人工势场法的躲避策略会大大增加现有巡逻策略的搜索难度。原因是能精确判断搜索者动作的目标可以在多个智能体各自负责的区域边界间反复移动，规避搜索者。与随机的静止目标搜索相比，应用巡逻策略搜索具备躲藏策略的动态目标平均搜索步数增加了2.0倍，证明了动态目标躲避策略的有效性以及改进现有多极子图巡逻策略的必要性。

图5 巡逻策略对静止目标和应用躲避策略的动态目标搜索结果对比

图6展示了不同数量智能体应用多级子图巡逻策略和训练后的协同搜索策略（智能搜索策略）对于静止目标搜索所需的平均步数。当智能单体搜索静态目标时，巡逻策略表现更为优秀。但当智能体数量大于1时，2种策略完成目标搜索的整体搜索效率相近。搜索者数量为3到10个时，2种策略平均搜索步数差值均在1.0步内，且随着搜索者数量的增加，2种策略完成目标搜索的平均步数都呈下降趋势，并最终收敛趋近于9.0步，证明对于静态目标，2种搜索方式具备相近的整体表现。

图6 静止目标搜索效率仿真校验

图7展示了巡逻策略和智能搜索策略对于有躲避能力的动态目标进行搜索所需的平均步数。其中单个搜索者的情况下，智能搜索策略所需时间过长，视为无法完成搜索任务。对于有躲避能力的运动目标，智能搜索策略比巡逻策略整体表现更佳。当智能体数量大于1时，智能搜索策略较巡逻策略，平均搜索效率提升了48.5个百分点，且随着搜索者数量的增加，2种策略完成目标搜索的平均步数都呈下降趋势。

图7 运动目标搜索效率仿真校验

4 结束语

本文提出了一种在已知环境下搜索静态目标和具备躲避能力的动态目标的协同搜索策略。在该搜索策略中，地图信息的提取采用了拓扑地图，以较少的数据量表示环境信息。初始搜索策略采用随机搜索策略，通过Q-learning强化学习框架不断训练更新并基于节点空闲时间即时调整。目标的躲避策略参照路径规划和追捕问题中基于位置的人工势场法设计了基于动作的人工势场法。通过仿真校验，校验了动态目标躲避策略的有效性，并通过与现有多极子图巡逻策略的对比仿真，证明了对于静态目标，本文所提协同搜索策略与多级子图巡逻策略整体表现相近，而对于具备躲避决策能力的动态目标，本文所提协同搜索策略的搜索效率有较大提升。同时协同搜索策略解决了多级子图巡逻策略中单体故障会导致其辖区成为盲区的问题。后续将进行算法移植，开展实物验证实验，并针对优化目标躲避模型或增加环境信息复杂度等方向开展进一步研究。■