適應於時變環境之改良型D*搜尋演算法

An Improved D* Search Algorithm Adapted to Time-varying Environments

吳承勳(Cheng-Hsun Wu)

指導教授 ： 駱榮欽

國立臺北科技大學/電資學院/電腦與通訊研究所/碩士(2011年)

https://doi.org/10.6841/NTUT.2011.00236

摘要

本篇論文將描述一個在未知以及動態環境下之路徑搜尋演算法。提出的方法能夠計算出行走路徑所需花費之時間，並且在獲得地圖資訊變更時修正原來的路徑。現存已有許多演算法能夠解決尋找最短路徑的問題，但這些方法大多數假設所處於的環境是靜態的。事實上不論是實際或虛擬的環境大多不是靜態環境。當遇到地圖資訊變更時重新搜尋路徑是一個應付動態環境最簡單的方法。但使用這種方法在即時的應用中有可能無法及時計算出新的路徑。如果無法及時獲得新的路徑，其結果可能會相當危險。如果一個自動導航車花了太多時間去反
應，它有可能撞到行人或者其他車輛。D*能夠不需要全部重新搜尋整張地圖，它能夠保留地圖上未改變的區域來計算改變區域的數值，進而找出新的最佳路徑。D*原本的目的是在未知或部分未知的環境下搜尋路徑並持續地調整。但後來人們發現D*也可以被使用於動態的環境，它能夠在每次有物體移動時有效率地修正路徑。雖然D*能夠勝任動態環境下之路徑規劃，但並不表示它沒有任何問題。我們發現有時候D*會想移動到其他物體正要移動到的地點。這表示有可能會發生碰撞，因此我們才發展出改良型的D*演算法解決上述之問題。

關鍵字

最短路徑 ； 路徑規劃 ； 動態規劃 ； A* ； D*

並列摘要

This thesis presents a method of finding a path between 2 points on a map. The map is considered unknown and containing moving objects. The proposed method calculates the travel time of a path, and modifies it when encountering any information changes.
Many algorithms have been developed to solve the shortest path problem. However, most of them assume the environment to be static. In fact, static environments are rare in either real or virtual scenes. Repeated execution of a static path searching algorithm would be a simplest solution to dynamic environments. But it may not meet time requirements in real-time applications. The failure to find a path in time could be fatal. An autonomous vehicle may crash onto people or other vehicles if it takes too much time to react.
D* has manage to modify the previous planned path without repeat A* search algorithm. It reuses information from unaffected states on a map to update the costs of changed states. The original purpose of D* algorithm is to find a path and keep updating it in an unknown or partially-known environment. D* can also be used in dynamic environments. D* modifies the path efficiently every time objects move.
Although D* can be used in dynamic environments, it’s not completely fine in all situations. Sometimes D* decides to move to a location that an object is moving to. That means future collisions are expected. Hence, we address this problem and develop an improved algorithm of D*.

並列關鍵字

Shortest Path Problem ； Path Planning ； Dynamic Programming ； A* ； D*

參考文獻

[5] K.P. Valavanis, T. Hebert, R. Kolluru and N. Tsourveloudis, "Mobile Robot Navigation in 2-D Dynamic Environments Using and Electrostatic Potential Field," IEEE Transactions on System, Man and Cybernetics, vol. 30, no. 2, 2000, pp. 187-196.

[6] K. Fujimura and H. Samet, "A Hierarchical Strategy for Path Planning Among Moving Obstacles," IEEE Transactions on Robotics and Automation, vol. 5, no. 1, 1989, pp. 61-69.

[8] A. Stentz, "Optimal and Efficient Path Planning for Partially-Known Environments," Proceedings of the IEEE International Conference on Robotics and Automation, May 1994, pp. 3310-3317.

[9] S. Koenig and M. Likhachev, "D* Lite," Proceedings of the AAAI Conference of Artificial Intelligence, 2002, pp. 476-483.

[1] Yu-Ching Chang, A Study on Outdoor Guidance of Autonomous Land Vehicles by Binocular Computer Vision Based on Artificial Intelligent Policy, Master’s Thesis, National Taipei University of Technology, Taipei, R.O.C., 2003.