陳長康，陳建勇，周家新

（海軍航空大學(xué)，山東煙臺264001）

在最優(yōu)搜索理論的研究中，對連續(xù)空間中的連續(xù)運(yùn)動(dòng)目標(biāo)進(jìn)行搜索，一般考慮的是連續(xù)空間的連續(xù)搜索路徑[1-2]。假設(shè)在連續(xù)的搜索路徑中，僅在某些時(shí)間段上，探測器實(shí)施探測，并且在探測過程中，探測器保持位置不變，這樣，搜索路徑問題，就變成探測點(diǎn)序列問題[3]。直升機(jī)吊放聲納搜潛是一種對目標(biāo)的搜索只能在離散時(shí)間上進(jìn)行有效的探測問題[4]，即探測點(diǎn)序列問題。文獻(xiàn)[4]計(jì)算了離散時(shí)間點(diǎn)上有限探測域的最優(yōu)搜索位置；文獻(xiàn)[5-6]給出了搜索狀態(tài)方程，并用射線法近似地對方程進(jìn)行求解；文獻(xiàn)[7-8]研究對隨機(jī)運(yùn)動(dòng)目標(biāo)進(jìn)行搜索的問題，給出了計(jì)算目標(biāo)位置概率密度函數(shù)的方法；文獻(xiàn)[9]討論了目標(biāo)的擴(kuò)散方程，并建立最優(yōu)搜索的最優(yōu)控制問題；文獻(xiàn)[10]由目標(biāo)模型和探測概率模型，提出隨機(jī)最優(yōu)控制問題；文獻(xiàn)[11]給出一維運(yùn)動(dòng)目標(biāo)最優(yōu)搜索的一種算法，并求得最優(yōu)的探測點(diǎn)位置；文獻(xiàn)[12]研究了一種基于梯度的尋優(yōu)算法求離散點(diǎn)探測概率最大點(diǎn)的尋優(yōu)問題；文獻(xiàn)[13]給出直升機(jī)搜潛初始探測點(diǎn)的選擇原則，考慮轉(zhuǎn)向延遲影響，進(jìn)而提出多機(jī)聯(lián)合搜索策略；文獻(xiàn)[14]針對提高直升機(jī)吊放聲納等離散搜索力的搜索效率，導(dǎo)出離散搜索力的最優(yōu)配置模型；文獻(xiàn)[15]根據(jù)給出的探測函數(shù)，研究了多個(gè)探測點(diǎn)的探測概率最優(yōu)問題；文獻(xiàn)[16]在一定條件下建立了目標(biāo)模型，研究了關(guān)于吊放聲納搜潛的探測點(diǎn)概率問題。

本文針對離散時(shí)間探測目標(biāo)這類問題，在討論了搜索狀態(tài)建模和一階搜索狀態(tài)方程求解的基礎(chǔ)上，建立了探測點(diǎn)序列的最優(yōu)控制模型，給出了一種最優(yōu)探測點(diǎn)序列的逼近算法以及縮短計(jì)算時(shí)間的簡化算法。在滿足一階搜索狀態(tài)方程的隨機(jī)恒速目標(biāo)條件以及有限指數(shù)探測函數(shù)條件下，將算法的2種形式應(yīng)用到算例，分別求得了給定探測起始點(diǎn)和搜索時(shí)間的最大發(fā)現(xiàn)概率的探測點(diǎn)序列。

1 搜索狀態(tài)方程及一階方程的解

設(shè)t∈T=[0,T]，令目標(biāo)空間X??n，搜索空間Y??m。定義搜索路徑函數(shù)Z∶T→Y，表示搜索者從0時(shí)刻搜索到T時(shí)刻所運(yùn)動(dòng)的軌跡，z=Z(t)，表示t時(shí)刻搜索者所處的位置。

定義探測率函數(shù)b(x,t,z)。定義搜索至t時(shí)刻未發(fā)現(xiàn)目標(biāo)和目標(biāo)位置的聯(lián)合概率分布密度函數(shù)f(x,t,Z)。定義t時(shí)刻目標(biāo)存在于x的條件下，從t時(shí)刻搜索到T時(shí)刻未發(fā)現(xiàn)目標(biāo)的概率，即目標(biāo)存活概率函數(shù)u(x,t,T,Z)。

目標(biāo)在Δt內(nèi)的隨機(jī)移動(dòng)向量具有二階矩的條件下，有搜索狀態(tài)方程[3]：

式（1）、（2）中：i、j表示空間維度；a(x,t)為速度均值函數(shù)向量；c(x,t)為目標(biāo)隨機(jī)移動(dòng)量二階矩的時(shí)間導(dǎo)數(shù)矩陣；ai(x,t)、cij(x,t)分別為a(x,t)的分量與c(x,t)的元素。

如果cij(x,t)=0，則搜索狀態(tài)方程化為一階方程。設(shè)向量函數(shù)和梯度向量均為列向量，一階搜索狀態(tài)方程為：

只要各個(gè)特征跡線不相交，那么，X空間中的任意一個(gè)點(diǎn)就僅有一條特征跡線通過。應(yīng)用終止條件u(x,T,T,Z)=1，初始條件f(x,0,Z)=ρ0(x)，可以得到搜索方程在特征線上的解：

式（7）中：x(τ),τ∈[t,T]是起點(diǎn)在x(t)，終點(diǎn)在x(T)的特征線。

式（8）中，x(τ)，τ∈[0,t]，是起點(diǎn)在x0=x(0)，終點(diǎn)在x(t)的特征線。

如果在0到t時(shí)刻不進(jìn)行探測，即b=0，在式（8）中有：

在式（7）中有：

按照聯(lián)合概率分布密度函數(shù)f的定義，設(shè)t∈[0,T]的探測點(diǎn)序列Z={zk}。按照Z搜索到T時(shí)刻，發(fā)現(xiàn)目標(biāo)的概率為：

2 探測點(diǎn)序列的最優(yōu)控制模型

在第1節(jié)對搜索狀態(tài)建模、一階搜索狀態(tài)方程求解以及給出發(fā)現(xiàn)概率模型的基礎(chǔ)下，建立了探測點(diǎn)序列的最優(yōu)控制模型。

對于搜索總時(shí)間T，有已知的時(shí)間序列為：

其中，t∈[tk,Tk],k=0,1,2,…,K表示探測實(shí)施探測的時(shí)間且在探測期間搜索者保持靜止，t∈[Tk,tk+1]表示搜索者轉(zhuǎn)移運(yùn)動(dòng)時(shí)間，期間探測器不探測。

設(shè)探測點(diǎn)Z(k)為系統(tǒng)狀態(tài)。令搜索者從Tk-1到tk的平均轉(zhuǎn)移速度為V(k)∈?m。系統(tǒng)狀態(tài)方程為：Z(k)=Z(k-1)+V(k-1)(tk-Tk-1)，Z(0)=z0控制函數(shù)約束：|V(k)|≤Vmax，Vmax為搜索者所能達(dá)到的最大速率。

將(Z)表示為初始時(shí)刻為0，初始狀態(tài)為Z(0)，終止時(shí)刻為T的性能指標(biāo)函數(shù)：

其中，f(x,T,Z,V)與前述的f(x,t,Z)意義相同，f(x,T,Z,V)指在函數(shù)f(x,t,Z)的基礎(chǔ)上考慮了聯(lián)合概率分布密度函數(shù)f與搜索者速度的關(guān)系。

初始時(shí)刻為tk，初始狀態(tài)為Z(k)，終止時(shí)刻為T的性能指標(biāo)函數(shù)為：

因?yàn)樵趖∈[Tj,tj+1]，探測器不進(jìn)行探測，有b(x,t,z)=0，從目標(biāo)存活概率函數(shù)的定義可得[3]：

根據(jù)動(dòng)態(tài)規(guī)劃原理，對于使J[Z(0),0]取極小的Z*、V*，必使以Z?(k)為初始狀態(tài)的J[Z(k),tk]取極小，即[3]：

動(dòng)態(tài)規(guī)劃的基本遞推方程為[3]：

3 最優(yōu)探測點(diǎn)序列的逼近算法

3.1 精確計(jì)算算法

在第2節(jié)建立了探測點(diǎn)序列的最優(yōu)控制模型的基礎(chǔ)上，結(jié)合動(dòng)態(tài)規(guī)劃原理給出一個(gè)最優(yōu)探測點(diǎn)序列的逼近算法。

1）對于搜索總時(shí)間T，有已知的時(shí)間序列為：

并給定初始狀態(tài)Z(0)；

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

3）n=0；

4）k=K-1；

5）據(jù)向量序列{Vn(k)}，計(jì)算探測點(diǎn)序列：Zn(k)=Zn(k-1)+Vn(k-1)(tk-Tk-1)；

6）求tk時(shí)刻一階搜索狀態(tài)方程的特征跡線解fn,un；

7）若k=-1，轉(zhuǎn)到步驟11）；

8）用最優(yōu)化方法，求J[Z(k),tk]極小的Vn?(k)；

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

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

11）計(jì)算(Zn,Vn)，若滿足精度：

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

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

14）結(jié)束。

3.2 簡化計(jì)算算法

在3.1節(jié)精確計(jì)算算法的基礎(chǔ)下，對算法進(jìn)行簡化以縮短計(jì)算的時(shí)間，具體簡化計(jì)算如下兩部分：

1）加大空間離散化計(jì)算所劃分的單元格面積，從而在不影響計(jì)算數(shù)據(jù)準(zhǔn)確性的情況下，通過舍去一定的計(jì)算精度提高了計(jì)算的效率。

2）整個(gè)算法的計(jì)算過程涉及大量的循環(huán)計(jì)算，其中，主要耗時(shí)在3.1節(jié)中步驟6）對fn、un的空間積分值的循環(huán)計(jì)算，因此對fn、un函數(shù)作如下簡化計(jì)算。

計(jì)算式（7）中un的方法和簡化方法：

式中：j=k,k+1,…,K；tk為探測點(diǎn)的探測初始時(shí)刻。精確計(jì)算中，在每段探測時(shí)間t∈[tk,Tk],k=0,1,2,…,K采用dτ=1 s的步長，依次計(jì)算對應(yīng)的b值后進(jìn)行乘積疊加，而簡化計(jì)算采取將每段探測時(shí)間的初始時(shí)刻tj對應(yīng)的b值與每段探測時(shí)間(Tj-tj)乘積求和作為積分的近似值。

計(jì)算式（8）中fn的方法和簡化方法：

式中：tj-Tj-1為探測點(diǎn)間隔時(shí)間，期間不探測，有探測函數(shù)b(x,t,z)=0。精確計(jì)算采用步長為dτ=1 s，依次計(jì)算b和??a(x(τ),τ)值后進(jìn)行累加。簡化計(jì)算采取將每段探測時(shí)間的初始時(shí)刻tj(j=0,1,2,…,k-1)對應(yīng)的b與??a(x(tj),tj)值與探測時(shí)間(Tj-tj)乘積求和，加上每段非探測時(shí)間的初始時(shí)刻Tj的??a(x(Tj),Tj)值與非探測時(shí)間tj+1-Tj的乘積求和作為整個(gè)積分的近似值。

4 算例分析

4.1 目標(biāo)模型

設(shè)初始時(shí)刻為0，目標(biāo)空間為二維空間，目標(biāo)的初始位置分布服從圓正態(tài)分布：

設(shè)目標(biāo)為隨機(jī)恒速運(yùn)動(dòng)目標(biāo)，其速度分布為圓正態(tài)分布：

目標(biāo)在t時(shí)刻速度的空間條件分布為[17]：

在x點(diǎn)的目標(biāo)速度期望值及其散度[17]為：

任意x(0)點(diǎn)所在的特征線方程[17]為：

很容易證明，隨機(jī)恒速運(yùn)動(dòng)目標(biāo)滿足一階搜索狀態(tài)方程。

計(jì)算中取σ=2 n mile，μ=8 kn。

4.2 探測模型

設(shè)搜索空間為二維空間，根據(jù)文獻(xiàn)[18]，給出指數(shù)型探測率函數(shù)為：

k=0,1,2,…,K，取探測器作用距離R=3 n mile。在t∈[0,T]，有搜索狀態(tài)方程（1）、（2）成立，對于t∈[tk,Tk]，令Z(t)=Z(k)=zk，表示探測期間搜索者保持靜止。

4.3 算例計(jì)算

4.3.1 算例一

應(yīng)用3.1的精確算法計(jì)算。

設(shè)搜索者進(jìn)行搜索過程的速度|V|=130km/h，即令給定的初始搜索速度的向量序列{V0(k)}中的速度大小為130km/h，目標(biāo)和搜索空間計(jì)算范圍為50 n mile×50 n mile，坐標(biāo)原點(diǎn)設(shè)在其中點(diǎn)處，將其離散化為200 m×200 m的單元格進(jìn)行計(jì)算；設(shè)Z(0)=(-11 n mile,-11 n mile)，T=94min，每個(gè)探測點(diǎn)探測時(shí)間為3min，探測點(diǎn)間隔時(shí)間為10min。計(jì)算結(jié)果如圖1所示。

圖1中，序號1為給定的探測起點(diǎn)，初始探測點(diǎn)序列任意給定，經(jīng)15次探測點(diǎn)序列的優(yōu)化計(jì)算，耗時(shí)約11 h，在滿足相鄰兩次計(jì)算的探測點(diǎn)序列的探測概率差小于0.1%的精度要求下，得到圖中給定精度要求的最大發(fā)現(xiàn)概率為0.6745的最優(yōu)探測點(diǎn)序列。

4.3.2 算例二

應(yīng)用3.2算法的簡化內(nèi)容進(jìn)行計(jì)算。

與算例一的假設(shè)條件相同，將目標(biāo)和搜索空間計(jì)算范圍離散化為400 m×400 m的單元格進(jìn)行計(jì)算，計(jì)算結(jié)果如圖2所示。

經(jīng)19次探測點(diǎn)序列的優(yōu)化計(jì)算，耗時(shí)約1 h，得到圖中給定精度要求的最大發(fā)現(xiàn)概率為0.618 5的最優(yōu)探測點(diǎn)序列。其中，圖2中的序號、序列等表示意義均與圖1相同。

5 結(jié)論

基于搜索狀態(tài)函數(shù)f、u和搜索路徑函數(shù)Z的發(fā)現(xiàn)概率模型，是對發(fā)現(xiàn)概率的一種精確描述，本文根據(jù)動(dòng)態(tài)規(guī)劃原理，設(shè)計(jì)了一種最優(yōu)探測點(diǎn)序列的逼近算法并給出其簡化計(jì)算形式，將算法的2種形式應(yīng)用到算例計(jì)算。算例表明，精確算法和簡化算法均能夠使任意給定的初始探測點(diǎn)序列收斂到一個(gè)滿足精度要求的最大發(fā)現(xiàn)概率的最優(yōu)探測點(diǎn)序列上，在優(yōu)先考慮計(jì)算效率并能容許一定的最優(yōu)性誤差時(shí)，簡化計(jì)算同樣能夠得到“最優(yōu)探測點(diǎn)序列”，并較精確算法的計(jì)算時(shí)長縮短了11倍。

該算法的兩種形式可解決直升機(jī)吊放聲納搜潛等一類離散時(shí)間探測問題，根據(jù)實(shí)際對計(jì)算效率與最優(yōu)性的優(yōu)先級要求，在給定精度條件下，提供最大發(fā)現(xiàn)概率的最優(yōu)探測點(diǎn)序列的重要參考與指導(dǎo)作用。

[1]肖斌，徐宏飛.搜索力最優(yōu)配置的求解與收斂性分析[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ī)動(dòng)目標(biāo)對搜索的最優(yōu)規(guī)避[J].軍事系統(tǒng)工程，2001，11（1）：4-9.WANG JINGQI，F(xiàn)AN KUIWU，ZHANG ZUILIANG.Optimal evasion of search by maneuvering target[J].Military System Engineering，2001，11（1）：4-9.（in Chinese）

[3]陳建勇.單向最優(yōu)搜索理論[M].北京：國防工業(yè)出版社，2016：152-168.CHEN JIANYONG.One-side optimal search theory[M]，Beijing：National Defense Industry Press，2016：152-168.（in Chinese）

[4]陳建勇，王健，單志超.離散時(shí)間探測隨機(jī)恒速目標(biāo)的最優(yōu)搜索算法[J].系統(tǒng)工程與電子技術(shù)，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ī)運(yùn)動(dòng)目標(biāo)的一種最優(yōu)搜索算法[J].海軍航空工程學(xué)院，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]張弛，陳建勇.有限探測區(qū)域最大概率探測點(diǎn)尋優(yōu)算法[J].兵器裝備工程學(xué)報(bào)，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ī)吊放聲納搜潛策略分析[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]李長明.離散搜索力的最優(yōu)配置模型及增量搜索計(jì)劃[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ī)運(yùn)動(dòng)目標(biāo)有限區(qū)域探測的概率事件收益[J].系統(tǒng)工程與電子技術(shù)，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ī)應(yīng)召搜潛發(fā)現(xiàn)概率[J].海軍航空工程學(xué)院學(xué)報(bào)，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ī)恒速運(yùn)動(dòng)目標(biāo)的搜索方程及持續(xù)探測概率[J].海軍航空工程學(xué)院學(xué)報(bào)，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.