請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/31543
標題: | Ellipsoid aMAPRM中間軸偵測與Voronoi邊界取樣之機器人路徑規劃應用 PATH PLANNING: Hybrid Ellipsoid aMAPRM Using Adaptive Voronoi-cuts |
作者: | Jerry Chen 陳任志 |
指導教授: | 傅立成(Li-chen Fu) |
關鍵字: | 路徑歸劃,機器人,控制,取樣, robot control,path planning,motion planning,probabilistic roadmap,voronoi diagram,delaunay edge,gaussian sampling, |
出版年 : | 2006 |
學位: | 碩士 |
摘要: | 機器人路徑規劃是相當複雜且具挑戰性的資訊工程題目. 主要是因為要考量的空間數會隨著機器人關節數增加, 而自由度夠大的機器人關節必須很多, 使得機器人路徑規劃成為一種高維度空間收尋的問題. 對於此類問題目前還沒有一貫的標準解法. 一般常見路徑規劃所採取的策略是透過Probabilistic Roadmap (PRM)在參數空間裡作暴力式的高密度取樣, 設法窮舉一切可能的機器人姿態. 如果沒有參考到gaussian, 直接作naïve的均分部收尋, 會非常耗時間.
接續Latombe, LaValle, Ferbach, Overmars, 幾位大師奠定的基礎, 近年來出現的許多新穎方向著重在Randomized Path Planning (RPP), 像是Obstacle-based PRM, Medial-axis PRM, Bridge Test, Progressive Constraints, 等. 從文獻裡也感覺的出新潮流多在探討如何能快速的計算出c-free的結構. Medial-axis PRM, Visibility planning, Reeb Graph planning, Progressive Constraints不外乎都在建立反映真實參數空間topology的路徑規劃. 本研究提出一種嶄新的混程式方法可以快速的探索參數空間, 逐步發現完整的c-free connectivity. 混程的式第一個方法試圖改進Yang and Brock提出的Adaptive Medial-axis PRM (aMAPRM). 它利用ellipsoid取樣邊界加快原本sphere取樣邊界在細小空間的取樣速度. 混程的式第二個方法利用c-free的voronoi edge當作取樣的空間, 藉此收尋出更多c-free, 然後在新的voronoi edge上繼續取樣. 如此輾轉更新許多回, 直到c-free達到一定密度, 即停. 透過兩中子方法的結合我們得到完整性更高, 更有效率的path planner. A hybrid Path Planner is proposed based on the Adaptive Medial Axis Probabilistic Roadmap Planner (aMAPRM). It addresses two key drawbacks of aMAPRM: 1) slow progress in vast regions having a major direction and 2) inability to sample through gates of narrow passages. It approaches the first issue by employing 'Ellipsoid aMAPRM', which uses the Ellipsoid instead of the Sphere as its sampling boundary, covering more free space with possibly fewer samples. This is different from Covariance Sampling in that, rather than waiting for collisions to occur and then perturbing a sampling covariance matrix, it determines direction prior to collision using nearest obstacle information from the collision detector. The second issue is resolved by employing 'Adaptive Voronoi-cuts', which samples across midsections of narrow passages instead of sampling inside them. The “ideal” sampling direction, according to this heuristic, is at the voronoi boundaries of known c-free. By iteratively bisecting midsections, the full connectivity of c-free is gradually understood. This research argues that disjoint roadmaps constructed by the modified aMAPRM can be bridged using Adaptive Voronoi-cuts to form a better, more complete roadmap. |
URI: | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/31543 |
全文授權: | 有償授權 |
顯示於系所單位: | 資訊工程學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-95-1.pdf 目前未授權公開取用 | 1.55 MB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。