連續(xù)搜索路徑的最優(yōu)化計(jì)算

陳建勇, 陳長(zhǎng)康, 孫明軍

(1. 海軍航空大學(xué)電子信息工程系, 山東 煙臺(tái) 264001;2. 海軍航空大學(xué)研究生管理大隊(duì), 山東 煙臺(tái) 264001)

0 引 言

最優(yōu)搜索理論中,對(duì)連續(xù)隨機(jī)運(yùn)動(dòng)的目標(biāo)進(jìn)行連續(xù)搜索的最優(yōu)路徑規(guī)劃,仍是一項(xiàng)困難的工作。與其他形式的最優(yōu)搜索問(wèn)題相比,這一類問(wèn)題尚沒(méi)有系統(tǒng)的解決方法。文獻(xiàn)[1-2]建立了搜索狀態(tài)方程,并用射線法近似求解了搜索方程。文獻(xiàn)[3-4]針對(duì)隨機(jī)運(yùn)動(dòng)目標(biāo)搜索問(wèn)題,給出了目標(biāo)位置概率密度函數(shù)和發(fā)現(xiàn)概率的計(jì)算方法。文獻(xiàn)[5]討論了目標(biāo)的擴(kuò)散方程,結(jié)合貝葉斯效應(yīng)建立了最優(yōu)搜索的最優(yōu)控制問(wèn)題。文獻(xiàn)[6]根據(jù)給出的目標(biāo)模型和搜索者探測(cè)概率模型,提出隨機(jī)最優(yōu)控制問(wèn)題。文獻(xiàn)[7-8]研究連續(xù)時(shí)空搜索問(wèn)題,給出了最優(yōu)軌跡的必要條件,將最優(yōu)搜索路徑問(wèn)題化為最優(yōu)控制問(wèn)題。搜索路徑的最優(yōu)控制模型是具有一般性意義的最優(yōu)搜索模型。文獻(xiàn)[9]應(yīng)用隨機(jī)最優(yōu)控制理論,求解了對(duì)一維環(huán)形路徑上進(jìn)行特定隨機(jī)運(yùn)動(dòng)的目標(biāo)進(jìn)行搜索的最優(yōu)搜索路徑。文獻(xiàn)[10]針對(duì)連續(xù)馬爾可夫運(yùn)動(dòng)目標(biāo),建立了搜索者方向和速度均作為決策變量的搜索路徑規(guī)劃模型,給出了求解復(fù)雜搜索路徑問(wèn)題的改進(jìn)雙鏈遺傳算法。文獻(xiàn)[11]關(guān)于離散時(shí)間的最優(yōu)路徑優(yōu)化問(wèn)題,給出割平面法和線性化法兩種求解方法。文獻(xiàn)[12]針對(duì)三維空間離散時(shí)間最優(yōu)路徑優(yōu)化問(wèn)題,提出了分支定界法。

在討論了搜索狀態(tài)建模和一階搜索狀態(tài)方程求解的基礎(chǔ)上,建立了連續(xù)搜索路徑的最優(yōu)控制模型,并給出了最優(yōu)路徑的逼近算法。在滿足一階搜索狀態(tài)方程的隨機(jī)恒速目標(biāo)條件及有限指數(shù)探測(cè)函數(shù)條件下,應(yīng)用本文的算法,給出了3個(gè)算例,分別求得了給定搜索起始點(diǎn)和搜索時(shí)間的最大發(fā)現(xiàn)概率搜索路徑。

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

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

定義探測(cè)率函數(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)方程[13]

(1)

(2)

式中,i、j表示空間維度；a(x,t)為速度均值函數(shù)向量;C(x,t)為目標(biāo)隨機(jī)移動(dòng)量二階矩的時(shí)間導(dǎo)數(shù)矩陣。

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

b(x,t,z)u(x,t,T,Z)

(3)

-b(x,t,z)f(x,t,Z)

(4)

(5)

(6)

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

(7)

f(x,t,Z)=ρ0(x0)·

(8)

式(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)的特征線。

按照聯(lián)合概率分布密度函數(shù)f的定義,沿著軌跡Z搜索到t時(shí)刻,發(fā)現(xiàn)目標(biāo)的概率為

(9)

對(duì)于任意t∈[0,T],沿Z搜索到T時(shí)刻發(fā)現(xiàn)目標(biāo)的概率為

(10)

2 搜索路徑的最優(yōu)控制模型

在第1節(jié)對(duì)搜索狀態(tài)建模和一階搜索狀態(tài)方程的求解,及給出發(fā)現(xiàn)概率模型的基礎(chǔ)上,建立了連續(xù)搜索路徑的最優(yōu)控制模型。

令搜索路徑函數(shù)Z(t)∈Rm為系統(tǒng)狀態(tài)函數(shù),搜索者的運(yùn)動(dòng)速度函數(shù)V(t)∈Rm為控制函數(shù),則系統(tǒng)狀態(tài)方程為

(11)

控制函數(shù)約束為|V(t)|≤Vm。

按照搜索路徑Z從0時(shí)刻搜索到T時(shí)刻未發(fā)現(xiàn)目標(biāo)的概率為

(12)

(13)

初始時(shí)刻為0,初始狀態(tài)為Z(0),而終止時(shí)刻為t∈[0,T]的性能指標(biāo)函數(shù)為

(14)

將式(13)表示成時(shí)間積分形式為

Jt+J[Z(t),t]

(15)

式中,J[Z(0),0]為初始時(shí)刻為t∈[0,T],初始狀態(tài)為Z(t),終止時(shí)刻為T的性能指標(biāo)函數(shù)。

構(gòu)造哈密頓函數(shù)為

(16)

由動(dòng)態(tài)規(guī)劃原理知,對(duì)于使J[Z(0),0]取極小的Z*和V*,必使J[Z(t),t]取極小。

對(duì)于所有t∈[0,T],存在向量λ*(t),使得下列HJB(Hamilton-Jacobi-Bellman)方程成立,表示為

(17)

式中[13]

(18)

由于

(19)

(20)

得到

(21)

3 最優(yōu)搜索路徑逼近算法

基于對(duì)搜索狀態(tài)建模和一階搜索狀態(tài)方程的求解,建立了連續(xù)搜索路徑的最優(yōu)控制模型,結(jié)合動(dòng)態(tài)規(guī)劃原理,最優(yōu)搜索路徑的逼近算法流程圖如圖1所示。

圖1 最優(yōu)搜索路徑逼近算法流程Fig.1 Flow chart of optimal search path approximation algorithm

算法具體計(jì)算步驟如下。

步驟2給定初始搜索速度的向量序列{V0(k)},k=0,1,2,…,K-1;n=0;k=K-1;

步驟3根據(jù)向量序列{Vn(k)},計(jì)算路徑軌跡為Zn(k+1)=Zn(k)+Vn(k)Δt;

步驟4求k時(shí)刻一階搜索狀態(tài)方程的特征跡線解un、fn,un、fn空間中一點(diǎn)的求解如式(7)、式(8)所示,特征跡線求解為式(27);若k=-1,轉(zhuǎn)到步驟8;

步驟5在求得空間值un、fn下,結(jié)合式(28)計(jì)算b(x,t,Z(t),V(t)),由式(21)、式(16)分別計(jì)算λ(k)、Hn(Zn,Vn,λ(k),k);

4 算 例

4.1 目標(biāo)模型

由于從信息源獲得的目標(biāo)位置數(shù)據(jù)具有不確定性,定位誤差的隨機(jī)性構(gòu)成了目標(biāo)初始位置的隨機(jī)性。用圓正態(tài)分布描述目標(biāo)的初始位置分布,依據(jù)的是定位誤差的分布。而在沒(méi)有目標(biāo)航向判斷依據(jù)的情況下,目標(biāo)速度的圓正態(tài)分布是最為恰當(dāng)?shù)脑O(shè)定分布。

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

(22)

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

(23)

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

(24)

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

(25)

(26)

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

(27)

證明可得,研究的隨機(jī)恒速運(yùn)動(dòng)目標(biāo)滿足一階搜索狀態(tài)方程。

計(jì)算中取σ=2 nm,μ=8 kn。

4.2 探測(cè)模型

設(shè)搜索空間為二維空間,根據(jù)文獻(xiàn)[15]針對(duì)潛艇給出的探測(cè)模型,令探測(cè)率函數(shù)為

b(x,t,z)=

(28)

取探測(cè)器作用距離R=1 nm。

搜索起始時(shí)刻為0,終止時(shí)刻為T,設(shè)搜索速度|V|=300 km/h,目標(biāo)和搜索空間計(jì)算范圍為50 nm×50 nm,坐標(biāo)原點(diǎn)設(shè)在計(jì)算區(qū)域的中點(diǎn)。

4.3 算例1

設(shè)Z(0)=(-11 nm,-11 nm),T=15 min。

搜索起點(diǎn)、初始路徑經(jīng)12次路徑逼近計(jì)算得到滿足精度要求的最優(yōu)路徑及相應(yīng)的發(fā)現(xiàn)概率如圖2所示。

4.4 算例2

將算例1最優(yōu)路徑的終點(diǎn)作為搜索起點(diǎn),即Z(0)=(-2.9 nm,0.6 nm),T=15 min。

搜索起點(diǎn)、初始路徑經(jīng)10次路徑逼近計(jì)算得到滿足精度要求的最優(yōu)路徑及相應(yīng)的發(fā)現(xiàn)概率如圖3所示。

圖3 算例2的初始路徑和最優(yōu)路徑Fig.3 Initial path and the optimal path of the second analysis example

4.5 算例3

設(shè)Z(0)=[-22 nm,-22 nm],T=15 min。

搜索起點(diǎn)、初始路徑經(jīng)9次路徑逼近計(jì)算得到滿足精度要求的最優(yōu)路徑及相應(yīng)的發(fā)現(xiàn)概率如圖4所示。

圖4 算例3的初始路徑和最優(yōu)路徑Fig.4 Initial path and the optimal path of the third analysis example

5 結(jié) 論

基于搜索狀態(tài)函數(shù)f、u和搜索路徑函數(shù)Z的發(fā)現(xiàn)概率模型,是對(duì)發(fā)現(xiàn)概率的精確描述。但即使最簡(jiǎn)單的目標(biāo)隨機(jī)運(yùn)動(dòng)模型和搜索者約束,也無(wú)法獲得搜索路徑的最優(yōu)化解析解。根據(jù)動(dòng)態(tài)規(guī)劃原理,設(shè)計(jì)了最優(yōu)路徑的逼近算法。多個(gè)算例表明,該算法能夠收斂到一條最優(yōu)路徑上。關(guān)于算法收斂性以及局部最優(yōu)與目標(biāo)隨機(jī)性特征的關(guān)系,還需要進(jìn)一步的工作。

參考文獻(xiàn)：

[1] HELLMAN O. Optimal search for a randomly moving object in a special cases[J]. Journal of Applied Probability, 1971, 8(3): 606-611.

[2] MANGEL M. Search for a randomly moving object[J]. SIAM Journal of Applied Mathematics, 1981, 40(2): 327-338.

[3] HELLMAN O. On the optimal search for a randomly moving target[J]. SIAM Journal of Applied Mathematics,1972,22(4): 545-552.

[4] MANGEL M. Probability of success in the search for a moving target[J]. Operations Research, 1982, 30(1): 216-222.

[5] 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.

[6] OHSUMI A. Stochastic control with searching a randomly moving target[C]∥Proc.of the American Control Conference, 1984: 500-504.

[7] LUKKA M. On the optimal searching tracks for a moving target[J]. SIAM Journal of Applied Mathematics, 1977, 32(1): 126-132.

[8] FORAKER III J C. Optimal search for moving targets in continuous time and space using consistent approximations[D]. Monterey California: Naval Postgraduate School, 2011.

[9] 朱清新,卿利,彭博.隨機(jī)運(yùn)動(dòng)目標(biāo)搜索問(wèn)題的最優(yōu)控制模型[J].控制理論與應(yīng)用,2007,24(5):841-845.

ZHU Q X, QING L, PENG B. Optimal control model of search problem for randomly moving targets[J]. Control Theory & Applications, 2007, 24(5): 841-845.

[10] 張獻(xiàn),任耀峰,沈靜.連續(xù)時(shí)空最優(yōu)搜索者路徑問(wèn)題的改進(jìn)雙鏈遺傳算法[J].系統(tǒng)工程與電子技術(shù),2015,37(5):1092-1098.

ZHANG X, REN Y F, SHEN J. Improved double chains genetic algorithm for optimal searcher path problem in continuous time and space[J].Systems Engineering and Electronics,2015,37(5): 1092-1098.

[11] ROYSET J O, SATO H. Route optimization for multiple searchers[J].Naval Research Logistics,2010,57(8):701-717.

[12] SATO H, ROYSET J O. Path optimization for the resource-constrained searcher[J].Naval Research Logistics,2010,57(5),422-440.

[13] 陳建勇. 單向最優(yōu)搜索理論[M]. 北京:國(guó)防工業(yè)出版社, 2016: 156-169.

CHEN J Y. One-side optimal search theory[M]. Beijing: National Defense Industry Press, 2016: 156-169.

[14] 陳建勇,張馳.隨機(jī)恒速運(yùn)動(dòng)目標(biāo)的搜索方程及持續(xù)探測(cè)概率[J].海軍航空工程學(xué)院學(xué)報(bào),2015,30(6): 521-525.

CHEN J Y, ZHANG C. 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.

[15] ALIEXANDRIDIS M G. Mathematical formulation of the ASW decision model[M]. Cognitive Simulation of Anti-submarine Warface Commander’s Tactical Decision Process. American office of Navy Research,1984: 55-59.