[發明專利]一種多分辨率障礙物環境下移動機器人混合路徑規劃方法

有效

• 申請號: 201610278237.5
• 申請日: 2016-04-29
• 公開（公告）號: CN105717929B
• 公開（公告）日: 2018-06-15
• 發明（設計）人: 尹全軍;彭勇;秦龍;焦鵬;張琪;楊偉龍;孫林
• 申請（專利權）人: 中國人民解放軍國防科學技術大學
• 主分類號: G05D1/02
• 分類號: G05D1/02
• 代理公司: 湖南兆弘專利事務所(普通合伙) 43008
• 代理人: 趙洪

本發明公開了一種多分辨率障礙物環境下移動機器人混合路徑規劃方法，目的是解決現有方法初始規劃存在盲目性、環境建模缺乏靈活性、實時避障能力差的問題。技術方案是采用自適應非均勻極徑的極坐標建模方法對移動機器人運動空間進行環境建模；采用重力粒子群搜索方法規劃出從起點到終點的初始全局路徑；根據初始全局路徑，采用改進的人工勢場法，通過預估最小安全距離和安全避碰角，進行局部動態避障，依次到達各初始全局路徑點；到達規劃終點則輸出最終的全局無碰路徑。采用本發明能有效改善初始全局規劃的盲目性和環境建模靈活性，對動態未知障礙物的實時避障能力強，方法的速度快、精度高、適應性強。

技術領域

本發明涉及移動機器人技術領域，尤其是一種靜態、動態障礙物并存，且障礙物分布具有多分辨率特點的復雜情況下的移動機器人混合路徑規劃方法。

背景技術

路徑規劃技術一直是智能移動機器人研究的核心內容之一，其要求機器人根據預先獲知或自身傳感器對環境的感知信息，自行規劃出一條從起點到終點，滿足一定準則(路徑長度最短等)的無碰安全路徑。高效、可靠的路徑規劃技術是機器人完成具體任務的前提和基本要求。

根據環境信息獲取程度不同，路徑規劃方法可分為依靠先驗已知信息的全局規劃方法和依靠局部感知信息的局部規劃方法。在一些大規模地圖范圍的路徑規劃任務中，障礙物環境往往具有多分辨率特點：即環境中障礙物分布疏密程度差異大、存在一些預知的典型障礙物，如通過衛星地圖等獲知的固定建筑等，局部還存在未探明的小的靜態或動態障礙物。此時傳統的全局規劃算法，如自由空間法等根據地圖幾何特征搜索路徑的方法，以及粒子群算法、啟發式A*等智能算法，無法處理未知的靜態或動態障礙物，而局部規劃算法，如人工勢場法、滾動窗口法等，由于缺乏已知全局信息的引導，往往計算復雜或易陷入局部死循環。因而，采用全局路徑規劃和實時局部避障相結合的混合路徑規劃方法是滿足移動機器人高效、可靠、實時需求的。

環境建模是機器人進行全局路徑規劃的前提，其與路徑規劃的算法效率緊密相關。常用的環境建模方法包括柵格法、鏈接圖法、等分坐標變換法等，然而這些方法在針對多分辨率的障礙物環境中缺乏靈活適應性：柵格法需要根據最小的障礙物確定柵格的劃分，造成極大的計算資源浪費；鏈接圖法根據障礙物頂點生成的網狀鏈接圖需要經過復雜處理才能定義種群的搜索空間；等分坐標變換法以等分始末點連線的垂線確定種群的搜索空間時，很難兼顧路徑解最優性與計算資源的平衡，在障礙物稀疏處搜索空間太大浪費計算資源，障礙物密集處離散化的搜索空間太小難以規劃出最優路徑。

粒子群算法是解決機器人全局路徑規劃最常用的算法之一，它是由Kennedy和Eberhart 兩位博士根據自然界鳥群覓食的行為特點首次在1995年的國際會議“IEEEInterational Conference on Neural Network”中的“Particle Swarm Optimization”(粒子群優化)一文中提出的一種智能搜索算法。粒子群中的每個粒子代表一個路徑解，粒子的維數代表路徑點的個數。粒子在搜索空間內展開隨機搜索，計算每個粒子所代表路徑解的評價指標(如路徑長度等)，選出粒子群中指標最優(長度最短、安全系數最高等)的粒子來更新每個粒子的歷史最優路徑解和粒子群的全局最優路徑解，以此引導當前粒子快速收斂到滿足路徑指標要求的最優路徑解。其具有結構簡單、參數易調節的優點，但其仍存在容易過早收斂到非最優路徑解的不足。