[發(fā)明專利]一種面向無人船的幾何路徑規(guī)劃方法

在審

• 申請(qǐng)?zhí)枺?/td>: 202110055498.1
• 申請(qǐng)日: 2021-01-15
• 公開（公告）號(hào): CN112859864A
• 公開（公告）日: 2021-05-28
• 發(fā)明（設(shè)計(jì)）人: 曹志英;杜意權(quán);王少博;唐嘉偉;張秀國;霍然;宋飛飛;張鳳閣
• 申請(qǐng)（專利權(quán)）人: 大連海事大學(xué)
• 主分類號(hào): G05D1/02
• 分類號(hào): G05D1/02
• 代理公司: 大連東方專利代理有限責(zé)任公司 21212
• 代理人: 姜玉蓉;李洪福

本發(fā)明公開了一種面向無人船的幾何路徑規(guī)劃方法，該方法采用回溯隊(duì)列來存儲(chǔ)規(guī)劃過程中可行的規(guī)劃路徑點(diǎn)，首先將船舶航行區(qū)域內(nèi)的障礙物進(jìn)行膨化處理，將初始起點(diǎn)設(shè)置為當(dāng)前起點(diǎn)并加入回溯隊(duì)列和規(guī)劃路徑，然后判斷初始起點(diǎn)與目標(biāo)點(diǎn)之間的連線是否有障礙物，如果沒有障礙物，則連線即為規(guī)劃的路徑；如果有障礙物，將當(dāng)前起點(diǎn)添加到規(guī)劃路徑中，并從回溯隊(duì)列中刪除當(dāng)前起點(diǎn)，確定第一個(gè)出現(xiàn)在當(dāng)前起點(diǎn)與目標(biāo)點(diǎn)連線上的障礙物，在該障礙物外圍根據(jù)算法規(guī)則規(guī)劃出繞過當(dāng)前障礙物的路徑點(diǎn)，并根據(jù)一定規(guī)則選擇其中一個(gè)路徑點(diǎn)作為新的起點(diǎn)加入到回溯隊(duì)列和規(guī)劃路徑中，重復(fù)以上步驟尋找新的路徑點(diǎn)，直到與障礙物連線上沒有障礙物即為路徑規(guī)劃完畢。

技術(shù)領(lǐng)域

本發(fā)明涉及船舶航行控制領(lǐng)域，尤其涉及一種面向無人船的幾何路徑規(guī)劃方法。

背景技術(shù)

目前全世界各國經(jīng)濟(jì)發(fā)展聯(lián)系越來越緊密，船舶作為一種重要的交通運(yùn)輸工具，在經(jīng)濟(jì)發(fā)展中具有舉足輕重的地位。隨著陸地資源的逐漸減少，世界各國將目光轉(zhuǎn)移到占地球大約三分之二的海洋中去，海洋資源的開采和使用離不開海上智能交通的發(fā)展，海上智能交通的發(fā)展決定著海洋資源的利用率。我國作為海洋大國，有著遼闊的海洋資源，這也對(duì)發(fā)展海上智能交通提出了要求，船舶自動(dòng)化就是其中最為基礎(chǔ)也是最急迫需要解決的部分。

在船舶自動(dòng)化的研究中，路徑規(guī)劃是最重要的部分之一。無人船舶的路徑規(guī)劃要在已知船舶航行環(huán)境的條件下，快速規(guī)劃一條安全有效的路徑幫助船舶避開危險(xiǎn)區(qū)域到達(dá)目標(biāo)點(diǎn)。路徑規(guī)劃主要有兩個(gè)部分：全局路徑規(guī)劃和局部路徑規(guī)劃。全局路徑規(guī)劃主要是針對(duì)已知環(huán)境中的已探明障礙物為船舶尋找到航行距離和時(shí)間最短的路徑。局部路徑規(guī)劃是對(duì)無人船航行過程中突然出現(xiàn)的動(dòng)態(tài)/靜態(tài)障礙物的感知和避障，并且在完成局部路徑規(guī)劃之后能夠自主回歸到下一個(gè)航路點(diǎn)。

針對(duì)船舶的路徑規(guī)劃，國內(nèi)外學(xué)者提出了許多有關(guān)船舶路徑規(guī)劃的方法，這些方法可以被劃分為傳統(tǒng)的無人船路徑規(guī)劃算法和仿生智能算法兩類。傳統(tǒng)的無人船路徑規(guī)劃算法有人工勢(shì)場(chǎng)法(APF)、A*、rapidly exploring random tree(RRT)、PRM等。APF通過將航行限制區(qū)轉(zhuǎn)換為虛擬障礙物區(qū)域，構(gòu)建虛擬斥力場(chǎng)避開靜態(tài)障礙物，從而引導(dǎo)無人船駛向目標(biāo)航路點(diǎn)。但是當(dāng)有一個(gè)相等的斥力和吸引力時(shí)或當(dāng)目標(biāo)點(diǎn)的斥力很大時(shí)，船舶就會(huì)停滯不前，陷入局部最優(yōu)。A*算法先把要搜尋的區(qū)域劃分成正方形的格子，從起點(diǎn)開始檢查其相鄰的方格，然后向四周擴(kuò)展直至找到目標(biāo)，最后從可行的格子中找到移動(dòng)代價(jià)最小的路徑。但是該方法的規(guī)劃路徑功能依賴于柵格地圖，柵格的間距大小和數(shù)量會(huì)直接影響算法的計(jì)算速度和準(zhǔn)確性。RRT算法通過狀態(tài)空間的隨機(jī)采樣點(diǎn)，把搜索導(dǎo)向空白區(qū)域，從而尋找到一條從起始點(diǎn)到目標(biāo)點(diǎn)的規(guī)劃路徑。該方法能夠有效地解決高維空間和復(fù)雜約束的路徑規(guī)劃問題，但是該方法規(guī)劃出來的路徑不是最優(yōu)的。PRM是一種基于圖搜索的方法，它將連續(xù)空間轉(zhuǎn)換成離散空間，再利用A*等搜索算法在路線圖上尋找路徑，以提高搜索效率。這種方法能用相對(duì)少的隨機(jī)采樣點(diǎn)來找到一個(gè)解，對(duì)多數(shù)問題而言，相對(duì)少的樣本足以覆蓋大部分可行的空間并且找到路徑的概率為1，但是當(dāng)采樣點(diǎn)太少或者分布不合理時(shí)，PRM算法是很難規(guī)劃出路徑的。

仿生智能算法主要包括遺傳算法(GA)、粒子群算法(PSO)和蟻群算法(ACO)等。這類算法將目標(biāo)船舶路徑規(guī)劃問題轉(zhuǎn)換為路徑優(yōu)化問題。例如蟻群算法以碰撞危險(xiǎn)和航程損失作為目標(biāo)函數(shù)，使用蟻群算法進(jìn)行最優(yōu)路徑求解，但該方法的計(jì)算量非常大并且要求系統(tǒng)的性能非常高。遺傳算法將適應(yīng)度函數(shù)分成兩部分，分別用來判斷路徑的長短和平滑程度，使用輪盤賭方法作為選擇方法，通過選擇、交叉和變異算子來尋找最優(yōu)路徑。但是該方法依賴于柵格環(huán)境，而且當(dāng)柵格較大時(shí)，計(jì)算時(shí)間較長并且容易陷入局部最優(yōu)。