多無人艇協同遍歷路徑規劃算法

翁 磊, 楊 揚, 鐘雨軒

多無人艇協同遍歷路徑規劃算法

翁 磊1, 楊 揚1, 鐘雨軒2*

(1. 上海大學 機電工程與自動化學院, 上海, 200444; 2. 上海大學 計算機工程與科學學院, 上海, 200444)

為了實現對島礁及周圍海域水下地貌信息的獲取, 同時使用多個無人掃測艇進行協同測繪以提高測繪效率, 文中提出一種協同遍歷路徑規劃算法: 采用掃描線多邊形方法得到動態柵格地圖, 建立水域環境模型, 基于-means++算法對任務區域進行分配, 分配區域內使用啟發式路徑規劃算法得到完全遍歷路徑。仿真結果滿足區域分配的均勻性和遍歷路徑的連通性要求。在此基礎上提出了動態重規劃算法, 根據實時可工作無人艇數量對未遍歷區域進行重分配。仿真結果證明, 在不同間距的柵格地圖中, 協同遍歷算法均提高了測繪效率, 路徑重復率較低, 可以快速高效地實現動態重規劃。

無人掃測艇; 協同;-means++算法; 遍歷路徑規劃; 動態重規劃

0 引言

由于島礁周圍水域地形復雜, 使用傳統人工測繪方式效率低下且有人員安全風險, 因此亟需一種智能海洋勘測裝備。無人掃測艇[1]具有吃水淺, 機動性強, 路徑跟隨穩定等特點, 非常適用于島礁測繪。面對一些復雜且廣闊的島礁環境, 使用單個無人掃測艇對作業區域進行掃測時間較長, 魯棒性差, 因此使用多個無人掃測艇組成多無人艇系統對作業區域進行協同測繪可以提高整體掃測效率和實驗系統的魯棒性[2-3]。

目前, 多智能體協同區域遍歷問題多采用基于神經網絡的方法和粒子群算法等[4], 這些智能算法易于在多無人車和多無人機等全驅動的系統中實現且計算量大。彭輝等[5]采用將協同遍歷問題分解為任務區域分配和遍歷路徑規劃2個部分進行求解, 降低了問題計算量和復雜度。

考慮到多無人艇系統的欠驅動系統特性, 為實現多無人艇協同遍歷的高效性, 文中采用將協同遍歷問題分解為任務區域分配和遍歷路徑規劃兩部分來求解。任務區域分配應用最為廣泛的是聚類算法, 通過將總體測繪區域劃分為每個無人艇測繪的子任務區域達到高效便利的目的。任務區域分配完成后需要對任務區域進行遍歷, 當單機器人完全遍歷路徑規劃通常采用A*算法[6]、神經網絡算法[7]等, 這些算法存在計算量大, 路徑規劃效果不佳等缺點。因此, 針對多無人艇協同遍歷問題, 文中提出了協同遍歷路徑規劃算法。流程圖如圖1所示。首先基于電子海圖使用掃描線多邊形填充算法進行環境建模得到柵格地圖; 接著使用-means++算法對任務區域進行分配; 然后在分配的區域內使用啟發式路徑規劃算法[8]規劃出完全遍歷路徑, 在此基礎上, 進一步提出動態重規劃算法, 根據實時的可工作無人艇數量對任務區域進行重分配, 體現了協同遍歷路徑規劃算法的魯棒性。

圖1 協同遍歷路徑規劃算法流程圖

1 環境建模與任務區域分配

環境建模是任務區域分配和路徑規劃的前提, 常用的環境地圖有柵格地圖[9]、拓撲地圖和幾何特征地圖等。考慮到無人掃測艇對路徑精度的要求和遍歷路徑的有序性, 文中使用柵格地圖顯示作業環境信息。

在電子海圖中選定測繪區域后, 根據獲得的障礙物信息和邊界信息填充柵格地圖, 常用的區域填充算法有掃描線多邊形填充算法[10]、邊填充算法和種子填充算法等。因為電子海圖顯示的島礁區域多為不規則多邊形, 因此文中采用掃描線多邊形填充算法建立環境模型。

1.1 掃描線多邊形填充算法

掃描線多邊形填充算法的過程如下: 1) 將環境地圖按照一定間隔距離離散為獨立柵格; 2) 在柵格地圖中以同樣的間距生成多條平行掃描線, 若掃描線與環境地圖中的障礙物邊界存在交點, 那么交點將成對存在, 記錄這些成對交點所在的位置; 3) 判斷各個柵格點與成對交點之間的位置關系, 若柵格處于交點之間則標記為障礙物柵格, 否則標記為自由柵格。

圖2為簡化島礁地圖的建模過程。外圍邊框為所選擇的待測繪區域, 多邊形區域為島礁所在的障礙物膨化區域, 對此區域按一定間距離散后得到圖2(a)所示的柵格地圖; 圖2(b)中按柵格行數生成多條掃描線后, 掃描線與障礙物邊界形成7對交點; 最后判斷每個柵格是否處于交點之內, 如圖(c)所示, 若是, 則該柵格處于障礙物區域, 標記為“–1”; 否則柵格處于可行區域, 標記為“1”, 檢測障礙物區域周圍自由柵格點間的連線和障礙物區域是否存在交點, 將存在交點的自由柵格設置為障礙物柵格。

掃描線多邊形算法實現簡單, 運行效率高, 適用于處理島礁類多邊形地圖, 可以通過調節離散間隔改變單位路徑長度, 滿足不同精度的實際測繪需求, 基于多邊形掃描線算法產生的柵格地圖易于實現聚類和遍歷路徑規劃。

1.2 K-means++聚類算法

在完成對作業區域建模后, 接下來需對作業區域進行劃分。考慮到多無人艇協同遍歷區域的連通性和均勻分配要求, 使用-means++聚類算法[11]對作業區域進行劃分。

圖2 掃描線多邊形算法過程圖

1) 根據任務場景分配的無人艇數量設置值;

4) 重復步驟3)直到選出個質心元素;

7) 不斷對步驟5)和步驟6)進行迭代, 直到聚類結果不再發生變化。

圖3 K-means++聚類效果圖

2 路徑規劃算法

完成作業區域環境建模和區域劃分后, 需對劃分后的區域進行完全遍歷路徑規劃。完全遍歷路徑規劃[12]是一種特殊的路徑規劃, 其目的是在工作區域內尋找一條經過所有可達點的連續路徑。其中應用較廣的是基于神經網絡模型[13]的方法。該算法存在計算量大和路徑規劃效果非最優等缺點, 因此針對無人掃測艇對測繪路徑的要求, 文中采用動態柵格法與優先級啟發式路徑規劃相結合的方法。

2.1 動態柵格法

通過掃描線多邊形填充算法得到柵格地圖后, 完成了地圖中可通過性柵格點的提取和初始化賦值。在無人艇作業過程中, 隨著無人掃測艇的運動, 通過改變已遍柵格點的收益值對環境進行動態描述, 引導無人掃測艇在動態柵格中對未遍歷區域進行掃測。

在單個無人掃測艇遍歷過程中的柵格點收益值呈現3種屬性狀態: 已遍歷區域收益值為0; 待掃測可行區域收益值為1; 障礙物區域收益值為–1。圖4為無人掃測艇作業過程中的某一時刻的動態柵格模型圖, 其中實心柵格點為無人艇當前所在位置。

圖4 掃測過程中動態柵格模型圖

2.2 優先級啟發式路徑規劃算法

獲取動態柵格地圖后需對路徑點進行選取, 為了保證完全遍歷路徑的有序性, 文中采用一種優先級啟發式路徑點選取規則, 其優先級定義如圖5所示。

圖5 方向優先級定義圖

無人掃測艇工作過程中, 在以八鄰域方式通行的情況下, 其可行區域為8個相鄰點, 按照優先級高低將其劃分為4等, 由高至低分別為: 上、下、左側(左上、左、左下)、右側(右上、右、右下)。定義上、下2個方向優先級較高以使豎直方向為主要運動方向, 定義左側優先級高于右側則使無人掃測艇的遍歷路徑由左往右推移, 保證規劃路徑的有序性。

圖6為優先級啟發式路徑規劃在動態柵格地圖中的遍歷路徑規劃示意圖。由圖可知, 優先級啟發式路徑規劃算法理論上可以在動態柵格地圖中有序地實現遍歷路徑規劃。

2.3 基于A*的啟發式搜索算法

當無人艇處于圖6所示的八鄰域柵格中時, 其中2個柵格為障礙物, 其余6個柵格皆為已遍歷, 此時優先級啟發式路徑規劃方法不再適用, 定義為“死鎖”狀態。基于動態柵格模型, 使用搜索臨時目標點并結合A*啟發式搜索算法產生最優路徑走出“死鎖”狀態。

圖6 啟發式路徑規劃動態柵格圖

1) 搜索臨時目標點

圖7 搜索臨時目標點

2) 建立代價地圖

在確定臨時目標點后, 需要定義A*搜索算法所需的代價地圖, 此時處于非測繪狀態, 只需要區分非障礙物柵格和障礙物柵格即可: 設置非障礙物柵格距離代價為1; 障礙物柵格代價為1 000, 如圖8所示。

圖8 A*代價地圖

3) 利用A*算法搜索路徑

在無人艇處于死鎖狀態下則激活A*啟發式搜索算法, 圖9為使用A*算法走出死鎖狀態的最優路徑示意圖, 將優先級啟發式路徑規劃算法和A*啟發式路徑規劃算法結合起來, 得到如圖10所示的島礁地圖環境中遍歷路徑規劃的效果。

圖10 遍歷路徑規劃整體效果圖

根據整體遍歷路徑可以看出, 將優先級啟發式算法和A*啟發式路徑規劃相結合可以實現相對有序、規律的遍歷路徑規劃效果, 及時走出“死鎖”狀態, 達到快速遍歷的效果。

3 動態重規劃

無人艇在島礁區域進行測繪時, 由于海洋中存在暗礁等障礙物和風、浪、涌等復雜環境因素的影響, 可能致使無人艇自身系統出現干擾和故障等情況。在多無人艇協同遍歷過程中, 如果出現單個或多個無人艇系統發生故障后失聯的問題, 會導致部分地圖遍歷無法完成, 因此需要使用動態重規劃算法完成任務重分配[15]。

因此, 基于-means++聚類算法提出動態重規劃算法, 在多無人艇協同遍歷過程中, 根據實時的多無人艇系統狀態, 動態地對未完全遍歷的任務區域進行重規劃, 以提高協同遍歷搜索的效率, 體現多無人艇系統的魯棒性和文中所提協同遍歷算法的適應性。

圖11為動態重規劃的過程: 1) 當檢測到單個或多個無人艇系統出現故障無法繼續工作時, 激活動態重規劃模塊; 2) 更新當前未遍歷區域、可工作的無人艇數量及實時位置坐標; 3) 以當前可工作無人艇數量作為值, 其實時位置作為個初始質心元素, 使用-means++聚類算法對未遍歷區域進行聚類, 使劃分區域靠近無人艇實時位置, 以滿足路徑連通性要求; 4) 任務區域重分配完成后, 使用路徑規劃算法對每塊重分配區域進行遍歷路徑規劃; 5) 得到每塊重規劃區域中的遍歷路徑輸出給可工作的無人艇。動態重規劃算法的偽代碼如下所示。

圖11 動態重規劃算法過程

動態重規劃方法不僅適用于解決多無人艇協同遍歷過程中, 部分無人艇因故障原因無法繼續執行當前剩余任務的問題, 同時還能用于解決各單艇工作效率不一致導致的整體作業效率下降問題。為實現整體任務區域遍歷的快速性, 當1艘無人掃測艇完成路徑遍歷后, 可以使用動態重規劃方法對未作業任務區域進行重分配, 縮短整體遍歷時間, 體現多無人艇協同遍歷的高效性優勢。

4 仿真結果與分析

利用MATLAB對協同遍歷路徑規劃算法進行仿真驗證。首先對協同遍歷路徑規劃算法進行任務區域分配和路徑規劃仿真驗證, 并對分配結果和設置的柵格大小的關系進行分析; 其次將協同遍歷路徑規劃算法和基于神經網絡模型的路徑規劃算法進行對比; 最后對動態重規劃算法進行仿真驗證。

4.1 協同遍歷路徑規劃算法

設置如圖12所示的初始測繪島礁區域, 其中的多邊形區域和柵格為障礙物區域, 為了驗證協同遍歷路徑規劃算法的有效性, 分別驗證無人艇數量為2、3、4、5時的任務區域分配效果和遍歷路徑質量。

圖12為設置柵格為10×10時無人艇數量聚類區域分配和遍歷路徑規劃效果, 不同形狀的節點表示不同聚類區域內的路徑點。由任務區域分配效果可知, 區域分配基本滿足均勻性要求, 路徑滿足連通性要求。

在不同間隔大小的柵格地圖中設置不同作業數量的無人艇, 通過分析平均任務路徑長度, 比較艇群作業效率。

對同一島礁環境地圖分別設置不同間距的掃描線, 產生柵格地圖大小分別為10×10, 20×20, 40×40, 80×80, 并設置無人艇數量為2,3,4,5, 取10次試驗結果的平均值作為平均任務路徑長度值。圖13為平均路徑長度對比折線圖, 根據圖中標注的路徑長度值可以看出, 在柵格劃分數量最多80×80時, 隨著分配無人艇數量的增加, 單個無人艇分配的路徑長度減小最多。此外, 隨著作業無人艇數量的增加, 單個無人艇的任務路徑長度快速減少, 尤其是在整體任務路徑較長時, 體現了多無人艇協同遍歷的高效性。

圖12 協同遍歷路徑規劃效果圖

圖13 動態柵格法對比圖

4.2 遍歷算法比較分析

在通過-means++算法得到聚類結果后, 分別使用啟發式路徑規劃算法和基于神經網絡的路徑規劃算法對分配區域進行遍歷, 以路徑長度、轉彎次數、路徑點重復率和遍歷覆蓋率作為評價指標比較路徑規劃質量。表1為=5時2種路徑規劃算法分別進行10次試驗結果的平均值, 通過結果可以分析得出, 啟發式路徑規劃算法和基于神經網絡的路徑規劃算法都能實現100%的地圖覆蓋率, 啟發式路徑方法平均路徑長度更短, 轉彎次數更少, 尤其是路徑點重復率更低。

表1 路徑規劃結果對比

圖14為=5時2種算法遍歷路徑效果對比圖, 由圖可知, 啟發式路徑規劃算法的遍歷路徑更加有序, 重復路徑點更少, 更適用于解決基于聚類算法分配任務區域的多無人艇協同遍歷問題。

圖14 遍歷算法對比圖

4.3 任務重規劃

對第3章提出的動態重規劃算法進行仿真驗證。圖15為任務重規劃對比圖, 將地圖柵格設置為10×10, 設置初始可工作無人艇的數量為5。如果5艘無人艇均為正常工作狀態, 在進行初始協同遍歷任務任務分配后, 5艘無人艇按照分配的路徑完成遍歷任務。在任務完成4個單位長度后, 有1艘無人艇發生障礙無法繼續任務, 此時激活動態重規劃模塊, 對未遍歷區域內的56個未遍歷路徑點基于可工作的4艘無人艇進行任務重規劃, 如圖所示為任務重規劃模塊輸出得到的遍歷路徑。根據如圖所示效果, 星形柵格點為重分配區域遍歷路徑起點, 不同形狀的柵格點表示不同的聚類區域, 路徑長度分別為14、16、15、15個單位長度, 重分配路徑滿足連通性和均勻性要求, 驗證了動態重規劃算法的有效性。

圖15 動態重規劃效果圖

在當前柵格大小的地圖中, 基于隨機聚類結果在設置初始路徑長度為4后分別進行10次動態重規劃算法, 得到平均重規劃時間為0.8 s, 由此數據可知該動態重規劃算法的快速性。

5 結束語

文中以多個無人掃測艇對島礁區域進行協同遍歷路徑規劃為背景, 提出了多無人艇協同遍歷路徑規劃算法, 使用K-means++算法對任務區域進行分配, 對分配的任務區域使用優先級和啟發式相結合的路徑規劃算法進行完全路徑遍歷, 并在此基礎上提出動態重規劃算法。根據仿真結果分析, 協同遍歷路徑規劃算法分配的任務區域滿足均勻性要求, 遍歷路徑滿足連通性, 動態重規劃算法可動態地對實時未遍歷區域進行重分配, 體現了協同遍歷路徑規劃算法的魯棒性和高效性。

[1] 申云磊, 高霄鵬. 無人艇的研究現狀與進展[J]. 船電技術, 2018, 38(9): 7-10.Shen Yun-lei, Gao Xiao-peng. Research Status and Progress of Unmanned Surface Vehicle[J]. Marine Electric & Electronic Engineering, 2018, 38(9): 7-10.

[2] 羅代超. 多水面無人艇協同區域搜索策略研究[D]. 哈爾濱: 哈爾濱工程大學, 2019.

[3] 梁宏晨. 基于蜂窩結構的多無人艇協同區域探測研究[D]. 廣州: 華南理工大學, 2019.

[4] 劉慶周, 吳鋒. 多智能體路徑規劃研究進展[J]. 計算機工程, 2020, 46(4): 1-10.Liu Qing-zhou, Wu Feng. Research Progress of Multi-Agent Path Planning[J]. Computer Engineering, 2020, 46(4): 1-10.

[5] 彭輝, 沈林成, 霍霄華. 多UAV協同區域覆蓋搜索研究[J]. 系統仿真學報, 2007, 19(11): 2472-2476.Peng Hui, Shen Lin-cheng, Huo Xiao-hua. Research on Multiple UAV Cooperative Area Coverage Searching[J]. Journal of System Simulation, 2007, 19(11): 2472-2476.

[6] 呂霞付, 程啟忠, 李森浩, 等. 基于改進A*算法的無人船完全遍歷路徑規劃[J]. 水下無人系統學報, 2019, 27(6): 695-703.Lü Xia-fu, Cheng Qi-zhong, Li Sen-hao, et al. Unmanned Surface Vehicle Full Traversal Path Planning Based on Improved A* Algorithm[J]. Journal of Unmanned Undersea Systems, 2019, 27(6): 695-703.

[7] 劉晶, 姚維, 章瑋. 移動機器人全覆蓋路徑規劃算法研究[J]. 工業控制計算機, 2019, 32(12): 52-54.Liu Jing, Yao Wei, Zhang Wei. Research on Complete Coverage Path Planning Algorithm of Mobile Robots[J]. Industrial Control Computer, 2019, 32(12): 52-54.

[8] 鐘雨軒, 葛磊, 張鑫, 等. 無人水面艇島礁海域完全遍歷路徑規劃[J]. 上海大學學報(自然科學版), 2017, 23(1): 17-26.Zhong Yu-xuan, Ge Lei, Zhang xin, et al. Complete Coverage Path Planning of USV Used for Mapping Round Island[J]. Journal of Shanghai University(Natural Science), 2017, 23(1): 17-26.

[9] 范云生, 趙永生, 石林龍, 等. 基于電子海圖柵格化的無人水面艇全局路徑規劃[J]. 中國航海, 2017, 40(1): 47-52, 113.Fan Yun-sheng, Zhao Yong-sheng, Shi Lin-long, et al. Global Path Planning for Unmanned Surface Vehicle Based on Grid Model of Electronic Chart[J]. Navigation of China, 2017, 40(1): 47-52, 113.

[10] 衛洪春, 彭小利. 掃描線多邊形區域填充算法研究[J].四川文理學院學報, 2012, 22(5): 77-82.Wei Hong-chun, Peng Xiao-Li. Study on the Algorithm of Scanning Line Filling in Polygon Area[J]. Sichuan University of Arts and Science Journal, 2012, 22(5): 77-82.

[11] 肖尚華, 胡燦林. 基于加權K-means聚類與路網無向圖的地圖分割算法[J]. 現代計算機, 2018(8): 78-81.Xiao Shang-hua, Hu Can-lin. Map Segmentation Based on Weighted K-means Clustering and Undirected Road Graph[J]. Modern Computer, 2018(8): 78-81.

[12] Senthilkumar K S, Bharadwaj K K. Multi-robot Exploration and Terrain Coverage in an Unknown Environment[J]. Robotics & Autonomous Systems, 2012, 60(1): 123-132.

[13] 王仲民, 井平安, 朱博. 基于神經元激勵的移動機器人遍歷路徑規劃[J]. 控制工程, 2017, 24(2): 283-286.Wang Zhong-min, Jing Ping-an, Zhu Bo. Coverage Path Planning of Mobile Robot Based on Neuronal Excitation[J]. Control Engineering of China, 2017, 24(2): 283-286.

[14] 謝坤霖, 李宗根, 代宇航, 等. 基于啟發式搜索算法的掃地機器人路徑規劃[J]. 西華大學學報(自然科學版), 2019, 38(4): 69-76.Xie Kun-lin, Li Zong-gen, Dai Yu-hang, et al. Sweeping Robot Path Planning Based on Heuristic Search Algorithm[J]. Journal of Xihua University(Natural Science Edition), 2019, 38(4): 69-76.

[15] 馬向峰, 韓瑋, 謝楊柳. 水面無人艇任務規劃系統分析[J]. 艦船科學技術, 2019, 41(23): 54-57.Ma Xiang-feng, Han Wei, Xie Yang-liu. Analysis and Research on Misson Planning System of USV[J]. Ship Science and Technology, 2019, 41(23): 54-57.

Collaborative Traversal Path Planning Algorithm of for Multiple Unmanned Survey Vessels

WENG Lei1, YANG Yang1, ZHONG Yu-xuan2*

(1. School of Mechatronic Engineering and Automation, Shanghai University, Shanghai 200444, China; 2. School of Computer Engineering and Science, Shanghai University, Shanghai 200444, China)

To obtain underwater geomorphological information of islands, reefs, and surrounding waters and improve surveying and mapping efficiency, collaborative surveying, and mapping using multiple unmanned survey vessels should be employed. In this study, a collaborative traversal path planning algorithm in conjunction with the scanline polygon method is used to obtain a dynamic grid map. A water environment model is then constructed, task areas are allocated based on the-means++ algorithm, and a full traversal path is obtained by the heuristic path planning algorithm. Simulation results meet the requirements of uniformity and connectivity of the traversal path. A dynamic reprogramming algorithm is then proposed to reallocate the untraversed areas based on the number of unmanned vessels that can work in real time. The collaborative traversal algorithm is shown to improve the mapping efficiency of the grid map with different spacing, and the path repetition rate is low, meaning that dynamic reprogramming can be realized quickly and efficiently.

unmanned survey vessel; collaborative;-means++ algorithm; traversal path planning; dynamic reprogramming

翁磊, 楊揚, 鐘雨軒. 多無人艇協同遍歷路徑規劃算法[J]. 水下無人系統學報, 2020, 28(6): 634-641.

TJ630; U675.7; P217

A

2096-3920(2020)06-0634-08

10.11993/j.issn.2096-3920.2020.06.007

2020-09-02;

2020-11-03.

國家重點研發計劃資助項目(2017YFC0806700); 科技部重點研發計劃(2018YFF0103400) .

鐘雨軒(1994-), 男, 碩士, 實驗員, 主要研究方向為無人艇導航、制導和控制等.

(責任編輯: 許 妍)