啟發式自適應步長優化Ｉｎｆｏｒｍｅｄ-ＲＲＴ* 算法

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

關鍵詞：路徑規劃；啟發式自適應步長；Ｉｎｆｏｒｍｅｄ-ＲＲＴ* ；三維場景

中圖分類號：Ｖ２７１． ４ 文獻標志碼：Ａ

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

０ 引言

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

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