本論文以局部拓樸地圖更新建立機器人即時路徑更新研究理論採用整合以DT/VD對偶與Quad-Edge資料結構並結合D*Lite為實驗理論。大部分機器人應用於靜態環境規劃較容易運算，對於動態環境需要即時地更新較為困難。所以本研究針對拓樸地圖從靜態地拓樸產生進階為動態拓樸地圖地更新，主要是利用三角剖分(Delaunay Triangulation, DT)的拓樸理論，建立障礙空間之特徵地圖，基於DT之特徵地圖結構簡單，計算快速且具有能快速反應空間中動態的障礙物之增、刪、移動、變形，作即時局部地圖更新，並且基於DT / VD(Voronoi Diagram)之對偶關係 可以快速地相互轉換，以連結障礙物之動態變化與路徑重規劃。然後再應用Quad-Edge資料結構來實踐這個DT/VD之相互對偶關係，以這種資料結構預存構成的拓樸幾何關係及共建立快速索引鏈，在更新時以查詢取代重複計算減低計算需求。經由DT的動態拓樸更新快速地索引並更新VD來達成動態路徑重規劃以D*Lite產生機器人行走之路徑。研究成果以數值模擬結構與實驗模擬動態證實在環境下拓樸更新，可減少拓樸地圖所需的時間，同時提供一種動態環境拓樸更新之方法。

This study is aimed to establish a fast organism for abstracting passage topology from the obstacle configurations in a two-dimensional working space which is dedicated to supporting the mobility of a ground vehicle. Due to a request of real-time path-planning, a swift passage topology providing is particularly emphasized in this study to meet the obstacle changes in the working space, where the obstacle changes could be defined as an obstacle insertion, an obstacle deletion, or an obstacle movement. A topological map consecutively responding to the obstacle changes is thus an important foundation to guarantee that the ground vehicle can freely real-time react to the environment, even the dynamic environment. More precisely, a timely update of the topological map which conveys the obstacle changes and prompts the re-planner the update is the main goal of this study. From the theoretical aspects, the reversible conversion between Delaunay triangulation (DT) and Voronoi diagram (VD) is an admissible candidate for such a task. As our previous studies, the connectivity of a VD is an excellent candidate for the path-planner, even for the environment dynamically reacted path-replanner. The scenario of dynamic environment often implies the presence of the obstacle changes in the working space. Hence, a set of DT-update algorithms which can dynamically reflect those obstacle changes has been implemented. Based on the dual properties of DT and VD, a quad-edge data structure is then employed as the swift convertor to generate adapted VD connections for path-replanning. With the DT/VD reversible dual conversion, the developed algorithms together with the quad-edge data structure share the merits of the intrinsic properties of the DT/VD dual, and realize the real-time update of the topological map.

目錄
中文摘要	I
英文摘要	II
目錄	IV
圖目錄	VII
表目錄	IX
第一章 緒論	1
1-1、 前言	1
1-2、 研究動機與目的	3
1-3、 相關文獻	4
第二章 基礎理論	8
2-1、 工作空間、障礙配置	8
2-2、 散亂點集之特徵地圖組成	9
2-3、 VD與DT對偶結構剖分	10
2-3-1、	VD與GVD	10
2-3-2、	廣義Voronoi結構劃分(GVD)	12
2-3-3、	內點判別演算法	14
2-4、 從VD到GVD	16
2-5、 DT	17
2-6、 DT與VD之對偶關係	18
2-7、 建立DT之基本演算法	19
2-7-1、	空外接圓準則	20
2-7-2、	初始三角剖分建立	21
2-8、 動態DT演算法	25
2-8-1、	障礙點插入	25
2-8-2、	障礙點刪除	27
2-8-3、	障礙點移動	30
2-9、 Quad-Edge資料結構	33
2-9-1、	基本原理	33
2-9-2、	資料結構	35
2-9-2-1、 有向邊：Class Edge包含下列欄位：	35
2-9-2-2、 節點：Class Vertex包含下列欄位：	36
2-9-2-3、 面：Class Face包含下列欄位：	36
2-10、 DT與VD交互操作	37
2-11、 D* Lite演算法	37
第三章 研究設備與方法	39
3-1、 研究設備	39
3-2、 研究方法	41
3-3、 實驗相關之步驟與方法應用	44
3-3-1、	障礙點之增、刪與移動	44
3-3-2、	Quad-Edge資料結構應用	46
3-3-3、	地圖變動偵測	49
第四章 實驗與討論	50
4-1、 局部障礙物變動引起資料結構觀察	50
4-2、 地圖複雜度與計算時間之差異	52
4-3、 全局規劃與局部規劃比較	57
4-4、 各種障礙物配置其動態DT/VD實例	63
4-5、 D*Lite 動態路徑規畫	68
4-6、 討論	70
第五章 結論與討論	72
參考文獻	73
附錄 I	79
附錄 II	90


圖目錄
圖1-1、 機器人動態路徑規劃之需求例	2
圖1-2、動態拓樸機器人運動規劃示意圖	3
圖1-3、本論文重點研究之關係	4
圖2-1、工作空間地圖與特徵地圖之範例	10
圖2-2、Voronoi結構劃分	11
圖2-3、區塊障障物內Voronoi頂點與邊	12
圖2-4、一般與廣義之 Voronoi 結構劃分	14
圖2-5、射線內點判別法	15
圖2-6、區塊障障物內Voronoi頂點與邊之剪除	17
圖2-7、DT與VD之對偶關係	18
圖2-8、動態拓樸地圖演算法示意圖	20
圖2-9、空外接圓準則	21
圖2-10、 a、b、c三點循序取得兩點當作x、y作空外接圓準則測試	24
圖2-11、 障礙點插入步驟範例	26
圖2-12、 障礙點刪除步驟範例	29
圖2-13、影響障礙點移動之判斷準則	30
圖2-14、 障礙點移動步驟範例	32
圖2-15、Quad-Edge互為對偶四條有向邊的基本結構	34
圖2-16、Quad-Edge資料結構中的基本指標	34
圖3-1、整體驗證流程圖	39
圖3-2、場地實際場景圖	40
圖3-3、組裝完成之NXT機器人	41
圖3-4、路徑規劃完整系統流程	43
圖3-5、動態DT/VD理論示意圖	46
圖3-6、圖中為Quad-Edge資料結構之DT/VD對偶關係，與表3-1、表3-2、表3-3資料結構的比對圖	47
圖4-1、工作空間中之障礙點變動實例及其所引起之DT變化	52
圖4-2、十點障礙物複雜度範例	53
圖4-3、二十點障礙物複雜度範例	54
圖4-4、三十點障礙物複雜度範例	55
圖4-5、障礙點變動之全局拓樸規劃	59
圖4-6、障礙點變動之局部拓樸規劃範例	60
圖4-7、單點障礙物變動範例	64
圖4-8、多點障礙物變動範例	65
圖4-9、區塊障礙物範例	66
圖4-10、多區塊障礙物範例	67
 

表目錄
表2-1、group_code的代碼意涵	36
表3-1、Class Vertex 資料結構	47
表3-2、Class Edge 資料結構	48
表3-3、Class Edge 資料結構	48
表4-1單點障礙變動之拓樸地圖重新提供之時間單位。(秒)	56
表4-2兩點障礙變動之拓樸地圖重新提供之時間單位。(秒)	56
表4-3三點障礙變動之拓樸地圖重新提供之時間單位。(秒)	56
表4-4 全局與局部拓樸更新之比較	61
表4-5全局與局之拓樸地圖轉換時間數據	62

[1]Chan-Yun Yang, Jr-Syu Yang, Feng-Li Lian, "Safe and Smooth: Mobile Agent Trajectory Smoothing by SVM," International Journal of Innovative Computing Information and Control,Volume 8, Number 7(B) ,pp.4959-4978,2012.
[2]Feng-Yi Chou, Chan-Yun Yang, Jr-Syu Yang. Support vector machine based artificial potential field for autonomous guided vehicle. In Proc. of SPIE vol. 7130, 71304J.
[3]周峰毅, 安全平滑之機器人路徑規劃, 淡江大學機械與機電學研究所，民國97年6月。
[4]馬志豪, 基於分類之避障路徑規劃與實現, 淡江大學機械與機電學研究所,民國99年6月。
[5]	蕭孟華, 隨機散佈障礙環境下動態路徑規劃–結合GVD、D* Lite、與SVM之研究, 淡江大學機械與機電學研究所，民國100年6月。
[6]H. Choset, and K. Nagatani, “Topological simultaneous localization and mapping (SLAM): toward exact localization without explicit localization,” IEEE Transactions on Robotics and Automation, 17(2): 125-137, 2001.
[7]J. Tse, E. VanWyk, and J. Whong, “Path planning with phased array SLAM and voronoi tessellation,” Report of Olin College, 2006.  
[8]S. Friedman, H. Pasula, and D. Fox, “Voronoi random fields: extracting the topological structure of indoor environments via place labeling,” in Proc. of International Joint Conference on Artificial Intelligence, Hyderabad, India, 2007, 2109-2114.
[9]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.
[10]	E. Masehian and M. R. Amin-Naseri, “A Voronoi diagram-visibility graph-potential field compound algorithm for robot path planning,” Journal of Robotic Systems, 21(6), 275-300, 2004.
[11]J. Overholt, G. Hudas, G. Fiorani, M. Skalny, and A. Tucker, Dynamic waypoint navigation using Voronoi classifier methods, U.S. Army report OMB No. 0704-0188, RDECOM-TARDEC Robotics Mobility Laboratory Warren, 2004.
[12]Y. Li , T. Dong, M. Bikdash, Y. Song, "Path planning for unmanned vehicles using ant colony optimization on a dynamic Voronoi diagram," in Proc. of International Conference on Artificial Intelligence, Las Vegas NV, 2006.
[13]K. Lee, W. K. Chung, “Navigable Voronoi diagram : a local path planner for mobile robots using sonar sensors,” in Proc. IEEE/RSJ International Conference on Intelligent Robots and Systems 2007(IROS 2007), San Diego, CA, 2813-2818, 2007.
[14]Bhattacharya, P. and Gavrilova, M.L. “Roadmap-based path planning - using the Voronoi diagram for a clearance-based shortest path,” IEEE Robotics & Automation Magazine, 15(2), 58-66, 2008.
[15]S. Honiden, M. E. Houle, C. Sommer, and M. Wolff, “Approximate shortest path queries using Voronoi duals,” Lecture Notes in Computer Science, 6290, 28-53, 2010.
[16]J. Hartmann. “Real-time path planning in large. dynamic environments based on a Voronoi diagram,” Projecto de Diplomacao, Departamento de informatica aplica da computacao, Universidade federal do rio grande do sul, Porto Alegre, 2010.
[17]M. de Berg, O. Cheong, M. Van Kreveld, M. Overmars, Computational Geometry: Algorithms and Applications, 3rd Edition, Springer, Berlin, 2008.
[18]F. Aurenhammer and R. Klein, “Voronoi diagrams,” in Handbook of Computational Geometry, Chapter V, Editors: J. Sack and G. Urrutia, Elsevier Science Publishing, 201-290, 2000.
[19]I. G. Gowda, D. G. Kirkpatrick, D. T. Lee, A. Naamad, “Dynamic Voronoi diagrams,” IEEE Transactions on Information Theory, 29(5), 724-730, 1983.
[20]T. Roos and H. Noltemeier, “Dynamic Voronoi diagrams in motion planning,” Lecture Notes in Control and Information Sciences, 180, 102-111, 1992.
[21]A. Sud, E. Andersen, S. Curtis, M. Lin, and D. Manocha, “Real-time path planning for virtual agents in dynamic environments”, in Proc. IEEE Virtual Reality Conference (VR'07), Charlotte, NC, 91-98, 2007.
[22]D. P. Huttenlocher, K. Kedem, and J. M. Kleinberg, “Voronoi diagrams of rigidly moving sets of points,” Information Processing Letters, 47, 217-223, 1992.
[23]O. Devillers, “On deletion in Delaunay triangulation,” in Proc. 15th Annual ACM Symposium on Computational Geometry, Miami Beach, FL, 181-188, 1999.
[24]L. Lee, M. Gahegan, “Interactive analysis using Voronoi digrams: algorithms to support dynamic update a generic triangle-based data structure,” Transaction in GIS, 6(2), 89-114, 2002.
[25]M. A. Mostafavia, C. M. Gold, M. Dakowicz, “Delete and insert operations in Voronoi/Delaunay methods and applications,” Computers & Geosciences, 523-530, 2003.
[26]J. D. Boissonnat, O. Devillers, R. Schott, M. Teillaud and M. Yvinec, “Applications of random sampling to on-line algorithms in computational geometry,” Discrete & Computational Geometry, 8(1), 51-71, 1992.
[27]C. M. Gold, P. R. Remmele, and T. Roos, “Fully dynamic and kinematic Voronoi diagrams in GIS,” Algorithmica (Special Issue on Cartography and GIS), 1999.
[28]M. Held, “VRONI: An engineering approach to the reliable and efficient computation of Voronoi diagrams of points and line segments,” Computational Geometry, 95-123, 2001.
[29]M. Held, S. Huber, “Topology-oriented incremental computation of Voronoi diagrams of circular arcs and straight-line segments,” Computer-Aided Design, 327-338, 2009.
[30]T. Imai, “A topology oriented algorithm for the Voronoi diagram of polygons,” in Proc. 8th Canadian Conference on Computational Geometry, Ottawa, Ontario, Canada, 107-112, 1996.
[31]F. M. Pinto, C. M. D. S. Freitas, “Dynamic Voronoi diagram of complex sites,” The Visual Computer, 27(6-8), 463-472, 2011.
[32]H. Zimmer, “Voronoi and delaunay techniques,” Lecture Notes Computer Sciences VIII, RWTH Aachen, 2005.
[33]A. Bowyer, “Computing Dirichlet tessellations,” The Computer Journal, 24(2),162–166, 1981.
[34]Guibas, Knuth, Sharir, “Randomized incremental construction of Delaunay and Voronoi diagrams,” in Proc. 17th Annual International Colloquium Automata & Languages Programming, LNCS 443, Springer Verlag, 414-431,1990.
[35]Edelsbrunner, Shah, “Incremental topological flipping works for regular triangulations,” Algorithmica, 15(3), 223-241, 1992.
[36]L. Guibas and J. Stolfi, “Primitives for the manipulation of general subdivisions and the computation of Voronoi diagrams,” ACM Transactions on Graphics, 4(2), 1985, 75-123.
[37]G. Tucker, N. Gasparini, R. Bras, S. Rybarczyk, and S. Lancaster, “An object-oriented framework for distributed hydrologic and geomorphic modeling using triangulated irregular networks,” in Proc. International Conference on GeoComputation IV, Fredericksburg, VA, 1999.
[38]P. Heckbert, “Quad-Edge data structure and library,” Carnegie Mellon University 
http://www.cs.cmu.edu/afs/andrew/scs/cs/15-463/2001/pub/src/a2/quadedge.html, 2001.
[39]P. Boguslawski, C. Gold, “Augmented quad-edge - 3D data structure for modelling of building interiors,” in Proc. ISPRS Workshop on Updating Geo-spatial Databases with Imagery & The 5th ISPRS Workshop on DMGISs, Xingjiang, China, 51-53, 2007.
[40]S. Koenig, M. Likhachev, “D* Lite,” in Proc. AAAI Conference of Artificial Intelligence, Alberta, Canada, 476-483, 2002.
[41]S. Koenig, M. Likhachev, “Fast replanning for navigation in unknown terrain,” IEEE Transactions on Robotics and Automation, 21(3), 354-363, 2002.
[42]G. Voronoi, “Nouvelles applications des parametres continus a la theorie des formes quadratiques,” Journal fur die reine und angewandte mathematik, 133, 97-178, 1907.
[43]D. G. Kirkpatrick, “Efficient computation of continuous skeletons,” in Proc. 20th IEEE Annual Symposium on Foundations of Computer Science, 18-27, 1979.
[44]D. T. Lee and R. L. Drysdale III, “Generalized Voronoi diagrams in the plain,” SIAM journal on computing, 10(1), 73-87, 1981.
[45]S. Fortune, “A sweepline algorithm for Voronoi diagrams,” Algorithmica, 2, 153-174, 1987
[46]A. Okabe, B. Boots, and K. Sugihara, “Nearest neighbourhood operations with generalized Voronoi diagrams: a review,” International journal of geographical information systems, 8(1), 43-71, 1994.
[47]C.M. Gold, “PAN Graphs: an aid to GIS analysis,” International journal of geographical information systems, 2, 29-42, 1988.
[48]R. A. Dwyer, “A faster divide-and-conquer algorithm for constructing Delaunay triangulations,” Algorithmica, 2(1-4), 137-151, 1987.
[49]L. Guibas, D. E. Knuth and M. Sharir, “Randomized incremental construction of Delaunay and Voronoi diagrams,” Algorithmica, 7(1-6), 381-413, 1992.
[50]D. T. Lee and A. K. Lin, “Generalized Delaunay triangulations for planar graphs, ” Discrete and Computational Geometry, 1, 201–217, 1986.
[51]F. P. Preparata, and M. I. Shamos, “Computational Geometry-an Introduction,” 1st Ed., Springer-Verlag, New York, 1985.
[52]A. Schmitt, and O. Kreylos, “When Is a Point Inside a Polygon,” http://idav.ucdavis.edu/~okreylos/TAship/Spring2000/PointInPolygon.html. Institute of Data Analysis and Visualization, UC Davis, USA, 2000.