English  |  正體中文  |  简体中文  |  Items with full text/Total items : 52052/87180 (60%)
Visitors : 8897573      Online Users : 297
RC Version 7.0 © Powered By DSPACE, MIT. Enhanced by NTU Library & TKU Library IR team.
Scope Tips:
  • please add "double quotation mark" for query phrases to get precise results
  • please goto advance search for comprehansive author search
  • Adv. Search
    HomeLoginUploadHelpAboutAdminister Goto mobile version
    Please use this identifier to cite or link to this item: http://tkuir.lib.tku.edu.tw:8080/dspace/handle/987654321/88018

    Title: 即時機器人路徑重規劃之Delaunay TriangulationVoronoi Diagram之拓樸結構
    Other Titles: Delaunay triangulation/voronoi diagram topological configuration for real-time path robotic replanner
    Authors: 周成翰;Chou, Cheng-Han
    Contributors: 淡江大學機械與機電工程學系碩士班
    楊智旭;Yang, Jr-Syu
    Keywords: 路徑規劃;廣義Voronoi結構劃分(GVD);D*Lite路徑規劃;三角剖分(DT,Delaunay Triangulation);Quad-Edge資料結構;拓樸地圖;Path Planning;Generalized Voronoi Tessellation;D* Lite;Delaunay Triangulation;Quad-edge Data structure
    Date: 2012
    Issue Date: 2013-04-13 11:56:57 (UTC+8)
    Abstract: 本論文以局部拓樸地圖更新建立機器人即時路徑更新研究理論採用整合以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.
    Appears in Collections:[機械與機電工程學系暨研究所] 學位論文

    Files in This Item:

    File SizeFormat

    All items in 機構典藏 are protected by copyright, with all rights reserved.

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