探测点序列的最优化与简化计算方法

陈长康，陈建勇，周家新

（海军航空大学，山东烟台264001）

在最优搜索理论的研究中，对连续空间中的连续运动目标进行搜索，一般考虑的是连续空间的连续搜索路径[1-2]。假设在连续的搜索路径中，仅在某些时间段上，探测器实施探测，并且在探测过程中，探测器保持位置不变，这样，搜索路径问题，就变成探测点序列问题[3]。直升机吊放声纳搜潜是一种对目标的搜索只能在离散时间上进行有效的探测问题[4]，即探测点序列问题。文献[4]计算了离散时间点上有限探测域的最优搜索位置；文献[5-6]给出了搜索状态方程，并用射线法近似地对方程进行求解；文献[7-8]研究对随机运动目标进行搜索的问题，给出了计算目标位置概率密度函数的方法；文献[9]讨论了目标的扩散方程，并建立最优搜索的最优控制问题；文献[10]由目标模型和探测概率模型，提出随机最优控制问题；文献[11]给出一维运动目标最优搜索的一种算法，并求得最优的探测点位置；文献[12]研究了一种基于梯度的寻优算法求离散点探测概率最大点的寻优问题；文献[13]给出直升机搜潜初始探测点的选择原则，考虑转向延迟影响，进而提出多机联合搜索策略；文献[14]针对提高直升机吊放声纳等离散搜索力的搜索效率，导出离散搜索力的最优配置模型；文献[15]根据给出的探测函数，研究了多个探测点的探测概率最优问题；文献[16]在一定条件下建立了目标模型，研究了关于吊放声纳搜潜的探测点概率问题。

本文针对离散时间探测目标这类问题，在讨论了搜索状态建模和一阶搜索状态方程求解的基础上，建立了探测点序列的最优控制模型，给出了一种最优探测点序列的逼近算法以及缩短计算时间的简化算法。在满足一阶搜索状态方程的随机恒速目标条件以及有限指数探测函数条件下，将算法的2种形式应用到算例，分别求得了给定探测起始点和搜索时间的最大发现概率的探测点序列。

1 搜索状态方程及一阶方程的解

设t∈T=[0,T]，令目标空间X⊂ℝn，搜索空间Y⊂ℝm。定义搜索路径函数Z∶T→Y，表示搜索者从0时刻搜索到T时刻所运动的轨迹，z=Z(t)，表示t时刻搜索者所处的位置。

定义探测率函数b(x,t,z)。定义搜索至t时刻未发现目标和目标位置的联合概率分布密度函数f(x,t,Z)。定义t时刻目标存在于x的条件下，从t时刻搜索到T时刻未发现目标的概率，即目标存活概率函数u(x,t,T,Z)。

目标在Δt内的随机移动向量具有二阶矩的条件下，有搜索状态方程[3]：

式（1）、（2）中：i、j表示空间维度；a(x,t)为速度均值函数向量；c(x,t)为目标随机移动量二阶矩的时间导数矩阵；ai(x,t)、cij(x,t)分别为a(x,t)的分量与c(x,t)的元素。

如果cij(x,t)=0，则搜索状态方程化为一阶方程。设向量函数和梯度向量均为列向量，一阶搜索状态方程为：

只要各个特征迹线不相交，那么，X空间中的任意一个点就仅有一条特征迹线通过。应用终止条件u(x,T,T,Z)=1，初始条件f(x,0,Z)=ρ0(x)，可以得到搜索方程在特征线上的解：

式（7）中：x(τ),τ∈[t,T]是起点在x(t)，终点在x(T)的特征线。

式（8）中，x(τ)，τ∈[0,t]，是起点在x0=x(0)，终点在x(t)的特征线。

如果在0到t时刻不进行探测，即b=0，在式（8）中有：

在式（7）中有：

按照联合概率分布密度函数f的定义，设t∈[0,T]的探测点序列Z={zk}。按照Z搜索到T时刻，发现目标的概率为：

2 探测点序列的最优控制模型

在第1节对搜索状态建模、一阶搜索状态方程求解以及给出发现概率模型的基础下，建立了探测点序列的最优控制模型。

对于搜索总时间T，有已知的时间序列为：

其中，t∈[tk,Tk],k=0,1,2,…,K表示探测实施探测的时间且在探测期间搜索者保持静止，t∈[Tk,tk+1]表示搜索者转移运动时间，期间探测器不探测。

设探测点Z(k)为系统状态。令搜索者从Tk-1到tk的平均转移速度为V(k)∈ℝm。系统状态方程为：Z(k)=Z(k-1)+V(k-1)(tk-Tk-1)，Z(0)=z0控制函数约束：|V(k)|≤Vmax，Vmax为搜索者所能达到的最大速率。

将(Z)表示为初始时刻为0，初始状态为Z(0)，终止时刻为T的性能指标函数：

其中，f(x,T,Z,V)与前述的f(x,t,Z)意义相同，f(x,T,Z,V)指在函数f(x,t,Z)的基础上考虑了联合概率分布密度函数f与搜索者速度的关系。

初始时刻为tk，初始状态为Z(k)，终止时刻为T的性能指标函数为：

因为在t∈[Tj,tj+1]，探测器不进行探测，有b(x,t,z)=0，从目标存活概率函数的定义可得[3]：

根据动态规划原理，对于使J[Z(0),0]取极小的Z*、V*，必使以Z∗(k)为初始状态的J[Z(k),tk]取极小，即[3]：

动态规划的基本递推方程为[3]：

3 最优探测点序列的逼近算法

3.1 精确计算算法

在第2节建立了探测点序列的最优控制模型的基础上，结合动态规划原理给出一个最优探测点序列的逼近算法。

1）对于搜索总时间T，有已知的时间序列为：

并给定初始状态Z(0)；

2）给定初始搜索速度的向量序列{V0(k)}，k=0,1,2,…,K-1；

3）n=0；

4）k=K-1；

5）据向量序列{Vn(k)}，计算探测点序列：Zn(k)=Zn(k-1)+Vn(k-1)(tk-Tk-1)；

6）求tk时刻一阶搜索状态方程的特征迹线解fn,un；

7）若k=-1，转到步骤11）；

8）用最优化方法，求J[Z(k),tk]极小的Vn∗(k)；

9）用Vn∗(k)更新序列{Vn(k)}；

10）k=k-1，返回步骤5）；

11）计算(Zn,Vn)，若满足精度：

12）n=n+1，返回步骤4）；

13）V∗={Vn(k)}，Z∗={Zn(k)}，；

14）结束。

3.2 简化计算算法

在3.1节精确计算算法的基础下，对算法进行简化以缩短计算的时间，具体简化计算如下两部分：

1）加大空间离散化计算所划分的单元格面积，从而在不影响计算数据准确性的情况下，通过舍去一定的计算精度提高了计算的效率。

2）整个算法的计算过程涉及大量的循环计算，其中，主要耗时在3.1节中步骤6）对fn、un的空间积分值的循环计算，因此对fn、un函数作如下简化计算。

计算式（7）中un的方法和简化方法：

式中：j=k,k+1,…,K；tk为探测点的探测初始时刻。精确计算中，在每段探测时间t∈[tk,Tk],k=0,1,2,…,K采用dτ=1 s的步长，依次计算对应的b值后进行乘积叠加，而简化计算采取将每段探测时间的初始时刻tj对应的b值与每段探测时间(Tj-tj)乘积求和作为积分的近似值。

计算式（8）中fn的方法和简化方法：

式中：tj-Tj-1为探测点间隔时间，期间不探测，有探测函数b(x,t,z)=0。精确计算采用步长为dτ=1 s，依次计算b和∇⋅a(x(τ),τ)值后进行累加。简化计算采取将每段探测时间的初始时刻tj(j=0,1,2,…,k-1)对应的b与∇⋅a(x(tj),tj)值与探测时间(Tj-tj)乘积求和，加上每段非探测时间的初始时刻Tj的∇⋅a(x(Tj),Tj)值与非探测时间tj+1-Tj的乘积求和作为整个积分的近似值。

4 算例分析

4.1 目标模型

设初始时刻为0，目标空间为二维空间，目标的初始位置分布服从圆正态分布：

设目标为随机恒速运动目标，其速度分布为圆正态分布：

目标在t时刻速度的空间条件分布为[17]：

在x点的目标速度期望值及其散度[17]为：

任意x(0)点所在的特征线方程[17]为：

很容易证明，随机恒速运动目标满足一阶搜索状态方程。

计算中取σ=2 n mile，μ=8 kn。

4.2 探测模型

设搜索空间为二维空间，根据文献[18]，给出指数型探测率函数为：

k=0,1,2,…,K，取探测器作用距离R=3 n mile。在t∈[0,T]，有搜索状态方程（1）、（2）成立，对于t∈[tk,Tk]，令Z(t)=Z(k)=zk，表示探测期间搜索者保持静止。

4.3 算例计算

4.3.1 算例一

应用3.1的精确算法计算。

设搜索者进行搜索过程的速度|V|=130km/h，即令给定的初始搜索速度的向量序列{V0(k)}中的速度大小为130km/h，目标和搜索空间计算范围为50 n mile×50 n mile，坐标原点设在其中点处，将其离散化为200 m×200 m的单元格进行计算；设Z(0)=(-11 n mile,-11 n mile)，T=94min，每个探测点探测时间为3min，探测点间隔时间为10min。计算结果如图1所示。

图1中，序号1为给定的探测起点，初始探测点序列任意给定，经15次探测点序列的优化计算，耗时约11 h，在满足相邻两次计算的探测点序列的探测概率差小于0.1%的精度要求下，得到图中给定精度要求的最大发现概率为0.6745的最优探测点序列。

4.3.2 算例二

应用3.2算法的简化内容进行计算。

与算例一的假设条件相同，将目标和搜索空间计算范围离散化为400 m×400 m的单元格进行计算，计算结果如图2所示。

经19次探测点序列的优化计算，耗时约1 h，得到图中给定精度要求的最大发现概率为0.618 5的最优探测点序列。其中，图2中的序号、序列等表示意义均与图1相同。

5 结论

基于搜索状态函数f、u和搜索路径函数Z的发现概率模型，是对发现概率的一种精确描述，本文根据动态规划原理，设计了一种最优探测点序列的逼近算法并给出其简化计算形式，将算法的2种形式应用到算例计算。算例表明，精确算法和简化算法均能够使任意给定的初始探测点序列收敛到一个满足精度要求的最大发现概率的最优探测点序列上，在优先考虑计算效率并能容许一定的最优性误差时，简化计算同样能够得到“最优探测点序列”，并较精确算法的计算时长缩短了11倍。

该算法的两种形式可解决直升机吊放声纳搜潜等一类离散时间探测问题，根据实际对计算效率与最优性的优先级要求，在给定精度条件下，提供最大发现概率的最优探测点序列的重要参考与指导作用。

[1]肖斌，徐宏飞.搜索力最优配置的求解与收敛性分析[J].火力与指挥控制，1998，23（4）：36-39.XIAO BIN，XU HONGFEI.The solving method for optimal arrangement of search-capacity and the convergence analysis[J].Fire Control&Command Control，1998，23（4）：36-39.（in Chinese）

[2]王景奇，范奎武，张最良.机动目标对搜索的最优规避[J].军事系统工程，2001，11（1）：4-9.WANG JINGQI，FAN KUIWU，ZHANG ZUILIANG.Optimal evasion of search by maneuvering target[J].Military System Engineering，2001，11（1）：4-9.（in Chinese）

[3]陈建勇.单向最优搜索理论[M].北京：国防工业出版社，2016：152-168.CHEN JIANYONG.One-side optimal search theory[M]，Beijing：National Defense Industry Press，2016：152-168.（in Chinese）

[4]陈建勇，王健，单志超.离散时间探测随机恒速目标的最优搜索算法[J].系统工程与电子技术，2013，35（8）：1627-1630.CHEN JIANYONG，WANG JIAN，SHAN ZHICHAO.Optimal search algorithm for detecting random constant speed targets with discrete time[J].System Engineering and Electronic Technology，2013，35（8）：1627-1630.（in Chinese）

[5]HELLMAN O.Optimal search for a randomly moving object in a special cases[J].Journal of Applied Probability，1971，8（3）：606-611.

[6]MANGEL M.Search for a randomly moving object[J].SIAM Journal ofApplied Mathematics，1981，40（2）：327-338.

[7] HELLMAN O.On the optimal search for a randomly moving target[J].SIAM Journal of Applied Mathematics，1972，22（4）：545-552.

[8]MANGEL M.Probability of success in the search for a moving target[J].Operations Research，1982，30（1）：216-222.

[9]HELLMAN O.On the effect of a search upon the probability distribution of a target whose motion is a diffusion process[J].The Annals of Mathematical Statistics，1970，41（5）：1717-1724.

[10]OHSUMI A.Stochastic control with searching a randomly moving target[C]//Proceeding of American Control Conference，1984：500-504.

[11]陈建勇，王健.对随机运动目标的一种最优搜索算法[J].海军航空工程学院，2013，28（4）：456-458.CHEN JIANYONG，WANG JIAN.An optimal search algorithm for random moving targets[J].Journal of Naval Aeronautical and Astronautical University，2013，28（4）：456-458.（in Chinese）

[12]张弛，陈建勇.有限探测区域最大概率探测点寻优算法[J].兵器装备工程学报，2016，37（4）：118-122.ZHANG CHI，CHEN JIANYONG.Optimization algorithm for maximum probability detection point in limited detection region[J].Journal of Ordnance Equipment Engineering，2016，37（4）：118-122.（in Chinese）

[13]金惠明，李建勋.反潜直升机吊放声纳搜潜策略分析[J].电光与控制，2011，18（8）：26-28，39.JIN HUIMING，LI JIANXUN.Analysis of helicopter anti submarine sonar submarine search strategy[J].Electronics Optics&Control，2011，18（8）：26-28，39.（in Chinese）

[14]李长明.离散搜索力的最优配置模型及增量搜索计划[J].火力与指挥控制，2004，29（5）：25-27.LI CHANGMING.Optimal distribution model of discrete search power and increment search plan[J].Fire Control&Command Control，2004，29（5）：25-27.（in Chinese）

[15]陈建勇，曲晓慧，王健.随机运动目标有限区域探测的概率事件收益[J].系统工程与电子技术，2014，36（6）：1039-1043.CHEN JIANYONG，QU XIAOHUI，WANG JIAN.Probability event returns for the finite area detection of a random moving target[J].System Engineering and Electronic Technology，2014，36（6）：1039-1043.（in Chinese）

[16]陈建勇，冷江，于传健.使用吊放声纳的直升机应召搜潜发现概率[J].海军航空工程学院学报，2004，19（5）：559-561.CHEN JIANYONG，LENG JIANG，YU CHUANJIAN.The detection probabilities of on-call helicopter antisubmarine search using dipping sonar[J].Journal of Naval Aeronautical Engineering Institute，2004，19（5）：559-561.（in Chinese）

[17]陈建勇，张驰.随机恒速运动目标的搜索方程及持续探测概率[J].海军航空工程学院学报，2015，30（6）：521-525.CHEN JIANYONG，ZHANG CHI.Search equation for a moving target with random constant velocity and the probability of persistence detecting[J].Journal of Naval Aeronautical and Astronautical University，2015，30（6）：521-525.（in Chinese）

[18]ALIEXANDRIDIS M G.Mathematical formulation of the asw decision model.cognitive simulation of anti-submarine warface commander’s tactical decision Process[M].Washington D.C.：American Office of Naval Research，1984：55-59.