請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/31543
完整後設資料紀錄
DC 欄位 | 值 | 語言 |
---|---|---|
dc.contributor.advisor | 傅立成(Li-chen Fu) | |
dc.contributor.author | Jerry Chen | en |
dc.contributor.author | 陳任志 | zh_TW |
dc.date.accessioned | 2021-06-13T03:14:32Z | - |
dc.date.available | 2006-08-04 | |
dc.date.copyright | 2006-08-04 | |
dc.date.issued | 2006 | |
dc.date.submitted | 2006-08-02 | |
dc.identifier.citation | [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. [3] N.M. Amato, O.B. Bayazit, L.K. Dale, C.V. Jones, D. Vallejo, 'OBPRM: An obstacle-based PRM for 3D workspaces', Workshop on Algorithmic Foundations of Robotics, p.155-168, 1998. [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. [5] N. Amenta, S. Choi, R.K. Kolluri, 'The Power Crust', 6th ACM Symposium on Solid Modeling, p.249-260, 2001. [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. [8] J.C. Latombe, 'Robot Motion Planning', Kluwer Academic Publishers, 1991. [9] J. Basch, L.J. Guibas, D. Hsu, A.T. Nguyen, 'Disconnection Proofs for Motion Planning', IEEE International Conference on Robotics and Automation, p.1765-1772, 2001. [10] O. Brock, Y. Yang, 'Adapting the Sampling Distribution in PRM Planners Based on an Approximated Medial Axis', IEEE International Conference on Robotics and Automation, 2004. [11] O. Brock, Y. Yang, R.N. Moll – 'Efficient and Robust Computation of an Approximated Medial Axis', ACM Symposium on Solid Modeling and Applications, 2004. [12] H. Choset, 'Incremental Construction of the Generalized Voronoi Diagram, the Generalized Voronoi Graph, and the Hierarchical Generalized Voronoi Graph', 1st Center for Geometric Computing Workshop on Computation Geometry, 1997. [13] H. Choset, G. Kantor, B. Lisien, D. Morales, I. Rekleitis, D. Silver, 'The Hierarchical Atlas' IEEE Transactions on Robotics, Volume 21, Issue 3, p.473-481, 2005. [14] H. Choset, J.Y. Lee, 'Sensor-based Exploration for Convex Bodies - A New Roadmap for a Convex-shaped Robot', IEEE Transactions on Robotics, Volume 21, Issue 2, p.240-247, 2005. [15] C. Holleman, L.E. Kavraki, 'A Framework for Using the Workspace Medial Axis in PRM Planners', IEEE International Conference on Robotics and Automation, p.1408-1413, 2000. [16] D. Hsu, T. Jiang, J. Reif, Z. Sun, 'The Bridge Test for Sampling Narrow Passages with Probabilistic Roadmap Planners'. IEEE International Conference on Robotics and Automation, 2003. [17] D. Hsu, J.C. Latombe, R. Motwani, 'Path Planning in Expansive Configuration Spaces', International Journal for Computational Geometry and Applications, Volume 9, Issues 4-5, p.495-512, 1999. [18] P. Ferbach, 'A Method of Progressive Constraints for Nonholonomic Motion Planning', IEEE International Conference on Robotics and Automation, p.2949-2955, 1996. [19] M. Foskey, M. Lin, D. Manocha, 'Efficient Computation of A Simplified Medial Axis', ACM Symposium on Solid Modeling and Applications, 2003. [20] R.B. Gillespie, V. Patoglu, 'Feedback-stabilized Minimum Distance Maintenance for Convex Parametric Surfaces', Robotics, IEEE Transactions, Volume 21, Issue 5, p.1009-1016, 2005. [21] J.E. Hopcroft, G.T. Wilfong, 'Reducing Multiple Object Motion Planning to Graph Searching', Society for Industrial and Applied Mathematics Journal on Computing, Volume 15, Issue 3, p.768-785, 1986. [22] L.E. Kavraki, J.C. Latombe, M.H. Overmars, P. Svestka, 'Probabilistic Roadmaps for Path Planning in High Dimensional Configuration Spaces', International Journal of Robotics Research, Volume 12, Issue 4, p.566-580, 1996. [23] J.J. Kuffner, S.M. LaValle, 'RRT-Connect: An Efficient Approach to Single Query Path Planning', IEEE International Conference on Robotics and Automation, 2000. [24] T. Lozano-Perez, M. Wesley, 'An Algorithm for Planning Collision-free Paths among Polyhedral Obstacles', Communications of the ACM, Volume 22, Issue 10, p.560-570, 1979. [25] S.M. LaValle, 'Planning Algorithms', Cambridge University Press, 2006. [26] J. Barraquand, J.C. Latombe, 'Robot Motion Planning: A Distributed Representation Approach', The International Journal of Robotics Research, Volume 10, Issue 6, p.628-649, 1991. [27] D. Manocha, G. Varadhan, 'Star-shaped Roadmaps - A Deterministic Sampling Approach for Complete Motion Planning', Robotics: Science and Systems, 2005. [28] M.H. Overmars, J.P. van den Berg, 'Using Workspace Information as a Guide to Non-uniform Sampling in Probabilistic Roadmap Planners', International Journal of Robotics Research, Volume 24, Issue 12, p.1055-1071, 2005. [29] T. Sugimoto, M. Tanemura, 'Random Sequential Covering of a Sphere with Identical Spherical Caps', Forma, Volume 16, Issue 3, p.209-212, 2001. [30] C. Warren, 'Global Path Planning using Artificial Potential Fields', IEEE International Conference on Robotics and Automation, p.316-321, 1989. | |
dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/31543 | - |
dc.description.abstract | 機器人路徑規劃是相當複雜且具挑戰性的資訊工程題目. 主要是因為要考量的空間數會隨著機器人關節數增加, 而自由度夠大的機器人關節必須很多, 使得機器人路徑規劃成為一種高維度空間收尋的問題. 對於此類問題目前還沒有一貫的標準解法. 一般常見路徑規劃所採取的策略是透過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. | zh_TW |
dc.description.abstract | 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. | en |
dc.description.provenance | Made available in DSpace on 2021-06-13T03:14:32Z (GMT). No. of bitstreams: 1 ntu-95-R93922142-1.pdf: 1587039 bytes, checksum: cbc747457be81dd05ebe71d6140f3280 (MD5) Previous issue date: 2006 | en |
dc.description.tableofcontents | 1 Introduction 1
1.1 Problem Formulation 1 1.2 Motivation 3 1.3 Chapter Overview 4 2 Related Works 5 2.1 Related Works Overview 5 2.2 Artificial Potential Fields 5 2.3 Rapidly-Exploring Random Trees 6 2.4 Grid-Based Planning 7 2.5 Visibility Planning 7 2.6 Reeb Graph Planning 8 2.7 Progressive Constraints 9 2.8 Probabilistic Roadmaps (PRM) 10 2.8.1 Obstacle-Based PRM (OBPRM) 11 2.8.2 Bridge Test Sampling 12 2.8.3 Medial Axis PRM (MAPRM) 12 2.9 Related Works Conclusion 13 3 Hybrid Adaptive Path Planning 15 3.1 Algorithm Overview 15 3.2 Theoretical Considerations 17 3.2.1 Lookout and Expansiveness 17 3.2.2 Voronoi Diagram as a Roadmap 20 3.2.3 Center of Maximal Balls Approximates The Medial Axis 21 3.2.4 Exact vs. Approximated Medial Axis 21 3.3 Ellipsoid aMAPRM 22 3.3.1 AMAPRM 23 3.3.2 Separation Angle Criteria 25 3.3.3 Complete Sphere Cover 26 3.3.4 Sample Convergence toward the Medial Axis 26 3.3.5 Gates of Narrow Passages 27 3.3.6 Ellipsoid Sampling 28 3.3.7 Projecting Sphere Samples onto an Ellipsoid 29 3.4 Random Cuts 30 3.5 Adaptive Voronoi-cuts 32 3.5.1 Voronoi and Delaunay Graphs 33 3.5.2 Bowyer-Watson Algorithm 33 3.5.3 The Shared Circumcircle in R2 and R3 35 3.5.4 Divide and Conquer Interpretation (Proof by Parts) 36 3.5.5 Gaussian Sampling 37 3.5.6 Gaussian Sampling Proof 37 3.5.7 Gaussian Bias vs. The Long Tail 42 3.5.8 Probabilistic Interpretation 43 3.6 Dijkstra's Shortest Path Algorithm 44 3.7 Algorithm Integration 46 4 Experiments 48 4.1 Ellipsoid aMAPRM vs Sphere aMAPRM 48 4.2 Adaptive Voronoi-cuts in Narrow Passages 51 4.2.1 Example 'S' 51 4.2.2 Example 'Snake' 52 4.2.3 Example 'Spiral' 54 4.2.4 Example 'Voronoi Diagram' 55 5 Conclusion 57 5.1 Statement of Results 57 5.2 Future Work 57 References 59 | |
dc.language.iso | en | |
dc.title | Ellipsoid aMAPRM中間軸偵測與Voronoi邊界取樣之機器人路徑規劃應用 | zh_TW |
dc.title | PATH PLANNING: Hybrid Ellipsoid aMAPRM Using Adaptive Voronoi-cuts | en |
dc.type | Thesis | |
dc.date.schoolyear | 94-2 | |
dc.description.degree | 碩士 | |
dc.contributor.oralexamcommittee | 連豐力(Feng-Li Lian),簡忠漢(Jong-Han Jean) | |
dc.subject.keyword | 路徑歸劃,機器人,控制,取樣, | zh_TW |
dc.subject.keyword | robot control,path planning,motion planning,probabilistic roadmap,voronoi diagram,delaunay edge,gaussian sampling, | en |
dc.relation.page | 61 | |
dc.rights.note | 有償授權 | |
dc.date.accepted | 2006-08-02 | |
dc.contributor.author-college | 電機資訊學院 | zh_TW |
dc.contributor.author-dept | 資訊工程學研究所 | zh_TW |
顯示於系所單位: | 資訊工程學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-95-1.pdf 目前未授權公開取用 | 1.55 MB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。