第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·