潛艇在水深底質數據下的航線規劃

李宏彪，張永亮

（華北計算技術研究所北京100083）

潛艇的航線規劃是指在已有地形數據的基礎之上，根據潛艇的潛水深度范圍以及可作戰需求，進行三維空間分析規劃出一條合理且路程較近的航線。多數情況下，是基于Dem數據進行分析規劃的，但往往某些海域并無詳細可靠的Dem數據，而只有比較粗糙的水深底質或等深線數據，所以本文結合參考文獻5的分治算法構造不規則三角網的方法，設計了一種通過水深底質或等深線數據快速計算Dem數據用來作為三維空間分析規劃的基礎。此方法效率較高，完全達到了實時航線規劃的要求。

如此密集的網格利用地杰斯特拉算法進行航線規劃復雜度太高，而A星雖然效率高，但在柵格數據下會走太多的彎路，所以目前解決這類航線規劃的方法主要是智能優化算法，例如蟻群算法、遺傳算法等方法在全局范圍內搜索較優航線，但大多數方法效率還是達不到實時航線規劃的效果。本文設計了一種A星加模擬退火算法的方式來進行分析規劃航線，這樣A星的作用是保證效率，模擬退火的作用是保跳出局部最優在全局范圍內搜索，將二者優勢相互結合，通過實驗得到了比較理想的效果[1-11]。

1 基于不規則三角網的Dem插值

首先根據水深底質離散點構造三角網（圖1），然后遍歷三角網中的每一個三角形對三角形內Dem值未知的網格點根據公式（1）進行插值（圖2），由于潛艇本身具有一定的寬度和長度，所以在通過Dem柵格塊時要保證其直行或轉彎時可以通過，為此我們選取的網格寬度為大于等于潛艇長度的兩倍。在三角形ABC中O為待插值網格點其坐標為（x，y），三角形 ABC 的三點坐標分別為，高程值分別為

圖1 構造三角網

圖2 三角形內網格點的插值

設O到A的距離為LOA，O到B的距離為LOB，O到C的距離為LOC。根據距離對點O的Dem值DEMO成反比的假設，可得對O點的Dem插值公式為：

算法步驟[5]：

1）根據所需要的Dem密度構建網格。

2）根據高程離散點利用分治算法構造Delaunay三角網。

3）遍歷三角網中的每一個三角形，對內Dem值未知的網格點，根據公式（1）進行插值計算。

2 構造Delaunay三角網的具體步驟

2.1 局部最優化處理

理論上為了構造Delaunay三角網，Lawson提出的局部優化過程LOP（Local Optimization Procedure），一般三角網經過LOP處理，即可確保成為Delaunay三角網，其基本做法如下所示[7]：

1）將兩個具有共同邊的三角形合成一個多邊形。

2）以最大空圓準則作檢查，看其第4個頂點是否在三角形的外接圓之內。

3）如果在，修正對角線即將對角線對調，即完成局部優化過程的處理。

LOP處理過程如圖3所示。

2.2 Delaunay三角網的構造算法大體步驟

1）構造一個超級三角形，包含所有散點，放入三角形鏈表。

圖3 LOP處理過程

2）將點集中的散點依次插入，在三角形鏈表中找出其外接圓包含插入點的三角形（稱為該點的影響三角形），刪除影響三角形的公共邊，將插入點同影響三角形的全部頂點連接起來，從而完成一個點在Delaunay三角形鏈表中的插入。

3）根據優化準則對局部新形成的三角形進行優化。將形成的三角形放入Delaunay三角形鏈表。

4）循環執行上述第2）步，直到所有散點插入完畢[7]。

這一算法的關鍵的第2）步如圖4所示。

圖4 第2）步的操作過程示意圖

為提高效率本文在構造三角網時采用的是參考文獻[5]的分治算法，實驗證明效率可大大提高[5]。

3 利用A星算法求出起點到終點的一條合理路徑

在潛艇的潛水深度確定的情況下，一條合理路徑就是找到一條可以由起點到末點的路徑保證潛艇由此路徑通過時不會觸礁且此路徑規避敵方打擊區域。

在已通過插值計算出的Dem數據中，可以很快計算出哪些Dem柵格可以通過，哪些不可通過，即潛艇的可行區域。在此可行區域上可以利用A星算法求出一條合理路徑。A星算法的基本思想與具體步驟如下。

每當主角走一步，就在身邊的8個方向插上節點編輯，然后使用探路器，探路器會告訴主角，插的哪個節點標記距離目標的路徑比較短，然后下一步就走向那里，走到之后，準備又插，發現，有的地方已經插過了，或者旁邊有障礙物，不能插，就替換插過的節點的父節點，比較，是不是比當前的短，如果是，就讓當前的父節點等于，被替換的父節點。

從A星算法的基本思想可以看到A星算法結果唯一，這樣其實它就是一個帶有方向指導的廣度尋路算法，所以其不具備隨機性，所以它只可能繞開障礙物，找到一個較優的代價路線，對于智能地放棄當前最優進而尋找另一條更加優越的代價路線做不到，通俗地說它只顧當下而不考慮全局。尤其在此種密集的網格數據中A星算法的弊端更是明顯，當遇到障礙物時它在不斷地試探靠近目標時走了太多的彎路，所以A星算法只可以找到一條合理繞開障礙物的較優的代價路線，但所以為實現在全局范圍內搜索一條較優的代價路線必須引入帶有隨即性質可以跳出局部最優的優化算法。下一小節設將計一種A星+模擬退火算法尋找一條實用的規劃路徑。

4 A星+模擬退火算法尋找較優路徑

算法設計主要思想：由于A星算法的弊端，必須引入一種優化算法從全局搜索的角度出發，來解決其走太多的彎路的問題。其主要思路就是以A星算法規劃出的路徑為基礎，設定一種地理環境的隨機改變與原始路徑的隨機取舍再利用A星算法求出一條合理的路徑，將此路徑與原路徑進行代價比較，利用模擬退火的思想進行取舍，經過模擬退火的充分降溫，最后得到一條合理并且行程較短的實用路徑，這里目標函數就是全路徑的路程長度。

5 試驗結果與分析

試驗平臺是Microsoft Windows XP操作系統，機器配置為主頻2.93 GHz，內存為2.93 GB，采用VC++6.0實現，實驗數據為某海域水深底質數據，潛水深度為865米到700米。

構造三角網效果如圖5所示。

利用A星算法求出起點到終點的一條合理路徑效果如下：

A星+模擬退火算法尋找較優路徑效果如圖6所示。

實驗各步驟性能（耗時）：

構造三角網，耗時578 ms。

圖5 構造三角網

圖6 A星+模擬退火算法尋找較優路徑

Dem插值，耗時556 ms。

尋找較優路徑效，843 ms。

共計1 977 ms，而原始的方法耗時6 788 ms，性能提高了70%。

實驗結果表明：

1）基于水深底質可以快速地生成Dem數據，根據潛艇的潛水深度可以快速計算出其可行區域，在此基礎上可以利用A星算法計算復雜度低的特性快速計算出一條合理的路線；

2）在柵格數據下A星算法計算出合理的路線彎路太多，在實際中無法作為一條潛艇的航行路線；

3）A星算法計算出合理的路線為基礎結合模擬退火算法的全局搜索，可以去除A星算法走太多的彎路的弊端；

4）實驗結果表明A星算法的高效率加上模擬退火算法的全局搜索，可以快速地規劃處一條合理且較優的水下航行路線。

6 結論

在潛艇在水下的航線規劃中，A星算法雖然具有效率高的優勢，但存在著規劃路徑復雜的缺陷，地杰斯特拉算法雖然具有規劃出最優的路線但存在著算法復雜度高的缺陷。文中將水深底質數據通過三角網Dem插值后，基于插值計算出的Dem數據，將A星算法與模擬退火算法綜合應用，這樣可以既利用了A星算法效率高的優勢，而且可以通過模擬退火算法進行優化使得A星算法規劃出的路徑復雜的問題解決，達到快速規劃出潛艇在水下的合理并且實用航線。實驗表明，該方法在耗時時間與航線的合理程度上有比較實用的優勢。但同時，在實際應用中可以通過設置規避區域（敵方打擊區域、敵方可探測區域或山谷狹窄區域等）來得到不同的航線規劃，指揮員可以選擇符合作戰要求的航線。由于本文算法具有效率較高的優勢，所以可以根據戰時突發情況實時規劃航線來及時更新當下更符合要求的航線。另外，本文給出的是一條航線，在實際應用中如果將該航線周圍一定范圍的可通過的柵格塊也納入其中，從而形成一個通路區域，效果會更加理想，有助于判斷該航線是否符合作戰要求。

[1]胡鵬，黃杏元，華一新.地理信息系統教程[M].武漢：武漢大學出版社，2002.

[2]張宏，溫永寧，劉愛利，等.地理信息系統算法基礎[M].北京:科學出版社，2006.

[3]馬少平，朱小燕.人工智能[M].北京:清華大學出版社，2004.

[4]張永亮，朱美正，李欣.模擬退火粒子群算法在矢量數據壓縮中的應用[J].計算機工程與軟件，2005，37（9）:1303-1306.

[5]張永亮，朱美正，李欣，等.基于稠密與稀疏高程點的Dem插值[J].計算機工程與應用，2014，50（1）:167-174.

[6]史娟.基于地形分析的路徑搜索算法研究[D].武漢：華中科技大學，2005.

[7]武百超，吳捷，崔繼憲.一種三角網的快速生成算法[J].礦山測量，2010（1）：41-43.

[8]顧春雷，楊漾，朱志春.幾種建立DEM模型插值方法精度的交叉驗證[J].測繪與空間地理信息，2011（5）：99-102.

[9]應申，李霖，王明常，等.計算幾何在地圖綜合中的應用[J].測繪科學，2005（3）:64-66.

[10]Cormen T H，Leiserson C E，Ronald L，等.算法導論[M].潘金貴，顧鐵成，李成法，等譯.2版.北京：機械工業出版社，2011.

[11]齊英劍，池娟，張彬.基于Zernike矩亞像素邊緣檢測的改進算法[J].西安郵電學院學報，2010，15（5）：75-78.

[12]陳榮華，韓旭里，吳宗敏.某型擬插值的多項式再生性[J].計算機工程與應用，2010，46（1）：1-3.

[13]宋俊輝，馮巖.負載均衡的分布式系統任務調度優化算法[J].吉林大學學報（理學版），2017（2）:383-387.

[14]丁西明，段漢根，范益政.四叉樹分解的圖像插值[J].計算機工程與應用，2011，47（20）：191-193.

[15]馬力，王大翊，汪永生.基于SOA的Web服務應用構建關鍵技術研究[J].物聯網技術，2014（8）:76-79.

[16]鮑蕊娜，李向新，麻明，等.基于凸殼技術的Delaunay三角網生成算法研究[J].科學技術與工程，2011（4）:764-767.