連續搜索路徑的最優化計算

陳建勇, 陳長康, 孫明軍

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

0 引 言

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

在討論了搜索狀態建模和一階搜索狀態方程求解的基礎上,建立了連續搜索路徑的最優控制模型,并給出了最優路徑的逼近算法。在滿足一階搜索狀態方程的隨機恒速目標條件及有限指數探測函數條件下,應用本文的算法,給出了3個算例,分別求得了給定搜索起始點和搜索時間的最大發現概率搜索路徑。

1 搜索狀態方程及一階方程的解

設t∈T=[0,T],令目標空間X?Rn,搜索空間Y?Rm。定義搜索路徑函數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內的隨機移動向量具有二階矩的條件下,有搜索狀態方程[13]

(1)

(2)

式中,i、j表示空間維度；a(x,t)為速度均值函數向量;C(x,t)為目標隨機移動量二階矩的時間導數矩陣。

如果Cij=0,則搜索狀態方程化為一階方程。設向量函數和梯度向量均為列向量,一階搜索狀態方程為

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

(3)

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

(4)

(5)

(6)

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

(7)

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

(8)

式(7)中,x(τ),τ∈[t,T]是起點在x(t),終點在x(T)的特征線;式(8)中,x(τ),τ∈[0,t],是起點在x0=x(0),終點在x(t)的特征線。

按照聯合概率分布密度函數f的定義,沿著軌跡Z搜索到t時刻,發現目標的概率為

(9)

對于任意t∈[0,T],沿Z搜索到T時刻發現目標的概率為

(10)

2 搜索路徑的最優控制模型

在第1節對搜索狀態建模和一階搜索狀態方程的求解,及給出發現概率模型的基礎上,建立了連續搜索路徑的最優控制模型。

令搜索路徑函數Z(t)∈Rm為系統狀態函數,搜索者的運動速度函數V(t)∈Rm為控制函數,則系統狀態方程為

(11)

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

按照搜索路徑Z從0時刻搜索到T時刻未發現目標的概率為

(12)

(13)

初始時刻為0,初始狀態為Z(0),而終止時刻為t∈[0,T]的性能指標函數為

(14)

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

Jt+J[Z(t),t]

(15)

式中,J[Z(0),0]為初始時刻為t∈[0,T],初始狀態為Z(t),終止時刻為T的性能指標函數。

構造哈密頓函數為

(16)

由動態規劃原理知,對于使J[Z(0),0]取極小的Z*和V*,必使J[Z(t),t]取極小。

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

(17)

式中[13]

(18)

由于

(19)

(20)

得到

(21)

3 最優搜索路徑逼近算法

基于對搜索狀態建模和一階搜索狀態方程的求解,建立了連續搜索路徑的最優控制模型,結合動態規劃原理,最優搜索路徑的逼近算法流程圖如圖1所示。

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

算法具體計算步驟如下。

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

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

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

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

4 算 例

4.1 目標模型

由于從信息源獲得的目標位置數據具有不確定性,定位誤差的隨機性構成了目標初始位置的隨機性。用圓正態分布描述目標的初始位置分布,依據的是定位誤差的分布。而在沒有目標航向判斷依據的情況下,目標速度的圓正態分布是最為恰當的設定分布。

設初始時刻為0,目標空間為二維空間,目標的初始位置分布服從圓正態分布

(22)

設目標為隨機恒速運動目標,其速度分布為圓正態分布

(23)

在t時刻，目標速度的空間條件分布為[14]

(24)

在x點的目標速度期望值及其散度[14]為

(25)

(26)

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

(27)

證明可得,研究的隨機恒速運動目標滿足一階搜索狀態方程。

計算中取σ=2 nm,μ=8 kn。

4.2 探測模型

設搜索空間為二維空間,根據文獻[15]針對潛艇給出的探測模型,令探測率函數為

b(x,t,z)=

(28)

取探測器作用距離R=1 nm。

搜索起始時刻為0,終止時刻為T,設搜索速度|V|=300 km/h,目標和搜索空間計算范圍為50 nm×50 nm,坐標原點設在計算區域的中點。

4.3 算例1

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

搜索起點、初始路徑經12次路徑逼近計算得到滿足精度要求的最優路徑及相應的發現概率如圖2所示。

4.4 算例2

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

搜索起點、初始路徑經10次路徑逼近計算得到滿足精度要求的最優路徑及相應的發現概率如圖3所示。

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

4.5 算例3

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

搜索起點、初始路徑經9次路徑逼近計算得到滿足精度要求的最優路徑及相應的發現概率如圖4所示。

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

5 結 論

基于搜索狀態函數f、u和搜索路徑函數Z的發現概率模型,是對發現概率的精確描述。但即使最簡單的目標隨機運動模型和搜索者約束,也無法獲得搜索路徑的最優化解析解。根據動態規劃原理,設計了最優路徑的逼近算法。多個算例表明,該算法能夠收斂到一條最優路徑上。關于算法收斂性以及局部最優與目標隨機性特征的關系,還需要進一步的工作。

參考文獻：

[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].控制理論與應用,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] 張獻,任耀峰,沈靜.連續時空最優搜索者路徑問題的改進雙鏈遺傳算法[J].系統工程與電子技術,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] 陳建勇. 單向最優搜索理論[M]. 北京:國防工業出版社, 2016: 156-169.

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

[14] 陳建勇,張馳.隨機恒速運動目標的搜索方程及持續探測概率[J].海軍航空工程學院學報,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.