Ellipsoid aMAPRM中間軸偵測與Voronoi邊界取樣之機器人路徑規劃應用

機器人路徑規劃是相當複雜且具挑戰性的資訊工程題目. 主要是因為要考量的空間數會隨著機器人關節數增加, 而自由度夠大的機器人關節必須很多, 使得機器人路徑規劃成為一種高維度空間收尋的問題. 對於此類問題目前還沒有一貫的標準解法. 一般常見路徑規劃所採取的策略是透過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.

並列關鍵字

robot control ； path planning ； motion planning ； probabilistic roadmap ； voronoi diagram ； delaunay edge ； gaussian sampling

參考文獻

[1] E.U. Acar, P.N. Atkar, H. Choset, D. Hull, A.A. Rizzi, "Exact Cellular Decompositions in Terms of Critical Points of Morse Functions for Sensor-based Coverage Tasks", International Journal of Robotics Research, 2001.

[2] E.U. Acar, H. Choset, J.Y. Lee, "Sensor-Based Coverage With Extended Range Detectors", IEEE Transactions on Robotics, Volume 22, Issue 1, p.189-198, 2006.

[4] N.M. Amato, P.F. Stiller, S.A. Wilmarth, "MAPRM: A Probabilistic Roadmap Planner with Sampling on the Medial Axis of the Free Space", IEEE International Conference on Robotics and Automation, p.1024-1031, 1999.

[6] S. Arimoto, T. Naniwa, H. Noborio, "A Quadtree-based Path-planning Algorithm for A Mobile Robot", Journal of Robotic Systems, Volume 7, Issue 4, p.555-574, 1990.

[7] D. Attali, A. Montanver, "Computing and Simplifying 2D and 3D Continuous Skeletons", Computer Vision and Image Understanding, Volume 67, Issue 3, p.261-273, 1997.

國際替代計量

Ellipsoid aMAPRM中間軸偵測與Voronoi邊界取樣之機器人路徑規劃應用

全文下載

主題瀏覽