啟發(fā)式自適應(yīng)步長優(yōu)化Ｉｎｆｏｒｍｅｄ-ＲＲＴ* 算法

摘 要：Ｉｎｆｏｒｍｅｄ-ＲＲＴ* 算法是解決全局路徑規(guī)劃問題常用的算法。當(dāng)處理狹窄環(huán)境時，Ｉｎｆｏｒｍｅｄ-ＲＲＴ* 算法往往容易陷入局部最優(yōu)解，而在復(fù)雜環(huán)境中路徑規(guī)劃的成本又往往過高。為了解決這些問題，提出了一種基于啟發(fā)式自適應(yīng)步長的采樣策略，以改進Ｉｎｆｏｒｍｅｄ-ＲＲＴ* 算法的不足之處。通過在隨機節(jié)點周圍擴展采樣點集來計算啟發(fā)式值，選擇最優(yōu)節(jié)點并按照其生長方向進行擴張。通過計算最優(yōu)節(jié)點與最近節(jié)點的距離，確定下一次采樣的步長。這使得機器人能夠更好地適應(yīng)二維和三維環(huán)境中的狹窄區(qū)域和復(fù)雜環(huán)境。將改進的算法在二維和三維環(huán)境中進行仿真驗證，實驗結(jié)果表明了該算法的有效性和魯棒性較為優(yōu)異。

關(guān)鍵詞：路徑規(guī)劃；啟發(fā)式自適應(yīng)步長；Ｉｎｆｏｒｍｅｄ-ＲＲＴ* ；三維場景

中圖分類號：Ｖ２７１． ４ 文獻(xiàn)標(biāo)志碼：Ａ

文章編號：１００３－３１０６（２０２４）１０－２４４６－０７

０ 引言

隨著機器人技術(shù)的迅速發(fā)展，移動機器人和無人機被廣泛應(yīng)用于偵查、搜救、運輸、救援、勘測和其他特殊領(lǐng)域［１－３］。而機器人路徑規(guī)劃則是實現(xiàn)上述場景的關(guān)鍵。路徑規(guī)劃簡單來說就是在保證機器人安全的情況下，找到一條漸近最優(yōu)路徑［４］。因此研究二維場景和三維場景下的路徑規(guī)劃算法是目前研究的熱點［５－６］。根據(jù)機器人對環(huán)境信息的掌握程度可以將路徑規(guī)劃分為全局路徑規(guī)劃［７］和局部路徑規(guī)劃［８］。常見的路徑規(guī)劃算法有基于圖搜索的Ａ算法［９］、基于隨機采樣的快速隨機搜索樹（Ｒａｐｉｄｌｙｅｘｐｌｏｒｉｎｇ Ｒａｎｄｏｍ Ｔｒｅｅ，ＲＲＴ）算法［１０］及一些智能仿生算法［１１－１３］。

隨著近幾十年的研究發(fā)展，不少學(xué)者逐漸優(yōu)化了上述算法，提升了算法的性能。如學(xué)者Ｌａｖａｌｌｅ［１４］通過引入優(yōu)化節(jié)點，提出ＲＲＴ* 算法，使得在足夠的迭代次數(shù)下能夠找到漸近最優(yōu)路徑。但是由于隨機采樣，會導(dǎo)致算法規(guī)劃效率較慢。針對這一問題，Ｇａｍｍｅｌｌ 等［１５］在ＲＲＴ* 算法的基礎(chǔ)上，提出了Ｉｎ-ｆｏｒｍｅｄ-ＲＲＴ* 算法。該算法通過構(gòu)建超橢球空間，限制了采樣空間，有效地提升了算法的采樣效率。隨后，Ｋａｒａｍａｎ 等［１６］于２０１１ 年將Ｉｎｆｏｒｍｅｄ-ＲＲＴ* 與Ｖｏｒｏｎｏｉ 圖結(jié)合，使算法能夠更好地利用環(huán)境特征。文獻(xiàn)［１７］通過提出一種基于自適應(yīng)增長策略和橢圓區(qū)域變權(quán)采樣策略的改進Ｉｎｆｏｒｍｅｄ-ＲＲＴ* 算法，并進行了軌跡優(yōu)化，改善了規(guī)劃效率。劉文倩等［１８］引入人工勢場加快了Ｉｎｆｏｒｍｅｄ-ＲＲＴ* 收斂到漸近最優(yōu)的速度。但是上述這些算法在狹窄環(huán)境和復(fù)雜環(huán)境下，其魯棒性不高且容易陷入局部最優(yōu)。