搜索論研究綜述*

劉軍偉 沙基昌 陳 超

(國防科技大學信C4ISR國防科技重點實驗室 長沙 410073)

1 引言

搜索論是軍事運籌學的一個分支,主要研究利用探測手段尋找指定目標優化方案的理論和方法。起源于二戰期間,因盟國在大西洋的海上交通運輸保障,受到德國潛艇的嚴重威脅,為了應對德國的潛艇,盟軍組織人員運用數學的方法對德國的潛艇實施搜索,取得了很好的效果。Bernard O.Koopman三篇名為“搜索論”論文的發表,把二戰期間研究搜索問題的基本理論作了介紹,搜索論正式作為一個研究內容被提出來。

二戰之后搜索論的原理已成功應用于許多重要領域,從大洋深處搜索潛水目標到對外層空間的人造衛星進行監視、偵察。如1966年在西班牙帕洛瑪附近的地中海海域搜索丟失的氫彈。之后搜索論被逐漸推廣應用到了資源勘探(地下或海底礦藏資源及水中魚群等資源),海空失事救援、航道搜掃,制導手段的探測目標等方面[1]。

本文從搜索理論、最優控制理論和對策論介紹了搜索論研究的內容,最后指出了目前搜索論研究的特點和存在的問題,給出了需要深入研究和完善的內容。

2 搜索理論

搜索理論是由和他的合作者在二戰期間創建的。搜索理論的發展經歷了四個時代[2]:經典時代、數學時代、算法時代和動態時代。經典時代(1942～1965)的主要代表是Koopman,他對靜止目標的最優搜索問題即搜索資源的最優分配問題進行了研究,他在靜止目標具有二元正態分布和探測函數具有指數函數形式的假定下研究了如何最大化發現目標的概率、并提出了在連續目標空間中且搜索資源連續可分的情況下進行搜索的資源分配方法[3～6]。在數學時代(1965～1975),主要是對最優搜索問題的數學本質進行研究,特別是靜態目標的搜索問題,并開發了相關求解工具。主要成果是Stone的《最優搜索理論》(Optimal Search Theory),它是對文獻[3～5]的完善和發展,解決了搜索問題的“最優搜索力配置存在的充分與必要條件”,研究的范疇仍然是對靜止目標的搜索問題,初步涉及了對兩種形式的動態目標的搜索,即“2單元格的馬爾可夫型運動(Markov Type Motion)”和“有條件確定型運動(Conditionally deterministic motion)”。其主要思想是用拉格朗日乘法將搜索力型運動條件約束的最優搜索力配置模型轉換為無約束條件的優化問題。1975～1985年被稱為搜索理論的算法時代。隨著相對廉價和高性能的計算機的普遍使用,這個時期的特點是人們將大量的研究精力轉向致力于解決運動目標的搜索問題,把搜索理論的研究重心逐漸從數學和分析方面的求解轉移到了從算法設計上去解決搜索問題。1985至今稱為動態時代。主要的特點是在搜索過程中引入反饋機制,搜索過程中依據得到的信息及時更改搜索計劃直到發現目標為止。

搜索理論由下面三個基本要素所構成:1)搜索目標,搜索是對搜索目標進行的搜索因此任何搜索問題均涉及到目標位置和移動路徑的概率分布函數;2)探測函數,給出了將投入到某個區域的搜索資源的數量與搜索目標位于該區域時成功探測到該目標的可能性大小聯系起來的函數關系;3)最優搜索計劃,在搜索過程,根據目標的分布函數,對所擁有的有限的搜索力在一定成本約束下如何分配才能使發現目標的概率最大。最優搜索問題可分為靜止目標搜索問題和運動目標搜索問題。下面分別對靜態目標搜索問題和動態目標搜索問題進行綜述。

2.1 靜態目標搜索問題

靜態目標搜索問題的研究成果是建立在Koopman,Dobbie,Gluss,De Guenin,Staroverov,Matula,Kadane,Onaga,Wegener,Chew,Mela,Tognetti,Weisinger等人的工作之上。Koopman最早提出了靜態目標最優離散搜索模型,即Koopman模型。之后,De Guenin將Koopman模型推廣到了連續空間中具有正規探測函數的搜索問題,給出了使得搜索函數達到最大值的正規探測函數須滿足的必要條件。Staroverov研究了離散空間中具有正規探測函數的搜索問題。與前兩者不同的是,Staroverov采用了使得查找和發現目標的時間期望值達到最小化的優化準則,而前兩者采用的是使成功發現目標的概率最大化且總的搜索成本小于預算值作為優化準則。Mela通過采用初等方法進行論證,證明了探測搜索(Detection Search)的最優搜索策略和行蹤搜索(Whereabouts Search)的最優搜索策略是不一樣的。探測搜索是指在搜索資源成本的限定的情況下選擇一種搜索策略使得找到目標的可能性最大;而行蹤搜索是指在搜索資源成本一定的情況下判斷目標最有可能出現的位置或區域。Chew研究了局部最優和全局最優搜索策略的關系,并被Kadane進一步推廣。Kadane的研究結果包含在Neyman-Pearson定理中。

上述經典的靜態目標最優搜索問題的主要結果都在基于已知目標的概率分布函數為假設前提的。朱清新研究了目標分布函數未知情況下的最優搜索問題。在此情況下的主要問題是如何選擇一個好的目標分布函數,從而使得探測概率達到最大,并且需要計算非真實目標分布函數下設計搜索策略的誤差。朱清新的研究考慮由最優搜索策略得到的探測概率的上下界,給出了在決策目標分布函數時的一些選擇準則,并對搜索空間是兩個單元格的情形做出誤差估計,并將結果推廣到N個單元格的情況[7～12]。

2.2 動態目標搜索問題

上世紀70年代中期到80年代中期,在軍事需求實用化的推動下,搜索論進入了動態目標的搜索算法研究。到目前為止與研究動態目標的相關著作和論述可分為以下兩類[12]:一類文章是討論作某種特殊類型的運動的目標,并且這種運動目標的搜索問題可轉化為用分析的方法去解決;另一類文章是基于1977年Brow n的觀察報告的基礎上,旨在建立針對動態目標的搜索問題的一般情況下的充分必要條件。在這些與動態目標有關的搜索問題的文獻中,人們著重對兩種特殊類型的運動目標進行了研究。第一類目標是有條件的確定動態目標,且具有可分解因子的雅可比行列式,這種類型的問題常常被簡化為關于靜態目標的一個等價問題,并最終可以用求解靜態目標搜索問題的方法加以解決。第二類目標是作馬爾可夫運動的目標。

按照目標是否對搜索者的行動做出反應來分,可把動態目標的搜索問題分為單邊搜索(One-si-ded Search)和雙邊搜索(Two-sided Search)問題,有的文獻也稱為單向搜索和雙向搜索。在單向搜索問題中,目標不能對搜索者的行為做出反應;與此相反,在雙向搜索問題中目標能夠對搜索者的行為做出反應。雙邊搜索問題有時也被稱為搜索博弈(Search Games)問題。

2.2.1 單向搜索問題

單向搜索問題可以分為以下兩種不同的類型:1)最優搜索密度問題;2)最優搜索路徑問題。當搜索資源能夠任意劃分,并且在一定的時間和空間中的搜索資源的應用不會對其它時間和空間中的搜索資源的應用帶來任務限制的問題就是最優搜索密度問題;而最優搜索路徑問題是指在某個時間的搜索資源的配置對一個后續時間的搜索資源的配置施加某種約束。在搜索路徑問題中,通常搜索者的運動速度和目標運動速度大致相同,如一艘潛艇搜索另一艘潛艇的情況;而最優搜索密度問題對搜索者的運動速度比目標的運動速度大得多的情況提供了一個合理的近似表達,如一架飛機搜索一艘在海上失事的船只的情況。

大多數用于計算動態目標的最優搜索方案的算法只適用于單向搜索問題。1)最優搜索密度問題算法。Brown應用Karush-Kuhn-Tucker條件設計出計算離散空間和時間中按照馬爾可夫運動的目標的最優探測搜索資源的分配算法[13],他將運動目標的搜索問題轉化為一系列的靜止目標搜索問題加以解決。Stone在1975年提出了針對任意離散時間的運動目標和指數形式的探測函數的算法[14],之后又給出了關于正規探測函數的最優探測搜索問題的充分必要條件,允許用本質上可以是任意的隨機過程去建立目標的運動模型[15]。并在1981年他與Discenza設計出計算生存者搜索問題的最優方案的算法[16],與Kadane設計計算運動目標的最優行蹤搜索方案的算法[17]。Washburn提出了向前向后(forward and backward,FAB)搜索算法是對Brown的算法的推廣,使Brown算法可應用于更廣泛的一類支付函數,而不限于只適用于使得探測概率達到最大值的問題[18]。2)最優搜索路徑問題算法。Trummel證明了離散時間和空間的最優搜索路徑問題是一個NP完備性問題[19]。Ohsumi用一個擴散過程來描述目標的運動,探測函數用指數形式給出,用標準的最優隨機控制理論的框架來解決連續時間和空間的搜索問題,從而得到一個動態規劃方程(Hamilton-Jacobi-Bellman方程),滿足這個議程的解決即可成為最優搜索方案的充分條件[20～21]。文獻[22～23]也是應用最優控制理論解決最優搜索問題。文獻[24]研究了目標在有限單元格進行馬爾可夫型運動,搜索者的搜索路徑受到限制的最優搜索問題,證明了最優搜索策略是固定的,并可由標準值迭代算法在有限的時間內計算出最優搜索策略。

此外,文獻[25]用貝葉斯方法研究了單一自動傳感器平臺對丟失目標的最優搜索,以空中飛機搜索海面艦船或海面漂浮物為背景,以搜索平均時間和探測概率為指標研究了最優搜索的解。文獻[26]研究了對隨機隱蔽目標的最優搜索策略問題。

2.2.2 雙向搜索問題

而對于多維連續空間的雙向搜索問題,文獻[29]得出以下結果,在二維或多維空間中,搜索者和規避者博弈問題的值υ滿足υ=u/g,其中u是搜索空間的Lebesgue測度,g是探測速率。要使規避者被捕獲時間大小(1-ε)u/g(規避者速度足夠大的情況下),規避者要采用如下策略:隨機選擇一點Z1,并停留一段確定時間D,然后隨機選擇另一點Z2(獨立于Z1),以最大速度移動到Z2,并停留時間D,如此反復。停留時間不應用太長,但另一方面,為了使在移動期間被捕獲的概率較小,規避者也不應該太頻繁地移動,即D不應用太短。多維空間中的搜索博弈問題的一個重要特性是存在一個以指數階遞減的函數P(t),使得對所有的t,在T時刻以后搜索者的捕獲率約等0。

文獻[30]主要針對已有的研究主要專注于雙方本身的各種約束條件的分析,而忽略了結合搜索域中的各處探測概率進行分析。在Washbum的離散搜索模型基礎上,提出了一種綜合考慮搜索花費和探測概率的雙邊搜索模型,用以描述雙方混策略的變化情況。

2.2.3 戰術性博弈問題

戰術性博弈問題是指研究與軍事背景相關的動態目標搜索問題。文獻[31]研究了潛艇與潛艇之間的追逐博弈。Baston在文獻[32]研究了搜索者和規避者沿著直線運動的搜索問題。Dubins研究了類似的問題[33]。Danskin研究了帶有聲納的直升飛機去探測一艘正在逃跑的潛艇的最優搜索策略[34]。Giammo[35]討論了兩支敵對軍隊在一個固定區域內互相搜索對方的問題。文獻[36～37]研究了規避者間能夠間歇性獲取搜索者所在位置信息的搜索問題,這種間歇性獲得信息的模型可用于海面上艦船通過聲波定位搜索潛艇的情況。

3 最優控制理論

由于搜索問題與最優控制問題的相似性,人們已經嘗試利用最優控制理論的結構框架去研究最優搜索問題,并取得一定成果。Ohsumi研究了探測一個做隨機運動的目標的最優搜索問題,他用一個隨機微分方程來描述目標的運動狀態,把搜索問題作為最優控制問題來描述,并通過找到一個能最小化搜索者探測失敗概率的控制信號來建立搜索者的策略[38]。他在文獻[39]中給出了目標運動模型和搜索過程模型,最優搜索策略通過最小化成本泛函實現。他將最優搜索問題作為一個使得具有指數形式的成本泛函達到最小化的最優控制問題來描述,其中的成本泛函反映了發現目標的探測概率。在文中引入了搜索函數的函數并給出了它的時間進化情況,檢驗了搜索問題最優控制存在性的充分條件,提出了為實施最優搜索而必須解決的Cauchy問題和求解這個Cauchy問題的一種有效方法,即用于解一階非線性微分方程的擬線性化技術,并給出了基于這種技術的兩種仿真結果。Mangel在文獻[40]中研究了只有一個搜索者的運動目標搜索問題。由于只涉及到常微分方程組,搜索密度函數 f(x,y,t,S)可通過漸進地求解密度函數所滿足的搜索議程而近似地計算,并計算出了關于目標位置和不成功搜索的聯合概率密度函數。

把最優搜索問題作為最優控制問題,利用動態規劃原理,可推導用于解決作隨機運動的目標的最優搜索問題的Hamilton-Jacobi-Bellman方程,可證明該方程的解就是所尋求的最優搜索策略,從而將原來的隨機運動目標的最優搜索問題對應的隨機系統最優控制問題轉化為一個確定性系統中的兩個等價問題,即解一個半線性二階偏微分方程和求一個連續可微函數的最小值問題,為復雜運動和隨機運動目標的最優搜索問題的解決開辟了一條新的途徑。

4 對策論

文獻[41]指出在軍事領域的搜索與反搜索是一種具有沖突對抗性質的對策。這種對策具有以下主要特征:1)雙方都在猜測對方可能會采取什么策略,從而以對方策略來決策自己的策略,即自己的策略是對方策略的反應;2)這種對策是一次性的,因此雙方各自只能采取自己的純策略;3)由于搜索與反搜索可能采取的策略中,它所要付出的代價或得到的利益,有時候是不易量化計算的,而且它的目標和結果主要在于采取一切可能手段去發現目標或不被發現,因此對抗結果的贏得,主要能表示出在所有可能的策略中采取什么策略對自己最有利,哪些對策結果出現對自己最好,或者說,雙方各自最希望出現什么對策的結果,最不希望出現什么對策結果。這就是說,對策的贏得主要以雙方各自對對策結果的選擇序來表示。基于以上特征,文獻[41]指出軍事領域的搜索與反搜索是比一般對策更高層次的對策,提出利用元對策的原理、對抗分析方法去建立搜索與反搜索的元對策模型。

5 結語

從以上搜索問題的研究現狀來看,到目前為止,對搜索問題的研究具有以下特點和問題:1)注重理論研究,離實際的應用還有一定差距,如Stone的《最優搜索理論》對靜止目標搜索問題的研究在理論上達到了成熟狀態,但是由于嚴格的假設條件、探測函數的正規性要求,使這些研究成果在現實的實用性受到了較大的限制。研究如何理論較好地應用到實際是搜索論形成的主要因素,也是以后在軍事對抗中以及其他方面應用搜索論要解決的主要問題;2)研究角度大多者是從搜索者的角度建立搜索模型,如使得搜索者的成功搜索概率最大化,搜索者的搜索成本最小等,基于規避者的角度研究的文獻相對不多。對基于規避者視角的規避搜索問題的研究是對搜索論內容的拓展;3)研究方法上,多數研究是把搜索問題作為一個決策問題來研究,即把某一方的策略固定后,再研究另一方的最優決策問題,這種研究方式簡化了軍事搜索問題的沖突對抗性,方便對搜索問題的研究,而且對搜索策略設計機制研究的文獻也很少。文獻[41]已經指出解決沖突對抗性質的對策問題的元對策方法,對我們的研究具有很好的借鑒意義,需要做進一步地深入研究。

[1]余濱,段采守.軍事運籌學[M].長沙:國防科技大學出版社,2008

[2]L.D.Stone.What's happened in search theory since the 1975 lanchester prize?[J].Operations Research,1989,37:6

[3]B.O.Koopman.Search and Screening[R].Center for Naval Analysis,1956

[4]B.O.Koopman.The Theory of Search,part 1:Kinetic Bases[J].Operation Research,1956(4)

[5]B.O.Koopman.The Theory of Search,part 2:Target Detection[J].Operation Research,1956(4)

[6]B.O.Koopman.The Theory of Search,part 3:The Optimun Distribution of Searching Effort[J].Operation Research,1957(5)

[7]Q.Zhu,N.U.Ahmed.Second order Hamilton-Jacobi-Bellman Equations in Infinite Demensional Banach Space[J].Proceedings of Dynamic Systems adn Applications,1994(1):415～422

[8]Q.Zhu,N.U.Ahmed.Danamic Programming Equations of Stochastic Optimal Control n Banach Space[J].Stochastic Analysis and Applications,1995,13(3):369～387

[9]Q.Zhu,N.U.Ahmed.Some Results on Parabolic E-quation Associated with Stochastic Optimal Control[J].Nonlinear Analysis,Theory,Methods and Applications,1995,24(9):1305～1319

[10]Q.Zhu,J.Oommen.On The Optimal Search Problem:The Case when the Target Distribution is Unknown[J].Proceedings of the Chilean Computer Science Society,1997(11):268～277

[11]Q.Zhu,J.Oommen.Optimal Search with Non-regular detection functions[J].Journal of University of Electronic Science and Technology in Chendu,1999:125～128

[12]朱清新.離散和連續空間中的最優搜索理論[M].北京:科學出版社,2005

[13]S.S.Brown.Optimal Search for Moving Target in Discrete Time and Space[J].Operations Research,1980,28:1275～1289

[14]L.D.Stone.Theory of Optimal Search[M].New York:Academic Press,1975

[15]L.D.Stone.Necessary and Sufficient Conditions for Optiaml Search Plans for Moving Targets[J].Mathematics of Operations Research,1979(4):431～440

[16]J.H.Discenza,L.D.Stone.Optimal Survivor Search with Multiple States[J].Operations Research,1981,29:309～323

[17]L.D.Stone,J.B.Kadane.Optimal Whereabouts Search for a Moving Target[J].Operations Research,1981,29:1154～1166

[18]A.R.Washburn.Search for a Moving Target:The FAB Algorithm[J].Operations Research,1983,31:739～751

[19]K.E.Trummel,J.R.Kadane.The Complexity of the Optimal Search Path Problem[J].Operations Research,1986,34:324～327

[20]A.Ohsumi.Stochastic Control with Searching a Randomly Moving Target[C]//Proceedings:1984 American Control Conference,1984

[21]A.Ohsumi.Algorithms for Optimal Searching and Control Systems for a Markovian Target[J].Control and Dynamic Systems,1986:99～118

[22]M.Lukka.On the Optimal Searching Tracks for a Moving Target[J].SIAM Journal of Apllied Mathematics,1977,32:126～132

[23]M.Mangel.Search for a Randomly Moving Object[J].SIAM Journal of Apllied Mathematics,1981,40:327～338

[24]S.Singh,V.Krishnamurthy.The optimal search for a Markovian target when the search path is constrained:the infinite-horizon case[J].Automatic Control,IEEE Transactions on,2003,48(3):493～497

[25]F.Bourgault,T.Furukawa,H.F.Durrant-Whyte.Optimal Search for a Lost Target in a Bayesian World[J].Springer Tracts in Advanced Robotics,2006,24:209～222

[26]O.B nichou,M.Coppey,M.Moreau,et al.Optimal Search Strategies for Hidden Targets[J].Phys.Rev.Lett.,2005,94(19):4

[27]R.Isaacs.Defferenctial Games[M].New York:Willey,1965

[28]S.Gal.Search Games[M].New York:Academic Press,1980

[29]S.Gal.Search Games with Mobile and Immobile Hider[J].SIAM J.Control and Optimization,1979,17

[30]A LPER S,GAL S.Rendezvous search on the line with distinguishable players[J].SIAM Journal of Control and Optimization,1995,33(4):1270～1276

[31]陳俊,王令群,鄭應平.基于離散模型的雙邊搜索博弈問題的研究[J].科技導報,2007,25(2):64～67

[32]A.Charnes,R.G.Schroeder.On Some Stochastic Tractical Antisubmarine Games[J].Naval Research Logistics Quarterly,1967,14:291～311

[33]V.J.Baston,F.A.Bostock.A High-Low Search Game on the Unit Interval[J].Mathematical Proceedings of the Cambridge Philosophy Society,1985,97:345～348

[34]L.Dubins.A Discrete Evasion Game[J].Annals of Mathematical Studies,1957,39:231～255

[35]J.M.Danskin.A HelicopterVerus Submarine Search Game[J].Operation Research,1968,16:509～517

[36]T.P.Giammo.On the Probability of Success in a Sudden Deach Search with International Moves Conflined to a Finete Area[J].SIAM Revies,1963,5:41～51

[37]S.P.Lalley,H.E.Robbins.Stochastic Search in a Conves Region[J].Probability Theory and Related Fields,1988,77:99～116

[38]M.Lehnerdt.On the structure of Discrete Sequential Search Problems and of their Solutions[J].Mathematis Operations and Statistic Series Optimization,1982,13:523～557

[39]A.Ohsumi.Optimal Searching for a Markovian Target and Relation to Optimal Stochastic Control[J].Theory and Applications of Nonlinear Control Systems,1986:569～583

[40]M.Mangel.Probabilit of Success in the Search for a Moving Target[J].Operations Research,1982,30:216～222

[41]張之駓.搜索論[M].大連:大連理工大學出版社,1992