基于改進A*算法的無人船完全遍歷路徑規劃

呂霞付, 程啟忠, 李森浩, 林 政

基于改進A*算法的無人船完全遍歷路徑規劃

呂霞付, 程啟忠, 李森浩, 林 政

(重慶郵電大學 工業互聯網與網絡化控制教育部重點實驗室, 重慶, 400065)

針對無人船在復雜環境下完全遍歷路徑規劃算法效率差、普適性低的問題, 文中提出了一種基于改進A*算法的無人船完全遍歷路徑規劃方法。首先通過地面站上位機電子地圖界面發布任務區域, 將該任務區域轉換為柵格地圖; 然后通過內螺旋算法開始對柵格地圖進行遍歷; 最后當無人船陷入死角時, 通過改進A*算法搜索最優路徑, 逃逸死角繼續遍歷, 直到完成所有可達區域的遍歷。仿真結果表明, 相比現有完全遍歷的優化方法, 該方法規劃的路徑步數從814步減少到784步, 重復率從優化前的7.8%改善至3.98%, 改善了性能指標, 具有較好的應用前景。

無人船; 路徑規劃; 完全遍歷; A*算法

0 引言

隨著人類對水資源的保護、對深海區域的探索和海上軍事的開展, 無人船(unmanned surface vehicle, USV)的研究和開發越來越受到關注與重視[1]。

USV作為水域交通系統的重要個體, 其路徑規劃一直是研究熱點[2]。根據全局和局部的不同, 將USV路徑規劃分為2種類型: 完全遍歷路徑規劃和點對點路徑規劃[3]。其中, USV完全遍歷路徑規劃主要應用于水面漂浮物清理, 水底地形探測, 海灣水域掃雷等方面。不同的完全遍歷算法效果也不一樣。

Balch[4]采用隨機式遍歷算法讓機器人直線行走, 當遇到障礙物隨機轉動一個角度后繼續行駛, 該算法比較簡單, 但局限性很大, 會出現重復清掃相同區域并且有的區域沒有清掃的情況; 王琦斐等[5]采用內螺旋覆蓋算法讓機器人按約定的方向順時針或逆時針進行遍歷, 當前方區域為障礙物或已經被遍歷過, 則向右(或向左)旋轉90°繼續行駛, 該算法過于簡單, 容易陷入局部死角或有些區域未被遍歷; 許興軍[6]提出了一種改進反復式全區域覆蓋算法, 并引入了區域分割的方式, 根據障礙物分布將任務區域分割成多個子區域, 再通過往復式算法遍歷子區域, 該方法完成了在實際應用中完全遍歷的路徑規劃, 比較簡單易用, 但該方法不適用其他環境, 重復率高, 區域劃分不明顯, 算法精度低。

近些年來, 隨著搜索算法的發展, 出現了模糊控制、人工勢場法、神經網絡、蟻群算法、遺傳算法和A*算法等, 能夠應付復雜和多變的工作環境, 解決了死角和漏掃的問題, 實現了在未知環境中的運動和規劃[7]。張赤斌等[8]將蟻群算法應用于完全遍歷中, 但該算法運算量大、實時性差; Mohamed等[9]提出了一種改進的遺傳算法, 通過改變種群的編碼方式, 在傳統遺傳算法的步驟上增加3個新的遺傳操作: 復原、重構和錄優, 使得尋優的路徑更加平滑, 但該算法需要大量的遺傳迭代, 增加的3個遺傳操作使得迭代次數更多, 遺傳過程被重復, 運算量變大; 陳超等[10]提出了一種基于可視圖的A*算法, 將起點與障礙物的特征點相連, 去除中間因其他障礙物遮擋的線段, 將A*算法與可視圖法相結合, 提高了對環境的適應性, 但該可視圖法需要用線段連接所有起點到障礙物特征點, 當環境中出現動態變化的障礙物, 需要通過可視圖法重新建立環境模型, 普適性差。USV路徑規劃技術取得了豐碩的成果, 但每一種方法都由于其自身的優點和不足不能應用于所有場合。目前USV完全遍歷路徑規劃算法創新之處在于多傳感器、多種路徑規劃技術的融合。

針對上述問題, 文中提出了一種改進A*算法的USV內螺旋完全遍歷路徑規劃算法。首先采用內螺旋遍歷算法進行遍歷, 當陷入死角時, 通過改進A*算法逃逸死角, 行進至最近的未被遍歷的柵格并繼續完成遍歷。仿真結果表明, 該方法行駛步數少、覆蓋率高、重復率小, 在復雜環境中性能更強。

1 基于柵格法的USV環境建模

1.1 柵格法環境建模概述

環境建模就是將能夠表示環境的數據信息進行抽象化, 以數學方法描述物體和它們之間的空間關系。柵格法環境建模容易實現, 是當前研究和應用最為廣泛的環境建模方法[11]。柵格法USV環境建模就是將USV工作的二維水面環境地圖劃分成若干個大小相同的柵格, 并根據可達區域和不可達區域的情況, 確定每個柵格的占有值。柵格法建模過程簡單, 運算量小, 更能直觀表示環境地圖遍歷的情況, 并且柵格坐標系的坐標點與經緯度坐標系一一對應, 能夠準確定位, 方便于環境建模和算法規劃。文中將采用柵格法完成USV環境建模, 為客觀地表示柵格法環境建模, 作如下定義。

定義1:

1.2 柵格大小選取

在柵格環境建模過程中, 柵格大小的選取[12]是一個很重要的問題, 其直接影響環境地圖信息的精度, 也同樣影響著完全遍歷路徑規劃算法的性能和效率。柵格大小的選取需要考慮以下4個因素: 環境地圖的大小與障礙物的復雜程度; USV的船身尺寸; 實際應用情況以及不同的應用場景和用途; 計算機的運算和存儲能力。

1.3 環境建模過程

11) 重復步驟1)、步驟3)和步驟6), 柵格化障礙物;

13) 基于柵格法的環境建模完成。

1.4 環境建模試驗

為驗證上述環境建模方法的可行性, 在地面站上位機電子地圖軟件選出4個坐標點, 經緯度如下:

用線段依次把這些坐標點連接形成的四邊形就是邊界。圖1中P1~P4圍成的不規則四邊形即地面站上位機軟件發布的任務區域。

2 基于柵格地圖的完全遍歷算法

在建立的柵格地圖中, 在滿足一項或多項評價指標最優的情況下, 通過完全遍歷算法可以遍歷所有可達區域, 并規劃出一條最優路徑。

2.1 算法性能評價指標

USV完全遍歷算法的性能主要采用以下5個性能指標來衡量。

1) 遍歷覆蓋率

遍歷覆蓋率是指路徑規劃完成后, USV所行駛過的面積與可達區域的比值, 即

完全遍歷時, 盡可能保證所有可達安全區域都要遍歷, 接近100%。遍歷覆蓋率百分比越高, 說明該算法的性能越好。

2) 遍歷重疊率

遍歷重疊率是指路徑規劃完成后, USV行駛中出現2次或多次重復遍歷的面積總和與可達安全區域面積的比值, 即

完全遍歷時, 在保證覆蓋率達到100%時, 出現重復遍歷的情況, 該數值越小, 完全遍歷算法性能越好。

3) 轉彎次數

4) 步數或路徑總長度

相同的遍歷覆蓋率下, 路徑總長度越小, 控制USV的算法性能越好。

5) 總用時間

2.2 完全遍歷算法比較

圖3 3種完全遍歷算法示意圖

表1為3種遍歷算法評價指標結果。由表中可知, 3種遍歷算法覆蓋率都為100%。傳統的往復前進算法, 雖然重復率為0, 但其以犧牲路徑總長度為代價, 遍歷時間和遍歷路徑遠遠大于其他2種遍歷算法。相比于改進往復前進算法, 螺旋式算法步數為350步, 減少了116步, 重復率只有2.94%, 遠低于改進往復前進算法的24.12%, 并且總用時減少了114 s。螺旋式遍歷算法不僅達到了完全覆蓋的效果, 而且極大地降低了重復率, 減少了USV的航行步數。

表1 3種完全遍歷算法評價指標

2.3 死角情況

在遍歷規劃時, 死角是USV特別需要注意的局部環境, 也是體現算法有效性和優越性的環境模型[16]。死角是指USV執行遍歷任務到達柵格地圖某處時, 相鄰的8個柵格是障礙物或者已經遍歷。陷入死角有2種情境, 情境1: USV行駛到某位置時, 所在柵格周圍相鄰的8個柵格除了上一步經過的柵格外其余都是障礙柵格, 如圖4(a)所示; 情境2: USV所在的柵格相鄰8個柵格都已經被遍歷過, 如圖4(b)所示。當USV陷入上述死角時, 需要搜索算法搜索最近的可達柵格, 并規劃一條最短路徑, 使得USV可以逃逸死角。

圖4 USV陷入死角示意圖

2.4 改進A*算法的完全遍歷路徑規劃算法

A*算法是一種啟發式搜索算法[13], 它結合了Dijkstra算法的迭代式檢查和最佳優先算法(best-first search, BFS)的方向性, 提高了效率, 減少了路程。由于其具有較好的性能和準確性, 可適用于各種環境, 經常被用于最優路徑的求解。

2.4.1 A*算法成本估計函數

A*算法成本估計函數為

利用A*算法在柵格地圖上進行規劃時, 選取2個節點中心點間的歐幾里得距離（直線距離）作為估計代價, 即

2.4.2 改進A*算法

1) 模型再分析

圖5 A*算法流程圖

圖6 柵格模型分析

2) 改進A*算法過程

改進A*算法的過程如下。

⑥算法結束, BestList鏈表中的節點為最優路徑。

3) 改進A*算法實例分析

BestList鏈表存放的節點即為改進A*算法的最優路徑。結合圖7說明改進A*算法的過程。

圖7 利用改進A*算法尋求最優路徑過程示意圖

根據點到線段的距離公式

由表2可知, 同傳統的A*算法相比, 改進A*算法可使USV朝任意角度轉向, 減少了不必要的節點, 路徑總長度變短。

表2 傳統A*算法與改進A*算法數據對比

2.4.3 改進A*算法的USV完全遍歷

為了完成柵格地圖的完全遍歷, 現將內螺旋遍歷算法與改進A*算法融合, USV執行完全遍歷任務時, 首先執行內螺旋遍歷算法, 當陷入死角時, 通過改進A*算法跳出死角, 繼續遍歷。改進A*算法的USV完全遍歷框架如圖8所示。

圖8 改進A*算法的USV完全遍歷框架

3 仿真試驗與分析

為了驗證文中完全遍歷算法的有效性, 建立與文獻[16]相似的環境柵格地圖。地圖由32×32個柵格組成, 其中黑色區域為邊界或障礙物。當USV進行完全遍歷任務時, 內螺旋遍歷時陷入死角, 坐標點為(17, 19), 如圖9所示。

圖10為遍歷陷入死角時傳統A*算法與改進A*算法搜索路徑示意圖。圖10(a)中的黃色路徑為傳統A*算法的路徑節點示意圖, 將柵格(12, 16)作為終點, 路徑包括19個節點。將這19個黃色節點存放在BestList鏈表中, 去掉中間不必要的節點并搜索最近未遍歷的柵格, 圖10(b)中綠色柵格路徑為改進A*算法的路徑節點示意圖, 終點從(12, 16)變成(12, 12), 路徑減少到3個節點, 大大減少了路程總長度。

圖9 USV內螺旋遍歷陷入死角

圖10 2種算法路徑示意圖

圖11為USV完全遍歷路徑規劃完成示意圖。由圖可以看出, 在復雜環境模型中, USV的完全遍歷路徑規劃的覆蓋率為100%, 在遍歷時USV遇到2次死角, 坐標點為(12, 21)、(17, 19), 通過改進A*算法逃逸死角, 繼續完成遍歷。

圖11 USV完全遍歷路徑規劃示意圖

表3為在環境柵格地圖下, 2種完全遍歷算法評價指標結果。由表可知, 基于改進A*算法的完全遍歷規劃路徑步數為784步, 重復率為3.98%。相比文獻[16]遍歷算法步數814步, 重復率為7.8%的結果, 文中方法不僅達到了完全覆蓋的效果, 而且降低了重復率、減少了步數和路徑長度, 因此更具優越性。

表3 2種完全遍歷算法評價指標

4 結束語

針對USV在復雜環境下完全遍歷路徑規劃算法效率差、普適性低的問題, 提出了一種改進A*算法的內螺旋完全遍歷路徑規劃算法。將電子地圖邊界轉化為柵格環境模型, 并在建立的柵格地圖中比較3種遍歷算法的優缺點, 得出內螺旋遍歷算法性能更優。USV執行遍歷任務時, 首先通過內螺旋遍歷算法開始遍歷, 若在行進過程中遇到死角, 采用改進A*算法實現USV以最短路徑逃逸死角并繼續完成遍歷。仿真結果表明, 文中方法不僅能夠有效地實現USV100%的完全遍歷, 而且降低了重復率, 減少了步數和路徑長度, 在復雜環境下具有較高的規劃效率。下一步將通過實物測試, 驗證該算法。

[1] 曹娟, 王雪松. 國內外無人船發展現狀及未來前景[J]. 中國船檢, 2018, 1(5): 94-97.

[2] 楊俊成, 李淑霞, 蔡增玉. 路徑規劃算法的研究與發展[J]. 控制工程, 2017, 24(7): 1473-1480.Yang Jun-cheng, Li Shu-xia, Cai Zeng-yu. Research and Development of Path Planning Algorithm[J]. Control Engineering of China, 2017, 24(7): 1473-1480.

[3] 張月. 清潔機器人全覆蓋路徑規劃研究[D]. 重慶: 重慶大學, 2015.

[4] Balch T. The Case for Randomized Search[C]//Workshop on Sensors and Motion, IEEE International Conference on Robotics and Automation, San Francisco, CA: IEEE, 2000: 213-215.

[5] 王琦斐, 楊軍. 基于內螺旋覆蓋算法的多AUV協作反水雷路徑規劃研究[J]. 計算機測量與控制, 2012, 20(1): 144-146, 160.

Wang Qi-fei, Yang Jun. Path Planning of Multiple AUVs for Cooperative Mine Countermeasure Using Internal Spiral Coverage Algorithm[J]. Computer Measurement & Control, 2012, 20(1): 144-146, 160.

[6] 許興軍. 智能割草機的區域全覆蓋算法設計與仿真[J]. 機電工程, 2012, 29(3): 302-306.

Xu Xing-jun. Design and Simulation on Regional All-covered Algorithm of Intelligent Mower[J]. Mechanical & Electrical Engineering Magazine, 2012, 29(3): 302-306.

[7] Yan R, Pang S, Sun H, et al. Development and Missions of Unmanned Surface Vehicle[J]. Journal of Marine Science and Application, 2010, 9(4): 451-457.

[8] 張赤斌, 王興松. 基于蟻群算法的完全遍歷路徑規劃研究[J]. 中國機械工程, 2008, 19(16): 1945-1949.Zhang Chi-bin, Wang Xing-song. Complete Coverage Path Planning Based on Ant Colony Algorithm[J]. China Mechanical Engineering, 2008, 19(16): 1945-1949.

[9] Mohamed A Y, Mohamed T L. The Path Planning of Cleaner Robot for Coverage Region Using Genetic Algorithms[J]. Journal of Innovation in Digital Ecosystems, 2016, 3(1): 37-43.

[10] 陳超, 唐堅. 基于可視圖法的水面無人艇路徑規劃設計[J]. 中國造船, 2013, 54(1): 129-135.Chen Chao, Tang Jian. A V-Graph Based Path Planning for Unmanned Surface Vehicle[J]. Shipbuilding of China, 2013, 54(1): 129-135.

[11] Arleo A, Millan J R, Floreano D. Efficient Learning of Variable Resolution Cognitive Maps for Autonomous Indoor Navigation[J]. IEEE Transactions on Robotics and Automation, 1999, 15(6): 990-1000.

[12] 彭剛, 沈宇. 一種變柵格地圖的巡檢機器人路徑規劃方法研究[J]. 智能機器人, 2017, 1(4): 41-43, 68.

[13] Hart P E, Nilsson N J, Raphael B. A Formal Basis for the Heuristic Determination of Minimum Cost Paths[J]. IEEE Transactions on Systems Science and Cybernetics, 1968, 4(2): 100-107.

[14] 姚雨, 李慶, 陳曦. 優化的A*算法在航跡規劃上的應用[J]. 微電子學與計算機, 2017, 34(7): 51-55.Yao Yu, Li Qing, Chen Xi. Optimization of the Application of A* Algorithm in Path Planning[J]. Microelectronics & Computer, 2017, 34(7): 51-55.

[15] 趙曉, 王錚, 黃程侃, 等. 基于改進A*算法的移動機器人路徑規劃[J]. 機器人, 2018, 40(6): 903-910.Zhao Xiao, Wang Zheng, Huang Cheng-kan, et al. Mobile Robot Path Planning Based on an Improved A* Algorithm[J]. Robot, 2018, 40(6): 903-910.

[16] 溫志文, 楊春武, 蔡衛軍, 等. 復雜環境下UUV完全遍歷路徑規劃方法[J]. 魚雷技術, 2017, 25(1): 22-26, 31.Wen Zhi-wen, Yang Chun-wu, Cai Wei-jun, et al. A Complete Coverage Path Planning Method of UUV under Complex Environment[J]. Torpedo Technology, 2017, 25(1): 22-26, 31.

Unmanned Surface Vehicle Full Traversal Path Planning Based on Improved A* Algorithm

Lü Xia-fu, CHENG Qi-zhong, LI Sen-hao, LIN Zheng

(Chongqing University of Posts and Telecommunications, Key Laboratory of Industrial Internet of Things & Network Control, Ministry of Education, Chongqing 400065, China)

To improve the efficiency and universality of full traversal path planning algorithm for unmanned surface vehicle(USV) in complex environment, a new full traversal path planning algorithm based on the improved A* algorithm is proposed. Firstly, user publishes the task area through the electronic map interface of the host computer in ground station, and converts the task area into a grid map. Then, the grid map is traversed through the inner spiral algorithm. Finally, when the USV is going into the dead angle, optimal path is searched through the improved A* algorithm, and the escape dead angle is traversed until all the reachable areas are traversed. Simulation results show that compared with the existing full traversal optimization method, the proposed algorithm reduces the planned path steps from 814 to 784, and improves the repetition rate from 7.8% to 3.98%. The algorithm improves the performance and has a good application prospect.

unmanned surface vehicle(USV); path planning; full traversal; A* algorithm

U664.82; TP301.6

A

2096-3920(2019)06-0695-09

10.11993/j.issn.2096-3920.2019.06.014

2019-03-09;

2019-04-04.

國家自然科學基金(61071117); 重慶市研究生科研創新項目(CYS14151).

呂霞付(1966-), 男, 博士, 教授, 主要研究方向為智能儀器儀表.

呂霞付, 程啟忠, 李森浩, 等. 基于改進A*算法的無人船完全遍歷路徑規劃[J]. 水下無人系統學報, 2019, 27(6): 695-703.

(責任編輯: 許 妍)