淡江大學覺生紀念圖書館 (TKU Library)
進階搜尋


下載電子全文限經由淡江IP使用) 
系統識別號 U0002-2507201214061800
中文論文名稱 即時機器人路徑重規劃之Delaunay Triangulation/Voronoi Diagram之拓樸結構
英文論文名稱 Delaunay Triangulation/Voronoi Diagram Topological Configuration for Real-Time Path Robotic Replanner
校院名稱 淡江大學
系所名稱(中) 機械與機電工程學系碩士班
系所名稱(英) Department of Mechanical and Electro-Mechanical Engineering
學年度 100
學期 2
出版年 101
研究生中文姓名 周成翰
研究生英文姓名 Cheng-Han Chou
學號 699370291
學位類別 碩士
語文別 中文
口試日期 2012-07-05
論文頁數 92頁
口試委員 指導教授-楊智旭
共同指導教授-楊棧雲
委員-連豊力
委員-王銀添
委員-孫崇訓
中文關鍵字 路徑規劃  廣義Voronoi結構劃分(GVD)  D*Lite路徑規劃  三角剖分(DT,Delaunay Triangulation)  Quad-Edge資料結構  拓樸地圖 
英文關鍵字 Path Planning  Generalized Voronoi Tessellation  D* Lite  Delaunay Triangulation  Quad-edge Data structure 
學科別分類 學科別應用科學機械工程
中文摘要 本論文以局部拓樸地圖更新建立機器人即時路徑更新研究理論採用整合以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.
論文使用權限
  • 同意紙本無償授權給館內讀者為學術之目的重製使用,於2014-07-26公開。
  • 同意授權瀏覽/列印電子全文服務,於2014-07-26起公開。


  • 若您有任何疑問,請與我們聯絡!
    圖書館: 請來電 (02)2621-5656 轉 2281 或 來信