[發(fā)明專利]大面積環(huán)境中的改進型快速搜索隨機樹路徑規(guī)劃方法

有效

• 申請?zhí)枺?/td>: 202011179457.5
• 申請日: 2020-10-29
• 公開（公告）號: CN112393739B
• 公開（公告）日: 2022-07-29
• 發(fā)明（設(shè)計）人: 黃杰;尚偉偉;董翔宇;朱俊;吳永恒;劉鑫;汪太平;楊波;柴宏博;陳源;崇寶辰;張飛
• 申請（專利權(quán)）人: 國網(wǎng)安徽省電力有限公司檢修分公司
• 主分類號: G01C21/34
• 分類號: G01C21/34
• 代理公司: 北京潤平知識產(chǎn)權(quán)代理有限公司 11283
• 代理人: 肖冰濱;劉兵

本發(fā)明實施方式提供一種大面積環(huán)境中的改進型快速搜索隨機樹路徑規(guī)劃方法，屬于機器人路徑規(guī)劃技術(shù)領(lǐng)域。本發(fā)明提供的大面積環(huán)境中的改進型快速搜索隨機樹路徑規(guī)劃方法通過將在規(guī)劃空間中尋找采樣點，在起始點和采樣點、采樣點和起始點、采樣點和目標點、目標點和采樣點之間分別建立搜索樹進行路徑搜索。將大面積環(huán)境的路徑規(guī)劃問題轉(zhuǎn)化為多個路徑規(guī)劃問題，降低了路徑規(guī)劃算法的復雜度，提高了路徑規(guī)劃算法的執(zhí)行效率。

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

本發(fā)明涉及移動機器人路徑規(guī)劃技術(shù)領(lǐng)域，具體地涉及一種大面積環(huán)境中的改進型快速搜索隨機樹路徑規(guī)劃方法。

背景技術(shù)

隨著人類生活水平的不斷提高以及工業(yè)自動化、智能化程度的迅速發(fā)展，機器人的應(yīng)用越來越廣泛，研究也越來越深入。智能移動機器人在農(nóng)業(yè)、工業(yè)、服務(wù)業(yè)、航天、醫(yī)療、軍事等不同的領(lǐng)域發(fā)展迅猛并被廣泛運用，具有很大的社會價值。機器人在移動過程中，會遇到許多障礙物，而如何在復雜多變的工作環(huán)境中規(guī)劃一條從起點到終點的無碰撞的路徑，是移動機器人研究的一大課題。

機器人的運動規(guī)劃在長久的發(fā)展過程中，形成了基于圖搜素的辦法、基于空間采樣的辦法、基于人工勢場的辦法等等許多不一樣的規(guī)劃方法。目前常用的規(guī)劃算法有A*、人工勢場法、動態(tài)窗口法、快速搜索隨機樹以及它們的變形優(yōu)化算法等，其中快速搜索隨機樹作為一種迭代的增量式搜索算法，因其概率完整性以及適用于高維空間的特性，受到相關(guān)行業(yè)人員的廣泛關(guān)注和研究。

在大面積復雜環(huán)境中的路徑搜索，目前的基于快速搜索隨機樹的改進算法的時間性能較低的問題并沒有被很好地解決。

發(fā)明內(nèi)容

本發(fā)明實施方式的目的是提供一種大面積環(huán)境中的改進型快速搜索隨機樹路徑規(guī)劃方法，該方法能夠克服現(xiàn)有技術(shù)中隨機搜索樹無法適應(yīng)大面積環(huán)境的技術(shù)缺陷。

為了實現(xiàn)上述目的，本發(fā)明實施方式提供一種大面積環(huán)境中的改進型快速搜索隨機樹路徑規(guī)劃方法，所述方法包括：

確定整個規(guī)劃空間的可通行區(qū)域和障礙物區(qū)域；

以起始點為圓心、所述起始點與目標點的距離的一半為半徑作圓??；

以預設(shè)的弧度間隔在所述圓弧上隨機選取采樣點；

判斷選取的采樣點是否在所述障礙物區(qū)域；

在判斷選取的采樣點在所述障礙物區(qū)域的情況下，再次以預設(shè)的弧度間隔在所述圓弧上隨機選取采樣點，并執(zhí)行所述方法的相應(yīng)步驟，直到判斷選取的采樣點不在所述障礙物區(qū)域；

在判斷選取的采樣點不在所述障礙物區(qū)域的情況下，在所述起始點和選取的采樣點建立第一棵搜索樹，在選取的采樣點和所述起始點之間建立第二棵搜索樹，在選取的采樣點和所述目標點之間建立第三棵搜索樹，在所述目標點和選取的采樣點之間建立第四棵搜索樹；

判斷所述第一棵搜索樹的擴展點和所述第二棵搜索樹的擴展點之間的距離是否小于或等于預設(shè)的閾值距離；

在判斷所述第一棵搜索樹的擴展點和所述第二棵搜索樹的擴展點之間的距離小于預設(shè)的閾值距離的情況下，將所述第一棵搜索樹當前的路徑和所述第二棵搜索樹當前的路徑組合以得到所述起始點和選取的采樣點之間的路徑；

判斷所述第三棵搜索樹的擴展點和所述第四棵搜索樹的擴展點之間的距離是否小于所述閾值距離；

在判斷所述第三棵搜索樹的擴展點和所述第四棵搜索樹的擴展點之間的距離小于所述閾值距離的情況下，將所述第三棵搜索樹當前的路徑和所述第四棵搜索樹當前的路徑組合以得到選取的采樣點和所述目標點之間的路徑；

將所述起始點和選取的采樣點之間的路徑和選取的采樣點和所述目標點之間的路徑組合以得到所述起始點和所述目標點之間的路徑。

可選地，所述以預設(shè)的弧度間隔在所述圓弧上隨機選取采樣點具體包括：