拓展搜索鄰域的平滑A*算法機器人路徑規劃

任玉潔，付麗霞，張 勇，毛劍琳

(昆明理工大學 信息工程與自動化學院，云南 昆明 650500)

路徑規劃已經成為當前機器人控制領域研究的熱點之一，它是指在一個障礙物環境下按照一定評判準則搜尋一條從起始點到目標點的最優或次優安全無碰撞路徑[1-3]。目前主要的路徑規劃方法有遺傳算法[4]、蟻群算法[5]、人工勢場法[6]、Dijkstra算法[7]。但是這些算法都存在一些缺陷。其中，遺傳算法編碼長度變化范圍大，收斂性較差；蟻群算法搜索速度慢，且易陷入局部最優；人工勢場法易陷入局部極小值，且在障礙物附近易發生振蕩；Dijkstra算法直接搜索全局而不考慮目標點信息，搜尋時間長。

A*算法作為一種經典啟發式搜索算法在20世紀60年代被提出，它具備最優性、完備性和高效性[8]，在路徑規劃鄰域備受關注，利用A*算法可以得到較好路徑規劃效果。但是由于A*算法的計算特點，規劃出的路徑點一般存在折線多、累計轉折角度大、易舍棄部分點而生成次優解等問題[9]。文獻[10]提出利用微分改進A*算法，有效降低轉折次數，但是涉及大量計算。文獻[11]提出建立平滑A*模型，路徑點一定程度上得到平滑。文獻[12]提出以每個柵格邊線作為路徑點，使路徑點不局限于柵格中心點，提高了A*算法規劃結果的平滑性。

本文在基于柵格法構建機器人路徑規劃環境模型基礎上，在傳統的A*算法上增加目標點方向擴展鄰域并對規劃結果進行二次平滑處理。利用改進后的A*算法規劃的路徑不僅簡化了路徑點數，路徑長度也有效降低。……