English  |  正體中文  |  简体中文  |  全文筆數/總筆數 : 49633/84879 (58%)
造訪人次 : 7690880      線上人數 : 80
RC Version 7.0 © Powered By DSPACE, MIT. Enhanced by NTU Library & TKU Library IR team.
搜尋範圍 查詢小技巧:
  • 您可在西文檢索詞彙前後加上"雙引號",以獲取較精準的檢索結果
  • 若欲以作者姓名搜尋,建議至進階搜尋限定作者欄位,可獲得較完整資料
  • 進階搜尋
    請使用永久網址來引用或連結此文件: http://tkuir.lib.tku.edu.tw:8080/dspace/handle/987654321/88018


    題名: 即時機器人路徑重規劃之Delaunay TriangulationVoronoi Diagram之拓樸結構
    其他題名: Delaunay triangulation/voronoi diagram topological configuration for real-time path robotic replanner
    作者: 周成翰;Chou, Cheng-Han
    貢獻者: 淡江大學機械與機電工程學系碩士班
    楊智旭;Yang, Jr-Syu
    關鍵詞: 路徑規劃;廣義Voronoi結構劃分(GVD);D*Lite路徑規劃;三角剖分(DT,Delaunay Triangulation);Quad-Edge資料結構;拓樸地圖;Path Planning;Generalized Voronoi Tessellation;D* Lite;Delaunay Triangulation;Quad-edge Data structure
    日期: 2012
    上傳時間: 2013-04-13 11:56:57 (UTC+8)
    摘要: 本論文以局部拓樸地圖更新建立機器人即時路徑更新研究理論採用整合以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.
    顯示於類別:[機械與機電工程學系暨研究所] 學位論文

    文件中的檔案:

    檔案 大小格式瀏覽次數
    index.html0KbHTML78檢視/開啟

    在機構典藏中所有的資料項目都受到原著作權保護.

    TAIR相關文章

    DSpace Software Copyright © 2002-2004  MIT &  Hewlett-Packard  /   Enhanced by   NTU Library & TKU Library IR teams. Copyright ©   - 回饋