[發(fā)明專利]一種機器人避碰路徑的規(guī)劃方法、裝置

有效

• 申請?zhí)枺?/td>: 201310586189.2
• 申請日: 2013-11-19
• 公開（公告）號: CN104154917A
• 公開（公告）日: 2014-11-19
• 發(fā)明（設計）人: 李華忠;梁永生;但唐仁;唐飛
• 申請（專利權）人: 深圳信息職業(yè)技術學院;李華忠
• 主分類號: G01C21/20
• 分類號: G01C21/20
• 代理公司: 深圳中一專利商標事務所 44237
• 代理人: 張全文

技術領域

本發(fā)明屬于機器人避碰和操控領域，尤其涉及一種機器人避碰路徑的規(guī)劃方法、裝置。

背景技術

目前，基于采樣的規(guī)劃技術已被廣泛應用于高自由度智能機器人避碰和操控等領域，成為國內外普遍關注的研究熱點。該方法的顯著優(yōu)點是基于隨機采樣只需近似構造自由位形空間，從而避免了采用骨架網格和柵格分解等方法需完整和精確構造全部有效C-空間模型，以尋找精確解析所帶來的PSPACE難題，規(guī)避了高自由度所引起的存儲空間和計算量呈指數爆炸增長的NP問題。最典型的兩類基于采樣的運動規(guī)劃方法為：快速隨機搜索樹法和概率地圖法。它們均利用采樣技術在自由C-空間中構造樹或圖，然后迭代細化，直到找到連接初始位形和目標位形的無碰撞路徑解。然而，該類方法的有效性，尤其在處理高維空間和復雜障礙環(huán)境等復雜問題時，嚴重依賴于所選的采樣參數和離散碰撞檢測距離參數。

發(fā)明內容

本發(fā)明實施例提供了一種機器人避碰路徑的規(guī)劃方法、裝置，旨在解決現(xiàn)有技術在處理高維空間和復雜障礙環(huán)境等復雜問題時，嚴重依賴于所選的采樣參數和離散碰撞檢測距離參數的問題。

一方面，提供一種機器人避碰路徑的規(guī)劃方法，所述方法包括：

步驟1、根據機器人的初始位形q_s和目標位形q_g計算得到碰撞檢測距離參數的初始值r_col；

步驟2、根據所述初始位形q_s、目標位形q_g構造雙向快速密集搜索樹，所述雙向快速密集搜索樹包括正向快速密集搜索樹和逆向快速密集搜索樹；

步驟3、設置所述雙向快速密集搜索樹的碰撞檢測距離參數的值為r_col；

步驟4、根據所述初始位形q_s、目標位形q_g采用自適應雙向快速密集搜索樹動態(tài)擴展方法生成一條機器人規(guī)劃路徑；

步驟5、對所述機器人規(guī)劃路徑上的離散采樣位形點分別進行碰撞檢測，如果所有離散位形點均沒有與障礙物發(fā)生碰撞，則將由所有離散采樣位形點組成的機器人規(guī)劃路徑作為有效路徑，如果有離散位形點與障礙物發(fā)生碰撞，則執(zhí)行步驟6；

步驟6、更新r_col的值為r_col/2；

步驟7、循環(huán)執(zhí)行步驟3至6，直至生成的機器人規(guī)劃路徑上的所有離散位形點均沒有與障礙物發(fā)生碰撞為止。

進一步地，所述步驟4包括：

根據所述初始位形q_s、目標位形q_g計算得到擴展步長的初始值r_ext；

根據所述初始位形q_s、目標位形q_g和所述擴展步長的初始值r_ext配置所述雙向快速密集搜索樹；

局部調整所述擴展步長的初始值r_ext，獲得一條機器人規(guī)劃路徑。

進一步地，所述局部調整所述擴展步長的初始值r_ext，獲得一條機器人規(guī)劃路徑包括：

從位形空間隨機采樣獲得一個隨機采樣位形點q_rand；

搜索所述正向快速密集搜索樹上與所述隨機采樣位形q_rand最近鄰的邊e₁；

在邊e₁上搜索與所述隨機采樣位形q_rand最近鄰的位形點

根據所述q_rand、以及所述擴展步長計算得到不與障礙物發(fā)生碰撞的新位形點q_new；

根據所述最近鄰的位形點以及所述新位形點q_new做碰撞檢測；

如果連接所述最近鄰的位形點和所述新位形點q_new之間的路徑沒有與障礙物發(fā)生碰撞，則搜索所述逆向快速密集搜索樹上與所述新位形點q_new最近鄰的邊e₂；

在邊e₂上搜索與所述新位形點q_new最近鄰的位形點

根據所述最近鄰的位形點以及所述新位形點q_new做碰撞檢測；