為了使自走車在環境中能確實有效率地達成任務，自走車要能知道自己在環境中的位置，並以最快的速度到達指定地點，執行指定動作。本文研究中使用人工智慧的D* Lite搜尋演算法，為自走車規劃一條從起始點到終點的最短路徑，供自走車在最短的時間內到達目的地。另外為了使自走車能正確的沿著這條規劃的路徑行走，使用以機率統計為基礎的蒙地卡羅定位演算法，來做位置估測與追蹤，這樣自走車行走起來不至於偏離原本規劃路徑太多。 D* Lite演算法將實驗環境切割成許多小方格，以廣度優先搜尋法為基礎，加入啟發函數使搜尋方向朝向目標點，以及重覆利用過去的計算資訊來加快計算速度，規劃出一條最短路徑供自走車行走，並能在遇到障礙物時快速地重新規劃一條新路徑。 蒙地卡羅定位演算法先由輪子上的編碼器以里程計方法推算出自走車位置，再加入雷射測距儀量測的環境資訊來修正這個位置，使得最後計算出來的結果較符合自走車的實際位置，完成對里程計方法推算出來的誤差補償。 最後本論文將這些方法實際應用在自走車上，並以數據統計表示，確實為自走車算出最短路徑供行走，及補償里程計方法在自走車長距離行走中的誤差，完成對自走車的路徑規劃與位置估測追蹤。 To accomplish the assigned task efficiently and correctly, a mobile robot should know where it is, reach the goal position as fast as it could and perform the assigned motion. This work uses the D* Lite search algorithm of Artificial Intelligent to plan a shortest path to ensure the mobile robot can reach goal quickly. Besides, to move along the path planned correctly, we use Monte Carlo localization algorithm of Probability and Statistics to realize the position estimation and tracking for the mobile robot. D* Lite search algorithm adds a heuristic function to make search direction orient to the goal, and reuses the past information to plan a shortest path quickly. It can replan a new path when encountering obstacles. Monte Carlo localization algorithm is used to calculate the position of the mobile robot. It can compute the final location closed to the actual position, which compensates the odometer errors and integrates the measurement data from laser range finder to correct the position.. In the experiment, two algorithms are applied on the mobile robot. We can plan a shortest path for the mobile robot to move, compensate the error when the mobile robot moves a long distance, and accomplish the path planning and position tracking for the mobile robot.
