本論文針對隨機散佈障礙環境下，安全平滑之動態路徑更新，結合非格點式之拓樸地圖，建立快速之路徑再規劃方法，以符合動態路徑規劃之需求，基於非格點式拓樸地圖，重新檢驗、修改廣義Voronoi結構劃分(GVT, Generalized Voronoi Tessellation)與D* Lite演算法(D* Lite Algorithm)之理論，確立一個時間精省具有再規劃能力之前處理器，再以支持向量機(SVM, Support Vector Machine)構築一個具最大邊限的安全平滑路徑。
本研究援引之廣義Voronoi結構劃分與D* Lite演算法皆為計算時間考量下一時之選，銜接非格點式之拓樸地圖，環環相扣，奠定一計算精省之再規劃方法，具有實際應用之潛力，再佐以支持向量機之平滑後處理，確可達於隨機散佈障礙環境下安全平滑之動態路徑更新的目的。

In real applications, a path planning under dynamic environment change is a practical and important topic for the grounded mobile robot. The study elementarily employs the methods of generalized Voronoi tessellation (GVT) and D* Lite shortest path algorithm for the topic. With the excellence of less computation, the topology of scatted waypoint configuration for mapping the terrain is first chosen for the real-time replanning request. The elementary methods are hence theoretically modified to fit adequately the waypoint topology. The modification seeks a swift solution to respond a replanning request corresponding to a waypoint topology change. The sub-sequential processes: waypoint topology change, GVT, and D* Lite form a pre-processing planner. It can be applied standalone to provide an optimized piecewise linear path for robot reaction. With an additional support vector machine (SVM) post-processing smoother, it can also provide a wide-margin safe and smooth path. The smooth path is optimized, too. The solid development based on the waypoint topology, instead of the quantized grid-map of previous researchers, is the most important contribution of the study. With small scaled experiments, evidential results show consistently the model is promising for a great improvement in applications and achieve the original goal of the study.

目錄
誌謝I
中文摘要II
英文摘要III
目錄V
圖目錄VIII
表目錄XII
第一章	緒論1
1-1、	前言1
1-2、	研究動機與目的3
1-3、	相關文獻3
1-4、	本研究特色5
第二章	基礎理論7
2-1、	地圖格式表示7
2-1-1、	特徵地圖7
2-1-2、	拓樸地圖13
2-2、	廣義Voronoi結構劃分(GVT)16
2-3、	內點判別演算法20
2-4、	路徑搜尋演算法24
2-4-1、	Dijkstra演算法25
2-4-2、	A*演算法25
2-4-3、	D*演算法27
2-4-4、	LPA*演算法27
2-4-5、	D* Lite演算法28
2-5、	地圖變動偵測29
2-6、	支持向量機(SVM)30
第三章	研究設備與方法35
3-1、	研究設備35
3-2、	研究方法38
3-2-1、	機器人導航與可移動障礙物40
3-2-2、	路徑初規劃41
3-2-2-1、	廣義Voronoi結構劃分41
3-2-2-2、	D* Lite產生最短路徑PVDL	44
3-2-2-3、	拓樸單點指定標籤51
3-2-2-4、	PSVM平滑路徑52
3-2-3、	路徑再規劃53
3-2-3-1、	拓樸更新與地圖資訊交接53
3-2-3-2、	D* Lite演算法重新找尋路徑55
3-2-3-3、	指定類別標籤與產生新的平滑路徑PSVM56
第四章	實驗與討論58
4-1、	非格點地圖路徑再規劃實例58
4-2、	格點與非格點地圖路徑再規劃比較77
4-3、	非格點地圖之D* Lite與A*路徑再規劃之比較101
4-4、	障礙物複雜度於非格點地圖路徑規劃之比較112
第五章	結論與討論115
參考文獻116
附錄121
 
圖目錄
圖1-1 安全平滑路徑規劃之需求實例2
圖1-2研究步驟流程圖6
圖2-1 地圖格式化與特徵地圖之範例9
圖2-2 特徵地圖配置實例11
圖2-3 網路連通拓樸地圖示意圖14
圖2-4 路徑點連結之拓樸地圖示意圖15
圖2-5 Voronoi結構劃分17
圖2-6 一般與廣義之Voronoi 結構劃分18
圖2-7 區塊障障物內Voronoi頂點與邊之剪除19
圖2-8 射線內點判別法21
圖2-9 射線內點判別演算法交點判斷法則23
圖2-10 支持向量機邊限示意圖34
圖3-1系統場地模擬圖36
圖3-2 場地實際場景圖36
圖3-3 組裝完成之NXT機器人38
圖3-4 系統流程圖39
圖3-5 廣義Voronoi結構劃分之拓樸地圖44
圖3-6 粗規劃之最短路徑PVDL50
圖3-7 障礙物貼上標籤的原則程序51
圖3-8 PVDL與障礙點指定標籤52
圖3-9 支向機之平滑曲線圖53
圖3-10 環境變動後產生之新拓樸地圖54
圖3-11 環境變動後產生新的粗路徑56
圖3-12 環境變動後重新指定類別標籤57
圖3-13 環境變動後更新之SVM平滑路徑57
圖4-1 圖書館樓層示意圖58
圖4-2 Voronoi結構劃分59
圖4-3 廣義Voronoi結構劃分60
圖4-4 D* Lite由起點開始拓展，並將鄰近節點加入待拓展集合U中61
圖4-5 由集合U中找出最小成本節點並以此拓展地圖資訊62
圖4-6 拓展完之節點達到區域一致性(灰色節點)63
圖4-7 找出集合U最小成本之節點64
圖4-8 持續拓展，以達到區域一致性為目標64
圖4-9 D* Lite演算法示意65
圖4-10 D* Lite演算法示意圖65
圖4-11 地圖資訊拓展完成66
圖4-12 由起點追溯最短路徑直到抵達終點67
圖4-13 SVM平滑路徑68
圖4-14 圖書館樓層環境變化示意圖69
圖4-15 新產生之廣義Voronoi圖形70
圖4-16 新舊地圖交接示意圖71
圖4-17 舊地圖資訊成功交接至新地圖72
圖4-18 由集合U找出更新後具最小成本之節點73
圖4-19 D* Lite演算法示意圖73
圖4-20 D* Lite演算法示意圖74
圖4-21 更新後地圖資訊拓展完成74
圖4-22 由起點追溯最短路徑直到抵達終點75
圖4-23 路徑再規劃之SVM76
圖4-24 案例一之格點地圖實際場景與路徑規劃結果80
圖4-25 案例一之非格點地圖實際場景與路徑規劃結果81
圖4-26 案例二之格點地圖實際場景與路徑規劃結果83
圖4-27 案例二之非格點地圖實際場景與路徑規劃結果84
圖4-28 案例三之格點地圖實際場景與路徑規劃結果86
圖4-29 案例三之非格點地圖實際場景與路徑規劃結果87
圖4-30 案例四之格點地圖實際場景與路徑規劃結果89
圖4-31 案例四之非格點地圖實際場景與路徑規劃結果90
圖4-32 案例五之格點地圖實際場景與路徑規劃結果93
圖4-33 案例五之非格點地圖實際場景與路徑規劃結果94
圖4-34 案例六之格點地圖實際場景與路徑規劃結果96
圖4-35 案例六之非格點地圖實際場景與路徑規劃結果97
圖4-36 案例七之格點地圖實際場景與路徑規劃結果99
圖4-37 案例七之非格點地圖實際場景與路徑規劃結果100
圖4-38 案例一之D* Lite路徑規劃實際場景與路徑規劃結果104
圖4-39 案例一之A*路徑規劃實際場景與路徑規劃結果105
圖4-40 案例二之D* Lite路徑規劃實際場景與路徑規劃結果107
圖4-41 案例二之A*路徑規劃實際場景與路徑規劃結果108
圖4-42 案例三之D* Lite路徑規劃實際場景與路徑規劃結果110
圖4-43 案例三之A*路徑規劃實際場景與路徑規劃結果111
圖4-44 非格點地圖於不同數量障礙物之路徑搜尋時間折線圖114
 
表目錄
表2-1 不同障礙物與虛擬點之定義10
表2-2 對應圖2-2之特徵地圖座標與單點性質辨識碼12
表3-1 Voronoi節點資料型態43
表4-1案例一之格點與非格點地圖路徑再規劃比較79
表4-2案例二之格點與非格點地圖路徑再規劃比較82
表4-3案例三之格點與非格點地圖路徑再規劃比較85
表4-4案例四之格點與非格點地圖路徑再規劃比較88
表4-5案例五之格點與非格點地圖路徑再規劃比較92
表4-6案例六之格點與非格點地圖路徑再規劃比較95
表4-7案例七之格點與非格點地圖路徑再規劃比較98
表4-8 案例一之D* Lite與A*演算法路徑規劃實驗記錄103
表4-9 案例二之D* Lite與A*演算法路徑規劃實驗記錄106
表4-10 案例三之D* Lite與A*演算法路徑規劃實驗記錄109
表4-11 非格點地圖於不同障礙物混雜度之拓樸地圖轉換時間113
表4-12 非格點地圖於不同障礙物混雜度D* Lite路徑搜尋時間113
表4-13 非格點地圖於不同障礙物數量之路徑搜尋時間比較114

[1]	A. Zelinsky and I. Dowson, “Continuous Smooth Path Execution for an Autonomous Guided Vehicle,” TENCON '92. Technology Enabling Tomorrow : Computers, Communications and Automation Towards the 21st Century, 1992 IEEE Region 10 International Conference, 871-875 vol. 2, Melbourne. 11-13 Nov., Australia, 1992.
[2]	T. Fraichard and M. Ahuactzin, “Smooth Path Planning for Cars,” ICRA 2001: 3722-3727, Proceedings of the 2001 IEEE International Conference on Robotics and Automation, ICRA 2001, May 21-26, Seoul, Korea, 2001.
[3]	C.-Y. Yang, J.-S. Yang, and F.-L. Lian, “Safe and Amooth: a Large-Margin SVM Embedded Robotic Path Planning,” Submitted to IEEE Transactions on Robotics, 2010.
[4]	周峰毅，安全平滑之機器人路徑規劃—基於大邊限支向機的研究，碩士論文，淡江大學機械與機電學系，民國九十六年
[5]	馬志豪，基於分類之避障路徑規劃與實現，碩士論文，淡江大學機械與機電學系，民國九十九年
[6]	V. N. Vapnik, “The Nature of Statistical Learning Theory,” Springer- Verlag, New York, 1995.
[7]	V. N. Vapnik, “Statistical Learning Theory,” John Wiley & Sons, New York, 1998.
[8]	A. J. Smola, P. L. Bartlett, B. Schölkopf and D. Schuurmans, ”Advances in Large Margin Classifiers,” Cambridge, MA: MIT press, 2000.
[9]	C. J. C. Burges, “A Tutorial on Support Vector Machines for Pattern Recognition,” Data Mining and Knowledge Discovery, vol. 2, no. 2, pp. 121-167, 1998.
[10]	A. J. Smola and B. Schölkoph, “Learning with Kernels,” MIT Press, Cambridge, MA, 2002.
[11]	J. Shawe-Taylor, N. Cristianini, “Kernel Methods for Pattern Analysis,” MIT Press, Cambridge, MA, 2004.
[12]	A. Bowyer, “Computing Dirichlet Tessellations,” The Computer Journal, vol. 24, no. 2, pp. 162-166, 1981.
[13]	G. Voronoi, “Nouvelles Applications Des Paramètres Continus à La Théorie Des Formes Quadratiques,” Journal Für Die Reine Und Angewandte Mathematik, vol. 133, pp. 97-178, 1907.
[14]	H. Choset, K. Lynch, S. Hutchinson, G. Kantor, W. Burgard, L. Kavraki and Se. Thrun, “Principles of Robot Motion Theory, Algorithms, and Implementation,” A Bradford Book The MIT Press Cambridge, Massachusetts London, England, 2005.
[15]	D. G. Kirkpatrick, “Efficient Computation of Continuous Skeletons,” in Proc. 20th IEEE Annual Symposium on Foundations of Computer Science, pp. 18-27, Oct., 1979.
[16]	D. T. Lee and R. L. Drysdale III, “Generalized Voronoi Diagrams in the Plain,” SIAM Journal on Computing, vol. 10, no. 1, pp. 73-87, 1981.
[17]	S. Fortune, “A Sweepline Algorithm for Voronoi Diagrams,” Algorithmica, vol. 2, pp. 153-174, 1987.
[18]	A. Okabe, B. Boots, and K. Sugihara, “Nearest Neighbourhood Operations with Generalized Voronoi Diagrams: a Review,” International Journal of Geographical Information Systems, vol. 8, no. 1, pp. 43-71, 1994.
[19]	P. Blaer, “Robot Path Planning Using Generalized Voronoi Diagrams,” http://www.cs.columbia.edu/ pblaer/projects/path planner/. The AVENUE Project, Columbia University, USA, 2000.
[20]	S. Honiden, M. E. Houle, C. Sommer, and M. Wolff, “Approximate Shortest Path Queries Using Voronoi Duals.” Proceedings of the National Science Council, Republic of China, Part A: Physical Science and Engineering , vol. 24, no. 2, pp. 115-119.
[21]	K. Lee, W. k. Chung, “Navigable Voronoi Diagram : A Local Path Planner for Mobile Robots Using Sonar Sensors,” Intelligent Robots and Systems, 2007. IROS 2007. IEEE/RSJ International Conference on, pp. 2813-2818, San Diego, CA, Oct. 29 2007-Nov. 2 2007.
[22]	E. Masehian and M. R. Amin-Naseri, “A voronoi Diagram-Visibility Graph-Potential Field Compound Algorithm for Robot Path Planning,” Journal of Robotic Systems, vol. 21,  no. 6, June 2004. 
[23]	J. Miura, “Support Vector Path Planning,” Proceedings of the 2006 IEEE/RS International Conference on Intelligent Robots and Systems, October 9-15, Beijing, China, 2006.
[24]	E. W. Dijkstra, "A Note on Two Problems in Connexion with Graphs," Numerische Mathematik, pp. 269–271, 1959. 
[25]	H. I. Kang, B. Lee, K. Kim,” Path Planning Algorithm Using the Particle Swarm Optimization and the Improved Dijkstra Algorithm,”  IEEE Pacific-Asia Workshop on Computational Intelligence and Industrial Application, pp. 1002-1004, December 2008.
[26]	DU Yanwei, “Research on Path Planning of Materials Supply of Lean Production Based on the Dijkstra Algorithm,” IEEE International Conference on Computer Science and Information Technology, vol. 9, pp. 692-695, July 2010.
[27]	P. E. Hart, N. J. Nillson, B. Raphael, “A Formal Basis for the Heuristic Determination of Minimum Cost Paths,” IEEE Transactions on Systems Science and Cybernetics, vol. 4, no. 2, pp. 100-107, July 1968.
[28]	A. Stentz, “The Focussed D* Algorithm for Real-Time Replanning,” In Proceedings of the International Joint Conference on Artificial Intelligence, pp. 1652-1659, 1995.
[29]	A. Stentz, “Optimal and Efficient Path Planning for Partially-Known Environments,” IEEE International Conference on Robotics and Automation, vol. 4, pp. 3310-3317, May 1994.
[30]	S. Koenig, M. Likhachev, D. Furcy, “Lifelong Planning A*,” Journal of Artificial Intelligence, vol. 155, no. 1-2, pp. 93-146, May 2004.
[31]	S. Baselau, F. Hahne, K. Ambrosi, “Shortest-Path Algorithms and Dynamic Cost Changes,” Operations Research Proceedings, vol. 2007, pp. 111-116, 2008.
[32]	S. Koenig, M. Likhachev, “D* Lite,” In Proceedings of the AAAI Conference of Artificial Intelligence, pp. 476-483, 2002.
[33]	S. Koenig, M. Likhachev, “Fast Replanning for Navigation in Unknown Terrain,” IEEE Transactions on Robotics and Automation, vol.21, no. 3, pp. 354-363, 2002.
[34]	M. Likhachev, D. Ferguson, G. Gordon, A. Stentz, S. Thrun, “Anytime Dynamic A*: An Anytime, Replanning Algorithm,” In Proceedings of the International Conference on Automated Planning and Scheduling, 2005.
[35]	Z. Du, D. Qu, F. Xu, D. Xu, “A Hybrid Approach for Mobile Robot Path Planning in Dynamic Environments,” IEEE International Conference on Robotics and Biomimetics, pp. 1058-1063, December 2007.
[36]	J. Baltes and N. Hildreth, “Adaptive Path Planner for Highly Dynamic Environments,” In Proceeding of RoboCup 2000: Robot Soccer World Cup IV, pp. 76-85, 2001.
[37]	A.Bicchi, G. Casalino, C. Santilli, “Planning Shortest Bounded-Curvature Paths for a Class of Nonholonomic Vehicles Among Obstacles,” In Proceeding of IEEE International Conference on Robotics and Automation, vol. 2, pp. 1349-1354, May 1995.
[38]	H. Miao and Y. C. Tian, “Robot Path Planning in Dynamic Environments Using a Simulated Annealing Based Approach,” International Conference on Control, Automation, Robotics and Vision, pp. 1253-1258, December 2008
[39]	F. P. Preparata, and M. I. Shamos, “Computational Geometry-an Introduction,” 1st Ed., Springer-Verlag, New York, 1985.
[40]	A. Schmitt, and O. Kreylos, “When Is a Point Inside a Polygon,” http://idav.ucdavis.edu/~okreylos/TAsh
ip/Spring2000/PointInPolygon.html. Institute of Data Analysis and Visualization, UC Davis, USA, 2000.
[41]	N. J. Nilsson, “A Mobile Automaton: An Application of Artificial Intelligence Techniques,” In 1st International Conference on Artificial Intelligence, pp. 509-520, 1969.
[42]	B.Chazelle, “Approximation and Decomposition of Shapes,” In J. T. Schwartz and C. K. Yap, editors, Algorithmic and Geometric Aspects of Robotics, pp.145-185, Lawrence Erlbaum Associates, Hillsdale, NJ, 1987.