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

Path planning with structure modified A* algorithm in dynamic environment

林宗佑(Lin Tsung-You)

指導教授 ： 王立昇

國立臺灣大學/工學院/應用力學研究所/碩士(2018年)

https://doi.org/10.6342/NTU201802627

摘要

由於近年來無人載具的興起，對於自動駕駛技術的需求也越來越高。對於自駕車而言，傳統的路徑規劃演算法已經不能符合需要。因此，本論文提出一個即時、有效率的方法進行自駕車路徑規劃。為了符合現實狀況，我們納入自駕車對於環境的感知距離的限制。透過邊走邊探索的模式，自駕車在運行過程中不斷地更新地圖，並且在發現原先路徑不適用後，即重新進行路徑規劃。
本論文提出數個方法改進傳統的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.

並列關鍵字

online path-planning ； realtime path-planning ； trajectory prediction ； kalman filter

參考文獻

[1] Tuncer, Adem, and Mehmet Yildirim. "Dynamic path planning of mobile robots with improved genetic algorithm." Computers & Electrical Engineering 38.6 (2012): 1564-1572.

[2] Song, K. T., & Sheen, L. H. (2000). Heuristic fuzzy-neuro network and its application to reactive navigation of a mobile robot. Fuzzy Sets and systems, 110(3), 331-340.

[3] 王冠尹, “適應性與啟發式RRT演算法在無人載具導控之應用” 台灣大學應用力學研究所碩士論文, 中華民國一百零六年七月。

[4] https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

[5] Hart, Peter E., Nils J. Nilsson, and Bertram Raphael. "A formal basis for the heuristic determination of minimum cost paths." IEEE transactions on Systems Science and Cybernetics 4.2 (1968): 100-107.