顧及艦船運動約束的機動航線實時規劃方法*

周寅飛 張立華 賈帥東 戴澤源 劉 翔

（1.海軍大連艦艇學院軍事海洋與測繪系 大連 116018）

（2.海軍大連艦艇學院海洋測繪工程軍隊重點實驗室 大連 116018）

1 引言

在軍事上，艦船需要通過機動來變換陣位，達到戰術目標。當前的艦船機動主要是通過艦操繪算的方式進行規劃，該方法的本質是三角計算，既無法顧及艦船運動約束，也無法顧及機動海域的礙航區避障。因此，根據艦船機動的軍事需求，顧及運動約束與礙航區約束來為艦船機動實時規劃航線，能夠提升艦船機動規劃的高效性與安全性，具有現實意義。

近年來，國內外學者針對航線規劃已經開展了大量的研究。啟發式算法是一類具有代表性的航線自動生成方法，陳曉等[1]在Maklink圖上基于Dijkstra算法先生成初始航線，然后通過蟻群算法來優化和調整初始航線；張岳平等[2]利用神經網絡與模擬退火算法對航路規劃問題進行求解；潘明陽等[3]改進A*算法來對內河水網航行問題進行航路規劃；謝玉龍等[4]通過改進遺傳算法實現了船舶路徑的高效率規劃。這類方法的計算效率與規劃網絡的粒度關聯緊密，細粒度下計算效率相對較低。張立華等[5]基于繞行礙航區的原則提出了一種航路二叉樹航線自動生成方法，這種方法以空間分析、拓撲計算為理論基礎，能夠在矢量電子海圖數據平臺下進行航線規劃，運算效率相對較高。隨后，汪柱等[6]對航路二叉樹算法通過遞歸搜索等方法進行了效率改進；王濤[7～8]將艦船轉向、航道寬度等約束加入到了航路二叉樹算法中，分別提出了考慮轉向限制和顧及航道寬度的最短距離航線自動生成方法；顧尚定等[9]通過分析礙航區的拓撲位置關系，建立了船舶通行的拓撲地圖；戴澤源[10]將海圖多圖幅進行信息融合，優化了航路二叉樹算法的距離與安全可靠性。然而，航路二叉樹算法沒有考慮艦船機動所要顧及的機動航向、機動時間、艦船最大航速等運動約束，難以滿足機動航線規劃的要求。最小化snap方法是無人機軌跡規劃的典型算法[11～13]，該方法能夠顧及運動約束，在無障礙區域快速求解規劃航線。但由于無人機與船舶動力學模型的不同，通過原始最小化snap方法生成的航線與計劃航線的偏離較大、航程增加較多，與艦船機動航線規劃的目標要求不相符。

為此，本文提出一種顧及艦船運動約束的機動航線實時規劃方法。首先依據航路二叉樹算法預生成航線；然后根據船舶的定常旋回半徑及降速公式，對預生成航線的空間結構和時間配置進行重構；最后根據艦船機動所需，構造運動約束方程與目標函數，通過二次規劃求解，以期結合航路二叉樹算法與最小化snap方法的優點，顧及艦船運動約束，實時高效地為艦船機動規劃航線。

2 顧及運動學約束的航路二叉樹航線規劃方法

2.1 航路點預生成

航路二叉樹算法的生成示意圖如圖1所示，設起點為S，終點為T，礙航區為O1、O2。連接起點S與終點T，與該連線相交的、與S點最近的礙航區為O1；先對O1進行繞行，得到繞行路徑P1P2、和P3P4；從繞行路徑末端節點P2和P4再分別連接終點T，重復以上過程，直至末端節點與終點的連線和障礙區沒有相交關系。通過以上過程，能夠生成所有繞行路徑組成的航路二叉樹鏈表，遍歷二叉樹則可得到起點S與終點T間的最短距離路徑。

圖1 航路二叉樹生成示意圖

2.2 預生成航路點的空間重構和時間配置

1）預生成航路點的空間重構

船舶的轉向具有一定的旋回半徑，然而航路二叉樹規劃出的航線是折線式的航線。在船舶操縱轉向的實踐中，通常會根據旋回半徑計算提前轉向點，當艦船到達提前轉向點即操縱船舶開始轉向。因此，本文以提前轉向點（例如圖2的B1點）、轉入下一航向的起點（例如圖2的C1點），對航路二叉樹算法預生成的航線進行重構。

圖2 艦船轉向處采點示意圖

如圖2所示，航段B1A1與航段A1C1的航向改變量θ叫做轉向角，船舶的定常旋回半徑為R。可作航段B1A1與航段A1C1以定常旋回半徑為半徑的外切圓，分別與航段B1A1相切于點B1，與航段A1C1相切于點C1。A1點的坐標設為(xA1,yA1)，航段B1A1與航段A1C1的直線方程已知，分別為y1=k1×(x-xA1)+yA1，y2=k2×(x-xA1)+yA1，則點B1、點C1的坐標可如式（1）進行求解，并用點B1、點C1取代點A1作為轉向控制點：

2）預生成航路點的時間配置

根據已經求得的航路點，可以計算得到任意父節點與子節點間的歐式距離，同時船舶的正常巡航速度已知，因此，可假設每段按勻速行駛，估算航路點間的時間序列為{t1,t2,t3,…,tn}。

預估時間的不合理，會致使之后生成的航線不符合運動學要求。船舶在轉向過程中會存在降速問題，在轉向節點間需依據降速系數，對其增加分配的時間。回轉降速系數k的計算公式為[14]

式中，v為轉向船速；v0為直航船速；K'為旋回性指數；CN為舵的法向力系數；θ為轉向角。因此，可為轉向曲線部分重新分配時間：

式中，R為定常旋回半徑，θ為轉向角，k為回轉降速系數，v0為直航船速。

2.3 約束方程構建與二次規劃求解

1）顧及機動目標與運動約束的方程構建

假設各個航路點間的航線可由多項式函數表示：

則為使規劃出的航線滿足運動學約束與機動目標要求，需對艦船起點與終點處的位置、航向、航速以及途徑點的位置進行約束，并使相鄰航線的位置、速度、加速度連續。

設從第j段航線的多項式系數向量為Pj，為滿足途徑點的位置約束，任一段航線的終點位置應與下一段航線的起點位置相同，即

為以指定速度到達目標位置，應使多項式的1階導數等于所需速度，即

其中，k為求導階數，i為多項式系數，j為航跡的段數，φ為所需設定的固定值。

為滿足各段間位置、速度、加速度的連續性約束，則應使前后段對應的次階導數相等，即：

其中，k為求導階數，i、l為多項式系數，j為航跡的段數。

2）目標函數構建與航線求解

以多項式表示航跡，可以通過保持導數的連續性確保平滑運動，并可以很容易地將一段航跡的端點選擇性地固定到期望的值。

多項式的階數n可由最小化目標函數確定，本文目標函數為變加速度的導數snap，則自由度為8，多項式系數n為7。則目標函數J為

式中，a1、…、aM是從第1段到第n段航路的所有多項式系數，Q為轉換得到的代價矩陣，則目標函數可列寫為J=pQpT。式（5）、（6）、（7）的等式方程約束，可同統一寫為矩陣Aeq與多項式系數向量P的乘積AeqP=deq。因此，通過上述等式方程和目標函數，可以有效地獲得一個QP問題的解，即統一寫成二次規劃問題的標準形式（9），通過二次規劃求解器進行求解：

3 仿真實驗

為了驗證本文方法的有效性，共設置兩組實驗，第一組實驗將本文方法與原始的最小snap方法進行比對，檢驗本文方法能否克服原始最小snap方法用于艦船航線規劃的諸多缺陷；第二組實驗目的在于檢驗本文所提方法的實時規劃能力。實驗所用船舶仿真模型參數如表1所示，其參數參照了文獻[8]的實驗設定。

表1 船舶模型參數

3.1 實驗一：與原始最小snap方法的對比實驗

本文與原始最小snap方法進行對比，以驗證所提方法能否有效克服原始方法所規劃航線與計劃航線偏離較大、航程增加較多的缺陷，起點、終點的航速、航向和位置設定如表2所示。

表2 對比實驗參數設定

實驗結果示意圖如圖3所示，黑色折線為計劃航線，紅色曲線是本文方法生成的航線，藍色曲線是原始最小snap方法生成的航線。實驗數據統計結果如表3所示，從結果可以看出，與原始的Minimum Snap方法所生成的航線相比，本文方法生成的航線與計劃航線的偏差較小，且因顧及運動約束的航程增加也較小，有效克服了原始方法的缺陷。

圖3 對比實驗仿真結果示意圖

表3 對比實驗的實驗結果

3.2 實驗二：實時機動規劃實驗

本實驗模擬艦船機動場景，假設從某一起始位置出發，需經過一中途點后轉向，以指定航向、航速到達指定陣位，通過本文所提方法進行機動航線規劃。具體實驗參數見表4，實驗結果示意圖如圖4所示，點線為設定航線，黑色曲線為本文方法生成的機動航線。為充分考慮機動的航向需求，該實驗分別設置艦船以八個方向的航向機動到指定位置。

圖4 機動規劃仿真結果

表4 實時機動規劃實驗參數

從圖4可以看出，本文規劃的航線，首先使艦船調整航向進入預定航線；然后在轉向位置前后通過轉向點附近旋回半徑解算的航路點進行轉向，進入下一計劃航向；最后在終點處調整航向到達終點。從表4可以看出，每次規劃的時間都在1s以內，基本能夠滿足艦船機動時根據任務、目標變化，實時規劃機動航線的需求。

4 結語

本文提出了一種顧及艦船運動約束的機動航線實時規劃方法，通過分析、計算及實驗比對，驗證了本文算法能夠充分顧及艦船運動約束，當前航向、航速，以及機動所需航向、航速的需求，實時高效地規劃機動航線。

然而，當前算法尚不能對艦船機動中的動態目標進行機動航線規劃，有待進一步的研究。