針對動態路徑規劃之D++演算法研究及其應用

The Research and Application of D++ Algorithm for Dynamic Path-Planning

陳品均(Pin-Jyun Chen)

指導教授 ： 鄭璧瑩

國立交通大學/工學院/機械工程系所/博士(2013年)

https://doi.org/10.6842/NCTU.2013.00412

摘要

移動機器人的導航科技是機器人科學中一項重要的技術。在過去數十年間，移動機器人的導航技術吸引了許多學界與產業界的注意，並發展出許多的技術。在已知或未知的環境所進行的主要導航科技，包括了探索、環境建置、定位、運動控制、路徑規劃。路徑規劃技術為引導機器人從一個起點走到它的目標點。現今的主要路徑規劃大致分為全域路徑規劃法，與區域路徑規劃法。全域路徑規劃法的優點為可找出最短路徑，然而計算量龐大且耗時久，故大多用於靜態環境。區域路徑規劃法的優點為可快速更新環境資訊並找出可行路徑，故適用於動態環境。然而區域路徑規劃法的缺點為不能保證找到最短路徑，尤其是處理類似迷宮的環境，非常容易卡在某特定區域(區域解)而無法找到終點。
在本研究中，我們改良舊有的Dijkstra演算法，並發展成一種新的演算法：D++演算法；並且應用它在移動機器人的導航科技中。我們結合了Dijkstra演算法與環境感測方法，讓原本屬於全域搜尋的Dijkstra演算法轉變區域搜尋的D++演算法，因此可讓機器人能即時決定下一步該怎麼移動。雖然D++演算法大部分時間為在有限的區域進行區域搜索，但它也可以在需要的時候擴大搜索範圍以避開區域解的狀況。因此D++演算法綜合了全域搜尋與區域搜尋的優點，不斷可快速反應處理動態環境問題，即使面對迷宮的環境，也可輕易解決區域解問題而成功找到終點。
　　而在本論文後面的章節，我們也應用D++演算法在實際的移動機器人上，並使其航行在數個測試環境中。由實驗結果我們驗證了D++演算法可有效地實現在真實的移動機器人上。因此我們可以期望未來可應用D++演算法於野外型探勘機器人，以應付複雜、未知、動態、廣大的真實環境。

關鍵字

機器人 ； 路徑規劃 ； Dijkstra演算法

並列摘要

The navigation of mobile robots is a vital aspect of technology in robotics. During the past few decades, the navigation of mobile robots has attracted notable attention, and considerable research was developed. The main technology of navigation in unknown or uncertain environments includes exploration, mapping, localization, motion control, and path-planning. Path planning is one of the main technologies to direct a robot from a starting point to its destination. The main methods of path planning at present can be classified by global search type and local search type. The advantage of global search path-planning is that it can find a shortest path. However, it need plenty of computation and takes a long time. Therefore it often only use static environment. The advantage of local search path-planning is that it can find probable moving direction very fast. Therefore, it is very suitable for dynamic environment. However, the shortcoming of local search path-planning is that it can not ensure to find a shortest path, especially for some environments of maze. It is very easily to get stuck at some area which is a local solution so that it can not a path to destination eventually.
In this paper, we applied the D++ algorithm, which is a novel and improved path-planning algorithm, to the navigation of mobile robots. The D++ algorithm combines Dijkstra’s algorithm with the idea of a sensor-based method, such that Dijkstra’s algorithm is adapted to local search, and the robot can determine its next move in real-time. Although the D++ algorithm frequently runs local search with limited ranges, it can compute optimum paths by expanding the size of the searching range to avoid local minima. Therefore D++ algorithm combines the advantages of global seach and local search. It not only can deal with dynamic environment rapidly, but also avoid to the problem of local solution for the environment of maze.
In the later chapters, we applied the D++ algorithm to a real mobile robot in a number of environments. According to the results of experiments we verified that the D++ algorithm is very practicability for real mobile robot. Therefore we can expect that use of the D++ algorithm enables robots to navigate efficiently in complex, unknown, dynamic and large environments.

並列關鍵字

Robot ； Path planning ； Dijkstra algorithm

參考文獻

[27] 蘇木春、張孝德，機器學習：類神經網路、模糊系統以及基因演算法則，全華科技股份有限公司，民國91年

[2] E. W. Dijkstra, “A note on two problems in connexion with graphs,” Numerische Mathematik 1, pp. 269–271, 1959.

[3] P. E. Hart, N. J. Nilsson, B. Raphael, "A Formal Basis for the Heuristic Determination of Minimum Cost Paths". IEEE Transactions on Systems Science and Cybernetics SSC4 4 (2): pp. 100–107, 1968.

[4] P. E. Hart, N. J. Nilsson, B. Raphael, “Correction to A Formal Basis for the Heuristic Determination of Minimum Cost Paths,” SIGART Newsletter 37, pp. 28–29, 1972.

[5] R. Dechter; P. Judea, “Generalized best-first search strategies and the optimality of A*,” Journal of the ACM 32 (3): pp. 505–536, 1985.