無人船路徑規劃的研究

桂林信息科技學院電子工程學院 黃 東

隨著海上智能交通的發展，國內在自主航行的無人船方面開始發展起來。本文針對是無人船全局路徑規劃的研究，提出用柵格—蟻群算法和離散蟻群算法來進行無人船路徑的規劃，而且驗證了兩種算法在無人船的全局路徑規劃的可行性。通過仿真實驗，在規劃路徑過程中，柵格—蟻群算法有較好的魯棒性。而離散蟻群算法在搜索地圖方面比柵格—蟻群算法更加有效，規劃的路徑長度更短更平滑，規劃結果更加理想。

隨著智能化不斷的發展，無人船控制技術早已不是傳統的遙控技術，而是通過算法編程來實現自主航行。早期無人船研究的算法，它的控制方式主要是航向保持模式。如今無人船的自動控制已發展到了航跡保持模式。這需要無人船在任何復雜工作環境下都能夠保持自動航行的能為，并能自主制定一條合適的航線，無人船根據此航線前進到達指定目標。針對無人船路徑規劃，本文研究在無人船的路徑規劃上，分別對柵格—蟻群算法和離散蟻群算法這兩種算法進行討論，并對這兩種算法進行分析以及有效的改進，為無人船自主航行技術的研究提供新的思路。

1 柵格—蟻群算法

1.1 柵格—蟻群算法

蟻群算法是90年代意大利學者Marco Dorigo在他的博士論文中提出的，受到大自然中螞蟻覓食筑巢的行為影響，而研究發現螞蟻雖然沒有視覺，但是行走時可以釋放一種生物分泌物，行走這條路徑的螞蟻越多，這條路徑生物分泌物的濃度也越大，從而影響更多的螞蟻選擇這條路徑。蟻群通過這種生物信息素來實現路徑的選擇，受此啟發，這位學者提出了一種仿生進化算法，也就是蟻群算法。目前該算法廣泛應用于路徑規劃、數據挖掘、組合優化、函數優化、網絡路由優化等。

1.2 柵格蟻群算法流程

假設有一群螞蟻，數量有N只，每只螞蟻都從起發點開始出發搜尋食物。在柵格示意圖模型中，螞蟻的每一步行走都只能從自己所在柵格旁最近的柵格中選擇一個柵格前行。如圖1所示，當這只螞蟻處在（2,2）這個柵格位置時，它可以選擇的柵格就會有（1,1）、（1,2）、（1,3）、（2,1）、（2,3）、（3,1）、（3,2）、（3,3）總共8個柵格。假設（2,3）和（3,3）是存在障礙物的，也就是說（2,3）和（3,3）是不可行柵格，那么這只螞蟻就不會走這兩個柵格。

圖1 柵格—蟻群算法搜索過程示意圖模型

假設這群螞蟻中，第k只螞蟻處在一個柵格i上，這時它要選擇到一個柵格j的概率可以用式(1)表示。

α為信息濃度啟發因子，它是一個大于0的常數。β是期望啟發因子，也是一個大于0的常數，是螞蟻選擇下一個柵格位置的依據。G是這只螞蟻k在某一位置時允許選擇柵格的集合。每只螞蟻會在其經過的路徑上留下分泌物也就是信息素。第k只螞蟻在其經過的路徑上留下的信息素可以用式(2)表示。

C0是信息素強度，是大于0的常數。LK是螞蟻尋找到的路徑總長。當所有的螞蟻完成一輪搜索之后需要更新信息素，可以用式(3)表示。

P表示的是信息素的保留率，它的取值范圍是0≤ρ＜1。在更新信息素之后就會進入下一輪循環的搜索。通過這種方式經過反復的迭代之后，路徑距離較短的路徑上的信息素濃度會越來越大，信息素的積累也越來越多。當迭代達到一定數量之后，算法會收斂，也就是螞蟻去搜索食物的路徑會集中到一條信息素較多，也就是距離較短的路徑上。迭代過程結束，也就是算法的結束。其實終止的條件是迭代到一定的數量值，也就是設定的數量值，本文采用就是這種方式。

蟻群算法有很多優點，比如具有很好的魯棒性和搜索較好解的能力。但也有一些不足之處，當柵格模型較大計算量大時，不可避免的顯示出搜索效率低下和增加搜索時間的弊端。

1.3 仿真實驗

仿真實驗用C++面向對象語言來實現算法，并將它存入到動態鏈接庫中，用LabView 2012軟件來做程序主界面并利用它來調用C++語言庫。軟件左邊顯示的是環境和路線圖，路徑規劃的結果用直線和曲線顯示在左邊這個地圖上，右側可以顯示規劃路徑中GPS坐標和算法計算所耗用的時間。

用高校的一個無名湖做了仿真實驗，把無名湖的GPS坐標生成柵格模型。柵格模型中每個柵格的邊長是5m，仿真柵格模型共70行65列。算法使用的參數如表1所示。

表1 柵格—蟻群算法參數

仿真結果如圖2所示。

圖2 柵格—蟻群算法規劃路徑仿真實驗

在左側圖中顯示有路徑規劃的起始點和目的地。右側的數據表明整個測試耗用時間766ms，圖中的封閉圓圈表示是小島，規劃的路徑避開了湖中的小島。可以看出規劃的是一條近似最佳的路徑。實驗表明柵格—蟻群算法能夠規劃出一條繞開小島的路徑，但還不夠精確，沒有能夠規劃出最優路徑。

2 離散—蟻群算法

在前面仿真實驗中，可以看到柵格—蟻群算法在無人船搜索路徑時由于受到柵格模型的限制，向前只有幾個方向。達不到更加準確地搜索路徑到達目的地。經過研究，在這里提出了離散蟻群算法。這種離散蟻群算法為了避免柵格模型的限制所以選用了源數據模型，讓螞蟻在搜索路徑前行時有很多方向可以選擇。最后計算結果得出的路徑長度比柵格模型得出的路徑長度更加短，也更加精確。

離散蟻群算法與柵格—蟻群算法這兩種算法相比較，離散蟻群算法中一條路徑的邊是否可行是不知道的，這只能由螞蟻在搜索路徑的時候來發現其周邊的路徑是否可行。而在柵格—蟻群算法中一條路徑的邊是否可行決定于此位置的柵格是不是可行柵格。另外離散蟻群算法與柵格—蟻群算法有一個明顯的差別，離散蟻群算法中因為螞蟻前進的步長是隨機的，所以當它搜索兩次路徑時路徑的邊是基本不會相同的。也就是說，螞蟻搜索路徑分泌的信息素是不會積累在某些固定的邊上。而柵格—蟻群算法中由于柵格模型的限制必然會使得可行柵格的邊是確定的。通過算法分析可以得出，采用柵格—蟻群算法可以把螞蟻搜尋路徑分泌的生物信息素保存在路徑邊上。而采用離散蟻群算法可以將螞蟻搜尋路徑的分泌的生物信息素存儲在路徑點上。而且能夠把蟻群螞蟻經過幾次搜尋的路徑和螞蟻搜尋路徑產生的生物信息素都保存在備份中，這為螞蟻在以后的路徑搜尋過程中找到保存的備份提供了方便，從而全面了解到此刻位置前方曾經走過的路徑點，依據路徑點上的生物信息素計算出選擇前行方向的概率。

2.1 離散蟻群算法流程

假設蟻群中總共有N個螞蟻，每個螞蟻從起始點出發搜索路徑。螞蟻搜索過程中前行方向的選擇是由一周離散化成后可成M個方向。如圖3所示，在此圖中M=18，螞蟻的前進方向為V■?，此刻位置為P。現在以y軸為正方向，然后順時針旋轉，那么螞蟻全部可以選擇的方向集合如式(4)表示。

圖3 離散蟻群算法搜索過程示意圖

螞蟻行走的步長是等于min Step和max Step之間的隨機數，min Step表示是最小步長，max Step表示是最大步長。步長也可以設為固定值。如式(5)所示。

對照某一個方向θ的下一步位置的坐標可以用式(6)表示。

為了不讓螞蟻搜索路徑時打轉回頭，陷入不斷轉圈的惡性循環。只有設置螞蟻前進轉彎不能大于90°。如圖5.7所示當前螞蟻前行時的所有可以選擇的方向中只有D3、D4…、D11（9個方向），不能選擇其它D12、D11…、D2（9個方向）。螞蟻在搜索路徑前進的過程中會感覺到曾經走過路徑點上保存的信息素。但這種螞蟻的感覺范圍是很有限的，一般來說螞蟻會感覺到在自己前進方向前方；小于自己感覺距離的半圓形區域內曾經走過的歷史路徑點。如圖5.7所示的陰影部分表示的就是螞蟻的感覺范圍，A、B和C三點是螞蟻感覺曾經走過路徑的歷史路徑點。例如路徑點A會使陰影部分被選擇的D3方向的概率增加，而D2方向因為大于90°而導致不會被選擇，D2的被選概率為0；同樣的原理路徑點B使陰影部分被選擇的D7和D8方向的概率增加；路徑點C使陰影部分被選擇的D9和D10的概率增加。蟻群中第k只螞蟻選擇方向θ前進的概率的計算如式(7)表示。

圖5 兩種算法規劃路徑效果

當螞蟻的感覺距離大于螞蟻和目標之間的間隔時，不論目標在哪個方向，螞蟻會立刻尋找到目標。蟻群中每只螞蟻搜索到一條路徑后，就會在它所走過路徑的路徑點上產生一些信息素，那么第k只螞蟻在走過的路徑點i上產生的信息素的計算可以用公式(8)計算。

C1是常數，而且大于1。LK表示的是螞蟻路徑總的長度。全部螞蟻完成一輪搜尋路徑后，曾經走過的路徑所保留的信息素會揮發一些，剩下的為保留率ρ（0≤ρ＜1）。接著進入下一輪迭代，達到結束條件后結束

2.2 仿真實驗

離散蟻群算法的仿真實驗還是將高校的一個無名湖作為源數據模型。在實驗中，螞蟻的min Step（最小步長）、max Step（最大步長）和feel Dist（感知距離）調整得很合理。實驗中起始點到目的地的距離為D，參數如表2所示。

表2 離散蟻群算法參數

仿真結果如圖4所示。

圖4 離散蟻群算法規劃路徑仿真實驗

從實驗中可以看出：在無名湖中的測試消耗了約43s的時間，實驗中規劃的路徑剛好繞過了湖中的小島。這驗證了離散蟻群算法是能夠準確的規劃出一條繞開障礙物的路徑的。

前面記述了柵格—蟻群算法以及離散蟻群算法的流程，并通過仿真實驗對這兩種算法進行了驗證。雖然算法的真實運行的效果會受到很多因素的影響，比如受到計算機整體的性能，編程所用的語言，實現算法的方式等。但在相同的測試條件下進行比較還是具有很好的參考性的。在這里再次對高校的這個無名湖進行了兩種算法的路徑規劃，這次兩種算法采用相同起點和目標，參數設置如表2，評估的結果如表3所示。

表3 兩種算法的比較

兩種算法路徑規劃的效果如圖5所示。

圖4和表3中表明柵格—蟻群算法和離散蟻群算法各有特點，在性能上柵格—蟻群算法較好，在規劃路徑結果上離散蟻群算法更好。柵格—蟻群算法本身受柵格模型的限制，得到的最優路徑有一些多余的彎路，它跟實際的最優路線比較有一些差距，如圖5(a)所示。離散蟻群算法由于步長的自適應性的特點，所以規劃的路徑還是彎折小，而且路徑很平滑。離散蟻群算法規劃的路徑可以說是最優的路徑，它跟實際的最優路線基本相同。無人船按照該路徑行駛會比較平穩，對自動控制來說是比較理想的。如圖5(b)所示。但是離散蟻群算法得到的最優路徑也是付出代價的，離散蟻群算法比柵格—蟻群算法更加耗時。總的來說，在實際使用中到底選用哪種算法，還是要根據實際需要來衡量。