[發(fā)明專利]一種基于概率模型的路徑規(guī)劃方法、系統(tǒng)及介質(zhì)

在審

• 申請(qǐng)?zhí)枺?/td>: 202111157218.4
• 申請(qǐng)日: 2021-09-30
• 公開（公告）號(hào): CN113741484A
• 公開（公告）日: 2021-12-03
• 發(fā)明（設(shè)計(jì)）人: 龔文勇;吳小天
• 申請(qǐng)（專利權(quán)）人: 暨南大學(xué)
• 主分類號(hào): G05D1/02
• 分類號(hào): G05D1/02
• 代理公司: 廣州市華學(xué)知識(shí)產(chǎn)權(quán)代理有限公司 44245
• 代理人: 李斌

本發(fā)明公開了一種基于概率模型的路徑規(guī)劃方法、系統(tǒng)及介質(zhì)，該方法包括給定地圖或點(diǎn)云上的起點(diǎn)和終點(diǎn)位置；多次執(zhí)行改進(jìn)的RRT算法；構(gòu)造概率轉(zhuǎn)移矩陣；基于概率模型進(jìn)行路徑規(guī)劃；基于push動(dòng)態(tài)規(guī)劃算法進(jìn)行最優(yōu)路徑計(jì)算。本發(fā)明對(duì)RRT方法進(jìn)行了改進(jìn)，克服其因步長(zhǎng)固定而自由度較低的問(wèn)題，使得RRT模型具有更大的隨機(jī)性，在RRT實(shí)驗(yàn)中可覆蓋盡可能多的節(jié)點(diǎn)。本發(fā)明采用基于push的方法實(shí)現(xiàn)高效的動(dòng)態(tài)規(guī)劃解法，不僅克服出現(xiàn)局部最優(yōu)解的問(wèn)題，而且對(duì)比常規(guī)動(dòng)態(tài)規(guī)劃方法的空間復(fù)雜度較低，占用的計(jì)算機(jī)內(nèi)存較小，運(yùn)行計(jì)算效率更高。

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

本發(fā)明屬于機(jī)器人的技術(shù)領(lǐng)域，具體涉及一種基于概率模型的路徑規(guī)劃方法、系統(tǒng)及介質(zhì)。

背景技術(shù)

路徑規(guī)劃是尋找給定兩點(diǎn)之間的一條距離最短或者其它最優(yōu)準(zhǔn)則下的路徑，且沿著這路徑路行走不會(huì)和其它的物體發(fā)生碰撞。兩點(diǎn)之間的最優(yōu)路徑可能是拐彎最少的路徑，也可能是減速最少的路徑，亦或是任何其它應(yīng)用要求的最優(yōu)路徑。路徑規(guī)劃不僅在機(jī)器人領(lǐng)域受到廣泛關(guān)注，其在無(wú)人車駕駛，無(wú)人機(jī)避障，GPS導(dǎo)航，GIS道路規(guī)劃，基因序列和電腦游戲等領(lǐng)域也發(fā)揮了巨大的作用。本發(fā)明給出的路徑規(guī)劃方案強(qiáng)調(diào)機(jī)器人在行走時(shí)與周圍環(huán)境交互時(shí)的安全性，能夠保證比較友好的人機(jī)交互過(guò)程，此發(fā)明能夠廣泛地應(yīng)用于服務(wù)型機(jī)器人，也能夠應(yīng)用在無(wú)人車導(dǎo)航領(lǐng)域，具有較好的市場(chǎng)應(yīng)用前景和產(chǎn)業(yè)化價(jià)值。

設(shè)計(jì)路徑需要滿足約束條件的能量函數(shù)，然后通過(guò)優(yōu)化技術(shù)搜索最優(yōu)的路徑是一種常用的路徑規(guī)劃方案。人工勢(shì)場(chǎng)法通過(guò)建模引力場(chǎng)和斥力場(chǎng)以達(dá)到設(shè)計(jì)最優(yōu)路徑的目的。人工勢(shì)場(chǎng)將障礙物對(duì)機(jī)器人的阻礙作用建模為斥力場(chǎng)，排斥機(jī)器人靠近障礙物，將目標(biāo)位置對(duì)機(jī)器人的吸引建模為引力場(chǎng)，在引力場(chǎng)和斥力場(chǎng)的作用下引導(dǎo)機(jī)器人到達(dá)目標(biāo)位置。人工勢(shì)場(chǎng)法設(shè)計(jì)的路徑比較光滑，而且不會(huì)撞上障礙物，但該方法存在一些偽目標(biāo)點(diǎn)，當(dāng)機(jī)器人到達(dá)這些位置時(shí)，算法不能給出下一步機(jī)器人前進(jìn)的方向，但其陷入局部最優(yōu)解。整數(shù)規(guī)劃，深度優(yōu)先，廣度優(yōu)先，最佳優(yōu)先，神經(jīng)網(wǎng)絡(luò)等方法也是基于能量函數(shù)的路徑規(guī)劃方法。

用幾何方法設(shè)計(jì)機(jī)器人行走的路徑一般是將空間劃分為一些基本的幾何單元，然后將這些基本幾何單元中不包含障礙物的單元組成一個(gè)集合，形成無(wú)碰撞空間，最后在無(wú)碰撞空間中尋找最優(yōu)路徑，常見的幾何路徑規(guī)劃方法有自由空間法，Voronoi圖方法和可視圖方法等。幾何路徑規(guī)劃方法首先構(gòu)建一個(gè)路徑圖絡(luò)，然后基于網(wǎng)絡(luò)的路徑規(guī)劃方法尋找最優(yōu)路徑,在路徑尋找以后進(jìn)一步平滑路徑，使機(jī)器人在此路徑上易于行走。

上面所述的都是傳統(tǒng)的路徑規(guī)劃方法，一般這些方法在地圖比較復(fù)雜且規(guī)模較大時(shí)會(huì)出現(xiàn)計(jì)算復(fù)雜度較高，計(jì)算時(shí)間長(zhǎng)，和局部極小值點(diǎn)等問(wèn)題。而且傳統(tǒng)的路徑規(guī)劃方法處理靜態(tài)場(chǎng)景的情形，對(duì)于動(dòng)態(tài)場(chǎng)景更是不易處理。

模擬退火算法由Alfaro和Garcia于1998年首次引入到機(jī)器人路徑規(guī)劃領(lǐng)域，使得大場(chǎng)景的路徑規(guī)劃問(wèn)題的求解成為可能，但是此方法收斂速度較慢，而且搜索得到的路徑具有隨機(jī)性。基于增強(qiáng)的模擬退火方法搜索動(dòng)態(tài)環(huán)境下的最優(yōu)路徑，部分地克服了模擬退火算法的弱點(diǎn)。禁忌搜索應(yīng)用于路徑規(guī)劃的能夠有效地避免陷入局部最優(yōu)點(diǎn)。蟻群優(yōu)化方法是另一種有效地最優(yōu)路徑計(jì)算方法,如SCAO-MH(Simple Ant Colony OptimizationMeta-Heuristic)方法存儲(chǔ)一張已訪問(wèn)節(jié)點(diǎn)信息表的方法，能夠有效地克服蟻群算法處理路徑規(guī)劃時(shí)的局部極值點(diǎn)問(wèn)題。概率路徑圖法構(gòu)建了一個(gè)啟發(fā)函數(shù)，然后根據(jù)此啟發(fā)函數(shù)尋找最優(yōu)路徑。另外，粒子群方法在路徑規(guī)劃中也有廣泛的應(yīng)用。上述的這些方法都可視為元啟發(fā)式方法，這些方法的優(yōu)點(diǎn)是能夠高效地獲得路徑解，但是這些方法一般都是隨機(jī)的，故不能獲得唯一解，而且很多時(shí)候它們也并不能獲得實(shí)時(shí)解。

Dijkstra算法是圖上的最短路徑搜索算法，但是其效率較低。為了利用Dijkstra算法的優(yōu)點(diǎn)，并提高其效率，研究人員提出了A*算法，目前A*算法及其變種是使用的比較廣泛的一種啟發(fā)式路徑規(guī)劃算法。A*算法的高效性主要在于應(yīng)用啟發(fā)函數(shù)減少搜索節(jié)點(diǎn)。