[發(fā)明專利]一種基于改進(jìn)A*算法和貝塞爾曲線的全局路徑規(guī)劃方法

在審

• 申請(qǐng)?zhí)枺?/td>: 202110024447.2
• 申請(qǐng)日: 2021-01-08
• 公開（公告）號(hào): CN112683278A
• 公開（公告）日: 2021-04-20
• 發(fā)明（設(shè)計(jì)）人: 金世俊;柴引引
• 申請(qǐng)（專利權(quán)）人: 東南大學(xué)
• 主分類號(hào): G01C21/20
• 分類號(hào): G01C21/20;G01C21/34;G05D1/02;G01S17/931
• 代理公司: 南京眾聯(lián)專利代理有限公司 32206
• 代理人: 蔣昱

本發(fā)明公開一種基于改進(jìn)A*算法和貝塞爾曲線的全局路徑規(guī)劃方法，具體包括以下步驟：步驟S1：利用激光雷達(dá)傳感器采集的環(huán)境信息建立柵格地圖，每個(gè)柵格被標(biāo)記為可行區(qū)域或障礙區(qū)域，并給定路徑規(guī)劃的起始點(diǎn)S和目標(biāo)點(diǎn)G；步驟S2：引入動(dòng)態(tài)調(diào)整因子μ優(yōu)化代價(jià)函數(shù)f(N)；步驟S3：將搜索鄰節(jié)點(diǎn)范圍擴(kuò)大為24鄰域，執(zhí)行改進(jìn)的A*算法，找出最優(yōu)路徑；步驟S4：去除路徑中的共線節(jié)點(diǎn)；步驟S5：利用貝塞爾曲線對(duì)路徑進(jìn)行平滑處理。本發(fā)明將傳統(tǒng)A*算法8鄰域搜索范圍擴(kuò)大為24鄰域，引入動(dòng)態(tài)調(diào)整因子μ優(yōu)化代價(jià)函數(shù)，提高了算法搜索效率，利用貝塞爾曲線對(duì)路徑進(jìn)行平滑處理，減少了折彎次數(shù)，相比傳統(tǒng)A*算法，路徑更平滑，路徑規(guī)劃效率更高且更可靠。

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

本發(fā)明涉及移動(dòng)機(jī)器人路徑規(guī)劃領(lǐng)域，特別是涉及到一種基于改進(jìn)A*算法和貝塞爾曲線的全局路徑規(guī)劃方法。

背景技術(shù)

根據(jù)外部環(huán)境信息是否已知，路徑規(guī)劃算法分為全局路徑規(guī)劃算法和局部路徑規(guī)劃算法；根據(jù)算法的搜索方式，可分為盲目式搜索和啟發(fā)式搜索算法。A*算法是一種具有啟發(fā)式特征的全局路徑搜索算法，集中了Dijkstra算法和最佳優(yōu)先搜索算法的優(yōu)點(diǎn)，具有簡(jiǎn)單高效、靈活性強(qiáng)和準(zhǔn)確性高的特點(diǎn)，被廣泛應(yīng)用于全局路徑規(guī)劃當(dāng)中。但傳統(tǒng)A*算法8鄰域搜索的方法，限制了節(jié)點(diǎn)的運(yùn)動(dòng)方向只能為0.25π整數(shù)倍，容易出現(xiàn)不是最短路徑且存在冗余節(jié)點(diǎn)和路徑拐點(diǎn)過多的問題。啟發(fā)函數(shù)h(N)的選擇，直接影響路徑搜索結(jié)果，當(dāng)靠近終點(diǎn)時(shí)，啟發(fā)函數(shù)h(N)在代價(jià)函數(shù)f(N)中所占比例減小,算法搜索效率就會(huì)降低，但是h(N)比重過高時(shí)，又會(huì)造成在路徑搜索初期的搜索空間過小，難以找到最優(yōu)解。

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

為了解決上述存在問題。本發(fā)明提供一種基于改進(jìn)A*算法和貝塞爾曲線的全局路徑規(guī)劃方法，該方法將傳統(tǒng)A*算法8鄰域搜索范圍擴(kuò)大為24鄰域，引入動(dòng)態(tài)調(diào)整因子μ優(yōu)化代價(jià)函數(shù)，提高了算法搜索效率，同時(shí)利用貝塞爾曲線進(jìn)行路徑平滑處理，進(jìn)一步減少了多余的路徑節(jié)點(diǎn)。

本發(fā)明提供一種基于改進(jìn)A*算法和貝塞爾曲線的全局路徑規(guī)劃方法，具體包括以下步驟：

步驟S1：利用激光雷達(dá)傳感器采集的環(huán)境信息建立柵格地圖，每個(gè)柵格被標(biāo)記為可行區(qū)域或障礙區(qū)域，并給定路徑規(guī)劃的起始點(diǎn)S和目標(biāo)點(diǎn)G；

步驟S2：引入動(dòng)態(tài)調(diào)整因子μ優(yōu)化代價(jià)函數(shù)f(N)；

步驟S3：將搜索鄰節(jié)點(diǎn)范圍擴(kuò)大為24鄰域，執(zhí)行改進(jìn)的A*算法，找出最優(yōu)路徑；

步驟S4：去除路徑中的共線節(jié)點(diǎn)；

步驟S5：利用貝塞爾曲線對(duì)路徑進(jìn)行平滑處理。

進(jìn)一步，所述步驟S2具體包括以下過程：

引入動(dòng)態(tài)調(diào)整因子μ優(yōu)化代價(jià)函數(shù)f(N)：

f(N)＝g(N)+μ·h(N)

其中，(x_S,y_S)為起始點(diǎn)S坐標(biāo)，(x_N,y_N)為當(dāng)前節(jié)點(diǎn)N坐標(biāo)，(x_G,y_G)為目標(biāo)點(diǎn)G坐標(biāo)；g(N)表示起始點(diǎn)S到當(dāng)前節(jié)點(diǎn)N的實(shí)際移動(dòng)代價(jià)函數(shù)；h(N)表示當(dāng)前節(jié)點(diǎn)N到目標(biāo)點(diǎn)G的估計(jì)移動(dòng)代價(jià)，通常將h(N)稱為啟發(fā)函數(shù)；隨著路徑搜索向目標(biāo)點(diǎn)靠近，動(dòng)態(tài)調(diào)整因子μ值越來越大，啟發(fā)函數(shù)h(N)所占比重就越大，增加了算法的快速收斂性，提高了搜索效率。

進(jìn)一步，所述步驟S3具體包括以下過程：

S3.1分別構(gòu)建開放列表OPEN表和關(guān)閉列表CLOSE表，其中OPEN表存放待檢測(cè)節(jié)點(diǎn)，CLOSE表存放檢測(cè)過或者不需要檢測(cè)的節(jié)點(diǎn)，并將起始節(jié)點(diǎn)放入OPEN表；

S3.2遍歷OPEN表，查找代價(jià)函數(shù)f值最小的節(jié)點(diǎn)作為要處理的當(dāng)前節(jié)點(diǎn)N，并將當(dāng)前節(jié)點(diǎn)N從OPEN表刪除，添加到CLOSE表；