[發(fā)明專(zhuān)利]一種基于拓展引導(dǎo)的非均勻采樣運(yùn)動(dòng)規(guī)劃方法

在審

• 申請(qǐng)?zhí)枺?/td>: 202210455016.6
• 申請(qǐng)日: 2022-04-27
• 公開(kāi)（公告）號(hào): CN114764250A
• 公開(kāi)（公告）日: 2022-07-19
• 發(fā)明（設(shè)計(jì)）人: 陳彥杰;張智星;蘭立民;于建業(yè)
• 申請(qǐng)（專(zhuān)利權(quán)）人: 福州大學(xué)
• 主分類(lèi)號(hào): G05D1/02
• 分類(lèi)號(hào): G05D1/02;G06Q10/04
• 代理公司: 福州元?jiǎng)?chuàng)專(zhuān)利商標(biāo)代理有限公司 35100
• 代理人: 蔡學(xué)俊;薛金才

本發(fā)明提供了一種基于拓展引導(dǎo)的非均勻采樣運(yùn)動(dòng)規(guī)劃方法，包括如下步驟：步驟S1、狹窄通道拓展起點(diǎn)選擇：利用混合高斯采樣，得到點(diǎn)集和點(diǎn)集，從點(diǎn)集中篩選狹窄通道拓展起點(diǎn)，組成集合；步驟S2、導(dǎo)向階段初始方向選擇；步驟S3、局部采樣：將當(dāng)前拓展點(diǎn)更新為，在為中心，半徑為，軸線方向?yàn)榈陌肭蛴騼?nèi)進(jìn)行均勻采樣，采樣點(diǎn)集合為；步驟S4、判斷是否仍位于狹窄通道內(nèi)：應(yīng)用本技術(shù)方案可實(shí)現(xiàn)在狹窄通道環(huán)境中能快速得到最優(yōu)解，并且無(wú)狹窄通道的環(huán)境中仍具有較高的性能。

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

本發(fā)明涉及移動(dòng)機(jī)器人運(yùn)動(dòng)規(guī)劃技術(shù)領(lǐng)域，特別是一種基于拓展引導(dǎo)的非均勻采樣運(yùn)動(dòng)規(guī)劃方法。

背景技術(shù)

隨著現(xiàn)代科學(xué)的飛速發(fā)展，自動(dòng)化、智能化水平不斷提高，機(jī)器人技術(shù)也愈發(fā)成熟，在工業(yè)、服務(wù)、醫(yī)療等領(lǐng)域得到了廣泛應(yīng)用。但隨著應(yīng)用場(chǎng)景的拓寬，機(jī)器所面對(duì)的環(huán)境也日趨復(fù)雜多變。如何在充滿(mǎn)不確定性的環(huán)境中使機(jī)器人安全高效地運(yùn)作成為了十分重要的課題。運(yùn)動(dòng)規(guī)劃作為機(jī)器人應(yīng)對(duì)各類(lèi)復(fù)雜環(huán)境完成智能自主作業(yè)的關(guān)鍵也因此受到的廣泛的關(guān)注與研究。

運(yùn)動(dòng)規(guī)劃在移動(dòng)機(jī)器人、工業(yè)機(jī)械臂、自動(dòng)駕駛等領(lǐng)域具有重要的地位。它主要根據(jù)給定的起始狀態(tài)和目標(biāo)狀態(tài)，在位形空間中得到一條連接起始狀態(tài)和目標(biāo)狀態(tài)的可行路徑，進(jìn)而得到一組不與障礙物發(fā)生碰撞的機(jī)器人位形序列。目前常見(jiàn)的運(yùn)動(dòng)規(guī)劃方法包括基于搜索的規(guī)劃方法、基于勢(shì)場(chǎng)的規(guī)劃方法和基于采樣的規(guī)劃方法。

為滿(mǎn)足一些任務(wù)要求，機(jī)器人有時(shí)需要在狹窄通道中工作。例如，移動(dòng)機(jī)器人在狹長(zhǎng)的走廊中通行，機(jī)械臂在零件的腔體內(nèi)部進(jìn)行焊接工作等。在狹窄通道中規(guī)劃一條安全可靠的路徑對(duì)運(yùn)動(dòng)規(guī)劃算法是一個(gè)巨大挑戰(zhàn)。基于搜索的規(guī)劃算法主要依賴(lài)于對(duì)規(guī)劃空間的網(wǎng)格細(xì)分，當(dāng)環(huán)境中存在狹窄通道時(shí)，需要增加細(xì)分網(wǎng)格的數(shù)量以精確地估計(jì)位形空間的連通性，但這也將大大增加計(jì)算負(fù)擔(dān)。基于勢(shì)場(chǎng)的規(guī)劃方法在存在狹窄通道的環(huán)境中可能無(wú)法找到最優(yōu)解，需要針對(duì)環(huán)境設(shè)計(jì)更復(fù)雜的勢(shì)函數(shù)避免陷入局部最優(yōu)解并實(shí)現(xiàn)最優(yōu)規(guī)劃，增加了規(guī)劃問(wèn)題的解決難度。而基于采樣的規(guī)劃算法不依賴(lài)于網(wǎng)格細(xì)分并且能夠收斂到最優(yōu)解，在存在狹窄通道的規(guī)劃問(wèn)題中可以規(guī)避上述問(wèn)題，有助于提高運(yùn)動(dòng)規(guī)劃的效率。

然而，對(duì)于基于采樣的規(guī)劃算法，由于在狹窄通道內(nèi)采樣概率低，狹窄通道區(qū)域探索困難等原因，在狹窄通道環(huán)境中的規(guī)劃效率將明顯降低。為解決該問(wèn)題，學(xué)界提出了許多改進(jìn)方法。其中一類(lèi)方法是識(shí)別并探索狹窄通道，該類(lèi)方法包括Spark PRM和RRV等。SparkPRM通過(guò)圖的大小和圖之間的連通性識(shí)別狹窄通道，通過(guò)在狹窄通道中構(gòu)建樹(shù)以連接不同的圖，但所構(gòu)建的樹(shù)缺乏拓展引導(dǎo)，效率不高，并且通過(guò)狹窄通道后的樹(shù)需要進(jìn)行裁剪，這意味著部分構(gòu)建樹(shù)的計(jì)算在之后的規(guī)劃當(dāng)中是無(wú)用的，增加了額外計(jì)算，不利于算法的后續(xù)迭代。RRV通過(guò)在拓展失效的采樣點(diǎn)附近采樣并執(zhí)行PCA算法識(shí)別狹窄通道并進(jìn)行拓展，但為了探索到探索狹窄通道的入口，需要在非狹窄通道區(qū)域額外增加較多采樣點(diǎn)，在無(wú)狹窄通道的環(huán)境會(huì)降低算法效率。并且，RRV探索入口時(shí)需要采用更小的拓展步距，降低了拓展的效率。總體而言，由于狹窄通道限制了樹(shù)的拓展，使用該類(lèi)方法需要增加較多額外計(jì)算，并且該類(lèi)算法主要修改規(guī)劃算法的拓展階段，考慮到各類(lèi)基于采樣的規(guī)劃算法在拓展和重布線等環(huán)節(jié)間的差異，不易于簡(jiǎn)便地進(jìn)行整合。

另一類(lèi)加快狹窄通道探索速度的方法為偏向采樣的方法，該類(lèi)方法包括高斯采樣和橋式測(cè)量法等方法。高斯采樣通過(guò)在無(wú)效采樣點(diǎn)附近依據(jù)高斯分布重新進(jìn)行采樣以提升狹窄通道內(nèi)采樣點(diǎn)密度，但同時(shí)也會(huì)增加障礙物外側(cè)的采樣點(diǎn)密度。橋式測(cè)量法相較高斯采樣能夠使采樣點(diǎn)更集中于狹窄通道中，但需要進(jìn)行更多的碰撞檢測(cè)，在障礙較多的規(guī)劃空間內(nèi)將增加大量計(jì)算。偏向采樣方法僅更改采樣點(diǎn)分布，易于整合入各類(lèi)基于采樣的規(guī)劃算法中，但由于缺少對(duì)狹窄通道的探索，難以使采樣點(diǎn)集中在期望區(qū)域，往往需要在開(kāi)闊區(qū)域獲得較多采樣點(diǎn)才能使狹窄通道內(nèi)采樣點(diǎn)密度達(dá)到期望數(shù)值，使得規(guī)劃路徑通過(guò)狹窄通道，不利于規(guī)劃算法的收斂。