混合型機器人路徑規劃及其實現

Abstract

本論文提出了一種混合型機器人路徑規劃演算法。其作法係利用影像形態學的知識，在已知環境地圖中建立一中軸地圖，並結合所提出的路徑規劃法搭配應用，使機器人可以直接將路徑規劃在地圖的中軸上。藉由此一作法，機器人得以在安全的路徑上移動，不但省去了處理避障或是重新規劃路徑的步驟，大幅減少執行路徑規劃時的計算成本，同時也提升了原始Dijkstra’s演算法與A*演算法的執行效率。最後，本論文也將此演算法實現於Android智慧型平台裝置以及NXT行動機器人上，以驗證所提出之混合型路徑規劃法之可行性。

This thesis proposes a hybrid path planning algorithm for mobile robots. Based on the iterative morphological methods, the hybrid path planning algorithm establishes a backbone path for the map. With the proposed path planning method, the robot can plan paths on the axis of the map. During the process, the hybrid path planning algorithm not only eliminates the need for re-processing obstacle avoidance or re-planning the path but also significantly reduces the cost of path planning computation. Moreover, this method improves the performance of the Dijkstra’s algorithm and the A* algorithm. Finally, this thesis also implements the proposed algorithm on the Android platform and the NXT robots to verify its practicability of the proposed hybrid path planning method.