基于IMM的无人机在线路径规划决策建模

杨啟明, 徐建城, 田海宝, 吴勇

(1.西北工业大学 电子信息学院, 陕西 西安 710072；2.空军驻江西地区军事代表室, 江西 南昌 330024)

无人机(UAV)在战争中的应用和出色表现已经使其作为一种新型作战力量受到越来越多的关注，与有人驾驶飞机相比，无人机具有隐蔽性好、不惧伤亡、可进行大过载机动等诸多优势。无人机智能化执行任务可以让人员的精力从繁重的具体操控上解脱出来，转而进行态势判断和推理等高级思考，这样能真正发挥人和机各自的优势，提升综合作战效率，因此无人机的智能化是其未来的发展方向[1-3]。无论军用还是民用领域，对运动目标实施跟踪是无人机的一个主要用途，实现跟踪自主化，能够在大幅降低操作强度的同时提高对目标信息探测的稳定性。本文试图对无人机跟踪目标的任务进行自主化设计，无人机周期地计算出行动策略，进而对飞行路径进行动态调整和规划以实现对目标的跟踪。

在状态存在随机性的规划问题中，多使用部分可观测的马尔科夫决策过程(POMDP)为建模方法。在基于POMDP的无人机路径规划应用方面有学者已经做了一些研究，例如文献[4]基于POMDP对无人机在线性观测方程下的路径规划进行了建模；文献[5]基于POMDP进行无人机对目标探测识别的建模；文献[6]基于POMDP对两栖车辆的运动路线进行了规划设计。上述文献均使用POMDP框架对路径规划问题进行了表述和求解，并取得了较为满意的结果，但是这些文献中均对目标的状态转移规律使用单一的运动模型(例如，匀速直线运动)来进行描述，这样与真实情况下的目标运动不相符合。本文以POMDP理论为基础，提出在POMDP模型中使用交互多模型(IMM)方法描述目标状态转移规律，用IMM方法实现模型的切换[7-8]，旨在构建适合于目标的机动变化下无人机跟踪路径的在线规划算法。

POMDP模型对问题有很强的表现力，但是对其精确求解十分困难[9]。累加代价的计算量会随着问题规模呈指数增长，此外观测的不完整性使得所获得状态信息具有随机性，因此对状态和观测信息均需用概率分布来描述，对远期代价和高维概率分布的精确计算需要较大的计算资源和时间开销。因此在无人机行动决策这样对实时性要求较高的在线规划场景，主要采用近似解法对模型进行求解，在有限时间内实时求出符合使用要求的次优解。在进行近似求解时，本文通过限定预测时限来降低远期代价的计算量，使用名义信念状态优化(NBO)算法[10]求解POMDP的行动序列，在满足跟踪性能的同时极大的降低了计算量。

1 路径规划问题建模

1.1 路径规划问题描述

无人机跟踪目标的路径规划的背景想定如下，无人机对地面一个移动目标进行观测并自动跟踪飞行。无人机使用传感器获得目标的距离和方位值，并以此为观测量自动调整无人机的飞行轨迹对目标保持跟踪，提供准确稳定的视频图像等目标信息。为了有效说明算法，本文假设无人机在固定高度飞行，简化无人机和目标的运动为二维平面内的运动。

1.2 路径规划POMDP各个要素

路径规划问题的POMDP模型可由6个要素的六元组〈S,A,T,O,C,B〉来表示,其中,S表示状态空间,A为行动空间,T为状态转移规律,O为观测和观测率,C表示代价函数,B为信念空间。下面对本文中各个要素代表的意义进行说明。

1.2.1 状态空间

1.2.2 行动空间

在跟踪目标的无人机路径规划问题中,每个决策点所采取的行动应能改变无人机的飞行状态,进而实时调整飞行路径。因此,本文采取加速度值ak和倾斜角φk作为行动值。在本时刻采取1组行动值,在下一时刻就可以改变无人机的状态。行动空间Ak=(ak,φk)。

1.2.3 观测和观测率

无人机获得的观测值由于设备误差和环境干扰通常是包含噪声的。因此,观测方程可以定义为状态Sk和观测噪声ηk的函数,如(1)式所示

zk=h(Sk)+ηk

(1)

传感器所获得的观测量是目标相对于无人机的距离和方位角信息[11-12]。因此,将h(Sk)定义为:

(1)式中,ηk为传感器的观测噪声序列,探测目标信息的过程中,ηk的分布与无人机和目标的位置相关,当无人机和目标距离较近时,观测噪声小,观测精度高,当距离较远时,空间内各种噪声较大,观测的误差较大。ηk的协方差可以表示为

Rk=R(xk,ξk)

(3)

0

式中,Mk=cos(φk)-sin(φk)

sin(φk)cos(φk)。

1.2.4 状态转移规律

状态转移规律是指在当前时刻下的状态在采取行动后到下一时刻的变化规律。对于定义的3个子系统,分别对其状态转移规律进行定义。

1) 无人机的状态转移规律定义为:

xk+1=Ψ(xk,Ak)

(5)

对函数Ψ定义的过程,就是设计行动值对无人机状态进行控制的方法的过程,即无人机在k时刻基于状态xk采取行动值Ak=(ak,φk),在k+1时刻到达状态xk+1的控制逻辑,本文采取的映射关系如下:

θk

(6)

(7)

θk+1=θk+(gTtanφk)vk

(8)

vk+1=vk+akT

(9)

vk+1=max{vmin,min{vmax,vk+1}}

(10)

(6)～(10)式分别求解出下一时刻无人机的位置和速度,式中g为重力加速度值,T为2个时刻之间的采样周期。在实际情况中无人机的速度存在上下限,采用(10)式对无人机速度的大小值进行了限制。

2) 目标的状态转移规律定义为:

ζk+1=f(ζk)+wk

(11)

式中,wk表示独立同分布的噪声序列,在本文中设定为零均值的高斯噪声,f表示目标的运动模型。

在已有的基于POMDP的无人机路径规划问题中,多将目标的运动模型假设为单一的运动模型,这对于研究POMDP的求解算法大有助益。但是在实际情况下地面目标不可能保持单一的运动形式,运动过程中受到地形和态势影响必然会存在各种机动,运动目标的动态模型比较复杂,传统的单一模型的定位跟踪算法不能实现良好的定位跟踪。采用交互式多模型算法(interacting multiple model,IMM)可以较好地解决这个问题[13-14]。

IMM的原理是将系统的运动模式映射为模型集,基于每个运动模型构建一个滤波器,所有模型的滤波器并行工作,利用每个滤波器输出的残差信息以及各模型的先验信息,依据假设检验规则,得出每个滤波器所对应的模型为当前时刻系统匹配模型的概率(称为模型概率),系统的状态估计是各模型滤波器估计的概率加权融合。

依据IMM,状态方程(11)式和量测方程(1)可以改写为(12)式。

ζk+1=f(ζk,mk)+w(k,mk)

zk=h(Sk,mk)+η(k,mk)

(12)

式中,mk是采样时刻k的有效模式,设系统模型集M={m1,m2,…,mr},模型的转换过程符合马尔可夫过程。

滤波状态(ξk,Pk)的转移规律按所采取的滤波算法确定。由于系统方程和观测方程为非线性方程,本文使用无迹卡尔曼滤波(UKF)算法,具体IMM-UKF滤波算法在1.2.6节介绍信念状态时一并介绍。

1.2.5 代价函数

代价函数表示在某个状态下采取某一行动所付出的代价值。本文采用无人机在当前状态下采取行动后,目标状态和滤波状态之间的均方误差值作为代价函数,代价函数可以表述为:

C(ζk,Ak)=Eηk+1,wk[‖ζk+1-ξk+1‖2|ζk,Ak]

(13)

1.2.6 信念状态和IMM-UKF算法

UKF和标准卡尔曼滤波都属于线性最小方差估计,算法都基于模型。标准卡尔曼滤波确定最佳增益阵时,使用了观测量的先验信息和一步预测均方误差阵,并基于系统和观测均为线性的假设。UKF根据估计量和观测量的协方差阵来确定最佳增益阵,协方差阵根据复现的一倍σ样本点计算,所以UKF在计算最佳增益阵的过程中未对系统方程和观测方程提出任何附加条件,算法既适用于线性对象,也适用于非线性对象。

1) 模型交互

∑ri=1

(14)

2) 模型条件滤波

UKF的算法步骤如下:

①计算k-1时刻的2n+1个σ样本点,n为ζ的维数,本文中n=4。

k-1

(15)

②确定权值

λn+λ

(16)

上式中,γ=n+λ,λ=α2(n+κ)-n,其中α是很小的正数,可以取10-4≤α≤1,本文中取1;κ=3-n;β取值与ζ的分布形式有关,对于本文中的采用的正态分布,β=2为最优值。(15)式中(Pk-1)(i)表示矩阵Pk-1的下三角分解平方根的第i列。

③计算k时刻的一步预测模型值

(17)

(19)

(19)式中Qk为(12)式中wk的方差阵。

④计算k时刻的一步预测样本点

i=n+1,n+2,…,2n

(20)

⑤更新量测

(21)

(23)

(24)

⑥滤波更新

增益矩阵为:

滤波值为:

k=k/k-1+Kk[zk-k/k-1]

(26)

3) 模型概率更新

(28)

对于各个模型j=1,2,…r,计算模型概率

4) 估计融合

计算k时刻的总体估计和误差协方差矩阵,分别为:

k=∑ri=1

POMDP模型的滤波状态根据融合的估计值得以更新,即ξk=k。继而,信念状态得到更新ζ)=Ν(ζ-ξk,Pk)。

1.3 路径规划POMDP模型

在无人机跟踪目标的路径规划POMDP模型中,目的是求解出一系列的最优行动值,让未来行动代价的累加值能够最小。由于无人机飞行的环境变化很快,对于较长时间后未来状态的预测无实际意义,因此只考虑未来H时限内的状态预测和行动策略求解,按照代价函数的定义,H时限内的行动代价的累加值可以表述为:

JH=E∑H-1k=0C(ζk,Ak)

(31)

由于状态ζk不完全可观测,只能求解得到信念状态分布,所以(31)式可以改写为:

JH=E∑H-1k=0C(bk,Ak)

(32)

式中

(33)

根据贝尔曼公式,在当前信念状态b0下,最优目标函数可以写为

(34)

(35)

根据贝尔曼公式,在k=0时刻的最优行动策略可以表述为

,A)

(36)

2 路径规划模型求解

2.1 算法的近似与假设

(37)

2.2 名义信念状态优化(NBO)算法

基于上述假设,NBO方法的核心可以被概括为如下公式:

J*(b)≈min∑kC(k,Ak)

(38)

①设系统噪声和观测噪声的均值均为0,则(1)式和(11)式可以写为

ζk+1=f(ζk)+wk,wk～Ν(0,Qk),

zk=h(Sk)+ηk,ηk～N(0,Rk)

(39)

bk+1=Φ(bk,Ak,ηk+1,wk)⟹k+1=Φ(k,Ak,0,0),

(40)

③用名义信念状态序列来代替信念状态的期望值,即

JH(b0)=Eb1,…,bH∑Hk=1C(bk,Ak)⟹

JH(b0)≈∑Hk=1C(k,Ak)

(41)

④根据(41)式求最优行动序列(A0,…,AH-1)。以min∑Hk=1C(k,Ak)为目标函数,以Ak的取值范围为约束条件,求解过程可以转化为一个标准的最优化问题,这里采用matlab中的fmincon函数来实现。

基于上述通用步骤,结合无人机目标跟踪路径规划的特点,设计基于IMM-UKF的无人机行动序列NBO求解算法如下。

ζ)=N(ζ-k,k)

(42)

由于预测时限H不长,所以认为在预测时限内目标均按照当前的匹配模型Fk运动,因此基于匹配模型Fk和k,通过(44)式可以递推出预测时限内各个时刻的。

k+1=Fkk

(44)

在预测过程中,没有量测信息输入,因此协方差矩阵的名义信念状态k可以通过克拉美罗下界来进行估计。

k+1=[(Fk

(45)

式中,Hk是量测函数h(Sk)对Sk求导得到的雅各比矩阵。

最后,根据代价函数的近似计算公式(37),将预测时限内递推得到的名义信念状态序列k带入(41)式,获得预测时限内的行动代价累加值,并以此为目标函数通过fmincon函数求得最优行动序列(A0,…,AH-1),取A0为当前时刻的行动策略并执行,则无人机状态改变,根据下一时刻的状态再执行IMM-UKF滤波,并重复上述步骤进行策略求解,不断往复,利用各个时刻求取的行动策略调整无人机状态,完成跟踪目标的路径规划。

3 仿真分析

本文在MTALAB环境下编写仿真程序,以无人机对单目标跟踪为背景进行仿真,基于跟踪的位置误差均值和无人机飞行轨迹对算法进行分析。目标的运动模型集合包括匀速直线运动,匀速左转弯运动和匀速右转弯3种运动。

单次仿真时间300 s,目标从(0,0)点开始沿水平轴方向匀速运动60 s,之后进行匀速左转弯运动60 s,再匀速直线运动60 s,之后再完成匀速右转弯运动60 s,最后再完成匀速直线运动60 s。

图1 目标状态估计和无人机路径规划

图2 基于IMM的位置误差均值

对基于IMM方法所建立的POMDP模型,分别在预测时限H=3和H=4的情况下各仿真30次,仿真结果如图1、图2和图3所示,从图1中可以看出无论是预测时限H=3和H=4,无人机在整个仿真过程中均能够跟踪目标,并围绕目标飞行。对比图1a)和图1b)可以发现,较之于H=3,在H=4时,行动策略所产生的无人机飞行轨迹更加平稳,围绕目标飞行的波动较小,这充分体现出了POMDP的远期代价计算特点,在当前状态下对目标未来状态进行预测能够让无人机对目标的行为有了预判,进而再计算出的行动策略能根据预测结果得到最优值,预测时限越长,策略越好。

图2a)反映了各次仿真中每一仿真时刻的位置误差平均值,从图中可以看出,不论H=3或H=4,整个仿真过程中滤波结果和目标真实位置之间的位置误差波动不是很大,在60 s、120 s、180 s、240 s等目标运动规律发生变化的时刻,位置误差均值并没有显著增加,说明采用IMM方法,无人机能够判断出目标的运动模型切变,在POMDP框架下对目标未来的远期状态进行预判,利用NBO方法求解的行动策略能够让无人机识别目标的运动规律而保持对目标的近距离跟踪。图3为各个时刻交互多模型集中各个模型的概率值,其中,P-CV代表匀速直线运动的概率值,P-CTL代表匀速左转弯运动的概率值,P-CTR代表匀速右转弯运动的概率值。图2b)反映了各次仿真整个过程的位置误差平均值,从整体上可以看出可H=4时的位置误差均值略小于H=3时的值,表1中的确切数据也反映了这一现象。H=4时位置误差均值为2.228 9,仅略小于H=3时的2.282 2,这在说明了POMDP模型决策远期性的同时也要求在设计预测时限时需要综合考虑计算开销和获得效果之间的平衡点。

表1 位置误差均值

图3 IMM中各个模型的概率值

图4 基于CV模型的飞行轨迹和位置误差均值

为了对比IMM方法,在同样条件下进行了仅采用匀速直线运动的一种运动模型的仿真30次。图4显示的是基于匀速直线运动(CV)模型的飞行轨迹和位置误差均值。UKF滤波和NBO算法预测中对目标的状态估计仅使用匀速直线运动这一种模型。从图4a)中可看出,在目标进行从直行进入转弯运动的过程中,无人机的飞行明显偏离了目标的运动轨迹,同时在图4b)中可以看出在目标进行左转弯运动和右转弯运动时,位置误差明显增大。从表1中也可以看出在整个仿真过程中仅采用CV模型的位置误差均值3.423 7远大于采用IMM算法的结果。在真实情况中,如果位置误差超过无人机传感器的有效探测距离,很有可能导致跟踪失败,为了验证,在相同情况下,将(3)式中的传感器测距不确定性m增大2%再进行仿真,结果如图5所示。

图5 CV模型下增大量测误差后仿真结果

在目标进行右转弯机动时,无人机丢失目标,跟踪失败。

对比图2a)和图4b)，说明基于IMM的无人机路径规划POMDP模型能够有效提高跟踪精度，使得规划的无人机路径更加贴合目标的运动，避免出现丢失目标的情况。

综上所述，在POMDP模型的状态转移规律中使用交互多模型机制能够比单一模型有效提高跟踪精度，能够保证无人机对机动目标跟踪的路径规划求解。

4 结 论

本文从无人机跟踪地面机动目标需求出发，针对无人机跟踪目标任务中的路径规划问题，引入POMDP理论，构建了基于POMDP的无人机在线路径规划决策模型。根据目标运动规律的多样性，使用了交互多模型(IMM)的方法描述状态转移规律并基于IMM-UKF算法来更新信念空间。为实现模型在线求解，引入了NBO算法，求解的行动策略能够实时完成无人机的运动调整和路径规划。仿真结果验证了本文所建立的无人机路径规划模型的有效性。

参考文献：

[1] Wang Z, Zheng M, Guo J, et al. Uncertain UAV ISR Mission Planning Problem with Multiple Correlated Objectives[J]. Journal of Intelligent & Fuzzy Systems, 2017, 32(1): 321-335

[2] 陈宗基,张汝麟,张平,等. 飞行器控制面临的机遇与挑战[J]. 自动化学报,2013,39(6):703-710

Chen Zongji, Zhang Rulin, Zhang Ping, et al. Flight Control: Challenges and Opportunities[J]. Acta Automatica Sinica, 2013,39(6):703-710 (in Chinese)

[3] 张耀中,张建东,史国庆. 无人机警戒雷达仿真系统的建模与仿真[J]. 火力与指挥控制,2016,41(2):93-96

Zhang Yaozhong, Zhang Jiandong, Shi Guoqing. Research on Modeling and Simulation of UAV Warning Radar[J]. Fire Control & Command Control, 2016,41(2): 93-96 (in Chinese)

[4] Ragi Shankarachary, Chong Edwin K P. UAV Path Planning in a Dynamic Environment via Partially Observable Markov Decision Process [J]. IEEE Trans on Aerospace And Electronic Systems, 2013,49(4):2397-2412

[5] Ponzoni Carvalho Chanel, Caroline, Teichteil Königsbuch. POMDP-Based Online Target Detection and Recognition for Autonomous UAVs[C]∥The 20th European Conference on Artificial Intelligence (ECAI), 2012

[6] Ragi Shankarachary, Chong Edwin K P. Decentralized Control of Unmanned Aerial Vehicles for Multitarget Tracking[C]∥2013 International Conference on Unmanned Aircraft Systems, 2013: 260-268

[7] Cork L, Walker R. Sensor Fault Detection for UAVs Using a Nonlinear Dynamic Model and the IMM-UKF Algorithm[C]∥Information, Decision and Control, 2007: 230-235

[8] 藏荣春，崔平远，崔祜涛，等. 基于IMM-UKF的组合导航算法[J]. 控制理论与应用，2007，24(4)：634-638

Zang Rongcui, Cui Pingyuan, Cui Hutao, et al. Integrated Navigation Algorithm Based on IMM-UKF[J]. Control Theory & Applications, 2007, 24(4): 634-638 (in Chinese)

[9] 万开方,高晓光,李波,等. 基于部分可观察马尔可夫决策过程的多被动传感器组网协同反隐身探测任务规划[J]. 兵工学报,2015,36(4):731-743

Wan Kaifang, Gao Xiaoguang, Li Bo, et al. Mission Planning of Passive Networked Sensors for Cooperative Anti-stealth Detection Based on POMDP[J]. Acta Armamentarii, 2015,36(4): 731-743 (in Chinese)

[10] Miller Scott A, Harris Zachary A, Chong Edwin K P. A POMDP Framework for Coordinated Guidance of Autonomous UAVs for Multitarget Tracking [J]. EURASIP Journal on Advances in Signal Processing, 2009, 2009(1): 1-17

[11] Gong S L, Wang B F, Honglan W U, et al. Tracking of Moving Targets on Airport Surface Based on IMM Algorithm[J]. Systems Engineering & Electronics, 2011, 33(10):2322-2326

[12] Wang D, Lv H, Wu J. In-Flight Initial Alignment for Small UAV MEMS-Based Navigation via Adaptive Unscented Kalman Filtering Approach[J]. Aerospace Science & Technology, 2017, 61:73-84

[13] Cui N, Hong L, Layne J R. A Comparison of Nonlinear Filtering Approaches with an Application to Ground Target Tracking[J]. Signal Processing, 2005, 85(8):1469-1492

[14] Ragi Shankarachary, Chong Edwin K P. Decentralized Guidance Control of UAVs with Explicit Optimization of Communication[J]. Journal of Intelligent & Robotic Systems, 2014,73(1):811-822