基于Voronoi圖改進的A*算法在機器人路徑規劃中的應用

摘要：文章描述了一種解決大規劃空間下機器人路徑規劃問題的算法。算法在初步規劃中采用Voronoi圖法描述規劃空間，使用A*算法搜索出一條初步的可行路徑；在二次規劃中，按照一定的規則在得到的路徑周圍重建規劃空間。重建后能夠有效地縮小規劃空間的面積，這樣使用算法搜索的實時性得到提升。使用C++軟件平臺進行仿真的結果顯示，多數情況下優化后規劃空間面積可以減少一半以上，優化效果明顯。

關鍵詞：機器人；路徑規劃；柵格法；Voronoi圖；A*算法

中圖分類號：TP242 文獻標識碼：A 文章編號：1009-2374（2012）21-0033-04