[發(fā)明專利]基于改進(jìn)A*算法與人工勢(shì)場(chǎng)算法的混合路徑規(guī)劃方法

在審

• 申請(qǐng)?zhí)枺?/td>: 202111521794.2
• 申請(qǐng)日: 2021-12-13
• 公開(kāi)（公告）號(hào): CN114489040A
• 公開(kāi)（公告）日: 2022-05-13
• 發(fā)明（設(shè)計(jì)）人: 王海軍;陶偉忠;胡小剛;任雷平;李韜;劉朝;楊文宇;上官星馳;張?jiān)铺?/a>
• 申請(qǐng)（專利權(quán)）人: 中煤科工集團(tuán)信息技術(shù)有限公司
• 主分類號(hào): G05D1/02
• 分類號(hào): G05D1/02
• 代理公司: 西安恒泰知識(shí)產(chǎn)權(quán)代理事務(wù)所 61216
• 代理人: 李鄭建

1.一種基于改進(jìn)A*算法與人工勢(shì)場(chǎng)法的混合路徑規(guī)劃方法，其特征在于，該方法將全局預(yù)測(cè)和局部實(shí)時(shí)規(guī)劃結(jié)合成一個(gè)混合的兩層算法，即采用改進(jìn)A*算法完成全局預(yù)測(cè)，得到全局最優(yōu)的路徑節(jié)點(diǎn)；然后在這些節(jié)點(diǎn)中選擇拐點(diǎn)作為實(shí)時(shí)規(guī)劃的指導(dǎo)，實(shí)時(shí)規(guī)劃層采用改進(jìn)人工勢(shì)場(chǎng)法實(shí)時(shí)動(dòng)態(tài)避開(kāi)障礙物，連續(xù)運(yùn)行每個(gè)子目標(biāo)點(diǎn)，最終到達(dá)目標(biāo)點(diǎn)完成任務(wù)；

所述改進(jìn)A*算法和改進(jìn)人工勢(shì)場(chǎng)法融合過(guò)程如下：

(1)通過(guò)相關(guān)傳感器對(duì)環(huán)境進(jìn)行測(cè)量，并根據(jù)環(huán)境的特性和相關(guān)對(duì)象的特性構(gòu)建真實(shí)地圖，以獲得與環(huán)境特性相匹配的網(wǎng)格環(huán)境模型；

(2)改進(jìn)的全局路徑規(guī)劃算法是從全局路徑規(guī)劃到局部路徑規(guī)劃的一級(jí)；

(3)從預(yù)先確定的路徑節(jié)點(diǎn)中找出相應(yīng)的轉(zhuǎn)折點(diǎn)，并將這些轉(zhuǎn)折點(diǎn)作為實(shí)時(shí)規(guī)劃的參考點(diǎn)；

(4)采用改進(jìn)的人工勢(shì)場(chǎng)法在實(shí)時(shí)規(guī)劃層進(jìn)行二次運(yùn)算，并以全局路徑上的轉(zhuǎn)折點(diǎn)作為子點(diǎn)進(jìn)行實(shí)時(shí)處理，以避開(kāi)障礙物；

(5)在實(shí)時(shí)規(guī)劃算法的指導(dǎo)下，連續(xù)遍歷每個(gè)子目標(biāo)點(diǎn)，最終到達(dá)目標(biāo)點(diǎn)。

2.如權(quán)利要求1所述的方法，其特征在于，所述混合的兩層算法由兩層路徑規(guī)劃實(shí)現(xiàn)，具體包括：

(1)獲取環(huán)境信息；

(2)建立柵格地圖；

(3)進(jìn)入全局規(guī)劃層中的改進(jìn)的A*算法全局路徑規(guī)劃步驟，創(chuàng)建子目標(biāo)點(diǎn)；

(4)從創(chuàng)建子目標(biāo)點(diǎn)進(jìn)入局部規(guī)劃層中的改進(jìn)人工視場(chǎng)算法建立子目標(biāo)點(diǎn)，經(jīng)子目標(biāo)點(diǎn)的終點(diǎn)判斷，如果是，則完成規(guī)劃任務(wù)，結(jié)束；如果否，返回局部規(guī)劃層中的改進(jìn)人工視場(chǎng)算法建立子目標(biāo)點(diǎn)步驟。

3.如權(quán)利要求1所述的方法，其特征在于，所述改進(jìn)的A*算法是將啟發(fā)式函數(shù)h(n)引入到搜索中，通過(guò)啟發(fā)式信息從節(jié)點(diǎn)中選擇一個(gè)擴(kuò)展搜索，從而減少了節(jié)點(diǎn)擴(kuò)展的范圍和計(jì)算量；從以下兩個(gè)方面進(jìn)行了改進(jìn)：

(1)減少路徑中轉(zhuǎn)折點(diǎn)的數(shù)量并執(zhí)行平滑，具體包括：

路徑節(jié)點(diǎn)的處理如下：從起始點(diǎn)開(kāi)始依次取三個(gè)相鄰的節(jié)點(diǎn)，如果第一個(gè)點(diǎn)和第三個(gè)點(diǎn)之間的直線沒(méi)有運(yùn)行障礙物，則刪除第二個(gè)節(jié)點(diǎn)，并連續(xù)刪除，直到所有的點(diǎn)都被處理完，最后的路徑從這些節(jié)點(diǎn)開(kāi)始存在保留節(jié)點(diǎn)連接；

(2)通過(guò)參數(shù)設(shè)置，對(duì)路徑中的節(jié)點(diǎn)數(shù)進(jìn)行簡(jiǎn)化，采用加權(quán)的思想，對(duì)評(píng)價(jià)函數(shù)進(jìn)行優(yōu)化，優(yōu)化后的表達(dá)式如下：

f(n)＝(1-ω)g(n)+ωh(n)

其中，n為當(dāng)前節(jié)點(diǎn)，g(n)表示從起始點(diǎn)到當(dāng)前節(jié)點(diǎn)n的實(shí)際代價(jià)值，h(n)表示啟發(fā)式函數(shù)，ω為常數(shù)，且0＜ω＜1，應(yīng)根據(jù)實(shí)際環(huán)境選擇ω值；

所述改進(jìn)的A*算法實(shí)現(xiàn)的技術(shù)步驟包括：

步驟1：將起始點(diǎn)和障礙物節(jié)點(diǎn)添加到OPEN表和CLOSED表中；

步驟2：判斷OPEN表是否為空，若是，結(jié)束；若否，則從OPEN表中選擇代價(jià)最小的節(jié)點(diǎn)，并放到CLOSED節(jié)點(diǎn)中；

步驟3：判斷當(dāng)前節(jié)點(diǎn)是否為目標(biāo)點(diǎn)，若是，結(jié)束；若否，則進(jìn)入步驟4；

步驟4：判斷當(dāng)前節(jié)點(diǎn)是否在CLOSED表，如果是，跳過(guò)該節(jié)點(diǎn)繼續(xù)拓展其它節(jié)點(diǎn)，并返回至步驟2；如果不是，則進(jìn)入步驟5；

步驟5：把該節(jié)點(diǎn)的子節(jié)點(diǎn)逐個(gè)放入OPEN表，并返回至步驟2。

4.如權(quán)利要求1所述的方法，其特征在于，所述改進(jìn)的人工勢(shì)場(chǎng)法是對(duì)傳統(tǒng)人工勢(shì)場(chǎng)法的勢(shì)場(chǎng)函數(shù)中引入動(dòng)態(tài)速度和加速度信息，建立新的引力和斥力函數(shù)，實(shí)現(xiàn)動(dòng)態(tài)避障規(guī)劃。