多無(wú)人艇協(xié)同遍歷路徑規(guī)劃算法

翁 磊, 楊 揚(yáng), 鐘雨軒

多無(wú)人艇協(xié)同遍歷路徑規(guī)劃算法

翁 磊1, 楊 揚(yáng)1, 鐘雨軒2*

(1. 上海大學(xué) 機(jī)電工程與自動(dòng)化學(xué)院, 上海, 200444; 2. 上海大學(xué) 計(jì)算機(jī)工程與科學(xué)學(xué)院, 上海, 200444)

為了實(shí)現(xiàn)對(duì)島礁及周圍海域水下地貌信息的獲取, 同時(shí)使用多個(gè)無(wú)人掃測(cè)艇進(jìn)行協(xié)同測(cè)繪以提高測(cè)繪效率, 文中提出一種協(xié)同遍歷路徑規(guī)劃算法: 采用掃描線多邊形方法得到動(dòng)態(tài)柵格地圖, 建立水域環(huán)境模型, 基于-means++算法對(duì)任務(wù)區(qū)域進(jìn)行分配, 分配區(qū)域內(nèi)使用啟發(fā)式路徑規(guī)劃算法得到完全遍歷路徑。仿真結(jié)果滿足區(qū)域分配的均勻性和遍歷路徑的連通性要求。在此基礎(chǔ)上提出了動(dòng)態(tài)重規(guī)劃算法, 根據(jù)實(shí)時(shí)可工作無(wú)人艇數(shù)量對(duì)未遍歷區(qū)域進(jìn)行重分配。仿真結(jié)果證明, 在不同間距的柵格地圖中, 協(xié)同遍歷算法均提高了測(cè)繪效率, 路徑重復(fù)率較低, 可以快速高效地實(shí)現(xiàn)動(dòng)態(tài)重規(guī)劃。

無(wú)人掃測(cè)艇; 協(xié)同;-means++算法; 遍歷路徑規(guī)劃; 動(dòng)態(tài)重規(guī)劃

0 引言

由于島礁周圍水域地形復(fù)雜, 使用傳統(tǒng)人工測(cè)繪方式效率低下且有人員安全風(fēng)險(xiǎn), 因此亟需一種智能海洋勘測(cè)裝備。無(wú)人掃測(cè)艇[1]具有吃水淺, 機(jī)動(dòng)性強(qiáng), 路徑跟隨穩(wěn)定等特點(diǎn), 非常適用于島礁測(cè)繪。面對(duì)一些復(fù)雜且廣闊的島礁環(huán)境, 使用單個(gè)無(wú)人掃測(cè)艇對(duì)作業(yè)區(qū)域進(jìn)行掃測(cè)時(shí)間較長(zhǎng), 魯棒性差, 因此使用多個(gè)無(wú)人掃測(cè)艇組成多無(wú)人艇系統(tǒng)對(duì)作業(yè)區(qū)域進(jìn)行協(xié)同測(cè)繪可以提高整體掃測(cè)效率和實(shí)驗(yàn)系統(tǒng)的魯棒性[2-3]。

目前, 多智能體協(xié)同區(qū)域遍歷問題多采用基于神經(jīng)網(wǎng)絡(luò)的方法和粒子群算法等[4], 這些智能算法易于在多無(wú)人車和多無(wú)人機(jī)等全驅(qū)動(dòng)的系統(tǒng)中實(shí)現(xiàn)且計(jì)算量大。彭輝等[5]采用將協(xié)同遍歷問題分解為任務(wù)區(qū)域分配和遍歷路徑規(guī)劃2個(gè)部分進(jìn)行求解, 降低了問題計(jì)算量和復(fù)雜度。

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

圖1 協(xié)同遍歷路徑規(guī)劃算法流程圖

1 環(huán)境建模與任務(wù)區(qū)域分配

環(huán)境建模是任務(wù)區(qū)域分配和路徑規(guī)劃的前提, 常用的環(huán)境地圖有柵格地圖[9]、拓?fù)涞貓D和幾何特征地圖等?？紤]到無(wú)人掃測(cè)艇對(duì)路徑精度的要求和遍歷路徑的有序性, 文中使用柵格地圖顯示作業(yè)環(huán)境信息。

在電子海圖中選定測(cè)繪區(qū)域后, 根據(jù)獲得的障礙物信息和邊界信息填充柵格地圖, 常用的區(qū)域填充算法有掃描線多邊形填充算法[10]、邊填充算法和種子填充算法等。因?yàn)殡娮雍D顯示的島礁區(qū)域多為不規(guī)則多邊形, 因此文中采用掃描線多邊形填充算法建立環(huán)境模型。

1.1 掃描線多邊形填充算法

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

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

掃描線多邊形算法實(shí)現(xiàn)簡(jiǎn)單, 運(yùn)行效率高, 適用于處理島礁類多邊形地圖, 可以通過調(diào)節(jié)離散間隔改變單位路徑長(zhǎng)度, 滿足不同精度的實(shí)際測(cè)繪需求, 基于多邊形掃描線算法產(chǎn)生的柵格地圖易于實(shí)現(xiàn)聚類和遍歷路徑規(guī)劃。

1.2 K-means++聚類算法

在完成對(duì)作業(yè)區(qū)域建模后, 接下來(lái)需對(duì)作業(yè)區(qū)域進(jìn)行劃分。考慮到多無(wú)人艇協(xié)同遍歷區(qū)域的連通性和均勻分配要求, 使用-means++聚類算法[11]對(duì)作業(yè)區(qū)域進(jìn)行劃分。

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

1) 根據(jù)任務(wù)場(chǎng)景分配的無(wú)人艇數(shù)量設(shè)置值;

4) 重復(fù)步驟3)直到選出個(gè)質(zhì)心元素;

7) 不斷對(duì)步驟5)和步驟6)進(jìn)行迭代, 直到聚類結(jié)果不再發(fā)生變化。

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

2 路徑規(guī)劃算法

完成作業(yè)區(qū)域環(huán)境建模和區(qū)域劃分后, 需對(duì)劃分后的區(qū)域進(jìn)行完全遍歷路徑規(guī)劃。完全遍歷路徑規(guī)劃[12]是一種特殊的路徑規(guī)劃, 其目的是在工作區(qū)域內(nèi)尋找一條經(jīng)過所有可達(dá)點(diǎn)的連續(xù)路徑。其中應(yīng)用較廣的是基于神經(jīng)網(wǎng)絡(luò)模型[13]的方法。該算法存在計(jì)算量大和路徑規(guī)劃效果非最優(yōu)等缺點(diǎn), 因此針對(duì)無(wú)人掃測(cè)艇對(duì)測(cè)繪路徑的要求, 文中采用動(dòng)態(tài)柵格法與優(yōu)先級(jí)啟發(fā)式路徑規(guī)劃相結(jié)合的方法。

2.1 動(dòng)態(tài)柵格法

通過掃描線多邊形填充算法得到柵格地圖后, 完成了地圖中可通過性柵格點(diǎn)的提取和初始化賦值。在無(wú)人艇作業(yè)過程中, 隨著無(wú)人掃測(cè)艇的運(yùn)動(dòng), 通過改變已遍柵格點(diǎn)的收益值對(duì)環(huán)境進(jìn)行動(dòng)態(tài)描述, 引導(dǎo)無(wú)人掃測(cè)艇在動(dòng)態(tài)柵格中對(duì)未遍歷區(qū)域進(jìn)行掃測(cè)。

在單個(gè)無(wú)人掃測(cè)艇遍歷過程中的柵格點(diǎn)收益值呈現(xiàn)3種屬性狀態(tài): 已遍歷區(qū)域收益值為0; 待掃測(cè)可行區(qū)域收益值為1; 障礙物區(qū)域收益值為–1。圖4為無(wú)人掃測(cè)艇作業(yè)過程中的某一時(shí)刻的動(dòng)態(tài)柵格模型圖, 其中實(shí)心柵格點(diǎn)為無(wú)人艇當(dāng)前所在位置。

圖4 掃測(cè)過程中動(dòng)態(tài)柵格模型圖

2.2 優(yōu)先級(jí)啟發(fā)式路徑規(guī)劃算法

獲取動(dòng)態(tài)柵格地圖后需對(duì)路徑點(diǎn)進(jìn)行選取, 為了保證完全遍歷路徑的有序性, 文中采用一種優(yōu)先級(jí)啟發(fā)式路徑點(diǎn)選取規(guī)則, 其優(yōu)先級(jí)定義如圖5所示。

圖5 方向優(yōu)先級(jí)定義圖

無(wú)人掃測(cè)艇工作過程中, 在以八鄰域方式通行的情況下, 其可行區(qū)域?yàn)?個(gè)相鄰點(diǎn), 按照優(yōu)先級(jí)高低將其劃分為4等, 由高至低分別為: 上、下、左側(cè)(左上、左、左下)、右側(cè)(右上、右、右下)。定義上、下2個(gè)方向優(yōu)先級(jí)較高以使豎直方向?yàn)橹饕\(yùn)動(dòng)方向, 定義左側(cè)優(yōu)先級(jí)高于右側(cè)則使無(wú)人掃測(cè)艇的遍歷路徑由左往右推移, 保證規(guī)劃路徑的有序性。

圖6為優(yōu)先級(jí)啟發(fā)式路徑規(guī)劃在動(dòng)態(tài)柵格地圖中的遍歷路徑規(guī)劃示意圖。由圖可知, 優(yōu)先級(jí)啟發(fā)式路徑規(guī)劃算法理論上可以在動(dòng)態(tài)柵格地圖中有序地實(shí)現(xiàn)遍歷路徑規(guī)劃。

2.3 基于A*的啟發(fā)式搜索算法

當(dāng)無(wú)人艇處于圖6所示的八鄰域柵格中時(shí), 其中2個(gè)柵格為障礙物, 其余6個(gè)柵格皆為已遍歷, 此時(shí)優(yōu)先級(jí)啟發(fā)式路徑規(guī)劃方法不再適用, 定義為“死鎖”狀態(tài)?；趧?dòng)態(tài)柵格模型, 使用搜索臨時(shí)目標(biāo)點(diǎn)并結(jié)合A*啟發(fā)式搜索算法產(chǎn)生最優(yōu)路徑走出“死鎖”狀態(tài)。

圖6 啟發(fā)式路徑規(guī)劃動(dòng)態(tài)柵格圖

1) 搜索臨時(shí)目標(biāo)點(diǎn)

圖7 搜索臨時(shí)目標(biāo)點(diǎn)

2) 建立代價(jià)地圖

在確定臨時(shí)目標(biāo)點(diǎn)后, 需要定義A*搜索算法所需的代價(jià)地圖, 此時(shí)處于非測(cè)繪狀態(tài), 只需要區(qū)分非障礙物柵格和障礙物柵格即可: 設(shè)置非障礙物柵格距離代價(jià)為1; 障礙物柵格代價(jià)為1 000, 如圖8所示。

圖8 A*代價(jià)地圖

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

在無(wú)人艇處于死鎖狀態(tài)下則激活A(yù)*啟發(fā)式搜索算法, 圖9為使用A*算法走出死鎖狀態(tài)的最優(yōu)路徑示意圖, 將優(yōu)先級(jí)啟發(fā)式路徑規(guī)劃算法和A*啟發(fā)式路徑規(guī)劃算法結(jié)合起來(lái), 得到如圖10所示的島礁地圖環(huán)境中遍歷路徑規(guī)劃的效果。

圖10 遍歷路徑規(guī)劃整體效果圖

根據(jù)整體遍歷路徑可以看出, 將優(yōu)先級(jí)啟發(fā)式算法和A*啟發(fā)式路徑規(guī)劃相結(jié)合可以實(shí)現(xiàn)相對(duì)有序、規(guī)律的遍歷路徑規(guī)劃效果, 及時(shí)走出“死鎖”狀態(tài), 達(dá)到快速遍歷的效果。

3 動(dòng)態(tài)重規(guī)劃

無(wú)人艇在島礁區(qū)域進(jìn)行測(cè)繪時(shí), 由于海洋中存在暗礁等障礙物和風(fēng)、浪、涌等復(fù)雜環(huán)境因素的影響, 可能致使無(wú)人艇自身系統(tǒng)出現(xiàn)干擾和故障等情況。在多無(wú)人艇協(xié)同遍歷過程中, 如果出現(xiàn)單個(gè)或多個(gè)無(wú)人艇系統(tǒng)發(fā)生故障后失聯(lián)的問題, 會(huì)導(dǎo)致部分地圖遍歷無(wú)法完成, 因此需要使用動(dòng)態(tài)重規(guī)劃算法完成任務(wù)重分配[15]。

因此, 基于-means++聚類算法提出動(dòng)態(tài)重規(guī)劃算法, 在多無(wú)人艇協(xié)同遍歷過程中, 根據(jù)實(shí)時(shí)的多無(wú)人艇系統(tǒng)狀態(tài), 動(dòng)態(tài)地對(duì)未完全遍歷的任務(wù)區(qū)域進(jìn)行重規(guī)劃, 以提高協(xié)同遍歷搜索的效率, 體現(xiàn)多無(wú)人艇系統(tǒng)的魯棒性和文中所提協(xié)同遍歷算法的適應(yīng)性。

圖11為動(dòng)態(tài)重規(guī)劃的過程: 1) 當(dāng)檢測(cè)到單個(gè)或多個(gè)無(wú)人艇系統(tǒng)出現(xiàn)故障無(wú)法繼續(xù)工作時(shí), 激活動(dòng)態(tài)重規(guī)劃模塊; 2) 更新當(dāng)前未遍歷區(qū)域、可工作的無(wú)人艇數(shù)量及實(shí)時(shí)位置坐標(biāo); 3) 以當(dāng)前可工作無(wú)人艇數(shù)量作為值, 其實(shí)時(shí)位置作為個(gè)初始質(zhì)心元素, 使用-means++聚類算法對(duì)未遍歷區(qū)域進(jìn)行聚類, 使劃分區(qū)域靠近無(wú)人艇實(shí)時(shí)位置, 以滿足路徑連通性要求; 4) 任務(wù)區(qū)域重分配完成后, 使用路徑規(guī)劃算法對(duì)每塊重分配區(qū)域進(jìn)行遍歷路徑規(guī)劃; 5) 得到每塊重規(guī)劃區(qū)域中的遍歷路徑輸出給可工作的無(wú)人艇。動(dòng)態(tài)重規(guī)劃算法的偽代碼如下所示。

圖11 動(dòng)態(tài)重規(guī)劃算法過程

動(dòng)態(tài)重規(guī)劃方法不僅適用于解決多無(wú)人艇協(xié)同遍歷過程中, 部分無(wú)人艇因故障原因無(wú)法繼續(xù)執(zhí)行當(dāng)前剩余任務(wù)的問題, 同時(shí)還能用于解決各單艇工作效率不一致導(dǎo)致的整體作業(yè)效率下降問題。為實(shí)現(xiàn)整體任務(wù)區(qū)域遍歷的快速性, 當(dāng)1艘無(wú)人掃測(cè)艇完成路徑遍歷后, 可以使用動(dòng)態(tài)重規(guī)劃方法對(duì)未作業(yè)任務(wù)區(qū)域進(jìn)行重分配, 縮短整體遍歷時(shí)間, 體現(xiàn)多無(wú)人艇協(xié)同遍歷的高效性優(yōu)勢(shì)。

4 仿真結(jié)果與分析

利用MATLAB對(duì)協(xié)同遍歷路徑規(guī)劃算法進(jìn)行仿真驗(yàn)證。首先對(duì)協(xié)同遍歷路徑規(guī)劃算法進(jìn)行任務(wù)區(qū)域分配和路徑規(guī)劃仿真驗(yàn)證, 并對(duì)分配結(jié)果和設(shè)置的柵格大小的關(guān)系進(jìn)行分析; 其次將協(xié)同遍歷路徑規(guī)劃算法和基于神經(jīng)網(wǎng)絡(luò)模型的路徑規(guī)劃算法進(jìn)行對(duì)比; 最后對(duì)動(dòng)態(tài)重規(guī)劃算法進(jìn)行仿真驗(yàn)證。

4.1 協(xié)同遍歷路徑規(guī)劃算法

設(shè)置如圖12所示的初始測(cè)繪島礁區(qū)域, 其中的多邊形區(qū)域和柵格為障礙物區(qū)域, 為了驗(yàn)證協(xié)同遍歷路徑規(guī)劃算法的有效性, 分別驗(yàn)證無(wú)人艇數(shù)量為2、3、4、5時(shí)的任務(wù)區(qū)域分配效果和遍歷路徑質(zhì)量。

圖12為設(shè)置柵格為10×10時(shí)無(wú)人艇數(shù)量聚類區(qū)域分配和遍歷路徑規(guī)劃效果, 不同形狀的節(jié)點(diǎn)表示不同聚類區(qū)域內(nèi)的路徑點(diǎn)。由任務(wù)區(qū)域分配效果可知, 區(qū)域分配基本滿足均勻性要求, 路徑滿足連通性要求。

在不同間隔大小的柵格地圖中設(shè)置不同作業(yè)數(shù)量的無(wú)人艇, 通過分析平均任務(wù)路徑長(zhǎng)度, 比較艇群作業(yè)效率。

對(duì)同一島礁環(huán)境地圖分別設(shè)置不同間距的掃描線, 產(chǎn)生柵格地圖大小分別為10×10, 20×20, 40×40, 80×80, 并設(shè)置無(wú)人艇數(shù)量為2,3,4,5, 取10次試驗(yàn)結(jié)果的平均值作為平均任務(wù)路徑長(zhǎng)度值。圖13為平均路徑長(zhǎng)度對(duì)比折線圖, 根據(jù)圖中標(biāo)注的路徑長(zhǎng)度值可以看出, 在柵格劃分?jǐn)?shù)量最多80×80時(shí), 隨著分配無(wú)人艇數(shù)量的增加, 單個(gè)無(wú)人艇分配的路徑長(zhǎng)度減小最多。此外, 隨著作業(yè)無(wú)人艇數(shù)量的增加, 單個(gè)無(wú)人艇的任務(wù)路徑長(zhǎng)度快速減少, 尤其是在整體任務(wù)路徑較長(zhǎng)時(shí), 體現(xiàn)了多無(wú)人艇協(xié)同遍歷的高效性。

圖12 協(xié)同遍歷路徑規(guī)劃效果圖

圖13 動(dòng)態(tài)柵格法對(duì)比圖

4.2 遍歷算法比較分析

在通過-means++算法得到聚類結(jié)果后, 分別使用啟發(fā)式路徑規(guī)劃算法和基于神經(jīng)網(wǎng)絡(luò)的路徑規(guī)劃算法對(duì)分配區(qū)域進(jìn)行遍歷, 以路徑長(zhǎng)度、轉(zhuǎn)彎次數(shù)、路徑點(diǎn)重復(fù)率和遍歷覆蓋率作為評(píng)價(jià)指標(biāo)比較路徑規(guī)劃質(zhì)量。表1為=5時(shí)2種路徑規(guī)劃算法分別進(jìn)行10次試驗(yàn)結(jié)果的平均值, 通過結(jié)果可以分析得出, 啟發(fā)式路徑規(guī)劃算法和基于神經(jīng)網(wǎng)絡(luò)的路徑規(guī)劃算法都能實(shí)現(xiàn)100%的地圖覆蓋率, 啟發(fā)式路徑方法平均路徑長(zhǎng)度更短, 轉(zhuǎn)彎次數(shù)更少, 尤其是路徑點(diǎn)重復(fù)率更低。

表1 路徑規(guī)劃結(jié)果對(duì)比

圖14為=5時(shí)2種算法遍歷路徑效果對(duì)比圖, 由圖可知, 啟發(fā)式路徑規(guī)劃算法的遍歷路徑更加有序, 重復(fù)路徑點(diǎn)更少, 更適用于解決基于聚類算法分配任務(wù)區(qū)域的多無(wú)人艇協(xié)同遍歷問題。

圖14 遍歷算法對(duì)比圖

4.3 任務(wù)重規(guī)劃

對(duì)第3章提出的動(dòng)態(tài)重規(guī)劃算法進(jìn)行仿真驗(yàn)證。圖15為任務(wù)重規(guī)劃對(duì)比圖, 將地圖柵格設(shè)置為10×10, 設(shè)置初始可工作無(wú)人艇的數(shù)量為5。如果5艘無(wú)人艇均為正常工作狀態(tài), 在進(jìn)行初始協(xié)同遍歷任務(wù)任務(wù)分配后, 5艘無(wú)人艇按照分配的路徑完成遍歷任務(wù)。在任務(wù)完成4個(gè)單位長(zhǎng)度后, 有1艘無(wú)人艇發(fā)生障礙無(wú)法繼續(xù)任務(wù), 此時(shí)激活動(dòng)態(tài)重規(guī)劃模塊, 對(duì)未遍歷區(qū)域內(nèi)的56個(gè)未遍歷路徑點(diǎn)基于可工作的4艘無(wú)人艇進(jìn)行任務(wù)重規(guī)劃, 如圖所示為任務(wù)重規(guī)劃模塊輸出得到的遍歷路徑。根據(jù)如圖所示效果, 星形柵格點(diǎn)為重分配區(qū)域遍歷路徑起點(diǎn), 不同形狀的柵格點(diǎn)表示不同的聚類區(qū)域, 路徑長(zhǎng)度分別為14、16、15、15個(gè)單位長(zhǎng)度, 重分配路徑滿足連通性和均勻性要求, 驗(yàn)證了動(dòng)態(tài)重規(guī)劃算法的有效性。

圖15 動(dòng)態(tài)重規(guī)劃效果圖

在當(dāng)前柵格大小的地圖中, 基于隨機(jī)聚類結(jié)果在設(shè)置初始路徑長(zhǎng)度為4后分別進(jìn)行10次動(dòng)態(tài)重規(guī)劃算法, 得到平均重規(guī)劃時(shí)間為0.8 s, 由此數(shù)據(jù)可知該動(dòng)態(tài)重規(guī)劃算法的快速性。

5 結(jié)束語(yǔ)

文中以多個(gè)無(wú)人掃測(cè)艇對(duì)島礁區(qū)域進(jìn)行協(xié)同遍歷路徑規(guī)劃為背景, 提出了多無(wú)人艇協(xié)同遍歷路徑規(guī)劃算法, 使用K-means++算法對(duì)任務(wù)區(qū)域進(jìn)行分配, 對(duì)分配的任務(wù)區(qū)域使用優(yōu)先級(jí)和啟發(fā)式相結(jié)合的路徑規(guī)劃算法進(jìn)行完全路徑遍歷, 并在此基礎(chǔ)上提出動(dòng)態(tài)重規(guī)劃算法。根據(jù)仿真結(jié)果分析, 協(xié)同遍歷路徑規(guī)劃算法分配的任務(wù)區(qū)域滿足均勻性要求, 遍歷路徑滿足連通性, 動(dòng)態(tài)重規(guī)劃算法可動(dòng)態(tài)地對(duì)實(shí)時(shí)未遍歷區(qū)域進(jìn)行重分配, 體現(xiàn)了協(xié)同遍歷路徑規(guī)劃算法的魯棒性和高效性。

[1] 申云磊, 高霄鵬. 無(wú)人艇的研究現(xiàn)狀與進(jìn)展[J]. 船電技術(shù), 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] 羅代超. 多水面無(wú)人艇協(xié)同區(qū)域搜索策略研究[D]. 哈爾濱: 哈爾濱工程大學(xué), 2019.

[3] 梁宏晨. 基于蜂窩結(jié)構(gòu)的多無(wú)人艇協(xié)同區(qū)域探測(cè)研究[D]. 廣州: 華南理工大學(xué), 2019.

[4] 劉慶周, 吳鋒. 多智能體路徑規(guī)劃研究進(jìn)展[J]. 計(jì)算機(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協(xié)同區(qū)域覆蓋搜索研究[J]. 系統(tǒng)仿真學(xué)報(bào), 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] 呂霞付, 程啟忠, 李森浩, 等. 基于改進(jìn)A*算法的無(wú)人船完全遍歷路徑規(guī)劃[J]. 水下無(wú)人系統(tǒng)學(xué)報(bào), 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] 劉晶, 姚維, 章瑋. 移動(dòng)機(jī)器人全覆蓋路徑規(guī)劃算法研究[J]. 工業(yè)控制計(jì)算機(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] 鐘雨軒, 葛磊, 張?chǎng)? 等. 無(wú)人水面艇島礁海域完全遍歷路徑規(guī)劃[J]. 上海大學(xué)學(xué)報(bào)(自然科學(xué)版), 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] 范云生, 趙永生, 石林龍, 等. 基于電子海圖柵格化的無(wú)人水面艇全局路徑規(guī)劃[J]. 中國(guó)航海, 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] 衛(wèi)洪春, 彭小利. 掃描線多邊形區(qū)域填充算法研究[J].四川文理學(xué)院學(xué)報(bào), 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] 肖尚華, 胡燦林. 基于加權(quán)K-means聚類與路網(wǎng)無(wú)向圖的地圖分割算法[J]. 現(xiàn)代計(jì)算機(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īng)元激勵(lì)的移動(dòng)機(jī)器人遍歷路徑規(guī)劃[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] 謝坤霖, 李宗根, 代宇航, 等. 基于啟發(fā)式搜索算法的掃地機(jī)器人路徑規(guī)劃[J]. 西華大學(xué)學(xué)報(bào)(自然科學(xué)版), 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] 馬向峰, 韓瑋, 謝楊柳. 水面無(wú)人艇任務(wù)規(guī)劃系統(tǒng)分析[J]. 艦船科學(xué)技術(shù), 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

翁磊, 楊揚(yáng), 鐘雨軒. 多無(wú)人艇協(xié)同遍歷路徑規(guī)劃算法[J]. 水下無(wú)人系統(tǒng)學(xué)報(bào), 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.

國(guó)家重點(diǎn)研發(fā)計(jì)劃資助項(xiàng)目(2017YFC0806700); 科技部重點(diǎn)研發(fā)計(jì)劃(2018YFF0103400) .

鐘雨軒(1994-), 男, 碩士, 實(shí)驗(yàn)員, 主要研究方向?yàn)闊o(wú)人艇導(dǎo)航、制導(dǎo)和控制等.

(責(zé)任編輯: 許 妍)