即時機器人路徑重規劃之Delaunay Triangulation/Voronoi Diagram之拓樸結構

Delaunay Triangulation/Voronoi Diagram Topological Configuration for Real-Time Path Robotic Replanner

周成翰(Cheng-Han Chou)

指導教授 ： 楊智旭

共同指導教授 ： 楊棧雲(Chan-Yun Yang)

淡江大學/工學院/機械與機電工程學系碩士班/碩士(2012年)

https://doi.org/10.6846/TKU.2012.01086

摘要

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

關鍵字

路徑規劃 ； 廣義Voronoi結構劃分(GVD) ； D*Lite路徑規劃 ； 三角剖分(DT，Delaunay Triangulation) ； Quad-Edge資料結構 ； 拓樸地圖

並列摘要

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.

並列關鍵字

Path Planning ； Generalized Voronoi Tessellation ； D* Lite ； Delaunay Triangulation ； Quad-edge Data structure

參考文獻

[4]馬志豪, 基於分類之避障路徑規劃與實現, 淡江大學機械與機電學研究所,民國99年6月。

[5] 蕭孟華, 隨機散佈障礙環境下動態路徑規劃–結合GVD、D* Lite、與SVM之研究, 淡江大學機械與機電學研究所，民國100年6月。

[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月。