[發(fā)明專利]一種柵格地圖的路徑規(guī)劃方法

在審

• 申請?zhí)枺?/td>: 202011548679.X
• 申請日: 2020-12-24
• 公開（公告）號: CN112683275A
• 公開（公告）日: 2021-04-20
• 發(fā)明（設(shè)計）人: 陳雙;鄭亮;孫龍龍;陳昕
• 申請（專利權(quán)）人: 哈爾濱工業(yè)大學(xué)蕪湖機器人產(chǎn)業(yè)技術(shù)研究院
• 主分類號: G01C21/20
• 分類號: G01C21/20;G01C21/32;G01C21/34;G05D1/02
• 代理公司: 蕪湖安匯知識產(chǎn)權(quán)代理有限公司 34107
• 代理人: 鐘雪

本發(fā)明公開了一種格地圖的路徑規(guī)劃方法，包括如下步驟：S1、構(gòu)建柵格地圖，對柵格地圖中的障礙物進(jìn)行膨脹處理；S2、構(gòu)建拓?fù)涞貓D，在狹道的出口及入口處設(shè)有拓?fù)潼c，兩個拓?fù)潼c均位于狹道的安全區(qū)域；S3、基于用Floyd算法獲取起始拓?fù)潼c至終止拓?fù)潼c的拓?fù)渎窂近c集，刪除拓?fù)渎窂近c集中的起始拓?fù)潼c及終止拓?fù)潼c，將剩余的拓?fù)潼c加入路徑點集中；S4、在路徑點集的首尾出分別加入任務(wù)起點及任務(wù)終點，基于A?stars算法依次規(guī)劃路徑點集中相鄰路徑點間的路徑，生成全局路徑點集。解決了Astar算法搜索具有沿墻走導(dǎo)致小車行走的安全系數(shù)不高的問題。

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

本發(fā)明屬于路徑規(guī)劃技術(shù)領(lǐng)域，更具體地，本發(fā)明涉及一種柵格地圖的路徑規(guī)劃方法。

背景技術(shù)

作為機電一體化的最高成就，移動機器人涉及到了諸多傳感器信息融合、系統(tǒng)工程、自動控制技術(shù)等學(xué)科領(lǐng)域的各類知識且交叉了眾多科學(xué)領(lǐng)域技術(shù)，在工業(yè)、農(nóng)業(yè)、醫(yī)療等行業(yè)廣泛應(yīng)用，要實現(xiàn)機器人在未知環(huán)境下作業(yè)，需要具備實時、自主運行的能力，路徑規(guī)劃是一個重要環(huán)節(jié)，其直接決定移動機器人行駛的路徑。路徑規(guī)劃是指在一個靜態(tài)或者動態(tài)、簡單或復(fù)雜運行的空間中，如何為機器人搜索一條恰當(dāng)?shù)膹钠瘘c至目標(biāo)點的移動路徑，并確保機器人在運動過程中能夠安全的、無碰地繞過所有障礙物。

現(xiàn)有的基于改進(jìn)Astar算法的港口無人機巡檢路徑規(guī)劃方法，根據(jù)港口實際環(huán)境建立飛行場地地圖，設(shè)置飛行起飛及所有任務(wù)點；然后采用改進(jìn)Astar算法進(jìn)行起點和任務(wù)點的路徑規(guī)劃，該方法并未考慮到經(jīng)過狹道的問題，在通過狹道時，Astar算法搜索出的路徑靠近一側(cè)障礙物，存在安全性不高的問題。

發(fā)明內(nèi)容

本發(fā)明提供了一種柵格地圖的路徑規(guī)劃方法，旨在改善上述問題。

本發(fā)明是這樣實現(xiàn)的，一種柵格地圖的路徑規(guī)劃方法，所述方法具體包括如下步驟：

S1、構(gòu)建柵格地圖，對柵格地圖中的障礙物進(jìn)行膨脹處理；

S2、構(gòu)建拓?fù)涞貓D，在狹道的出口及入口處設(shè)有拓?fù)潼c，兩個拓?fù)潼c均位于狹道的安全區(qū)域；

S3、基于用Floyd算法獲取起始拓?fù)潼c至終止拓?fù)潼c的拓?fù)渎窂近c集，刪除拓?fù)渎窂近c集中的起始拓?fù)潼c及終止拓?fù)潼c，將剩余的拓?fù)渎窂近c加入路徑點集中；

S4、在路徑點集的首尾出分別加入任務(wù)起點及任務(wù)終點，基于A-stars算法依次規(guī)劃路徑點集中相鄰路徑點間的路徑，生成全局路徑點集。

進(jìn)一步的，路徑點集中相鄰路徑點間的路徑規(guī)劃方法具體包括如下步驟：

S41、生成一個包含開始節(jié)點n0的搜索圖G，把n0放在OPEN表中，生成空表CLOSED表；

S42、選擇OPEN表上的第一個節(jié)點，將其從OPEN表中移入CLOSE表，稱該節(jié)點為n；

S43、檢測節(jié)點n是否為目標(biāo)節(jié)點，若檢測結(jié)果為是，則在搜索圖G中基于n到n0的指針找到相鄰路徑點間的路徑，若檢測結(jié)果為否，則轉(zhuǎn)向步驟S44；

S44、擴展節(jié)點n，生成其后繼節(jié)點集M，節(jié)點n的祖先不可在節(jié)點集M中，且節(jié)點集M中的節(jié)點均為可行走的節(jié)點；

S45、針對后繼節(jié)點集M中每個不在搜索圖G中的節(jié)點，建立一個指向n的指針，針對節(jié)點集M中每個已在OPEN表或CLOSE表中的節(jié)點m，若到目前為止到達(dá)節(jié)點m的估價函數(shù)f最小值通過節(jié)點n，則將節(jié)點m的指針修改為指向節(jié)點n；

S46、基于估價函數(shù)f從小至大的順序重新排列OPEN表中的節(jié)點，并返回步驟S44。

進(jìn)一步的，估價函數(shù)f(n)表示如下：

f(n)＝g(n)+h(n)

g(n)為任務(wù)起點到節(jié)點n的最短路徑值，h(n)為節(jié)點n到任務(wù)終點的最短路徑；