1、基于定向模型的搜索和救援的問題摘要：本文提出一種新的方法去解決海上搜索和救援的問題。通過連接空間和持續時間，用飛機的最長的續航時間T，研究一種簡單的空中搜索資產模型。打算通過這個模型去最大化的檢測合作目標（搜索和救援）。提出的模型是基于假設現存的先驗信息（比如信息融合過程的結果），在可能的地理位置上去建立一個遏制空間分布可能位置的模型。這個可能性區域是基于一個定向模型獲得，這個模型不但運用了切割閾值去定義和牽制搜索路徑的概率而且還努力的按照不同的等級的經行搜索力度的分配。最后我們驗證模型在實例中的應用。關鍵詞：海上搜救 定向運動模型1.引言：本文，考慮運用MATLAB可視化界面快速海上墜毀飛機

2、落水點，本文，我們考慮通過區域聯通，連接空間和持續時間，用飛機的最長的續航時間T，去研究搜索路徑問題。其目的是最大限度的確定合作目標(搜索和救援)。先驗信息（如傳感器數據、專家的意見)可以用來建立一個可能的位置目標的空間分布信息。像這樣的分布可能是一種概率的，可能的，模糊的或任何其他類型的不確定性建模功能。導引頭或搜索器是一種空中平臺的機器配備有不同的傳感器(如掃描雷達、測繪雷達、光電、紅外線)。空中平臺有一個最大的飛行時間，被加油、任何其他系統或人類的約束所限制。因此問題在于去及時的確定一系列搜索行動的順序和去得到最大的找到目標所在空間的機會。在這種情況下搜尋活動將在兩個地區之間運輸，并且主

3、動搜索每個地區。搜索計劃應該及時提供搜救路徑幾乎以及分配搜尋力度針對每一個可能的區域。根據(Kierstead 和 Balzo 2003)的研究表明搜索路徑問題和精力分配問題密切相關。(Stone 1975)的搜尋理論認為目標和尋找者之間存在一種模仿的概率。第一次正式的提出搜索理輪的是Koopman (1980) 和美國海軍運行研究組織在第二次世界大戰中為了反潛戰提出的更好的策略。從那以后，搜索理論主要應用于監測、搜救任務和搜尋（如找到1980年消失的美國核潛艇蝎子號或者在在蘇伊士運河清除未爆炸武器）。搜索路徑的設計問題在很多正在進行的研究中都有涉及。在本文中，我們以數學規劃的角度提出一種新穎

4、的模型。本文結構如下：在第一部分我們針對搜索和救援問題提供一個概述；然后在第二部分回顧關于搜索和救援問題的相關工作；在第三部分我們將描述一個不同的搜尋和搜救問題，用這樣的方法我們開始去解決問題。首先建立一個可能的搜尋區域在第四部分，然后在第五部分用一個合適的定向模型去建立搜尋路徑并針對每個可能存在目標物的區域合理的安排搜尋力度。在第六部分我們將提供一個模型的實例驗證，最后在第七部分給出本文的結論。2.搜索和救援模型對大多數組織而言，資源管理對引導搜尋和搜救，監督和偵察任務是非常重要的部分。這個問題的特點是合理運用無人的移動設備（例如海上巡邏飛機、直升機、無人機、船舶）和固定的監督設備（如地面雷

5、達）對大面積地理區域進行識別，評估和追蹤最大數量的移動或靜止或漂移的目標。所搜尋的對象不一定能意識到被觀察，并且他們可能是配合的也可能是不配合的，可能是友好的也可能是敵對的。并且加上監控設備的稀缺（比如缺少光電、紅外線和合成孔徑雷達傳感器），追蹤能力（普通雷達模式），稀缺的空中設備，時間和空間的限制都使得搜索和搜救問題變得非常困難。搜索任務通常是計劃對于一個給定的搜尋區域考慮如何使得搜尋成本最小，時間最短，距離最短，危險最小化，以及運用有限的設備通過有效的搜尋，最大可能的成功搜尋到目標。搜索路徑規劃問題是棘手的，復雜的，因為它是多方面以及非確定性多項式難題即使對靜止的目標(Trummel 和

6、Weisinger 1986)。也有很多因素需要被考慮在內：l 平臺的配置和性能一般與平臺的物理和功能性能有關（比如飛機）；l 平臺的數量以及其配置；l 傳感器，或者其他被用來充當尋找者眼睛的儀器，雷達、聲吶、電視、照相機；l 被搜尋的對象或者目標可能是靜止的或者移動的，配合的或者不配合的，友好的或者敵對的；l 地理或者物理的搜尋區域可能是連續的（比如歐幾里得空間）或者離散的（一系列單元），可能是封閉的也可能是開放的。l 可用的搜尋目標可能是連續的（衡量時間或者追蹤距離）或者離散的（衡量限定數量的掃描或者查看）。為了增加SAR特區任務的效益，Abi-Zeid 和 Frost (2005)，基于

7、搜救理論和優化系統開放了一個決策支持系統（SARPlan）。SARPlan系統旨在最大化的利用有效資源以在更短的時間內盡可能多的發現幸存者。在搜索理論的基礎上，SARPlan系統給SAR特區任務提供了一個最佳的空中搜救計劃。SARPlan系統中約束滿足程序的CSP和傳統的優化技術被用來派生優化計劃。值得注意的是最優化計劃是一個計劃的概率搜索，預期達到能夠用最少的時間，搜尋最少的面積，運用最少的相關成本，最大的利用有效的資源找到搜尋目標。Doré et al. (2009)，針對搜索和搜救提出了一個擴展的搜尋理論。他們提出的這個理論相信功能對信息融合以及更新對優化搜索計劃內容非常重要。

8、離散路徑問題是基于假設搜尋者或者搜查人和目標在離散的時間和空間維度上移動。此外，關于離散時間的移動目標搜尋模型經常假設目標移動滿足馬爾科夫鏈屬性(Hong et al. 2009)。在目標滿足馬爾科夫鏈移動或者有條件的確定性移動的情況下，Dambreville 和 Cadre (2002)提出了一個優化搜索的算法針對搜索資源滿足廣義的線性約束而更新的問題。Eagle (1984)提出了最優動態規劃模型。Stewart (1979)提出了一種搜尋效應，當這種效應受到路徑的限制時，新穎的重新安置。Eagle 和 Yee (1990)擴展了Stewart (1979)的工作，提出了在7×7

9、搜索網格上的一種分支定界搜尋算法。這項工作可能會在Dell et al. (1996) 和 Hohzaki 以及 Iida (1997)上有所延展。Hong et al. (2009) 提出了一種創新的擬多項式算法去解決在單個搜尋路徑約束下的離散時間的馬爾科夫鏈式的目標搜尋。這種創新是基于一個大約沒有發現的可能的計算從條件概率反映在修復時間窗口的搜尋歷史。Jacobson 和 McLay (2006)同時提出一種廣義的爬山算法去決定在多個搜尋平臺上的最優搜尋策略。Kierstead 和 Balzo (2003)提出了一種遺傳算法（GA）對移動的目標規劃搜索路徑。在他的論文中，Janez (20

10、07)提出了一種模擬傳感器規劃問題就類似汽車調度問題（VRP）。這種構想是基于假設目標的坐標搜尋者是事先知道的。與前面提到的工作不同，目標的靜止的并且他們的位置是定義良好的。這樣問題的關鍵就是分配不同的檢測工具去檢測每一個目標。3.問題描述優先級劃分應急信號信息融合過程傳感器1傳感器2傳感器3空間密度可能性分布過濾過程資源分配路徑規劃任務分配飛行平臺任務行動效果評估圖1 簡化流程圖對于一種給定的搜索情況，令一個搜索者 s 與適當的傳感器在一個給定的平臺上組合。多個的搜索者可能會被安排前往不同的搜索區域。在每個搜索區域搜索路徑可能都遵循一種靜態或者動態的模式。本文旨在給一個特定的搜索者最優的路徑

11、搜索計劃。我們主要專注于空中搜索。我們假設這個過程如圖1所示。首先一個遇險信號可能會被搜索和救援中心接收，這將激活它的優先級過程。信息將會從不同的信息源傳遞出來（如傳感器）。信息融合過程將產生可能的目標位置空間分布。通過過濾過程，可以在搜索區域生成一個合川分布函數。我們假設先驗信息可以通過信息融合流程，關于如何合理的分布，利用目標在一個特定的控制區域來代表可能性（Kao et al. 2001)。這種強度分配可能涉及到更高程度的信心（比如可能性概率），因此對象更限制在一個特定區域的控制區域。此時，分布函數不一定是一個概率分布函數。為了去生成更多的智能分布地圖，可能會應用不同的聚類技術。一個好的

12、搜救計劃應該獲得最大的成功概率（POS），這樣才能最大概率的找到搜救目標。為了估計成功概率，我們使用另外兩種概率模型經行對比。一種是遏制概率（POC），反映目標在一定的搜索區域單元內的概率。另一種是檢測概率（POD），反映在搜索區域內傳感器檢測到搜索目標的概率。值得注意的是這種檢測概率是函數提供的傳感器在特定的區域內。為了簡化模型，我們假設檢測到目標的概率是和花費在搜索特定區域的時間有關的函數。我們簡化條件概率是為了表達在外側的傳感器的功能范圍，其掃描寬度設為W，以及的在區域的總時間(Frost 1998)。我們假設檢測概率遵循以下表達式： （1）其中表達在區域的有效掃描寬度，是區域j的表面積

13、，是平臺到達區域的速度，是相應水平的力度去安排到區域的時間。本文，我們提出了一種路徑規劃算法去最大化的找到配合的目標在一定的時間范圍內。這種模型的效果可能受到時間，搜索區域，追蹤長度或者其他的一些相應的指標所衡量。這三種概率模型的關系遵循以下表達式： （2）現在，問題的關鍵是去確定可能的搜索區域，并且去安排合適的空中搜尋設備找到目標，在一定范圍內優化一系列的目標。4：可能的搜索區域搜索的第一步在于識別可能包含搜索目標的邊界區域（PC）。主觀的信息如（規則，莊家評判）和客觀的信息（如歷史數據，傳感器融合的數據一般都用來去定義和約束這個區域。比如，國際海陸空搜索救援手冊就給出了建立這樣的可能區域的

14、指導方針。其他的一些方法比如概率分布函數或者模糊函數也可能被應用在建立搜索區域模型上。然后，將這個可能存在搜救目標的區域劃分為J個小單元。圖2 用2維視圖來展示目標可能分布的位置圖3 切割圖表示在每一次努力所能搜索到的最小的區域。在每一個小單元的搜索可能遵從一種預先定義或動態的模型。我們假設搜索的問題如圖2 所示。一個機載平臺的飛行路徑應該能夠有最大化的機會去找到目標在相應的地理區域上。飛機應該被限制飛行時間，因為目標可能會被限制生存時間。我們用不同的輪廓來代表遏制概率的分布的函數。用輪廓的濃度越濃代表概率越高。我們提出應用切割閾值的方法，由此我們得到如圖3所示的概率分布。閾值的價值可能會影響

15、搜索面積。更高價值的閾值可以使機載平臺飛越不同地區以及花費更多的時間在輪廓更密集和其他有價值的地方。這樣飛行路徑可能由圖4所示。圖4 飛行路徑因此，搜索區域是圖G=(V,E)的頂點（如圖5所示）。搜索平臺從頂點i = 1開始訪問其他地區(頂點)。為了表示在兩個區域i和j之間訪問，搜索平臺用表示時間(到所有的i)，值得注意的是，考慮到只有一個頂點驗證,其中是搜索和救援任務的時窗。5：定向模型搜尋和搜救問題只用一個搜救平臺（SARP）呈現一些類似的與定向問題做比較的可變利潤（OPVP）。這種（OPVP）是去找到一組汽車路線在開始和結束的起始點上，穿過一系列頂點的子集并且必須在總時間不超過一個給定的

16、限制（最大任務時間）。其中在每個頂點車輛搜集所占利潤的百分比決定了花費在這個頂點的時間(Erdogan 和 Laporte 2013)。OPVP和以下我們提出的模型對SARP1之間的差異是我們考慮到應用theMillerTuckerZemlin (MTZ)規劃處理子閉跡消去問題。圖5一個飛行路徑的實例5.1:變量l 是一個二進制變量。如果然后搜索平臺，在拜訪區域i后，將飛到區域j，否則，在一個區域比如i和j之間的飛行將不會被考慮在一個最優的飛行計劃。l 代表飛行的時間，搜索平臺將在區域i飛行的時間(有水平分配給區域i的時間決定)。5.2：約束條件第一個約束條件是限制搜救時間的，針對每個給定時間

17、的任務 （3） （4） 第二個約束條件確保了流保護在頂點上： （5）第三個限制條件確保每次飛行都必須包含頂點1 （6）最后一組約束是為了去確保不存在子集。在參考文獻中，很多模型都提出了消除子旅游問題(Miller et al.1960)。包括他們提出的MTZ公式(Kara et al. 2004): （7）其中是積極的變量，p代表飛行過頂點的數目。對于p=n的情況，MTZ模型對這種旅行商問題可以被使用。在文獻本質上，MTZ指定的許多擴展和推廣公式提出了旅行商問題(Sherali and Driscoll 2002)。這些MTZ規劃提出的擴展問題之一被Desrochers 和 Laporte (

18、1991)提出來去解決車輛路徑問題。 （8）其中代表關聯邊緣（i，j）的距離，代表從頂點1到頂點j的最短路徑的長度，代表從頂點j到頂點1的最短路徑長度。L是最大飛行距離，并且。在下列關系式中：并且，由此the Desrochers 和 Laporte 的公式 (8) 變成一下公式： （9）其中。然而一系列的約束（9）對SARP1并不是像我們假設的對所有的那樣有效，這將迫使最佳的路線必須包括所有的頂點。這個下界是有效的如果頂點j的被拜訪的路徑是最佳的（比如）。因此,我們建議將Laporte和Desrochers的公式重新闡述如下: （10）其中。命題1：制定SARP1(10)是有效的為了證明SA

19、RP1公式(10)是有效的,我們必須確認約束(10)消除子集的可行性以及可行的子集長度超過任務時間。考慮一個子集不包括頂點1：其中，且k=1,p并且。此外，并且總結從1到p-1的約束服從其中矛盾和所有的時間都包含在表1里面。表1每一對中心區域之間的飛行時間我們要證明，任何子回路時間長度不能超過任務總時間.考慮到下面的子回路：，其中，表示這個分段的長度。總的約束是，且 （11）對于有 （12）5.3:目標函數目標函數是最大化總的成功POSi的概率去訪問區域頂點 （13）其中代表在每個頂點i的可能的密閉度，它代表了我們正在搜尋的目標是區域的概率。（）5.4:非線性混合整數規劃模型首先提供一些非線性

20、混合整數規劃方程：其中6：驗證結果在本文中，我們考慮的問題如圖6所示。固定機翼監視飛機是在0的位置。信息融合過程建立了可能性區域如圖6所示。在我們應用一個切閾值后，我們得到了10個區域是包含目標的潛在位置。圖6檢測問題在這個應用中，每個區域的容積的概率的輪廓是圓形的。兩個區域之間的航空交通速度為650公里/小時。表1顯示了兩個區域中心之間的飛行時間。其中飛行時間是使用下面的公式計算： （15）其中R是地球半徑，和分別代表地球在中心區域i的半徑的長和寬。這個公式是基于球形地球上兩點之間的距離計算中心的半徑的經度和緯度，其誤差通常高達0.3%。遏制的概率（POC）從信息融合過程中獲得的每一個區域的

21、分布。表2為每個區域提供的累積概率。為簡單起見，對機載傳感器的掃描寬度是應該是恒定的，各地區在300米（0.3公里）相同。盡管如此，該模型處理變量清掃寬度。飛機搜索速度是恒定在350 km / h以內。在這里,可以考慮變量的搜索速度對于每個地區。表2提供了KA（KA= )和POC的價值以及需要計算目標函數(如Eq.13所示)。總體任務的時間是20小時(飛機降落在機場的時間應該不晚于t0 + 20 h)。然后提出監測問題是制定根據這個模型（如Eq.14所示）我們獲得一個非線性混合整數規劃:決策變量:144包括110整數數量限制:156與113的非線性表2每個檢測地區的參數我們建立一個計算機程序用

22、lingo12.0來解決這個問題。這個實驗測試用嵌件組合2 GHZ的筆記本電腦。解決方法在運行41分鐘29秒后獲得。估計POS(目標函數)的價值是0.606167。給出的解決方案如表3所示。表3最優結果我們得出的最優路徑是0-2-5-10-8-9-4-3-0如圖7所示(時間是以小時來計算)。圖7最優搜索路徑的映射搜索在開始。飛機從機場中轉，在區域2開始搜尋。從整個搜索時間分配到區域2 有1.5761小時。搜索模式在區域1是另外的優化問題，由空勤人員解決。如果目標沒有在區域2，那么該飛機將移動到區域5并且花費2.479小時的搜索時間。如果目標被發現，飛機可能恢復其常規日常例行作業或返回基地（機場

23、0）。區域之間的交通不總是被動的。該飛機繼續部署其傳感器和收集數據（沿過境路徑包含的概率通常是高于0）該模型提出了優化的路徑，以及在搜索空間中的每個區域的努力水平的分配。解決這個問題的執行時間可能被視為一個約束條件。該求解器花費最多的時間以提高從98到99%的最佳解決方案。如果我們接受98%的解，這個求解器生成一個潛在的優化解決方案在3分鐘以內， Erdogan 和 Laporte(2013)給出的線性的去解決OPVP以及CPLEX的使用能有助于減少執行時間。7：結論即使該模型是一個簡化的實際監控問題，但是它提供了一個新的角度去規劃和調度搜索活動的空間和時間約束的連續時間。該模型優化的路徑，以

24、及在搜索空間中的每個區域的搜索努力的分配，是通過添加額外的系統約束，目標函數和決策變量（包括不同類型的傳感器，或優化搜索速度）。該模型可以擴展，提出的模型假設一個靜態的狀態的世界。在飛行任務之前，該路徑是生成的，沒有額外的信息是隨著時間的推移而獲得的。然而，人們應該認識到，信息是隨著時間的推移獲得的。融合過程將繼續更新的空間分布的概率的遏制，這應該導致一個動態搜索問題的制定。參考文獻【1】Abi-Zeid I, Frost JR (2005) SARPlan: a decision support system for Canadian search and rescue operations

25、.Eur J Oper Res 162(3):630653【2】Dambreville F, Le Cadre JP (2002) Detection of a Markovian-target with optimization of the search efforts under generalized linear constraints. Naval Res Logist 49(2):117142【3】Dell RF, Eagle JN,Alves Martins GH, Garnier SantosA(1996) Usingmultiple searchers in constra

26、ined-path moving target search problem. Naval Res Logist 43(4):463480【4】Desrochers M, Laporte G (1991) Improvements and extensions to The MillerTuckerZemlin subtour elimination constraints. Oper Res Lett 10(1):2736【5】Doré PE,Martin A, Abi-Zeid I, Maupin P, Jousselme AL (2009) Theory of belief f

27、unctions for information combination and update in search and rescue operations. In:The proceedings of the 12th internationalconference on information fusion Seattle, Washington, pp 514521【6】Eagle JN (1984) The optimal search for a moving target when the search path is constrained. Oper Res 32(5):11

28、071115【7】Eagle JN, Yee JR (1990) An Optimal Branch, an optimal branch bound procedure for the constrained path moving target search problem. Oper Res 38(1):110114【8】Erdogan G, Laporte G (2013) The orienteering problem with variable profits.Networks 61:104116【9】Frost J (1998) The theory of search: a

29、simplified explanation. Report by Soza & Company Ltd and Office of Search and Rescue US Coast Guard Hohzaki R, Iida K (1997) Optimal strategy of route and look for the path constrained search problem with reward criterion. Eur J Oper Res 100(1):236249【10】Hong SP, Cho SJ, Park MJ (2009) A pseudo-

30、polynomial heuristic for path-constrained discrete-time Markovian-target search. Eur J Oper Res 193(2):351364【11】IAMSAR (1999) International Aeronautical and Maritime Search And Rescue Manual. ICAO/IMO publications Jacobson SH, McLay LA (2006) Optimal search strategies using simultaneous generalized

31、 hill climbing algorithms. Math Comput Model 43(910):10611073【12】Janez F (2007) Optimization method for sensor planning. Aerosp Sci Technol 11(4):310316【13】Kao D, Dungan J, Pang A (2001) Visualizing 2D probability distributions from EOS satellite image-derived data sets: a case study. In: Proceedings of the conference on visualization 01 San Diego. C