臺灣博碩士論文加值系統

人工智慧（Artificial Intelligence）領域長久以來一直是電腦科學中的一門學問，人工智慧的研究領域包含相當廣泛，本研究專注於Mobile Robots的移動路徑尋找，當Robot所處的環境是動態，即障礙物是可以被重新置放的（Relocated），那麼我們就不能夠預先計算整條路徑。於是每次Robot偵測到環境改變時，就必須重頭再做一次重新規劃（Re-plan）導致花費過多的計算時間。因此D*（Stentz 1994）與D* Lite（S. Koenig and M. Likhachev. 2002）的動態規劃演算法就是解決此類問題。
由於真實世界的Mobile Robots相當於電腦遊戲中的電腦控制角色，所以本研究將Robot的路徑規劃技術應用至電腦遊戲中，以提升電腦遊戲中的路徑規劃效率。
另外因為以Lifelong Planning A*為基礎的D* Lite動態規劃演算法仍然必須做一次完整的搜尋，導致Robot因等待搜尋完成而降低效率，因此本研究提出一個階層跳躍式的方法來加速D* Lite的搜尋速度，並區分搜尋為三個階段。所以本研究提出：
． 第一階段利用階層式的地圖定義方法與障礙物的判斷分析來加速搜尋。
． 第二階段以中繼點（Waypoints）的概念達成一個分段跳躍式的路徑，提升搜尋的效率。
． 第三階段則是讓Robot於動態環境時，能夠識別環境的變化並重複使用前次搜尋結果來產生新的中繼點或路徑。

目錄II
圖目錄IV
表目錄VI
1 緒論1
1.1 研究動機.................................................................................................. 1
1.1.1. 遊戲人工智慧.......................................................................................... 1
1.1.2. 為什麼要路徑規劃技術？ ...................................................................... 2
1.2 研究目的.................................................................................................. 3
1.3 研究流程.................................................................................................. 4
1.4 研究限制.................................................................................................. 5
2 文獻探討6
2.1 搜尋演算法（Search Algorithms） ........................................................ 6
2.1.1. 狀態空間搜尋（State Space Search）.................................................... 6
2.1.2. 盲目搜尋法（Uninformed Search）....................................................... 7
2.1.3. 啟發式搜尋法（Heuristic Search）........................................................ 9
2.2 地圖表示（Map Representations） ...................................................... 13
2.2.1. 方格表示法（Grid Representations） .................................................. 13
2.2.2. 連續空間分割法.................................................................................... 14
2.2.3. 地形成本（Terrain Cost） .................................................................... 17
2.3 障礙類型（Obstacle Category） .......................................................... 17
2.4 動態規劃（Dynamic Planning） .......................................................... 19
2.4.1. 何謂動態規劃？ .................................................................................... 19
2.4.2. 動態規劃的相關研究............................................................................ 19
3 研究架構23
3.1 問題定義................................................................................................ 23
3.2 系統架構................................................................................................ 24
3.2.1. 完整搜尋階段........................................................................................ 25
3.2.2. 重新規劃階段........................................................................................ 25
4 完整搜尋階段27
II
4.1 地圖定義................................................................................................ 27
4.1.1. 地圖座標................................................................................................ 28
4.1.2. 狀態展開（State Expansion） .............................................................. 29
4.2 Macro D* Lite完整搜尋階段................................................................ 30
4.2.1. 角落穿越問題........................................................................................ 30
4.2.2. 路徑讀取方法........................................................................................ 32
4.2.3. 障礙判斷方法........................................................................................ 35
4.3 中繼點（Waypoints）選擇階段........................................................... 45
4.3.1. 中繼點（Waypoints）判斷方法........................................................... 46
4.4 D* Lite完整搜尋階段............................................................................ 56
4.4.1. D* Lite初始化設定................................................................................ 57
5 重新規劃階段58
5.1 區域一致性（Locally Consistent） ...................................................... 58
5.1.1. 小節點區域一致性................................................................................ 58
5.1.2. 大節點區域一致性................................................................................ 59
5.2 環境變化影響範圍................................................................................ 61
5.2.1. 小節點環境影響範圍............................................................................ 63
6 實驗與結果分析65
6.1 實作平台................................................................................................ 65
6.2 實驗說明................................................................................................ 65
6.3 實驗數據與結果分析............................................................................ 66
7 結論與建議74
參考文獻76
III
圖目錄
頁次
圖1-1 Age of Empires II Screenshot[29]......................................................................... 1
圖1-2 兩條繞過障礙物的可行路徑[21] ........................................................................ 2
圖1-3 複雜的路徑規劃技術[18] .................................................................................... 3
圖2-1 有Edges互相連接的方格地圖[18] ...................................................................... 6
圖2-2 廣度優先搜尋[16] ................................................................................................ 7
圖2-3 雙向廣度優先搜尋[16] ........................................................................................ 8
圖2-4 Dijkstra’s Algorithm[16]....................................................................................... 8
圖2-5 最佳優先搜尋[16] ................................................................................................ 9
圖2-6 二元堆積樹（Binary Heaps）[20] .................................................................... 10
圖2-7 A*搜尋法[16] ..................................................................................................... 12
圖2-8 一個遊戲地圖分割成方格（Tiles）[21] .......................................................... 13
圖2-9 不同方格（Grid）的表示[14]........................................................................... 14
圖2-10 多邊形的可視點表示[18] ................................................................................ 15
圖2-11 四元樹（Quadtrees）[9].................................................................................. 15
圖2-12 潛在的場地（Potential Fields）[30] ............................................................... 16
圖2-13 道路地圖（Road Maps）[18].......................................................................... 16
圖2-14 有不同移動成本的地形型態[21] .................................................................... 17
圖2-15 LPA*的區域一致性（Locally Consistent）[6]............................................... 20
圖2-16 A*（左）與LPA*（右）的比較[2]................................................................ 21
圖2-17 在未知地面有目標的導航[4] .......................................................................... 22
圖3-1 D* Lite虛擬碼[5]................................................................................................ 24
圖3-2 搜尋階段表示圖................................................................................................. 26
圖4-1 搜尋地圖（狀態空間）的定義方式................................................................. 27
圖4-2 節點座標定義方法............................................................................................. 28
圖4-3 Macro D* Lite（左）與D* Lite（右）狀態展開示意圖................................. 29
圖4-4 Macro D* Lite（左）與D* Lite（右）狀態空間搜尋..................................... 30
圖4-5 障礙物角落穿越問題......................................................................................... 31
圖4-6 未修正角落穿越的狀態展開（左）與最短路徑（右）................................. 31
圖4-7 已修正角落穿越的狀態展開（左）與最短路徑（右）................................. 32
IV
圖4-8 最短路徑讀取優先順序..................................................................................... 33
圖4-9 最短路徑示意圖................................................................................................. 33
圖4-10 未修正前的路徑讀取會發生角落穿越問題................................................... 34
圖4-11 Macro D* Lite（左）與D* Lite（右）的路徑讀取比較............................... 35
圖4-12 Macro D* Lite狀態展開順序........................................................................... 36
圖4-13 水平方向的障礙物定義................................................................................... 37
圖4-14 狀態展開朝右時忽略右方大節點................................................................... 38
圖4-15 狀態展開朝右時加入右方大節點................................................................... 39
圖4-16 垂直方向的障礙物定義................................................................................... 40
圖4-17 狀態展開朝上時忽略上方大節點................................................................... 41
圖4-18 狀態展開朝上時加入上方大節點................................................................... 42
圖4-19 對角線方向的障礙物定義............................................................................... 43
圖4-20 狀態展開朝右上時忽略右上大節點............................................................... 44
圖4-21 狀態展開朝右上時加入右上大節點............................................................... 45
圖4-22 Macro D* Lite（左）的中繼點與D* Lite（右）的路徑比較....................... 46
圖4-23 基本路徑連接狀態定義................................................................................... 47
圖4-24 水平方向路徑連接狀態................................................................................... 47
圖4-25 第0 組第一種中繼點選擇方法....................................................................... 48
圖4-26 第0 組第二種中繼點選擇方法....................................................................... 49
圖4-27 第0 組第四、五、六種中繼點選擇方法....................................................... 50
圖4-28 垂直方向路徑連接狀態................................................................................... 51
圖4-29 第2 組第一種中繼點選擇方法....................................................................... 52
圖4-30 第2 組第二種中繼點選擇方法....................................................................... 53
圖4-31 第2 組第四、五、六種中繼點選擇方法....................................................... 54
圖4-32 對角線方向路徑連接狀態............................................................................... 55
圖4-33 第4 組中繼點選擇方法................................................................................... 55
圖4-34 中繼點跳躍搜尋方法....................................................................................... 56
圖5-1 大節點為完全方向性障礙物............................................................................. 60
圖5-2 障礙物造成路徑大節點與中繼點改變............................................................. 61
圖5-3 障礙物造成路徑大節點改變但未影響中繼點................................................. 62
圖5-4 障礙物僅造成小節點路徑改變......................................................................... 63
圖5-5 環境變化可能影響的範圍................................................................................. 64
圖6-1 完整搜尋測試數據比較圖................................................................................. 69
圖6-2 重新規劃測試數據比較圖................................................................................. 72
V
表目錄
頁次
表6-1 程式實作平台..................................................................................................... 65
表6-2 實驗資料關鍵字說明......................................................................................... 66
表6-3 地圖創造時間..................................................................................................... 66
表6-4 完整搜尋結果（20%障礙物） ......................................................................... 67
表6-5 完整搜尋結果（30%障礙物） ......................................................................... 68
表6-6 重新規劃結果（30%障礙物隨機重新置放0.05%） ...................................... 70
表6-7 重新規劃結果（30%障礙物隨機重新置放0.1%） ........................................ 71

[1]S. Koenig, M. Likhachev, Y. Liu and D. Furcy, 「Incremental Heuristic Search in Artificial Intelligence,」 Artificial Intelligence Magazine, Vol. 25, Iss. 2, pp. 99-112, June 2004.
[2]S. Koenig, M. Likhachev and D. Furcy, 「Lifelong Planning A*,」 Artificial Intelligence, Vol. 155, Iss. 1-2, May 2004.
[3]S. Koenig and M. Likhachev, 「Incremental A*,」 In Advances in Neural Information Processing Systems 14, pp. 1539-1546, December 2001.
[4]S. Koenig and M. Likhachev, 「Improved Fast Replanning for Robot Navigation in Unknown Terrain,」 In Proceedings of the International Conference on Robotics and Automation, pp. 968–975, 2002.
[5]S. Koenig and M. Likhachev, 「D* Lite,」 In Proceedings of the Eighteenth National Conference on Artificial Intelligence, pp. 476-483, July 2002.
[6]Sven Koenig, Maxim Likhachev, Yaxin Liu, and David Furcy, 「Greedy On-line Planning, Slides of a Tutorial,」 In Proceedings of the Sixth International Conference on AI Planning and Scheduling, April 2002.
[7]A. Stentz, 「The Focussed D* Algorithm for Real-Time Replanning,」 In Proceedings of the International Joint Conference on Artificial Intelligence, pp. 1652–1659, August 1995.
[8]A. Stentz, 「Optimal and Efficient Path Planning for Partially-Known Environments,」 In Proceedings of the IEEE International Conference on Robotics and Automation, Vol. 4, pp. 3310-3317, May 1994.
[9]Alex Yahja, Anthony Stentz, Sanjiv Singh, and Barry L. Brumitt, 「Framed-Quadtree Path Planning for Mobile Robots Operating in Sparse Environments,」 In Proceedings of the IEEE Conference on Robotics and Automation, pp. 650-655, May 1998.
[10]Alex Yahja, Sanjiv Singh, and Anthony Stentz, 「Recent Results in Path Planning for Mobile Robots Operating in Vast Outdoor Environments,」 In Proceedings of the Symposium on Image, Speech, Signal Processing and Robotics, September 1998.
[11]Ramalingam, G. and Reps, T., 「An Incremental Algorithm for a Generalization of the Shortest-path Problem,」 Journal of Algorithms, Vol. 21, pp. 267–305, 1996.
[12]P. Yap, 「Grid-based Pathfinding,」 In Proceedings of the 15th Canadian Conference on Artificial Intelligence, pp. 44-55, 2002.
[13]P. Yap and J. Schaeffer, 「Path-finding on a Grid,」 In Proceedings of the 5th Joint Conference of Information Sciences, pp. 454-457, 2002.
[14]Y. Bjornsson, M. Enzenberger, R. Holte, J. Schaeffer and P. Yap, 「Comparison of Different Abstractions for Pathfinding on Maps,」 In Proceedings of the International Joint Conference on Artificial Intelligence, pp. 1511-1512, 2003.
[15]P. Yap, 「New Ideas in Pathfinding,」 In Proceedings of the AAAI Spring Symposium: Artificial Intelligence and Interactive Entertainment, pp. 95-97, 2002.
[16]Bryan Stout, 「Smart Moves: Intelligent Pathfinding,」 Game Developer Magazine, pp. 28-35, October 1996.
[17]Marco Pinter, 「Toward More Realistic Pathfinding,」 Game Developer Magazine, pp. 54-64, April 2001.
[18]Amit J. Patel, 「Amit's Thoughts on Path-Finding and A-Star,」 January 2004. http://theory.stanford.edu/~amitp/GameProgramming/
[19]Patrick Lester, A* Pathfinding for Beginners, March 2003. http://www.policyalmanac.org/games/aStarTutorial.htm
[20]Patrick Lester, Using Binary Heaps in A* Pathfinding, April 2003. http://www.policyalmanac.org/games/binaryHeaps.htm
[21]Patrick Lester, 「Two-Tiered A* Pathfinding,」 January 2003. http://www.policyalmanac.org/games/twoTiered.htm
[22]Logan, B., and Alechina, N., 「A* With Bounded Costs,」 In Proceedings of the 15th National Conference on Artificial Intelligence, pp. 444-449, 1998.
[23]Martin Heni, 「Path Finding Algorithms in Computer Games Using Qt/KDE, 「 November 2003. http://www.heni-online.de/
[24]David Gordon, 「Ant-based Pathfinding,」 Final Year Undergraduate Projects, School of Computing, Leeds University, 2002.
[25]F. Markus Jonsson, 「An Optimal Pathfinder for Vehicles in Real-world Digital Terrain Maps,」 The Department of Numerical Analysis and Computing Science, The Royal Institute of Science, 1997.
[26]R. Holte, M. Perez, R. Zimmer, and A. MacDonald, 「Hierarchical A*: Searching Abstraction Hierarchies Efficiently,」 In Proceedings of the 13th National Conference on Artificial Intelligence, pp. 530-535, 1996.
[27]Botea A., Mueller M., and Schaeffer J., 「Near Optimal Hierarchical Path-finding,」 In Journal of Game Development, Vol. 1, Iss. 1, 2004.
[28]Bjorn Reese and Bryan Stout, "Finding a Pathfinder," In Proceedings of the AAAI Spring Symposium on Artificial Intelligence and Computer Games, pp. 69-72,1999.
[29]John E. Laird, 「The Future of Game AI,」 Game Developer Magazine, August 2000.
[30]Stefan Baert, 「Motion Planning Using Potential Fields,「 July 2000. http://www.gamedev.net/reference/articles/article1125.asp