中国指挥与控制学会会刊 
无人机具有体积小,结构设计灵活,发生意外损毁相对损失成本较小,更易于防雷达、防红外线探测的特点。因此,相对于载人飞机,无人机更适用于复杂场景与危险环境中的侦察、搜索、监测和攻击任务,在民用领域以及军事领域的应用日渐广泛。其中,无人机集群协同区域搜索,可以极大地节约搜索时间,提升发现目标的概率,降低搜索成本,是无人机在现代战争中的重要应用场景,也是美军无人机技术的中长期发展目标之一[1]。
早期的无人机区域搜索模型为覆盖模型,即通过蛇形扫描、内螺旋扫描或制定规则的方式让无人机的扫描轨迹覆盖目标区域。在多无人机集群方面,传统方法主要基于任务区域分割。即划分任务区域为独立的子区域,并让集群内的无人机在不同的任务子区域内进行区域覆盖[2⇓-4]。这些方法简单易行,可解释性强,在具体的应用场景中验证了方法的有效性。但这些区域分割搜索方法往往受限于分割区域的不确定,且很难平均分配搜索任务,这导致在实际应用中算法效果比较有限。还有些方法让无人机集群按照某种规则进行区域搜索[5],这类方法参考鸟群飞行的策略,避免碰撞且保持了多无人机的协同。但这类方法与区域分割方法均缺乏对搜索目标先验信息或无人机机载传感器探测概率的相关讨论。表面上看,无人机集群按规则搜索的搜索路径尽可能多地覆盖了目标区域;实际上,无人机集群往往很难优先覆盖搜索目标活动热度大的区域。这意味着,找到搜索目标所花费的时间较大,即固定时间内发现目标的可能性相对较小。此外,对于区域划分方法而言,考虑搜索目标先验信息的区域划分方法与不考虑先验信息的区域划分方法完全不同,结合规则搜索方法实现均衡无人机搜索任务时间较为困难,算法泛化能力较差,无人机整体搜索效果难于体现。也有些文献提出了基于智能算法的无人机协同搜索策略[6],不划分任务区域,无人机集群进行全局协同,这种方法极大地改进了无人机集群搜索方法的稳定性,但也没有考虑搜索目标相关的概率问题。也有部分研究考虑了传感器发现目标的概率以及搜索目标在任务区域内的概率问题[7⇓-9],与实际问题较为贴合,但概率模型较为复杂,且并未考虑多智能体的整体搜索效率。综合来看,各种方法各有所长,但又很难完全贴合无人机集群搜索的真实应用场景。
受这些方法启发,综合各种方法的优点,本文提出了一种既考虑搜索目标与传感器相关概率,又不进行任务区域分割的整体集群搜索方法:基于航迹消除与策略迭代的无人机集群区域目标搜索方法。该方法通过热度网格地图来量化搜索目标在任务区域内出现的概率,把无人机在热度区域网格间的移动视为状态转移过程,把无人机传感器扫描到的区域热度值作为奖励,并把无人机经过的航迹做热度消除处理,即航迹消除,避免无人机发生路径冲突,进而利用策略迭代的方法,不断更新无人机采用不同策略飞行的价值,找出当前状态的最佳动作策略,动态规划无人机航迹,使得无人机的航迹尽可能覆盖到任务区域热度值大的部分。
1 无人机集群区域搜索任务问题描述
本文基于无障碍物的空旷地带或海域上的无人机实际巡逻、监测、搜索的场景,研究了一种已知搜索目标先验信息的无人机集群区域搜索问题。假设搜索目标在某个区域内的活动热度已知,需派出具有不同性能参数的无人机从多个点位出发集群搜索目标区域,在给定时间内,使无人机发现目标的可能性最大,使无人机的航迹尽可能覆盖到搜索目标活动热度值最大的区域。
假设搜索目标活动热度区域为1 000 km×1 000 km的网格区域,每个网格为1 km×1 km的矩形网格。搜索目标在i行j列网格活动的热度值(或概率值)为hij。不妨设无人机飞行高度恒定,机载传感器采用下侧环扫的方式探测目标,如图1a) 所示。显然,机载传感器与目标投影距离越大,越不容易发现目标,而越近则越容易,假设l型无人机机载传感器在飞行高度固定为h0时,发现目标的概率为pl(d)如下:
其中,d为无人机与搜索目标之间的投影距离(无人机投影与搜索目标均视为点),Rl为型号为l的无人机在规定飞行高度时能探测到搜索目标的最大投影距离,a与λl为l型无人机的传感器固定参数,用以区分不同传感器对发现目标概率的影响(具体值可以通过实际飞行实验,再结合发现搜索目标的概率进行数据拟合得到)。
若无人机匀速飞行,无人机的传感器每Δt时间探测目标区域一次,且l型无人机的速度为vl,机载传感器的探测区域为圆域(圆心为无人机传感器的投影点,半径为最大探测投影距离),无人机的航迹为带状,则搜索目标有可能多次被传感器扫到,即被多个圆盖住,如图1a) 所示,图1b) 为图1a) 的投影平面图。其中,目标投影与无人机投影位置均被视为网格中心点;d1为目标第一次被无人机环扫区域盖住时目标与无人机传感器之间的投影距离,而d3为目标第三次被无人机环扫区域盖住时目标与无人机传感器之间的投影距离。
若搜索目标被机载传感器扫描了M次,且每次传感器扫描结果相互独立,由公式(1)得到,搜索目标被l型无人机发现的概率为
pl=1- (1-pl(di))
其中,di表示机载传感器第i次扫描到目标时,目标与无人机传感器间的投影距离。
2 无人机航迹热度消除
为了在给定时间内尽快发现搜索目标,需要让无人机集群的航迹尽量覆盖热度值大的目标区域。虽然无人机探测过的区域是否能发现目标依然是个概率问题(见式2),但从常识出发,未探索过的、热度值大的区域更具有搜索价值。为了避免路径重复,量化探测效果,本文引入航迹热度消除策略对航迹上的热度进行更新,即无人机探测过的区域对应热度值按照被探测到的概率衰减,热度更新具体方法如下:
=
其中, 为t时间步第i行第j列网格位置的热度值,(xi,yj)第i行第j列网格的中心节点。
若总探测次数为T,则最终目标区域的剩余热度值为
这个值越小,说明无人机航迹盖住区域的热度值越大,而目标最终被探测到的可能性(覆盖率)为
1-
该指标综合考虑了目标的活动热度以及航迹上传感器多次探测发现目标的可能性,体现了目标最终被无人机发现的概率。因此,模型的优化目标为找到恰当的无人机集群飞行路径,使得覆盖率最大。
3 策略迭代
为了合理规划无人机的搜索轨迹,本文引入动态规划的基本方法之一:策略迭代[10]。策略迭代交替使用“策略评估”和“策略更新”两个步骤,找到每个状态下(无人机所在的网格位置)的最佳策略(每个状态下,采用的动作,即无人机在每个网格位置上的后续飞行方向)。其中,第t个时间步(每个时间步无人机均发生状态变化,从当前状态到下一个状态)无人机所在网格位置为状态St,状态的价值为V(St),无人机从一个状态移动到下一个状态为动作at,无人机航迹上消除的热度值视为动作奖励Rt,对于不同的飞行策略π,航迹上的状态以及奖励均不相同。且每一个状态的价值,都受后续状态价值的影响。为了找到热度覆盖率最大的无人机航迹,本文通过策略迭代方法,使每一个状态的价值最大化,最终找到具有最大价值的策略,即无人机的航迹。
基于策略π状态s的价值Vπ(s)指在状态s时按照策略π做动作,可以获得的长期回报的期望,定义如下:
Vπ(s)=E(Gt|St=s)
其中,St为第t个时间步后无人机的状态(所处的网格位置),Gt为t个时间步后,无人机获得的回报。Gt的一般形式为
Gt=Rt+1+γRt+2+…γT-t-1RT
Rt表示t时刻无人机获得的奖励。γ为折扣系数,表明当前回报受远期奖励的影响较小,受近期奖励的影响较大,T为终止时刻。
把式(7)代入(6)可得
Vπ(s)=E(Rt+1+γGt+1|St=s)=E(Rt+1|St=s)+γE(Gt+1|St=s)
令π(a|s)表示在状态s下,无人机采用动作a的概率,p(s',r|s,a)为无人机在状态s,采用动作a达到状态s',获得奖励r的概率,则:
$\begin{array}{l} E\left(R_{t+1} \mid S_{t}=s\right)=\sum_{a} \pi(a \mid s) r= \\ \quad \sum_{a} \pi(a \mid s) \sum_{s^{\prime}, r} p\left(s^{\prime}, r \mid s, a\right) r \\ E\left(G_{t+1} \mid S_{t}=s\right)= \\ \quad \sum_{a} \pi(a \mid s) \sum_{s^{\prime}, r} p\left(s^{\prime}, r \mid s, a\right) V_{\pi}\left(s^{\prime}\right) \end{array}$
代入公式(8)得
$V_{\pi}(s)=\sum_{a} \pi(a \mid s) \sum_{s^{\prime}, r} p\left(s^{\prime}, r \mid s, a\right)\left[r+\gamma V_{\pi}\left(s^{\prime}\right)\right]$
根据上面得到的状态价值Vπ(s)可以得到状态-行动价值q(s,a),定义如下:
$\begin{array}{c} q_{\pi}(s, a)=E\left(R_{t}+\gamma V_{\pi}\left(S_{t+1}\right) \mid S_{t}=s, A_{t}=a\right)= \\ \sum_{s^{\prime}, r} p\left(s^{\prime}, r \mid s, a\right)\left[r+\gamma V_{\pi}\left(s^{\prime}\right)\right] \end{array}$
理论上,有多少个状态,就可由公式(9)计算出多少状态价值,但显然直接计算过于繁琐,因此,把(9)式改写为迭代公式,如下:
Vk+1(s)= π(a|s) p(s',r|s,a)[r+γVk(s')]
其中,Vk+1(s)表示第k+1次迭代时状态s的价值。
策略迭代的具体步骤:
步骤1:策略评估
通过输入任意状态初始值V0(s)(s为任意状态),以及初始策略π0代入公式(11)进行迭代计算,就可以达到收敛的价值V*(s)。其中,达到收敛表示用公式(11)计算出的Vk+1(s),不论s为何种状态,在k足够大时,均趋于平稳。
步骤2:策略提升
把第一步得到的每个状态价值代入公式(10),计算状态动作价值,找到使状态-行动价值q(s,a)最大的策略π*。即:每种状态s下,找到使q(s,a)最大的动作。
步骤3:迭代
把策略π*以及V*(s)代入第一步,第二步继续运算。
重复这三个步骤,直至策略收敛(π*不发生变化)为止。
4 基于航迹消除与策略迭代的无人机集群搜索算法
基于航迹消除与策略迭代的无人机集群搜索算法在考虑搜索目标在任务区域中出现的热度信息,以及无人机机载传感器探测到目标的概率等先验信息的基础上,通过对无人机的航迹热度消除来更新每个时间步上的目标区域热度(见式5)。同时,也利用策略迭代的方法使得航迹尽可能覆盖到热度值大的区域,进而找到无人机集群的飞行路径。
算法步骤:
步骤1:定义状态、动作与状态奖励值
设无人机所处网格位置即为无人机所在状态。理论上,无障碍区域内的航向可以任意变化,但考虑航向变化越少,实际飞行操作与策略迭代方法越容易实现,因此不妨设航向为向上、向下、向左、向右四种。奖励值r为每个状态下搜索区域内的目标活动热度值,无人机在t时刻状态St=s时,选择四个方向中的一个飞行,并在下一时刻到达状态St+1=s',获得s'状态所对应的热度值作为奖励。
步骤2:把航迹消除融入策略迭代
1) 执行策略评估以及策略提升找到最优策略
设所有状态的初始价值为零,且所有状态下的动作(向上、向下、向左、向右)概率均为0.25,进行一次策略评估与策略提升,令V0(s)=0,先利用公式(11)不断迭代,找到每个状态下收敛的价值V*(s);再把V*(s)代入公式(10),计算四种动作(向上、向下、向左、向右)的q(s,a),找到使q(s,a)最大的策略π*。
2) 航迹热度消除
按照策略π*执行动作,找到每个状态的下一状态。让无人机从当前状态到达新状态,产生一段航迹。按照公式(3)更新这一段航迹的热度,则被航迹覆盖过的网格内热度值降低。
3)迭代
重复上面两个步骤。每执行一次为一个时间步,航迹延长一段,航迹热度更新一次,达到给定时间步,运算终止,得到无人机的完整航迹。
步骤3:无人机集群搜索
上面的两个步骤为一架无人机的路径规划步骤,无人机集群飞行只需要按顺序在消除前序无人机航迹的搜索区域内继续重复上面两个步骤即可。由于有航迹消除策略,发生路径冲突的可能性不大,不同无人机航迹规划的计算顺序(计算顺序并非时间先后,而是不同无人机套用前两个步骤计算的先后顺序,这个顺序差异对覆盖率会有影响)成为提高无人集群飞行效率的关键。为了找到最合理的计算顺序,应尝试多种组合方式。最后,覆盖率最大的组合即为无人机集群的最优方式。
步骤4:冲突发现,航迹修正
无人机集群搜索待解决的关键问题主要包括两个方面。一方面是提高搜索效率的问题,另一方面是避免冲突(多架无人机同一时刻经过同一点,或同一时期共享同一段航迹),保证飞行安全,符合现实操作的问题。前面的三个步骤解决了第一个问题,而第二个问题,本文采用航迹修正策略。通过修正不合理的航迹角度,来使实际飞行过程更符合要求。具体包括冲突修正以及路径平滑两部分。由于航迹规划引入了航迹消除策略,探索过的区域热度值相对较小,无人机的航迹更倾向于探索新区域,因此,大规模路径冲突的可能性不大。但如果确实存在局部路径冲突,如多架无人机在同一机场起飞,且附近区域热度值为0,则这些无人机的初始航迹很可能会相同。这时可以通过局部插值处理路径冲突。例如,在原始路径外就近找一些点进行插值,使得无人机的路径相互错开,但又不会偏离原路径太多,不会对后续搜索造成过大影响。而路径平滑则主要针对无人机航迹在局部区域过于复杂的情况,可以采用局部曲线拟合的方式对原无人机轨迹上的状态点进行拟合[11⇓-13]。
5 实例计算
为验证提出的模型与方法的有效性,本文仿真生成了两种搜索任务区域为1 000 km×1 000 km,网格大小为1 km×1 km的热度区域,飞机的起点位置表示为热度数据的行标与列标组合,为(800,200),(900,500),分别标为A1、A2。地理热度图像如图2 所示。
设两个机场各派出两架无人机,参数如表1 所示。
表1 算例参数Tab.1 Example parameters |
| 参数 | 值 | |
|---|---|---|
| 飞行速度 | 600 km/h | |
| 最大探测投影半径 | 100 km | |
| A1机场派出1型无人机 | 传感器固定参数λ | 1/15 |
| 传感器固定参数a | 1 | |
| 飞行时长 | 2.5 h | |
| 飞行速度 | 900 km/h | |
| 最大探测投影半径 | 150 km | |
| A2机场派出2型无人机 | 传感器固定参数λ | 1/20 |
| 传感器固定参数a | 1 | |
| 飞行时长 | 2 h | |
| 传感器 | 探测间隔时间 | 20 s |
| 策略迭代 | 回报折扣系数 | 0.9 |
考虑到直接按照1 000 km×1 000 km的网格区域进行策略迭代计算效率过低,且过多改变无人机方向也不利于实际操作,为了降低算法复杂度,改进运算的效率,不妨将1 km2为单位的网格划分为400 km2的网格。每个新网格热度为包含在其中的原始网格热度之和。策略迭代中的状态为无人机所在的网格位置,动作以及奖励定义方式与原来一致。则无人机从当前状态移动到下一个状态时,传感器采集信息的次数为20/(vt')。其中,20为网格长度,v为无人机飞行速度,t'为扫描时间间隔。若无人机探测圆域盖住网格中点,则按照公式(3)消除相应网格热度值。
1)仿真搜索区域1上的搜索结果
2)仿真搜索区域2上的搜索结果
可以看出,规则搜索法较为简单,可解释性强,但无人机集群搜索效果受搜索区域热度分布以及中心点选取影响。图2 所示的两种区域,并不能划分为相对独立的四个热点子区域,这导致派出四架无人机搜索时,很难确定每个无人机的搜索任务范围。这意味着需要通过反复调整无人机的回型路径起始中心点,才能找到较好的无人机航迹。因此,这种规则搜索算法的覆盖率并不高,且泛化能力差。
相对而言,用策略迭代法的覆盖率较高,泛化能力强。可以看出,在两个区域上所有无人机的航迹交叉点对应的时刻不同,且没有共同的航迹,表明无人机无相撞风险。此外,除了部分位置,无人机轨迹形态也比较平滑。但原搜索区域中最亮的子区域,即热度值最大的子区域内无人机轨迹较为复杂,且航迹在部分网格中存在往复(倒飞)。一方面,这种复杂航迹与热度值分布有关。由于热度数据是通过仿真方式生成,与实际问题的热度区域热度值变化比较清晰不同,仿真出的热度数据部分子区域与周围区域相比热度值较大,但该子区域内热度变化较小。这可能会导致在这个子区域的某个具体状态下,周围的状态热度值变化都相同,这使得在该状态下不管采用什么动作(用式10)算出的状态动作价值都相等,无法进行策略提升。此时,无人机会随机选择一个动作产生航迹,这意味着,无人机在该状态附近的飞行轨迹无序且复杂。这种局部热度分布特征在实际问题中比较少见,即使存在上述局部飞行轨迹较为复杂的情况,这种不规则轨迹也可以通过分段拟合进行平滑处理。另一方面,即使图上显示航迹往复,也是符合飞行实际的,(计算用的网格大小为400 km2,无人机在网格内可以掉头飞行,且对计算影响较小)。此外,从策略迭代方法的理论上看,航迹消除过程并不是热度清零,而是参考了传感器的探测率,按比例消除航迹上的目标热度值。这意味着在某些目标活动热度值很大的区域,即使有航迹热度消除,这一区域的热度也依然较大,这导致无人机会在某个子路径上重复飞行,即在目标出现大的路径上巡回飞行。这种巡回模式也体现了重点区域重点搜索的特征。综合可知,用航迹消除与策略迭代的无人机集群区域目标搜索方法是一种比较简便且合理的轨迹规划方法。
6 结束语
基于航迹消除与策略迭代的无人机集群区域目标搜索方法是根据无障碍区域搜索的实际场景,在搜索目标活动热度信息已知的基础上,采用航迹消除策略,将寻找无人机集群在热度区域上的最优搜索路径问题,转化为无人机航迹上的最大覆盖热度问题,以覆盖率体现目标最终被搜索到的概率,并结合策略迭代方法动态规划无人机航迹。仿真实验证明,该方法具有较强的可操作性和实用性。