[發(fā)明專利]一種多無人艇協(xié)同遍歷路徑規(guī)劃方法及系統(tǒng)

有效

• 申請?zhí)枺?/td>: 202011549643.3
• 申請日: 2020-12-24
• 公開（公告）號: CN112797999B
• 公開（公告）日: 2022-06-03
• 發(fā)明（設(shè)計）人: 羅均;翁磊;鐘雨軒;袁曉宇;王屹輝;曹宏昊;彭艷
• 申請（專利權(quán)）人: 上海大學(xué)
• 主分類號: G01C21/34
• 分類號: G01C21/34
• 代理公司: 北京高沃律師事務(wù)所 11569
• 代理人: 王愛濤

1.一種多無人艇協(xié)同遍歷路徑規(guī)劃方法，其特征在于，包括：

確定待測繪海域地圖；

對所述待測繪海域地圖進(jìn)行離散化處理以獲取柵格地圖；

根據(jù)所述柵格地圖，確定可遍歷柵格點和障礙柵格點；

采用K-means++算法對所述可遍歷柵格點進(jìn)行聚類處理以確定多個相互連通路徑點區(qū)域；所述相互連通路徑點區(qū)域的個數(shù)與無人艇的個數(shù)相同；

采用優(yōu)先級啟發(fā)式路徑規(guī)劃約束條件，對每個所述相互連通路徑點區(qū)域內(nèi)無人艇的行駛路徑進(jìn)行規(guī)劃；一個所述相互連通路徑點區(qū)域配置一個所述無人艇；所述優(yōu)先級啟發(fā)式路徑規(guī)劃約束條件為行駛路徑按照優(yōu)先級從高到低順序進(jìn)行規(guī)劃的條件；

在無人艇路徑遍歷過程中，當(dāng)所述無人艇無法繼續(xù)工作時，更新所述柵格地圖內(nèi)未遍歷區(qū)域以及當(dāng)前可工作無人艇數(shù)量、當(dāng)前可工作無人艇位置坐標(biāo)；

根據(jù)所述當(dāng)前可工作無人艇數(shù)量和所述當(dāng)前可工作無人艇位置坐標(biāo)，采用K-means++算法對所述未遍歷區(qū)域內(nèi)的可遍歷柵格點進(jìn)行聚類處理以確定多個更新后的相互連通路徑點區(qū)域；所述更新后的相互連通路徑點區(qū)域的個數(shù)與所述當(dāng)前可工作無人艇數(shù)量的個數(shù)相同；

采用優(yōu)先級啟發(fā)式路徑規(guī)劃約束條件，對每個所述更新后的相互連通路徑點區(qū)域內(nèi)當(dāng)前可工作無人艇的行駛路徑進(jìn)行規(guī)劃；一個所述更新后的相互連通路徑點區(qū)域配置一個所述當(dāng)前可工作無人艇。

2.根據(jù)權(quán)利要求1所述的一種多無人艇協(xié)同遍歷路徑規(guī)劃方法，其特征在于，所述根據(jù)所述柵格地圖，確定可遍歷柵格點和障礙柵格點，具體包括：

采用掃描線多邊形算法對所述柵格地圖進(jìn)行處理以確定可遍歷柵格點和障礙柵格點。

3.根據(jù)權(quán)利要求1所述的一種多無人艇協(xié)同遍歷路徑規(guī)劃方法，其特征在于，所述采用優(yōu)先級啟發(fā)式路徑規(guī)劃約束條件，對每個所述相互連通路徑點區(qū)域內(nèi)無人艇的行駛路徑進(jìn)行規(guī)劃，具體包括：

確定優(yōu)先級啟發(fā)式路徑規(guī)劃約束條件；所述優(yōu)先級啟發(fā)式路徑規(guī)劃約束條件包括第一優(yōu)先級、第二優(yōu)先級、第三優(yōu)先級以及第四優(yōu)先級，且所述第一優(yōu)先級的優(yōu)先級高于所述第二優(yōu)先級的優(yōu)先級，所述第二優(yōu)先級的優(yōu)先級高于所述第三優(yōu)先級的優(yōu)先級，所述第三優(yōu)先級的優(yōu)先級高于所述第四優(yōu)先級的優(yōu)先級；所述第一優(yōu)先級對應(yīng)的區(qū)域為所述相互連通路徑點區(qū)域的上方，所述第二優(yōu)先級對應(yīng)的區(qū)域為所述相互連通路徑點區(qū)域的下方，所述第三優(yōu)先級對應(yīng)的區(qū)域依次為所述相互連通路徑點區(qū)域的左上方、左方和左下方，所述第四優(yōu)先級對應(yīng)區(qū)域的依次為所述相互連通路徑點區(qū)域的右上方、右方和右下方；

采用所述優(yōu)先級啟發(fā)式路徑規(guī)劃約束條件，對每個所述相互連通路徑點區(qū)域內(nèi)無人艇的行駛路徑進(jìn)行規(guī)劃。

4.根據(jù)權(quán)利要求1所述的一種多無人艇協(xié)同遍歷路徑規(guī)劃方法，其特征在于，還包括：

在無人艇路徑遍歷過程中，采用動態(tài)柵格法對所述相互連通路徑點區(qū)域進(jìn)行動態(tài)描述，以確定已遍歷柵格點和未遍歷柵格點；

在無人艇路徑遍歷過程中，當(dāng)所述無人艇處于死鎖狀態(tài)時，確定目標(biāo)柵格點和無人艇處于死鎖狀態(tài)時的位置點；所述死鎖狀態(tài)為所述無人艇周圍的八領(lǐng)域點均為障礙物柵格點和/或已遍歷柵格點時的狀態(tài)；

根據(jù)所述目標(biāo)柵格點和所述無人艇處于死鎖狀態(tài)時的位置點，采用A*啟發(fā)式搜索算法，確定無人艇最短路徑；所述無人艇最短路徑為無人艇走出死鎖狀態(tài)的路徑。

5.根據(jù)權(quán)利要求4所述的一種多無人艇協(xié)同遍歷路徑規(guī)劃方法，其特征在于，所述在無人艇路徑遍歷過程中，當(dāng)所述無人艇處于死鎖狀態(tài)時，確定目標(biāo)柵格點和無人艇處于死鎖狀態(tài)時的位置點，具體包括：

確定無人艇處于死鎖狀態(tài)時的位置點；

確定所述相互連通路徑點區(qū)域內(nèi)最左列未遍歷柵格點；

確定所述最左列未遍歷柵格點內(nèi)的最上方未遍歷柵格點和最下方未遍歷柵格點；

計算所述最上方未遍歷柵格點與所述無人艇處于死鎖狀態(tài)時的位置點的第一距離，計算所述最下方未遍歷柵格點與所述無人艇處于死鎖狀態(tài)時的位置點的第二距離；

比較所述第一距離和所述第二距離，并將最小距離對應(yīng)的未遍歷柵格點確定為目標(biāo)柵格點。