第16卷第3期 智能系统学报 Vol.16 No.3 2021年5月 CAAI Transactions on Intelligent Systems May 2021 D0:10.11992/tis.202009012 无人机群目标搜索的主动感知方法 楼传炜，葛泉波2，刘华平3，袁小虎 (1.上海海事大学物流工程学院，上海201306：2.同济大学电子与信息工程学院，上海201804：3.清华大学计 算机科学与技术系，北京100084：4.清华大学自动化系，北京100084) 摘要：为提升蚁群搜索算法在规模大的栅格环境中对未知目标的搜索效率.提出基于蚁群算法的主动感知搜 索框架。该框架通过应用历史环境信息来选择无人机的运动方式，并由无人机运动方式和感知域信息得到新 的环境信息，从而实现无人机群的智能自动化搜索功能。新方法计算出一种具有探索偏好的未搜索概率，可使 无人机搜索时偏向未搜索程度高的栅格，以此来提高算法的搜索能力。同时，以未搜索概率和信息素作为运动 方式决策的依据来建立一种新的运动方式选择机制。该机制不仅考虑了目标可能出现的区域，又可兼顾未知 区域，从而可实现无目标先验信息条件下的搜索过程。仿真结果表明，此算法在规模大的栅格环境中，与现有 算法相比具有更高的搜索效率，并且得到的目标分布信息将更加全面。 关键词：无人机：蚁群算法：无目标先验条件：具有探索偏好的搜索概率；主动感知搜索框架：未知区域：运动方 式选择机制：环境信息 中图分类号：TP393文献标志码：A文章编号：1673-4785(2021)03-0575-09 中文引用格式：楼传炜，葛泉波，刘华平，等.无人机群目标搜索的主动感知方法.智能系统学报，2021,16(3)：575-583. 英文引用格式：LOU Chuanwei,,GE Quanbo,LIU Huaping,etal.Active perception method for UAV group target searchJ.CAAI transactions on intelligent systems,2021,16(3):575-583. Active perception method for UAV group target search LOU Chuanwei',GE Quanbo',LIU Huaping',YUAN Xiaohu' (1.Logistics Engineering College,Shanghai Maritime University,Shanghai 201306,China;2.School of Electronics and Information Engineering,Tongji University,Shanghai 201804,China;3.Department of Computer Science and Technology,Tsinghua University, Beijing 100084,China;4.Department of Automation,Tsinghua University,Beijing 100084,China) Abstract:To enhance the search efficiency of the ant colony algorithm for unknown targets in a large-scale grid envir- onment,an active perception search framework based on the ant colony algorithm is proposed.In this framework,the unmanned aerial vehicle(UAV)motion mode was selected using the historical environment information.The new envir- onment information was obtained from the motion mode and sensing domain information of the UAV to enhance the in- telligent automatic search function of the UAV group.The new algorithm calculates an unsearched probability with ex- ploration preference to carry out a UAV search with a bias towards the grid with the highest unsearched degree,which improves the algorithm's searchability.Additionally,based on the unsearched probability and pheromone,a new mo- tion mode selection mechanism was developed.This mechanism considers the possible known and unknown target re- gions for searching targets with no prior information.The simulation results showed that this algorithm has higher search efficiency and more comprehensive target distribution information than the existing algorithms used in large- scale grid environments. Keywords:unmanned aerial vehicle;ant colony;without prior information of the target;an unsearched probability with exploration preference;active perception search framework;unknown region;motion mode selection mechanism;envir- onmental information 收稿日期：2020-09-10. 随着无人机技术的不断发展，无人机(unmanned 基金项目：国家自然科学基金项目(61773147，U1509203:浙江 省自然科学基金项目(LR17F030005). aerial vehicle,UAV)在军事、商业和农业等各个领 通信作者：刘华平.E-mail:hpliu@tsinghua.edu.cn 域中屡见不鲜，且多无人机系统较单架无人机具
DOI: 10.11992/tis.202009012 无人机群目标搜索的主动感知方法 楼传炜1 ，葛泉波2 ，刘华平3 ，袁小虎4 （1. 上海海事大学 物流工程学院，上海 201306; 2. 同济大学 电子与信息工程学院，上海 201804; 3. 清华大学 计 算机科学与技术系，北京 100084; 4. 清华大学 自动化系，北京 100084） 摘 要：为提升蚁群搜索算法在规模大的栅格环境中对未知目标的搜索效率，提出基于蚁群算法的主动感知搜 索框架。该框架通过应用历史环境信息来选择无人机的运动方式，并由无人机运动方式和感知域信息得到新 的环境信息，从而实现无人机群的智能自动化搜索功能。新方法计算出一种具有探索偏好的未搜索概率，可使 无人机搜索时偏向未搜索程度高的栅格，以此来提高算法的搜索能力。同时，以未搜索概率和信息素作为运动 方式决策的依据来建立一种新的运动方式选择机制。该机制不仅考虑了目标可能出现的区域，又可兼顾未知 区域，从而可实现无目标先验信息条件下的搜索过程。仿真结果表明，此算法在规模大的栅格环境中，与现有 算法相比具有更高的搜索效率，并且得到的目标分布信息将更加全面。 关键词：无人机；蚁群算法；无目标先验条件；具有探索偏好的搜索概率；主动感知搜索框架；未知区域；运动方 式选择机制；环境信息 中图分类号：TP393 文献标志码：A 文章编号：1673−4785(2021)03−0575−09 中文引用格式：楼传炜, 葛泉波, 刘华平, 等. 无人机群目标搜索的主动感知方法 [J]. 智能系统学报, 2021, 16(3): 575–583. 英文引用格式：LOU Chuanwei, GE Quanbo, LIU Huaping, et al. Active perception method for UAV group target search[J]. CAAI transactions on intelligent systems, 2021, 16(3): 575–583. Active perception method for UAV group target search LOU Chuanwei1 ，GE Quanbo2 ，LIU Huaping3 ，YUAN Xiaohu4 (1. Logistics Engineering College, Shanghai Maritime University, Shanghai 201306, China; 2. School of Electronics and Information Engineering, Tongji University, Shanghai 201804, China; 3. Department of Computer Science and Technology, Tsinghua University, Beijing 100084, China; 4. Department of Automation, Tsinghua University, Beijing 100084, China) Abstract: To enhance the search efficiency of the ant colony algorithm for unknown targets in a large-scale grid environment, an active perception search framework based on the ant colony algorithm is proposed. In this framework, the unmanned aerial vehicle (UAV) motion mode was selected using the historical environment information. The new environment information was obtained from the motion mode and sensing domain information of the UAV to enhance the intelligent automatic search function of the UAV group. The new algorithm calculates an unsearched probability with exploration preference to carry out a UAV search with a bias towards the grid with the highest unsearched degree, which improves the algorithm’s searchability. Additionally, based on the unsearched probability and pheromone, a new motion mode selection mechanism was developed. This mechanism considers the possible known and unknown target regions for searching targets with no prior information. The simulation results showed that this algorithm has higher search efficiency and more comprehensive target distribution information than the existing algorithms used in largescale grid environments. Keywords: unmanned aerial vehicle; ant colony; without prior information of the target; an unsearched probability with exploration preference; active perception search framework; unknown region; motion mode selection mechanism; environmental information 随着无人机技术的不断发展，无人机 (unmanned aerial vehicle，UAV) 在军事、商业和农业等各个领 域中屡见不鲜，且多无人机系统较单架无人机具 收稿日期：2020−09−10. 基金项目：国家自然科学基金项目 (61773147，U1509203)；浙江 省自然科学基金项目 (LR17F030005). 通信作者：刘华平. E-mail：hpliu@tsinghua.edu.cn. 第 16 卷第 3 期 智 能 系 统 学 报 Vol.16 No.3 2021 年 5 月 CAAI Transactions on Intelligent Systems May 2021
·576· 智能系统学报 第16卷 有更好的容错性和鲁棒性，在目标搜索以及路径 索偏好的刺激概率，构建了无人机运动方式选择 规划方面有着广泛应用，其中无人机路径规划 机制，设计了环境信息的更替方式，最后进行了 问题常用蚁群算法优化解决，已有学者在环境已 仿真验证。 知的基础上研究了二维平面81以及三维空间川 上的路径规划方法，文献[12]在TSP问题中利用 1问题描述 负信息素实现搜索的多样化，有效减少了遍历城 本文设定n架无人机在环境I下协同搜索未 市的时间。文献[13】提出一种求解凸优化子问题 知动态目标，每架UAV独立感知环境并将信息 的定制内点法来提高多无人机协同轨迹规划效 存入环境栅格中与其他UAV交互，将存储的目 率。文献[14]基于蚁群协调方式，提出了基于仿 标信息整合并更新，获取系统更新后的信息，通 生集群算法的无人机集群分布式目标搜索模型。 过运动方式选择机制决策下一步的动向，从而有 在此类问题研究中，搜索目标的位置是已知的， 效地搜索目标。为有效开展搜索工作，UAV只对 而无人机群搜索任务主要是对不确定的或动态的 高浓度信息素区域的和未搜索区域感兴趣。 目标的搜索，因此上述蚁群算法不能解决目标 11环境描述 位置未知的问题。 本文用I,×L的栅格来表征环境L,如图1所示。 为了解决未知目标问题，文献[16]利用基于 信息素的修正蚁群算法完成了对未知目标的搜 索，然而由于此算法存在禁忌表，在规模较大的 环境中只有一定感知能力的蚂蚁很难完全地根据 908 步长遍历环境，因此局限于规模较小的环境，且 启发函数在栅格环境下并不适用。文献[17] 根据同构无人机的数目对矩形搜索区域分割，将多UAV 搜索转化为单个UAV的区域遍历搜索，以此实 图1搜索环境 现地图的全覆盖搜索。在实际搜索中，UAV与目 Fig.1 Search environment 标到达同一区域时难免有时差，也会给搜索任务 每架UAV占据一个栅格，其单步可行域是与 带来挑战，对此，文献[18]用概率函数来描述目 自身所在栅格的相邻8个栅格，运动步长为1格， 标模型，对每个栅格进行目标概率的更新，概率 且都装载了可以探测到目标的传感器，设其感知 越高则表示目标存在几率越高，有效实现了复杂 范围为r,考虑到无人机的物理结构限制，设其最 环境中无人机群对未知目标的搜索。 大偏航角0为90°。 主动感知是无人机在搜索目标时通过选择其 UAVs的位置坐标可认为是所在栅格的中心 运动方式，增加在外部环境中通过传感器获得的 节点坐标，根据栅格序号与坐标转换公式，计算 信息。在主动感知的概念中，行动与知觉密不可 其准确的坐标(xy): 分，良好的知觉对无人机的搜索任务至关重要， ∫x=a(mod(j,MM0-0.5) 因此在现实世界中实时操作时，可通过行动来帮 y=a(MM+0.5-ceil(j/MM)) 助它们感知，以获取更为完善的环境信息。 式中：a为单个栅格边长；MM=I,=I,表示横 为了优化蚁群搜索算法，使之适用于规模较 (纵)坐标的最大栅格数；j表示栅格序号；mod() 大的栅格环境，本文基于主动感知，结合UAV运 和ceil()分别为取余运算和舍余取整运算。 动与栅格对应关系以及目标概率函数提出无人机 假设1任意两架无人机相差一定的飞行高 群目标搜索的主动感知方法。新方法的搜索机制 度且各无人机飞行高度固定，在同一栅格出现时 保留了信息素对UAV的引导作用，本文提出了 不会发生碰撞。 具有探索偏好的未搜索概率，优化了状态转移概 假设2无人机不受人为操控，仅通过算法 率计算方法，使无人机偏向未搜索的区域，减少 进行控制。 自锁出现的几率，并通过改变目标概率函数中的 1.2目标描述 参数实现了搜索环境的信息更替。 本文设定3个运动轨迹不同的目标，假设目 本文首先描述了研究问题，包括环境、无人 标各有其运动规律且相互独立。目标不具备探 机、目标以及研究动机，然后结合主动感知框架， 索UAV的能力，若目标在冲出搜索区域前未被 对无人机的运动进行了设定，以此提出了具有探 探测到，则视为搜索失败
有更好的容错性和鲁棒性，在目标搜索以及路径 规划方面有着广泛应用[1-6] ，其中无人机路径规划 问题常用蚁群算法优化解决，已有学者在环境已 知的基础上研究了二维平面[7-8] 以及三维空间[9-11] 上的路径规划方法，文献 [12] 在 TSP 问题中利用 负信息素实现搜索的多样化，有效减少了遍历城 市的时间。文献 [13] 提出一种求解凸优化子问题 的定制内点法来提高多无人机协同轨迹规划效 率。文献 [14] 基于蚁群协调方式，提出了基于仿 生集群算法的无人机集群分布式目标搜索模型。 在此类问题研究中，搜索目标的位置是已知的， 而无人机群搜索任务主要是对不确定的或动态的 目标的搜索[15] ，因此上述蚁群算法不能解决目标 位置未知的问题[16]。 为了解决未知目标问题，文献 [16] 利用基于 信息素的修正蚁群算法完成了对未知目标的搜 索，然而由于此算法存在禁忌表，在规模较大的 环境中只有一定感知能力的蚂蚁很难完全地根据 步长遍历环境，因此局限于规模较小的环境，且 启发函数在栅格环境下并不适用。文献 [17] 根据同构无人机的数目对矩形搜索区域分割，将多UAV 搜索转化为单个 UAV 的区域遍历搜索，以此实 现地图的全覆盖搜索。在实际搜索中，UAV 与目 标到达同一区域时难免有时差，也会给搜索任务 带来挑战，对此，文献 [18] 用概率函数来描述目 标模型，对每个栅格进行目标概率的更新，概率 越高则表示目标存在几率越高，有效实现了复杂 环境中无人机群对未知目标的搜索。 主动感知是无人机在搜索目标时通过选择其 运动方式，增加在外部环境中通过传感器获得的 信息。在主动感知的概念中，行动与知觉密不可 分，良好的知觉对无人机的搜索任务至关重要， 因此在现实世界中实时操作时，可通过行动来帮 助它们感知，以获取更为完善的环境信息[19]。 为了优化蚁群搜索算法，使之适用于规模较 大的栅格环境，本文基于主动感知，结合 UAV 运 动与栅格对应关系以及目标概率函数提出无人机 群目标搜索的主动感知方法。新方法的搜索机制 保留了信息素对 UAV 的引导作用，本文提出了 具有探索偏好的未搜索概率，优化了状态转移概 率计算方法，使无人机偏向未搜索的区域，减少 自锁出现的几率，并通过改变目标概率函数中的 参数实现了搜索环境的信息更替。 本文首先描述了研究问题，包括环境、无人 机、目标以及研究动机，然后结合主动感知框架， 对无人机的运动进行了设定，以此提出了具有探 索偏好的刺激概率，构建了无人机运动方式选择 机制，设计了环境信息的更替方式，最后进行了 仿真验证。 1 问题描述 本文设定 n 架无人机在环境 I 下协同搜索未 知动态目标，每架 UAV 独立感知环境并将信息 存入环境栅格中与其他 UAV 交互，将存储的目 标信息整合并更新，获取系统更新后的信息，通 过运动方式选择机制决策下一步的动向，从而有 效地搜索目标。为有效开展搜索工作，UAV 只对 高浓度信息素区域的和未搜索区域感兴趣。 1.1 环境描述 本文用 Ix×Iy 的栅格来表征环境 I，如图 1 所示。 Iy Ix 90° 图 1 搜索环境 Fig. 1 Search environment 每架 UAV 占据一个栅格，其单步可行域是与 自身所在栅格的相邻 8 个栅格，运动步长为 1 格， 且都装载了可以探测到目标的传感器，设其感知 范围为 r，考虑到无人机的物理结构限制，设其最 大偏航角 θ 为 90°。 UAVs 的位置坐标可认为是所在栅格的中心 节点坐标，根据栅格序号与坐标转换公式，计算 其准确的坐标 (x,y)： { x = a(mod (j,MM)−0.5) y = a(MM+0.5−ceil(j/MM)) 式中： a 为单个栅格边长； MM=I x=I y，表示 横 (纵) 坐标的最大栅格数；j 表示栅格序号；mod(·) 和 ceil(·) 分别为取余运算和舍余取整运算。 假设 1 任意两架无人机相差一定的飞行高 度且各无人机飞行高度固定，在同一栅格出现时 不会发生碰撞。 假设 2 无人机不受人为操控，仅通过算法 进行控制。 1.2 目标描述 本文设定 3 个运动轨迹不同的目标，假设目 标各有其运动规律且相互独立。目标不具备探 索 UAV 的能力，若目标在冲出搜索区域前未被 探测到，则视为搜索失败。 ·576· 智 能 系 统 学 报 第 16 卷
第3期 楼传炜，等：无人机群目标搜索的主动感知方法 ·577· 根据文献[18]的方法，用栅格对环境划分 于历史环境信息选择的运动方式；X(1-1)和X() 后，当未知环境下的多无人机协同搜索目标时， 表示无人机相邻时刻的运动状态，根据蚂蚁觅食 目标状态的不确定性使搜索过程被简化为一个概 的仿生机理选择不同的运动方式，运动状态表达 率问题，每一个栅格都用概率密度x,y,σ)表示目 式为 标存在的可能性，公式为 X(0)=[x(①)，y(),v(),c 1 式中：x、y表示无人机坐标；v表示无人机的速 度；c表示无人机是否捕获到目标，c=1时表示捕 式中：x和y的坐标相互独立且均相对于一个栅 获到目标，反之表示没有捕获到目标。无人机感 格而言，以栅格中心为原点建立横纵坐标，坐标 知域信息S()由运动方式和运动状态决定，感知 范围均为[-0.5a,0.5a:为标准差，如图2所示。 域信息表达式为 S(t)=[r(),T(t0),s(] 式中：T为所有无人机已搜索过的栅格序号集合： s为无人机可选的运动方式集合；π为信息素。无 人机通过综合考虑信息素浓度、栅格访问情况和 可选的运动方式进行搜索，得到新的环境信息。 05 0 格 -0.5-0.5 0格 (I H() 图2目标分布 Fig.2 Target distribution 1.3研究动机 为提升蚁群搜索算法对规模较大的栅格环境 A() S(1) 的适应力，本文结合主动感知里运动与感知相结 合的特性，提出基于蚁群算法的主动感知搜索框 架，使无人机实现根据环境信息选择运动方向的 功能。在搜索过程中，由于启发函数只与相邻节 什+ Y(-1) X(1) 点间距离有关，文献[16]中蚁群的决策机制并不 能随着周围环境的变化而提高引导性能。本文在 决策机制的基础上融入了栅格访问值，提出具有 图3主动感知搜索框架 探索偏好的未搜索概率，使得无人机探索的兴趣 Fig.3 Active perception search framework 随栅格访问值的增大而提高，将刺激概率与表征 无人机飞行高度一定的条件下，飞机通过调 目标热点的信息素相结合，得到无人机运动方式 整偏航、俯仰和滚转姿态，固定翼产生的合力会 选择机制。在这种机制下，无人机会综合考虑目 对飞机产生左前进、前进、右前进、左后退、右后退、 标高概率出现区域和未探索区域，与仅通过信息 后退、左移和右移这8个方向的运动，如图4所示。 素来搜索的这种机制相比更具目标针对性和环境 的探索性。此外，为了将无人机搜索结果与信息 素更新有机结合，本文将目标存在概率作为信息 素更新的量的尺度，通过改变标准差调节尺度大 小，实现了环境信息的更替。 2主动感知搜索框架 本文基于蚁群搜索算法提出了UAVs主动感 知搜索框架，如图3所示。 图3中H(1-1)和H()分别代表相邻时刻的 历史环境信息，此信息由目标出现概率和蚂蚁的 信息素表示，目标出现概率的更新与信息素的释 图4无人机运动方式 放和挥发表示环境信息的变化；A()为无人机基 Fig.4 UAV motion mode
根据文献 [18] 的方法，用栅格对环境划分 后，当未知环境下的多无人机协同搜索目标时， 目标状态的不确定性使搜索过程被简化为一个概 率问题，每一个栅格都用概率密度 f(x,y,σ) 表示目 标存在的可能性，公式为 f (x, y,σ) = 1 2πσ exp( − ( x 2 +y 2 2σ2 )) 式中：x 和 y 的坐标相互独立且均相对于一个栅 格而言，以栅格中心为原点建立横纵坐标，坐标 范围均为 [−0.5a,0.5a]；σ 为标准差，如图 2 所示。 3 2 1 0 0.5 0.5 0 0 y/格 −0.5 −0.5 z/格 x/格 图 2 目标分布 Fig. 2 Target distribution 1.3 研究动机 为提升蚁群搜索算法对规模较大的栅格环境 的适应力，本文结合主动感知里运动与感知相结 合的特性，提出基于蚁群算法的主动感知搜索框 架，使无人机实现根据环境信息选择运动方向的 功能。在搜索过程中，由于启发函数只与相邻节 点间距离有关，文献 [16] 中蚁群的决策机制并不 能随着周围环境的变化而提高引导性能。本文在 决策机制的基础上融入了栅格访问值，提出具有 探索偏好的未搜索概率，使得无人机探索的兴趣 随栅格访问值的增大而提高，将刺激概率与表征 目标热点的信息素相结合，得到无人机运动方式 选择机制。在这种机制下，无人机会综合考虑目 标高概率出现区域和未探索区域，与仅通过信息 素来搜索的这种机制相比更具目标针对性和环境 的探索性。此外，为了将无人机搜索结果与信息 素更新有机结合，本文将目标存在概率作为信息 素更新的量的尺度，通过改变标准差调节尺度大 小，实现了环境信息的更替。 2 主动感知搜索框架 本文基于蚁群搜索算法提出了 UAVs 主动感 知搜索框架，如图 3 所示。 图 3 中 H(t－1) 和 H(t) 分别代表相邻时刻的 历史环境信息，此信息由目标出现概率和蚂蚁的 信息素表示，目标出现概率的更新与信息素的释 放和挥发表示环境信息的变化；A(t) 为无人机基 于历史环境信息选择的运动方式；X(t－1) 和 X(t) 表示无人机相邻时刻的运动状态，根据蚂蚁觅食 的仿生机理选择不同的运动方式，运动状态表达 式为 X (t) = [ x (t), y (t), v (t), c ] 式中：x、y 表示无人机坐标；v 表示无人机的速 度；c 表示无人机是否捕获到目标，c=1 时表示捕 获到目标，反之表示没有捕获到目标。无人机感 知域信息 S(t) 由运动方式和运动状态决定，感知 域信息表达式为 S (t) = [τ(t),T (t),s(t)] 式中：T 为所有无人机已搜索过的栅格序号集合； s 为无人机可选的运动方式集合；τ 为信息素。无 人机通过综合考虑信息素浓度、栅格访问情况和 可选的运动方式进行搜索，得到新的环境信息。 H (t−1) X (t−1) A (t) S (t) H (t) X (t) t++ t++ 图 3 主动感知搜索框架 Fig. 3 Active perception search framework 无人机飞行高度一定的条件下，飞机通过调 整偏航、俯仰和滚转姿态，固定翼产生的合力会 对飞机产生左前进、前进、右前进、左后退、右后退、 后退、左移和右移这 8 个方向的运动，如图 4 所示。 图 4 无人机运动方式 Fig. 4 UAV motion mode 第 3 期 楼传炜，等：无人机群目标搜索的主动感知方法 ·577·
·578· 智能系统学报 第16卷 由于无人机在飞行过程中受物理结构限制， 状态下，各可选运动方式的未搜索概率(unsearch- 偏航运动能力比俯仰、滚转运动能力弱，因此在偏 able probability,UP),此概率表示不同运动方式对 航运动中更容易出现执行器饱和20。鉴于上述考 无人机的吸引程度。UP的计算过程如下： 虑，参考文献[21]，本文为无人机设定了一个90 1)统计各运动方式下的栅格访问值 的最大偏航角，最大偏航角定义为上一时刻无人 由于无人机运动步长为1格，无人机各运动 机运动方向与此刻运动方向所夹的最大角度。如方式下对应的栅格即为当前栅格的相邻栅格，因 图5所示，本文设定无人机的运动步长为栅格地 此需要对任意两栅格之间设定一个访问权限，以 图的1个栅格长度，在设定下，无人机每次选择运 此限定无人机的运动步长。无向图的邻接矩阵 动方式时，最多考虑5个运动方向(4个角落只有 第i行（或第i列）中的非零元素为第i个栅格的 3个运动方向)，且实现掉头所需的最小转弯半径 度，刚好对应此栅格的相邻栅格，因此本文采用 r为0.5格。 无向图的邻接矩阵（以下简称为邻接矩阵）建立 相邻栅格的连接。 无人机每到达一个栅格，系统会更改该栅格 的访问状态，记录在mark中，无人机当前时刻各 运动方式的栅格访问值统计通过邻接矩阵锁定可 访问栅格，并统计对应mark中非零的数量，即为 栅格访问值，统计过程如下： ①按先上后下，先左后右的顺序对各运动方 式对应的栅格进行排序； 图5最大偏航角下无人机的运动 Fig.5 Motion of UAV under the maximum yaw angle ②按顺序选择一个栅格： ③根据此栅格的序号，通过邻接矩阵锁定相 搜索过程中，无人机根据最大偏航角得到初 步的运动方式可选集合，结合T得到最终的可选 邻栅格： 方式集合，避免出现重复搜索现象。无人机综合 ④统计这些相邻栅格储存的mark值； 信息素的浓度变化以及环境的探索程度两个因 ⑤通过累加的方法计算得到该运动方式对应 素，实现互相的配合。在一次迭代中，无人机偏 的栅格访问值。 ⑥重复步骤②~⑤，直至完成所有栅格访问值 好于探索未搜索的区域，从而达到各无人机分散 的统计。 搜索的效果，且在搜索过程中根据是否捕获目标 2)统计各运动方式下的未搜索概率 来选择释放或挥发信息素，以此改变信息素浓 某一运动方式下的未搜索概率表示无人机对 度，进而使各区域的信息素浓度产生差异。在下 该运动方式的倾向程度，文献[20]为无人机避障 一次迭代中，高浓度的信息素对附近无人机起引 提出了基于排列组合的刺激概率(stimulate prob- 导作用，低浓度的信息素起相反效果，从而使得 ability,SP)引导方法，本文在机器人运动方式的 无人机对目标分布可能性高的区域加强搜索。 选择过程中采用并改进了此方法。在排列组合 3具有探索偏好的未搜索概率 中，具有探索偏好的未搜索概率(unsearchable probability with exploring preferences,UPEP) 在完成上述运动方向的限制后，根据主动感 作已经在可选运动方式集合里选择某一运动方式 知框架，算法需要一定的机制来抉择出无人机最 (此方式对应的栅格未被访问)的条件下，在包含 感兴趣的区域所对应的运动方式，蚁群算法中作 所有未被访问栅格对应的运动方式集合中，选择 为核心函数之一的启发函数是蚂蚁当前位置与下 其中一个运动方式的概率，计算方式为 一位置坐标差欧氏距离的倒数。在栅格地图环境 下，相邻位置间的距离并不相等，因此所有运动 UPEP;;=Normalize 方式下函数值仅有2种值，存在一定的错误导向 式中：i表示无人机序号；为无人机所在栅格序 性。文献[22]采用强化最优解的引导作用、减小 号；mark为栅格j的栅格访问值；Normalize()为 最差解路径上的信息素来加快算法的收敛速度， 归一化函数，其值为数组元素除以数组中最大值 但是降低了算法的探索能力。基于上述问题，本 与最小值和的商。图6为刺激概率SP和UP 文借鉴文献[20]中的避障机制，计算无人机当前 EP随栅格访问值变化的特性曲线对比图
由于无人机在飞行过程中受物理结构限制， 偏航运动能力比俯仰、滚转运动能力弱,因此在偏 航运动中更容易出现执行器饱和[20]。鉴于上述考 虑，参考文献 [21]，本文为无人机设定了一个 90° 的最大偏航角，最大偏航角定义为上一时刻无人 机运动方向与此刻运动方向所夹的最大角度。如 图 5 所示，本文设定无人机的运动步长为栅格地 图的 1 个栅格长度，在设定下，无人机每次选择运 动方式时，最多考虑 5 个运动方向 (4 个角落只有 3 个运动方向)，且实现掉头所需的最小转弯半径 r 为 0.5 格。 图 5 最大偏航角下无人机的运动 Fig. 5 Motion of UAV under the maximum yaw angle 搜索过程中，无人机根据最大偏航角得到初 步的运动方式可选集合，结合 T 得到最终的可选 方式集合，避免出现重复搜索现象。无人机综合 信息素的浓度变化以及环境的探索程度两个因 素，实现互相的配合。在一次迭代中，无人机偏 好于探索未搜索的区域，从而达到各无人机分散 搜索的效果，且在搜索过程中根据是否捕获目标 来选择释放或挥发信息素，以此改变信息素浓 度，进而使各区域的信息素浓度产生差异。在下 一次迭代中，高浓度的信息素对附近无人机起引 导作用，低浓度的信息素起相反效果，从而使得 无人机对目标分布可能性高的区域加强搜索。 3 具有探索偏好的未搜索概率 在完成上述运动方向的限制后，根据主动感 知框架，算法需要一定的机制来抉择出无人机最 感兴趣的区域所对应的运动方式，蚁群算法中作 为核心函数之一的启发函数是蚂蚁当前位置与下 一位置坐标差欧氏距离的倒数。在栅格地图环境 下，相邻位置间的距离并不相等，因此所有运动 方式下函数值仅有 2 种值，存在一定的错误导向 性。文献 [22] 采用强化最优解的引导作用、减小 最差解路径上的信息素来加快算法的收敛速度， 但是降低了算法的探索能力。基于上述问题，本 文借鉴文献 [20] 中的避障机制，计算无人机当前 状态下，各可选运动方式的未搜索概率 (unsearchable probability，UP)，此概率表示不同运动方式对 无人机的吸引程度。UP 的计算过程如下： 1) 统计各运动方式下的栅格访问值 由于无人机运动步长为 1 格，无人机各运动 方式下对应的栅格即为当前栅格的相邻栅格，因 此需要对任意两栅格之间设定一个访问权限，以 此限定无人机的运动步长。无向图的邻接矩阵 第 i 行 (或第 i 列) 中的非零元素为第 i 个栅格的 度，刚好对应此栅格的相邻栅格，因此本文采用 无向图的邻接矩阵 (以下简称为邻接矩阵) 建立 相邻栅格的连接。 无人机每到达一个栅格，系统会更改该栅格 的访问状态，记录在 mark 中，无人机当前时刻各 运动方式的栅格访问值统计通过邻接矩阵锁定可 访问栅格，并统计对应 mark 中非零的数量，即为 栅格访问值，统计过程如下： ①按先上后下，先左后右的顺序对各运动方 式对应的栅格进行排序； ②按顺序选择一个栅格； ③根据此栅格的序号，通过邻接矩阵锁定相 邻栅格； ④统计这些相邻栅格储存的 mark 值； ⑤通过累加的方法计算得到该运动方式对应 的栅格访问值。 ⑥重复步骤②~⑤，直至完成所有栅格访问值 的统计。 2) 统计各运动方式下的未搜索概率 某一运动方式下的未搜索概率表示无人机对 该运动方式的倾向程度，文献 [20] 为无人机避障 提出了基于排列组合的刺激概率 (stimulate probability，SP) 引导方法，本文在机器人运动方式的 选择过程中采用并改进了此方法。在排列组合 中，具有探索偏好的未搜索概率 (unsearchable probability with exploring preferences，UPEP) 可看 作已经在可选运动方式集合里选择某一运动方式 （此方式对应的栅格未被访问）的条件下，在包含 所有未被访问栅格对应的运动方式集合中，选择 其中一个运动方式的概率，计算方式为 UPEPi j = Normalize markj C 1 markj C markj L 式中：i 表示无人机序号；j 为无人机所在栅格序 号；markj 为栅格 j 的栅格访问值；Normalize(·) 为 归一化函数，其值为数组元素除以数组中最大值 与最小值和的商。图 6 为刺激概率 SP 和 UPEP 随栅格访问值变化的特性曲线对比图。 ·578· 智 能 系 统 学 报 第 16 卷
第3期 楼传炜，等：无人机群目标搜索的主动感知方法 ·579· 1.0 -文献20] 1.0 0.8 -UPEP 0.8 三0.6 0.4 0.4 03 0.2 0 3 4 56 0 0.20.40.60.81.01.2 栅格访问值 图6SP和UPEP特性曲线对比 图8Pb曲线 Fig.6 Comparison of SP and UPEP characteristic curves Fig.8 Pob curve 由图6可见，UPEP随栅格访问值的升高而升 高，栅格访问值越高，未搜索概率越大，无人机对 5环境信息的更替 此栅格就越有兴趣探索；文献[20]的刺激概率 无人机根据历史环境信息选择了运动方式并 SP曲线中在栅格访问值为2、3、4和5时，其刺激 更新了状态后，需要对其所在栅格以及路径进行 概率均小于栅格访问值等于1时的刺激概率，在 信息更新，形成新的环境信息，因此环境信息分 [1,5]区间内，刺激概率并不具有单调递增性。 目标出现概率Pb和吸引无人机的信息素τ。P 4无人机运动方式选择机制 表示在一定的搜索后，相应栅格中目标出现的概 率，并用热力图的形式将其可视化；无人机上一时 无人机选择运动方式时不能仅对未搜索区域 刻的路径信息由τ表示，由于对信息素的依赖性， 感兴趣，在搜索过的区域中极有可能有与目标相 τ值的高低会直接影响无人机运动方式的选择。 关的历史环境信息，本文基于蚁群算法的状态转 以上2种环境信息皆由当前时刻的无人机目 移概率，将上节的UPEP与信息素相结合，得到各 标捕获状态c决定，信息增量表达式为 运动方式的评价指标P,计算公式为 4g=-30a,c=1 Pu(0=- [i(t)]upij p,c≠1 (1) ∑[rarp. (2) seallowed c-lo dsr 式中：i表示无人机序号；j为无人机所在栅格序 式中：P为信息素挥发因子，作为无人机状态衰减 号；allowed为第i架无人机的第j种运动方式； 值；d表示无人机与目标的欧氏距离；r为无人机 s为这些运动方式的序号；a为信息素重要因子； 感知域半径。由式(2)可见，当d心r时，c=0,即无 1为时间。式(1)会根据未搜索概率对信息素进行 人机捕获目标失败，△σ设定为衰减值，反之，设 衰减，概率越小，衰减越多，计算所得的状态转移 定为增长值，且增长值与衰减值之比为30：1。 概率即为无人机各运动方式选择概率。 5.1目标发现概率 无人机在选择运动方式时只看概率高低会导 某一栅格中目标出现概率为对应概率密度函 致搜索的局部最优，丧失广泛性，因此本文采用 数的双重定积分，即 累积和函数cumsum(~),形成幸运轮盘，图7为轮 盘展开示意图。 y.ndids 根据1.3节的目标描述，在栅格边长不变的 0.52 条件下，目标概率密度函数的自变量只有σ，由 图8可知σ与Pb呈反比趋势。 20% 8% 32% 18% 22% 因此，可以通过改变σ的方式达到调节P的 运动1 运动2 运动3 运动4 运动5 目的。σ的更新方式为 图7轮盘展开示意图 c(t)=c(t-1)+0.05△g Fig.7 Diagram of the roulette's expansion 5.2信息素更新方式 由图8可见，各运动方式根据式(1)计算所得 蚁群算法的信息素用于储存路径信息，并非 概率越高，在此轮盘中所占面积越大；采用随机 存储在栅格中，因此σ无法与信息素对应。无向 函数rand()作为指针并认为此函数产生的伪随 图的邻接矩阵除了建立栅格联系，还可以将矩阵 机数足够接近真正的随机数。如产生的随机数 内的数值细化表征所建联系的强弱，本文以此来 为0.52，则无人机选中第3种运动方式。 进行信息素的更新
1.0 0.8 0.6 0.4 0.2 0 1 2 3 4 5 7 6 栅格访问值 函数值 文献[20] UPEP 图 6 SP 和 UPEP 特性曲线对比 Fig. 6 Comparison of SP and UPEP characteristic curves 由图 6 可见，UPEP 随栅格访问值的升高而升 高，栅格访问值越高，未搜索概率越大，无人机对 此栅格就越有兴趣探索；文献 [20] 的刺激概率 SP 曲线中在栅格访问值为 2、3、4 和 5 时，其刺激 概率均小于栅格访问值等于 1 时的刺激概率，在 [1,5] 区间内，刺激概率并不具有单调递增性。 4 无人机运动方式选择机制 无人机选择运动方式时不能仅对未搜索区域 感兴趣，在搜索过的区域中极有可能有与目标相 关的历史环境信息，本文基于蚁群算法的状态转 移概率，将上节的 UPEP 与信息素相结合，得到各 运动方式的评价指标 P，计算公式为 Pi j(t) = [ τi j(t) ]α ∑ · upi j s∈allowedj [τis (t)] α · upis (1) 式中：i 表示无人机序号；j 为无人机所在栅格序 号；allowedj 为第 i 架无人机的第 j 种运动方式； s 为这些运动方式的序号；α 为信息素重要因子； t 为时间。式 (1) 会根据未搜索概率对信息素进行 衰减，概率越小，衰减越多，计算所得的状态转移 概率即为无人机各运动方式选择概率。 无人机在选择运动方式时只看概率高低会导 致搜索的局部最优，丧失广泛性，因此本文采用 累积和函数 cumsum(·)，形成幸运轮盘，图 7 为轮 盘展开示意图。 0.52 20% 8% 32% 18% 22% 运动 1 运动 2 运动 3 运动 4 运动 5 图 7 轮盘展开示意图 Fig. 7 Diagram of the roulette’s expansion 由图 8 可见，各运动方式根据式 (1) 计算所得 概率越高，在此轮盘中所占面积越大；采用随机 函数 rand(·) 作为指针并认为此函数产生的伪随 机数足够接近真正的随机数。如产生的随机数 为 0.52，则无人机选中第 3 种运动方式。 1.0 0.8 0.6 0.4 0.2 0 0.2 0.4 0.6 0.8 1.2 1.0 σ Pob/% 图 8 Pob 曲线 Fig. 8 Pob curve 5 环境信息的更替 无人机根据历史环境信息选择了运动方式并 更新了状态后，需要对其所在栅格以及路径进行 信息更新，形成新的环境信息，因此环境信息分 目标出现概率 Pob 和吸引无人机的信息素 τ。Pob 表示在一定的搜索后，相应栅格中目标出现的概 率，并用热力图的形式将其可视化；无人机上一时 刻的路径信息由 τ 表示，由于对信息素的依赖性， τ 值的高低会直接影响无人机运动方式的选择。 以上 2 种环境信息皆由当前时刻的无人机目 标捕获状态 c 决定，信息增量表达式为 ∆σ = { −30ρ, c = 1 ρ, c , 1 c = { 1, d ⩽ r 0, d > r (2) ∆σ 式中：ρ 为信息素挥发因子，作为无人机状态衰减 值；d 表示无人机与目标的欧氏距离；r 为无人机 感知域半径。由式 (2) 可见，当 d>r 时，c=0，即无 人机捕获目标失败， 设定为衰减值，反之，设 定为增长值，且增长值与衰减值之比为 30∶1。 5.1 目标发现概率 某一栅格中目标出现概率为对应概率密度函 数的双重定积分，即 Pob = w 0.5a −0.5a w 0.5a −0.5a f (x, y,σ)dxdy 根据 1.3 节的目标描述，在栅格边长不变的 条件下，目标概率密度函数的自变量只有 σ，由 图 8 可知 σ 与 Pob 呈反比趋势。 因此，可以通过改变 σ 的方式达到调节 Pob 的 目的。σ 的更新方式为 σ(t) = σ(t−1)+0.05∆σ 5.2 信息素更新方式 蚁群算法的信息素用于储存路径信息，并非 存储在栅格中，因此 σ 无法与信息素对应。无向 图的邻接矩阵除了建立栅格联系，还可以将矩阵 内的数值细化表征所建联系的强弱，本文以此来 进行信息素的更新。 第 3 期 楼传炜，等：无人机群目标搜索的主动感知方法 ·579·
·580· 智能系统学报 第16卷 信息素更新的目的是使得较优路径上的信息 婪搜索由于贪婪思想，多架无人机均选择了相同 素增加，同时根据挥发因子p(0<p<1)的值模拟一 的路径，容易导致局部最优。本文就无人机群航 种挥发的方式削弱较差路径上的信息素，避免信 迹覆盖率、地图高亮区域和目标捕获点的分布规 息素的无限累积，出现局部解1。路径上的信息 律3个指标对这4种算法进行了比对分析，其中 素更新为 航迹覆盖率对比如图11所示。 (j.5)=.Pob (3) 开始 式中：j为栅格序号；为邻接矩阵中第j行中的 所在列；1为当前时刻。式(3)仅仅更新无人机上 初始化参数 一时刻到当前时刻的路径，σ的正负分别对应信 n,a、iter、t、 息素的产生和挥发，式(3)的挥发是系统根据无 p、MM、、i 人机的搜索状况而进行的，实际环境中，信息素 发现 目标 作为昆虫的外激素也会因为温度等环境因素而自 计算 然挥发，为了构建环境的真实性以及避免过度地 f(x,y,) -0p 局部搜索，需要进行全局更新： 信息增量△d =-1(1-p) (4) 方向限定 式中p为信息素挥发因子。 更新fx,八列 计算UPEP 6仿真实验 更新t 本文仿真环境为Windows10系统，电脑配置 计算P 为i5-8300H/1050Ti,本次仿真在Matlab R2014b版 K<n 轮盘赌法 本中进行。仿真场景设置如表1所示。 选择节点 表1仿真场景参数设置汇总表 Table 1 Summary of simulation scenario parameter setting 将所选节点 放入禁忌表 环境 无人机 仿真时长 目标 MM=37 n:10架 单次步数k:60/次 0初值=0.6 结束 a=1 v:1步/格 迭代数iter:30次 图9本文算法流程 初值=100 =2 Fig.9 Algorithm flow chart of this paper p=0.1 0=909 文献[16]中对环境进行节点建模，节点个数 为32个，为了对比大环境中本文算法的有效性， 实验设置了1369个节点的栅格环境。基于上述 (a)贪婪搜索方法 b)随机搜索方法 场景，为了能够比较算法的优劣性，需要进行多 角度、长时间迭代的对比分析，本文仿真对比了基 于贪婪思想的搜索方法、随机搜索方法、文献[16) 的搜索方法和本文的搜索方法。贪婪搜索方法是 在运动方向中选择信息素浓度最高的方向；随机 搜索方法则是没有任何决策机制，随机选择运动 (c)本文搜索方法 (d)文献[16搜索方法 方向22。图9为本文算法的流程。 图104类算法的可视化界面 图10所示为基于贪婪、随机、本文搜索方法以 Fig.10 Visual interface of four algorithms 及文献[16]搜索方法运行结束后的可视化界面。 如图11所示，本文的搜索算法的航迹覆盖率 图10中的4幅图均为各自算法最后一次迭 均值达到80%左右，仅以此结果来看，本文搜索 代下的热力图和无人机群航迹图。结果表明，主 的效果比较可观，文献[16]搜索算法的覆盖率仅 动搜索和随机搜索与贪婪搜索相比，其目标的捕 有52.3%，以此可以表明本文所提算法相较于文 捉率高，捕捉范围广：且主动算法的搜索覆盖最 献[16)更适用于较大的环境。然而动态目标相对 广，随机搜索容易围绕在出生点附近，所以其捕 于无人机群体具有时间和空间的不确定性，因此 获目标的效率很大程度取决于出生点的好坏，贪 实验中用热力图中高亮区域的数量来表征算法中
信息素更新的目的是使得较优路径上的信息 素增加，同时根据挥发因子 ρ(0<ρ<1) 的值模拟一 种挥发的方式削弱较差路径上的信息素，避免信 息素的无限累积，出现局部解[23]。路径上的信息 素更新为 τ t ( j, ξj ) = τ t · P t ob (3) 式中：j 为栅格序号；ξj 为邻接矩阵中第 j 行中的 所在列；t 为当前时刻。式 (3) 仅仅更新无人机上 一时刻到当前时刻的路径，σ 的正负分别对应信 息素的产生和挥发，式 (3) 的挥发是系统根据无 人机的搜索状况而进行的，实际环境中，信息素 作为昆虫的外激素也会因为温度等环境因素而自 然挥发，为了构建环境的真实性以及避免过度地 局部搜索，需要进行全局更新： τ t = τ t−1 ·(1−ρ) (4) 式中 ρ 为信息素挥发因子。 6 仿真实验 本文仿真环境为 Windows 10 系统，电脑配置 为 i5-8300H/1050Ti，本次仿真在 Matlab R2014b 版 本中进行。仿真场景设置如表 1 所示。 表 1 仿真场景参数设置汇总表 Table 1 Summary of simulation scenario parameter setting 环境 无人机 仿真时长 目标 MM=37 n:10架 单次步数k：60/次 σ初值 =0.6 a = 1 v：1步/格 迭代数iter：30次 — τ初值 =100 r=2 — — ρ = 0.1 θ = 90° — — 文献 [16] 中对环境进行节点建模，节点个数 为 32 个，为了对比大环境中本文算法的有效性， 实验设置了 1 369 个节点的栅格环境。基于上述 场景，为了能够比较算法的优劣性，需要进行多 角度、长时间迭代的对比分析，本文仿真对比了基 于贪婪思想的搜索方法、随机搜索方法、文献 [16] 的搜索方法和本文的搜索方法。贪婪搜索方法是 在运动方向中选择信息素浓度最高的方向；随机 搜索方法则是没有任何决策机制，随机选择运动 方向[24-25]。图 9 为本文算法的流程。 图 10 所示为基于贪婪、随机、本文搜索方法以 及文献 [16] 搜索方法运行结束后的可视化界面。 图 10 中的 4 幅图均为各自算法最后一次迭 代下的热力图和无人机群航迹图。结果表明，主 动搜索和随机搜索与贪婪搜索相比，其目标的捕 捉率高，捕捉范围广；且主动算法的搜索覆盖最 广，随机搜索容易围绕在出生点附近，所以其捕 获目标的效率很大程度取决于出生点的好坏，贪 婪搜索由于贪婪思想，多架无人机均选择了相同 的路径，容易导致局部最优。本文就无人机群航 迹覆盖率、地图高亮区域和目标捕获点的分布规 律 3 个指标对这 4 种算法进行了比对分析，其中 航迹覆盖率对比如图 11 所示。 开始 初始化参数 n, α、iter、τ、 ρ、MM、v、δ 计算 f (x, y, δ) 计算 Pi 将所选节点 放入禁忌表 发现 目标 i<n 结束 方向限定 计算 UPEP 轮盘赌法 选择节点 信息增量 Δδ Y −30 ρ ρ N 更新 f (x, y, δ) 更新 τ M M Y iter<30 N N Y 图 9 本文算法流程 Fig. 9 Algorithm flow chart of this paper (a) 贪婪搜索方法 (b) 随机搜索方法 (c) 本文搜索方法 (d) 文献 [16] 搜索方法 图 10 4 类算法的可视化界面 Fig. 10 Visual interface of four algorithms 如图 11 所示，本文的搜索算法的航迹覆盖率 均值达到 80% 左右，仅以此结果来看，本文搜索 的效果比较可观，文献 [16] 搜索算法的覆盖率仅 有 52.3%，以此可以表明本文所提算法相较于文 献 [16] 更适用于较大的环境。然而动态目标相对 于无人机群体具有时间和空间的不确定性，因此 实验中用热力图中高亮区域的数量来表征算法中 ·580· 智 能 系 统 学 报 第 16 卷
第3期 楼传炜，等：无人机群目标搜索的主动感知方法 ·581 目标被捕获的效率，设定了亮度>75%为高亮栅 5 3 捕获点 格，如图12所示。 :平均值 2 σ标准差 100 ·本文算法 +贪婪算法 15 一随机算法 -文献[16]算法 10 60 100 200300400 500600 数据长度 (c)文献[161搜索方法 3 30 捕获点 101520 30 25 -“平均值 迭代次数次 -o标准差 1” 图114类算法航迹覆盖率对比 Fig.11 Comparison of track coverage of four algorithms 35 贪婪算法 0 100 200300400500600 ← 30 随机算法 数据长度 25 ·主动算法 (d)本文搜索方法 20 文献[16算法 15 图134类算法目标捕获点分布 10 Fig.13 Four types of target capture points distribution 表24类算法一维数据统计表 101520 2530 Table 2 One-dimensional data statistics of four algorithms 迭代次数/饮 方法 贪婪搜索 随机搜索 本文方法 文献[5] 图124类算法高亮区域数量对比 11.36 20.08 19.26 Fig.12 Comparison of hot spot area of four algorithms 20.08 从图12中可以明显看出，4种搜索算法随着 u-g 2.60 5.96 8.47 5.99 迭代次数的增加，其高亮栅格逐渐增多。然而贪 目标从左侧穿越环境到右侧，因此采取x坐 婪算法因为局部最优，导致后半段高亮栅格数量 标可表明目标被捕获时的分布情况，数据平均值 不再增长，即目标总在同样的地方被捕获。文献[16 的搜索方法由于受到环境的限制，高亮栅格明显 u越接近环境边长的中间值(=185小整个数 2 少于随机搜索和本文搜索方法。如图12由于无 据在地图中分布得越均匀；两个数据标准差σ之 人机每次迭代均在地图中心产生，本文搜索方法 间分布的点越多，即4一σ越大，捕获点越分散，说 较随机搜索效果略好一些。因此本文用目标捕获 明算法搜索到的目标分布越接近目标真实分布； 点的分布表示算法搜索到的目标分布，结果如图13 实验结果表明，本文算法搜索到的目标分布更加 所示。4类算法一维数据统计如表2所示。 均匀及分散，更接近真实目标分布，文献[16] 的搜索方法效果与随机搜索接近。 35 捕获点 3 5 -4平均值 σ标准差 7结束语 20 经上述仿真实验结果可得：本文提出的主动 10 5 感知框架下的UAVs目标搜索算法适用于未知环 0 100 200 300 400 500 境下未知目标的无人机群体目标搜索问题。相比 数据长度 较于文献[5]的蚁群搜索算法、贪婪搜索和随机 (a)贪焚搜索方法 搜索，本文提出的主动搜索方法对环境探索的覆 :.捕获点 盖性强，对运动目标的捕获能力也较强。然而， 050 一4平均值 σ标准差 算法中UAVs仅仅依靠共享的环境信息互相通 信，协作搜索能力还有待提升，因此以后可对UAV 10 的通信能力以及无人机协同方式深入研究。 5 100 200 300400 500600700 参考文献： 数据长度 (b)随机搜索方法 [1]齐小刚，李博，范英盛，等.多约束下多无人机的任务规
目标被捕获的效率，设定了亮度>75% 为高亮栅 格，如图 12 所示。 100 80 60 40 20 0 5 10 15 20 30 25 迭代次数/次 UAV 航迹覆盖率/% 文献[16]算法 本文算法 随机算法 贪婪算法 图 11 4 类算法航迹覆盖率对比 Fig. 11 Comparison of track coverage of four algorithms 35 30 25 20 10 5 15 0 5 10 15 20 30 25 迭代次数/次 文献[16]算法 亮度 >75% 栅格数/个 主动算法 随机算法 贪婪算法 图 12 4 类算法高亮区域数量对比 Fig. 12 Comparison of hot spot area of four algorithms 从图 12 中可以明显看出，4 种搜索算法随着 迭代次数的增加，其高亮栅格逐渐增多。然而贪 婪算法因为局部最优，导致后半段高亮栅格数量 不再增长，即目标总在同样的地方被捕获。文献 [16] 的搜索方法由于受到环境的限制，高亮栅格明显 少于随机搜索和本文搜索方法。如图 12 由于无 人机每次迭代均在地图中心产生，本文搜索方法 较随机搜索效果略好一些。因此本文用目标捕获 点的分布表示算法搜索到的目标分布，结果如图 13 所示。4 类算法一维数据统计如表 2 所示。 35 30 25 20 15 10 5 0 100 200 300 400 500 捕获点在 x 轴的投影 35 30 25 20 15 10 5 捕获点在 x 轴的投影 数据长度 0 100 200 300 400 500 600 700 数据长度 (a) 贪婪搜索方法 (b) 随机搜索方法 捕获点 μ 平均值 σ 标准差 捕获点 μ 平均值 σ 标准差 表 2 4 类算法一维数据统计表 Table 2 One-dimensional data statistics of four algorithms 方法 贪婪搜索 随机搜索 本文方法 文献[5] μ 11.36 20.08 19.26 20.08 μ−σ 2.60 5.96 8.47 5.99 ( MM 2 = 18.5 ) 目标从左侧穿越环境到右侧，因此采取 x 坐 标可表明目标被捕获时的分布情况，数据平均值 μ 越接近环境边长的中间值 ，整个数 据在地图中分布得越均匀；两个数据标准差 σ 之 间分布的点越多，即 μ−σ 越大，捕获点越分散，说 明算法搜索到的目标分布越接近目标真实分布； 实验结果表明，本文算法搜索到的目标分布更加 均匀及分散，更接近真实目标分布，文献 [16] 的搜索方法效果与随机搜索接近。 7 结束语 经上述仿真实验结果可得：本文提出的主动 感知框架下的 UAVs 目标搜索算法适用于未知环 境下未知目标的无人机群体目标搜索问题。相比 较于文献 [5] 的蚁群搜索算法、贪婪搜索和随机 搜索，本文提出的主动搜索方法对环境探索的覆 盖性强，对运动目标的捕获能力也较强。然而， 算法中 UAVs 仅仅依靠共享的环境信息互相通 信，协作搜索能力还有待提升，因此以后可对 UAV 的通信能力以及无人机协同方式深入研究。 参考文献： [1] 齐小刚, 李博, 范英盛, 等. 多约束下多无人机的任务规 35 30 25 20 15 10 5 捕获点在 x 轴的投影 30 25 20 15 10 5 捕获点在 x 轴的投影 0 100 200 300 400 600 500 数据长度 0 100 200 300 400 500 600 数据长度 (c)文献 [16] 搜索方法 (d) 本文搜索方法 捕获点 μ 平均值 σ 标准差 捕获点 μ 平均值 σ 标准差 图 13 4 类算法目标捕获点分布 Fig. 13 Four types of target capture points distribution 第 3 期 楼传炜，等：无人机群目标搜索的主动感知方法 ·581·
·582· 智能系统学报 第16卷 划研究综述[.智能系统学报，2020,15(2)204-217. [8]曹建秋，张广言，徐鹏.A*初始化的变异灰狼优化的无人 QI Xiaogang,LI Bo,FAN YingSheng,et al.A survey of 机路径规划[J/OL].计算机工程与应用：1-12 mission planning on UAV system based on multi-con- [2021-06-16]http://kns.cnki.net/kcms/detail/11.2127.TP.20201225 straints[J].CAAI transactions on intelligent systems,2020, 0932.014.html. 15(2):204-217. CAO Jiangiu,ZHANG Guangyan,XU Peng.A*initializa- [2]张松灿，普杰信，司彦娜，等.蚁群算法在移动机器人路 tion of varitated gray wolf optimized UAV path plann- 径规划中的应用综述[】.计算机工程与应用，2020， ing[J/OL].Computer engineering and applications:1-12. 56(8):10-19 [2021-06-16]http://kns.cnki.net/kcms/detail/11.2127. ZHANG Songcan,PU Jiexin,SI Yanna,et al.Survey on TP.20201225.0932.014.html application of ant colony algorithm in path planning of mo- [9]莫宏伟，马靖雯.基于蚁群算法的四旋翼航迹规划).智 bile robot[J].Computer engineering and applications, 能系统学报，201611(2)：216-225. 2020,56(8):10-19 MO Hongwei,MA Jingwen.Four-rotor route planning [3]鲁亚飞，吴岸平，陈清阳.无人机对地目标多帧融合定位 based on the ant colony algorithm[J].CAAI transactions on 与误差收敛特性分析J].国防科技大学学报，2021， intelligent systems,2016,11(2):216-225. 43(2):66-73. [10]魏永超，邓岚，李涛，等.采用改进细菌觅食优化算法的 LU Yafei,WU Anping,CHEN Qingyang.Multi frame fu- 无人机航迹规划).电讯技术，2021,61(5)：560-566. sion positioning and error convergence analysis of UAV to WEI Yongchao,DENG Lan,LI Tao,et al.UAV track ground target[J].Journal of National University of De- planning with improved bacterial foraging optimization fense Science and Technology,2021,43(2):66-73. algorithm[J].Telecommunication engineering,2021, [4]李坎，李云鹏，赵江波.无人机集群自组织搜索仿真模型 61(5:560-566. 设计与实现[J/0L].系统仿真学报：1-14.[2021-06-16] [11]赵红超，周洪庆，王书湖.无人机三维航迹规划的量子 http://kns.cnki.net/kcms/detail/11.3092.V.20210602.1421.0 粒子群优化算法).航天控制，2021,391)：40-45 04.html. ZHAO Hongchao,ZHOU Hongqing,WANG Shuhu. LI Kan,LI Yunpeng,ZHAO Jiangbo.Design and imple- Quantum particle swarm optimization algorithm of three- mentation of UAV swarm self-organizing search model[J/OL]. dimensional path planning of unmanned aerial vehicle[J]. Journal of system simulation:1-14.[2020-06-16] Aerospace control,2021,39(1):40-45. http://kns.cnki.net/kcms/detail/11.3092.V.20210602.1421. [12]MONTGOMERY J,RANDALL M.Anti-pheromone as a 004.html tool for better exploration of search space[C]//Proceed- [5]辛建霖，左家亮，岳龙飞，等.基于改进启发式蚁群算法 ings of the 3rd International Workshop on Ant Al- 的无人机自主航迹规划[J/OL].航空工程进展：1-8 gorithms.Brussels,Belgium:Springer,2002. [2021-06-16]http://kns.cnki.net/kems/detail/61.1479.V. [13]王祝，徐广通，龙腾.基于定制内点法的多无人机协同轨 20210524.1220.010.html 迹规划[J/OL].自动化学报：1-12[2021-07-12]htps:∥ XIN Jianlin,ZUO Jialiang,YUE Longfei,et al.Autonom- doi.org/10.16383j.aas.c200361 ous path planning for unmanned aerial vehicle based on WANG Zhu,XU Guangtong,LONG Teng.Multi-UAV improved heuristic ant colony algorithm[J/OL].Advances collaborative trajectory planning based on the custom in- in aeronautical science and engineering:1-8. point method[J/OL].Journal of automation:1-12 [2021-06-16]http://kns.cnki.net/kcms/detail/61.1479.V.20210524. [2021-07-12]https:/ldoi.org10.16383j.aas.c200361. 1220.010.html. [14]吴莹莹，丁肇红，刘华平，等.面向环境探测的多智能体 [6]樊娇，雷涛，韩伟，等.无人机航迹规划技术研究综述) 自组织目标搜索算法.智能系统学报，2020,15(2)： 郑州大学学报（工学版），2021,42(3)：39-46 289-295. FAN Jiao,LEI Tao,HAN Wei,et al.A survey of UAV WU Yingying,DING Zhaohong,LIU Huaping,et al. path planning[J].Journal of Zhengzhou University (engin- Self-organizing target search algorithm of multi-agent eering science).2021,42(3):39-46. system for envi-ronment detection[J].CAAI transactions [7]裴振兵，陈雪.波改进蚁群算法及其在机器人避障中的 on intelligent systems,2020,15(2):289-295. 应用).智能系统学报，2015,10(1)：90-96. [15]杜永浩，邢立宁，蔡昭权.无人飞行器集群智能调度技 PEI Zhenbing,CHEN Xuebo.Improved ant colony al- 术综述).自动化学报，2020,46(2)：222-241 gorithm and its application in obstacle avoidance for DU Yonghao,XING Lining,CAI Zhaoquan.Survey on robot[J].CAAl transactions on intelligent systems,2015, intelligent scheduling technologies for unmanned flying 10(1):90-96. craft clusters[J].Acta automatica sinica,2020,46(2):
划研究综述 [J]. 智能系统学报, 2020, 15(2): 204–217. QI Xiaogang, LI Bo, FAN YingSheng, et al. A survey of mission planning on UAV system based on multi-constraints[J]. CAAI transactions on intelligent systems, 2020, 15(2): 204–217. 张松灿, 普杰信, 司彦娜, 等. 蚁群算法在移动机器人路 径规划中的应用综述 [J]. 计算机工程与应用, 2020, 56(8): 10–19. ZHANG Songcan, PU Jiexin, SI Yanna, et al. Survey on application of ant colony algorithm in path planning of mobile robot[J]. Computer engineering and applications, 2020, 56(8): 10–19. [2] 鲁亚飞, 吴岸平, 陈清阳. 无人机对地目标多帧融合定位 与误差收敛特性分析 [J]. 国防科技大学学报, 2021, 43(2): 66–73. LU Yafei, WU Anping, CHEN Qingyang. Multi frame fusion positioning and error convergence analysis of UAV to ground target[J]. Journal of National University of Defense Science and Technology, 2021, 43(2): 66–73. [3] 李坎, 李云鹏, 赵江波. 无人机集群自组织搜索仿真模型 设计与实现 [J/OL]. 系统仿真学报: 1−14. [2021−06−16] http://kns.cnki.net/kcms/detail/11.3092.V.20210602.1421.0 04.html. LI Kan, LI Yunpeng, ZHAO Jiangbo. Design and implementation of UAV swarm self-organizing search model[J/OL]. Journal of system simulation: 1−14. [2020−06−16] http://kns.cnki.net/kcms/detail/11.3092.V.20210602.1421. 004.html. [4] 辛建霖, 左家亮, 岳龙飞, 等. 基于改进启发式蚁群算法 的无人机自主航迹规划 [J/OL]. 航空工程进展: 1−8. [2021−06−16] http://kns.cnki.net/kcms/detail/61.1479.V. 20210524.1220.010.html. XIN Jianlin, ZUO Jialiang, YUE Longfei, et al. Autonomous path planning for unmanned aerial vehicle based on improved heuristic ant colony algorithm[J/OL]. Advances in aeronautical science and engineering: 1−8. [2021−06−16] http://kns.cnki.net/kcms/detail/61.1479.V.20210524. 1220.010.html. [5] 樊娇, 雷涛, 韩伟, 等. 无人机航迹规划技术研究综述 [J]. 郑州大学学报(工学版), 2021, 42(3): 39–46. FAN Jiao, LEI Tao, HAN Wei, et al. A survey of UAV path planning[J]. Journal of Zhengzhou University (engineering science), 2021, 42(3): 39–46. [6] 裴振兵, 陈雪. 波改进蚁群算法及其在机器人避障中的 应用 [J]. 智能系统学报, 2015, 10(1): 90–96. PEI Zhenbing, CHEN Xuebo. Improved ant colony algorithm and its application in obstacle avoidance for robot[J]. CAAI transactions on intelligent systems, 2015, 10(1): 90–96. [7] 曹建秋, 张广言, 徐鹏. A*初始化的变异灰狼优化的无人 机路径规划 [J/OL]. 计算机工程与应用: 1−12. [2021−06−16] http://kns.cnki.net/kcms/detail/11.2127.TP.20201225. 0932.014.html. CAO Jianqiu, ZHANG Guangyan, XU Peng. A* initialization of varitated gray wolf optimized UAV path planning[J/OL]. Computer engineering and applications: 1−12. [2021−06−16] http://kns.cnki.net/kcms/detail/11.2127. TP.20201225.0932.014.html. [8] 莫宏伟, 马靖雯. 基于蚁群算法的四旋翼航迹规划 [J]. 智 能系统学报, 2016, 11(2): 216–225. MO Hongwei, MA Jingwen. Four-rotor route planning based on the ant colony algorithm[J]. CAAI transactions on intelligent systems, 2016, 11(2): 216–225. [9] 魏永超, 邓岚, 李涛, 等. 采用改进细菌觅食优化算法的 无人机航迹规划 [J]. 电讯技术, 2021, 61(5): 560–566. WEI Yongchao, DENG Lan, LI Tao, et al. UAV track planning with improved bacterial foraging optimization algorithm[J]. Telecommunication engineering, 2021, 61(5): 560–566. [10] 赵红超, 周洪庆, 王书湖. 无人机三维航迹规划的量子 粒子群优化算法 [J]. 航天控制, 2021, 39(1): 40–45. ZHAO Hongchao, ZHOU Hongqing, WANG Shuhu. Quantum particle swarm optimization algorithm of threedimensional path planning of unmanned aerial vehicle[J]. Aerospace control, 2021, 39(1): 40–45. [11] MONTGOMERY J, RANDALL M. Anti-pheromone as a tool for better exploration of search space[C]//Proceedings of the 3rd International Workshop on Ant Algorithms. Brussels, Belgium: Springer, 2002. [12] 王祝,徐广通,龙腾.基于定制内点法的多无人机协同轨 迹规划 [J/OL].自动化学报:1−12[2021−07−12] https:// doi.org/10.16383/j.aas.c200361. WANG Zhu, XU Guangtong, LONG Teng. Multi-UAV collaborative trajectory planning based on the custom inpoint method[J/OL]. Journal of automation:1−12 [2021−07−12] https://doi.org/10.16383/j.aas.c200361. [13] 吴莹莹, 丁肇红, 刘华平, 等. 面向环境探测的多智能体 自组织目标搜索算法 [J]. 智能系统学报, 2020, 15(2): 289–295. WU Yingying, DING Zhaohong, LIU Huaping, et al. Self-organizing target search algorithm of multi-agent system for envi-ronment detection[J]. CAAI transactions on intelligent systems, 2020, 15(2): 289–295. [14] 杜永浩, 邢立宁, 蔡昭权. 无人飞行器集群智能调度技 术综述 [J]. 自动化学报, 2020, 46(2): 222–241. DU Yonghao, XING Lining, CAI Zhaoquan. Survey on intelligent scheduling technologies for unmanned flying craft clusters[J]. Acta automatica sinica, 2020, 46(2): [15] ·582· 智 能 系 统 学 报 第 16 卷
第3期 楼传炜，等：无人机群目标搜索的主动感知方法 ·583 222-241 on intelligent systems,2016,11(1):27-36. [16]PURBOLINGGA Y.JAZIDIE A,EFFENDI R.Modified [24]薛政钢.基于多群体蚁群算法的多无人机协同搜索方 ant colony algorithm for swarm multi agent exploration 法研究D].开封：河南大学，2018 on target searching in unknown environment[Cl//Proceed- XUE Zhenggang.Research on Multi-UAV cooperative ings of 2019 International Conference of Artificial Intelli- search methods based on multi-colony ant colony al- gence and Information Technology.Yogyakarta,Indone- gorithm[D].Kaifeng:Henan University,2018. sia:IEEE.2019. [25]刘刚，裴红蕾.复合形引导蜂群寻优的无人机航迹多目 [17]LUO Fuyu,WANG Wei,LI Zhe.Multi-unmanned 标规划).机械设计与制造，2020(4)：253-257 vehicle for region traversal search based on ant colony al- LIU Gang,PEI Honglei.Unmanned air vehicle route gorithm[Cl//Proceedings of the 3rd International Sym- multi-object planning based on bee colony algorithm posium on Autonomous Systems.Shanghai,China,2019: guided by complex form[J].Machinery design manu- 329-334. facture,.2020(4):253-257 [18]YUE Wei,XI Yun,GUAN Xianhe.A new searching ap- proach using improved multi-ant colony scheme for 作者简介： multi-UAVs in unknown environments[J].IEEE access, 楼传炜，硕士研究生，主要研究方 2019,7:161094161102. 向为多智能体系统。 [19]BAJCSY R.Active perception[J].Proceedings of the IEEE,1988,76(8):966-1005. [20]AKKA K,KHABER F.Mobile robot path planning using an improved ant colony optimization[J].International journal of advanced robotic systems,2018,15(3):1-7. [21]时浩，田聪玲，任意，等.基于稀疏A*算法的微小型固 葛泉波，研究员，博士生导师，博 定翼无人机航迹规划[.兵工自动化，2021,40(3)： 士，主要研究方向为工程信息融合方 14-18,39. 法及应用、人机混合系统智能评估。 发表学术论文100余篇。 SHI Hao,TIAN Congling,REN Yi,et al.Route planning of small fixed-wing UAV based on sparse A*algorithm[J] Ordnance industry automation,2021,40(3):14-18,39. [22]LUO Qiang,WANG Haibao,ZHENG Yan,et al.Re- search on path planning of mobile robot based on im- 刘华平，副教授，博士生导师，国 家杰出青年基金获得者、中国人工智 proved ant colony algorithm[J].Neural computing and ap- 能学会理事、中国人工智能学会认知 plications,.2020,32(6:1555-1566. 系统与信息处理专业委员会秘书长 [23]夏小云，周育人.蚁群优化算法的理论研究进展[).智 主要研究方向为机器人感知、学习与 能系统学报，2016,11(1)27-36. 控制、多模态信息融合。主持国家自 XIA Xiaoyun,ZHOU Yuren.Advances in theoretical re- 然科学基金重点项目2项。发表学术 search of ant colony optimization[J].CAAl transactions 论文340余篇
222–241. PURBOLINGGA Y, JAZIDIE A, EFFENDI R. Modified ant colony algorithm for swarm multi agent exploration on target searching in unknown environment[C]//Proceedings of 2019 International Conference of Artificial Intelligence and Information Technology. Yogyakarta, Indonesia: IEEE, 2019. [16] LUO Fuyu, WANG Wei, LI Zhe. Multi-unmanned vehicle for region traversal search based on ant colony algorithm[C]//Proceedings of the 3rd International Symposium on Autonomous Systems. Shanghai, China, 2019: 329−334. [17] YUE Wei, XI Yun, GUAN Xianhe. A new searching approach using improved multi-ant colony scheme for multi-UAVs in unknown environments[J]. IEEE access, 2019, 7: 161094–161102. [18] BAJCSY R. Active perception[J]. Proceedings of the IEEE, 1988, 76(8): 966–1005. [19] AKKA K, KHABER F. Mobile robot path planning using an improved ant colony optimization[J]. International journal of advanced robotic systems, 2018, 15(3): 1–7. [20] 时浩, 田聪玲, 任意, 等. 基于稀疏 A*算法的微小型固 定翼无人机航迹规划 [J]. 兵工自动化, 2021, 40(3): 14–18, 39. SHI Hao, TIAN Congling, REN Yi, et al. Route planning of small fixed-wing UAV based on sparse A* algorithm[J]. Ordnance industry automation, 2021, 40(3): 14–18, 39. [21] LUO Qiang, WANG Haibao, ZHENG Yan, et al. Research on path planning of mobile robot based on improved ant colony algorithm[J]. Neural computing and applications, 2020, 32(6): 1555–1566. [22] 夏小云, 周育人. 蚁群优化算法的理论研究进展 [J]. 智 能系统学报, 2016, 11(1): 27–36. XIA Xiaoyun, ZHOU Yuren. Advances in theoretical research of ant colony optimization[J]. CAAI transactions [23] on intelligent systems, 2016, 11(1): 27–36. 薛政钢. 基于多群体蚁群算法的多无人机协同搜索方 法研究 [D]. 开封: 河南大学, 2018. XUE Zhenggang. Research on Multi-UAV cooperative search methods based on multi-colony ant colony algorithm[D]. Kaifeng: Henan University, 2018. [24] 刘刚, 裴红蕾. 复合形引导蜂群寻优的无人机航迹多目 标规划 [J]. 机械设计与制造, 2020(4): 253–257. LIU Gang, PEI Honglei. Unmanned air vehicle route multi-object planning based on bee colony algorithm guided by complex form[J]. Machinery design & manufacture, 2020(4): 253–257. [25] 作者简介： 楼传炜，硕士研究生，主要研究方 向为多智能体系统。 葛泉波，研究员，博士生导师，博 士，主要研究方向为工程信息融合方 法及应用、人机混合系统智能评估。 发表学术论文 100 余篇。 刘华平，副教授，博士生导师，国 家杰出青年基金获得者、中国人工智 能学会理事、中国人工智能学会认知 系统与信息处理专业委员会秘书长， 主要研究方向为机器人感知、学习与 控制、多模态信息融合。主持国家自 然科学基金重点项目 2 项。发表学术 论文 340 余篇。 第 3 期 楼传炜，等：无人机群目标搜索的主动感知方法 ·583·