本論文以局部拓樸地圖更新建立機器人即時路徑更新研究理論採用整合以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.
