應用粒子群優化算法改進無人船航行路徑規劃研究

高 炳 王 林 張少明 陳錦濠

（1.廣東交通職業技術學院 海事學院 廣州 510800；2.廣東省船舶自動化工程技術研究中心 廣州 510800）

0 引 言

無人船艇在軍用和民用領域都有應用，成為相關領域的研究熱點和趨勢。無人船在海上巡邏、調查、監測和掃雷、海上搜救、垃圾清潔和環境監測等方面的應用已有多項案例，并獲得一定成果。路徑規劃對于無人駕駛船艇的航行自動化和航線優化具有重要意義。這項技術要求在復雜的海洋環境中，根據已知地理信息數據，找出一條從開始到結束的最安全、最短的航行路線。目前，在航線規劃中應用了很多算法，如蟻群算法、人工勢場法、神經網絡算法和粒子群優化算法。

由無人船航線規劃已有的案例和成果數據發現，在使用傳統算法時易被困在局部最優、控制精度和抗干擾適應性不夠等問題，因而有針對性地提出應用粒子群優化算法來改進無人船航行路徑規劃；通過在粒子初始化過程中加入適應度函數等改進方法，使路徑種群在初始化過程中更加有效，以實現求解更優航跡。

1 FR 無人船設計與實現背景

作者團隊在廣州開發的小型FR 無人船（第一版）融合了智能傳感，應用了基于PLC 控制器的軟硬件設計，并實現了小型無人船智能控制解決方案，在試驗水池內進行測試和控制，可達到一定范圍內的自主導航和遙控性能要求，如圖1所示。該解決方案采用一對多上位機控制策略，無線透明傳輸技術測試遙控器。

圖1 小型FR 無人船硬件框架及試驗水池測試圖

FR 無人船以油污的提取與檢測為主要模擬設計功能，監測并采集15%的油污染信號。無線透明傳輸模塊采用433～480 MHz、RS485 端口PLC為主要通信方式，聯合遠程控制技術、4G 網絡模塊，組合百度GIS 定位模塊。LIKONG 組態配置主機的HMI 和后端數據庫管理，并利用該方法策略操作自主導航計算，實現上位計算機監測和自主導航功能。

該設計解決方案減少了用于檢測船舶方向和控制船舶航向的轉向裝置。雙舷外部直流電動機被用來提供動力，通過調節雙電動機的轉速來控制船舶的轉向。定制的1.4 m 船型實模配備防水防撞和抗磨裝置、錄像監控裝置及帶有警告燈的保護系統，并采用封閉式泡沫填充、完全隔絕水以及鞋底絕緣設計。其采用有刷直流電機，額定技術參數為：12 V、1 800 r/min、20 A；為保障一定的航行續航能力，還配置2 套12 V 鋰電池電源。

2 應用粒子群優化算法改進航跡規劃模型構建

粒子群優化算法在全局搜索能力、收斂速度和精度等方面具有優勢，現已獲得越來越廣泛的關注，是一種應用潛力很大的智能算法[11-12]。經典粒子群優化算法的主要缺點是易于困處局部最優，為此研究團隊提出改進粒子群優化算法，以提高全局尋優能力。

2.1 航行空間建模與粒子有效性判定

在FR 無人船航行避障的過程中，需要對無人船水域周圍環境進行適當描述，然后才能規劃有效的無碰撞航跡。在本研究設計航行域圖中，把FR 無人船的運動看作質點運動，柵格的粒度是在FR 無人船半徑的基礎上，添加安全預留距離（如圖2所示）。

圖2 水面障礙物膨化修正

如果實際水面障礙物形狀不規則，則將其按最大邊長補成由正方形柵格組成的水面障礙物區域。如果水面障礙物不滿一個柵格粒度，則將該阻障填充為一個柵格。把有阻障的柵格用Y 示意，沒有阻障的柵格用N 示意，便形成由Y 和N 組成的FR無人船航行空間S。工作空間S 中，每個柵格由坐標和序號組成，兩者相互對應。設航行域圖是n維，則生成的最優航跡數組也是n維的，其中設第h維解為q，在柵格地圖中表示第h行q列，并且表示該條航跡在第h行列的最小值為q。

粒子的有效性是指在粒子尋優過程中，生成的粒子（即航跡）具有可行性。如果生成的航跡中經過水面障礙物，則稱之為無效路徑。有效的粒子穿過水面障礙物時，存在穿行式和繞行式這2 種方式。建模時，由于對水面障礙物已進行膨化處理并考慮了安全預留距離，所以穿行式粒子也有效可行。

2.2 應用粒子群優化算法改進航跡規劃建模

FR 無人船水域航跡規劃可以抽象為：給定起始點S 和到達點D，依次找到n個航行經過的坐標點序列（即找到n個航跡點坐標），使無人船沿著這些航跡點順序依次組成的航跡段航行時，能夠有效避開已知的水面障礙物，并滿足特定的任務要求，以獲得最優或近似最優航線。由此，水域全局航線規劃的問題即是要如何獲得最有效的n個航跡點坐標的問題。

FR 無人船在水面航行，其n個航跡點坐標可以表示為：

設粒子群種群的范圍為M，全部粒子群即可用一個矩陣表示，即Pi={P1，P2PM},1 ≤i≤M。粒子群中的每個粒子都代表一條潛在的航行路徑。潛在航線是否最優或接近最優，與任務規劃時考慮的優化目標及約束條件有關，可采用不同的代價函數來表示。該代價函數值越小，表明對應粒子的適應值越好。代價函數的構建可參考人工勢場法的思想：阻障或易受攻擊的威脅區、傾覆的風險等需要盡量避免的約束條件可用“斥力”形式表示，斥力越大則代價也就越大。

本研究中路徑優化過程中所要實現目標的目標函數，分別為：Clength路徑長度、Cangle航行轉角、Cthreat水面障礙物避撞。在算法進行路徑點搜索時，使用適應度函數對路徑點進行評價，因此需要將上述的3 個目標函數轉化為算法的適應度函數。本文采用權重系數法來解決多目標函數向算法適應度函數映射的問題。通過為每一個目標函數分配一個權重值，然后將各目標函數加權求和即可得到適應度函數。

考慮到與水面障礙物的相撞以及長度代價和航行轉角代價，基于研究分析，FR 無人船航線的評價參數（即粒子i的適應度函數），可由式（2）確定：

式中：β1、β2、β3分別為權重系數，且β1+β2+β3=1.0；Ad(Pi)為粒子i的適應度函數，Ad(Pi)的值越小，說明該航線越優。

2.3 改進粒子群優化算法機理

改進粒子群優化算法的原理流程如圖3所示。

其中重點用能單元節能降耗集結了最多的細分項，包括既有建筑綠色化改造、空調節能、鍋爐節能、制氧節能等。以鍋爐節能為例，又細分出降低管道熱損失、合理設置供暖溫度、使用余熱利用設備等多項舉措。

圖3 改進粒子群優化算法的基本原理流程

給定起始點S 和到達點D 之間，基于以上改進的粒子群優化算法進行航線優化求解方法為：第一步進行初始化算法參數，包括粒子的初始當前位置、初始最好位置及對應的適應值、基本參數如粒子數、問題維數、初始化空間及搜索空間等。第二步輸入已知粒子位置、適應值等，計算粒子群體平均最優位置；計算粒子新位置的適應值Ad（Pi）以替代粒子當前最好位置；若新位置的適應值小于全局最好位置的適應值，則替代全局最好位置及其適應值，不然不變。

以上第二步輪回直到t=MAXITER。若全局最小適應值小于最大數的β3倍，則由對應的粒子群最優位置獲取規劃的最優航行路線，算法結束；若全局最小適應值大于最大數的β3倍，則取固定值1.0，循環以上第一、二步，然后輸出結果。若全局最小適應值仍大于最大數的β3倍，則指示航線不存在。

3 試驗及驗證

3.1 模擬仿真計算

為驗證上述改進算法的可行性和有效性，在全局靜態40×40 網格矩陣中分布水面障礙物。在參數和環境相同的情況下，對傳統與改進的粒子群優化算法進行仿真比較分析。

在模擬軟件界面指定FR 無人船任意起始點和到達點坐標，可以指定考慮避障的安全警戒距離和各項指標的權重等，其中粒子群規模、維數、單次仿真計算迭代次數、仿真計算總次數依次為40、20、2 000、10，并在廣東船舶自動化工程技術研究中心實驗電腦上運行測試。為了驗證本文算法的有效性，分別針對A、B、C 這3 種不同復雜程度的航行環境狀態進行多次仿真實驗，通過比較2 種算法得到最優路徑的最少時間、平均收斂迭代次數等觀測點，來評判2 種算法的優劣。根據建模假設運行環境狀態進行仿真實驗，表1和圖4為3 種航行環境狀態時2 種算法仿真結果對比。仿真結果顯示，考慮航速變化時，最小航跡長度上，改進粒子群優化算法比傳統粒子群算法一樣。在航跡耗時上，改良粒子群優化算法比傳統粒子群算法有不同程度的下降。特別是在比較復雜的航行環境狀態A 時，耗時減少8.84%。對比觀測點可以看出隨著環境復雜度的增加，改進粒子群優化算法的平均收斂迭代次數也要優于傳統算法，特別是在復雜度較高的航行環境狀態A 下，改進粒子群優化算法相比傳統算法的迭代次數降低34.82%，具有明顯優勢。

表1 3 種航行環境狀態時改進粒子群優化算法與傳統粒子群優化算法仿真結果比較

圖4 改進粒子群優化算法與傳統粒子群算法仿真結果柱形對比

3.2 水池模擬試驗

為了驗證本文提出的改進粒子群優化算法在真實環境下的航線規劃準確性、控制精度以及仿真計算的可靠性，筆者在室外開闊水池搭建了試驗平臺，并進行了應用改進粒子群優化算法的“FR”小型無人船水池航行與仿真計算對比試驗。在前文介紹的自主研制FR 無人船基礎上，試驗中申請單獨域名來實現GPRS 模塊與上位機之間的無線數據傳輸，而上位機與FR 無人船的交互傳輸具體實現形式分別是：上位機向FR 無人船發送航行目標位置坐標，FR 無人船向上位機傳輸其實際經緯度位置數據和監控視頻信息。開闊水池試驗時，上位機服務器通過上述單獨域名接入互聯網后，安置在距離試驗水池300 m 的實驗室內，分別針對A、B、C這3 種不同復雜程度的航行環境狀態進行對照試驗。

圖5至圖7分別是FR 無人船在環境狀態A、B、C 下的航行軌跡圖。圖中實線為FR 無人船在開闊水池的實測試驗航行軌跡，虛線為將各環境狀態對應的邊界條件輸入仿真模型所得仿真計算航行 軌跡。

圖5 在環境狀態A 下的FR 無人船航行軌跡圖

圖6 在環境狀態B 下的FR 無人船航行軌跡圖

圖7 在環境狀態C 下的FR 無人船航行軌跡圖

對照試驗結果顯示：FR 無人船的試驗航行軌跡與對應的仿真航行軌跡基本吻合，應用改進粒子群優化算法的FR 無人船能夠有效避開障礙物規劃航行軌跡。圖中試驗與仿真航行軌跡相比，在航程的中后段出現小幅偏折，原因在于該處附近設有循環水閥引起微小波浪，導致FR 無人船經過水池該處附近時航行軌跡偏折。

圖8 在環境狀態A 下的基于改進粒子群優化算法與基于傳統粒子群優化算法的航跡對照圖

由此說明：改進粒子群優化算法更接近全局最優，穩定性更好。傳統粒子群優化算法雖有一定的震蕩，但穩定性不好，易陷于局部最優。通過實驗可以看出：在復雜環境中，本文提出的改進粒子群優化算法對障礙物有一定的規避能力。從規劃的路徑來看，FR 無人船避開所有障礙物，并避開或跳出所遇到的局部最小值點，準確到達目標點。

通過上述仿真計算、試驗和驗證，本研究提出的改進粒子群優化算法能夠有效避開航行區域內的障礙物。其軌跡規劃速度明顯快于傳統粒子群優化算法，收斂迭代次數相對較少，路徑收斂速度快。改進的粒子群優化算法優化能力更強，速度更快，滿足FR 無人船運動實時控制響應的需求，適用于無人船全局航線的快速規劃。

4 結 語

本文在已開發的FR 無人船基礎上，分析其設計與實現背景，應用粒子群優化算法來改進航跡規劃，完成模型構建、算法優化、模擬仿真計算和試驗驗證。通過在粒子初始化時添加適應度函數加以修正改進，使路徑種群在初始化有較高的有效性，從而增進算法的整體收斂速度和航跡跟蹤精度。采用改進的粒子群優化算法使初始時每一個粒子不會因為路徑中某維解存在阻障，使該個粒子路徑的有效性大降。這樣就可最大限度拓寬粒子的路徑種群，因此算法在迭代中就可以在有效性普遍較高的粒子種群中挑選最優路徑。

仿真實驗結果顯示，應用改進粒子群優化算法在復雜環境中，FR 無人船能規避水面障礙物，逃離局部最小值點，準確到達設定點，收斂速度更快，滿足及時響應的需要。

本研究僅針對短時干擾下應用粒子群優化算法改進無人船的航跡路徑規劃優化方案，而針對長時持續干擾此法可能在求解航跡最優上出現波動和不穩定性，甚至可能不是最優解，此問題也將是下一步繼續深化研究的方向。