改良式 A* 演算法於動態環境路徑規劃與避障之應用

Abstract

由於近年來無人載具的興起，對於自動駕駛技術的需求也越來越高。對於自駕車而言，傳統的路徑規劃演算法已經不能符合需要。因此，本論文提出一個即時、有效率的方法進行自駕車路徑規劃。為了符合現實狀況，我們納入自駕車對於環境的感知距離的限制。透過邊走邊探索的模式，自駕車在運行過程中不斷地更新地圖，並且在發現原先路徑不適用後，即重新進行路徑規劃。 本論文提出數個方法改進傳統的A*演算法，使之適用於即時路徑規劃與避障。再者，透過修改啟發式函數與動態目標點的方法，處理滿足姿態要求的路徑規劃問題。最後，透過結合擴展卡爾曼濾波器(EKF)的方法，使線上路徑規劃適用於移動障礙物或時變地圖。 實驗與模擬結果顯示，這些修正有效降低傳統A*演算法的計算時間，並且使其能夠根據需求的末端姿態做路徑規劃。模擬結果顯示，擴展卡爾曼濾波器確實可以提供足夠的障礙物預測資訊。再配合增加維度的路徑規劃演算法，我們可以實現平面運動的障礙物避障。

The design of on-road autonomous vehicles requires a real-time, effective path-planning algorithm for time-varying environment. To accommodate the real situation on-road, the restriction of the observation distance of the sensors on the autonomous vehicle is imposed. In this research, three methods are proposed to modify the offline A* path-planning algorithm for avoiding obstacles observed during path tracking. By redesigning the heuristic function and including the attitude requirements, we can obtain a suitable path adaptive to initial attitude and final attitude, as well as avoiding sharp turning which may cause difficulties in path-tracking. Moreover, Extended Kalman Filter(EKF) is integrated with the previous online path-planning algorithm to deal with moving obstacle.sSimulations and Experiments show that the proposed path-planning algorithm can reduce computation time significantly, and EKF can provide adequate information for moving obstacles such that the real-time path-planning and obstacle-avoidance are made possible.