政大機構典藏-National Chengchi University Institutional Repository(NCCUR):Item 140.119/95637
English  |  正體中文  |  简体中文  |  Post-Print筆數 : 27 |  全文筆數/總筆數 : 113324/144300 (79%)
造訪人次 : 51121683      線上人數 : 885
RC Version 6.0 © Powered By DSPACE, MIT. Enhanced by NTU Library IR team.
搜尋範圍 查詢小技巧：
  • 您可在西文檢索詞彙前後加上"雙引號"，以獲取較精準的檢索結果
  • 若欲以作者姓名搜尋，建議至進階搜尋限定作者欄位，可獲得較完整資料
    •  進階搜尋
    政大機構典藏 > 資訊學院 > 資訊科學系 > 學位論文 >  Item 140.119/95637


    請使用永久網址來引用或連結此文件: https://nccur.lib.nccu.edu.tw/handle/140.119/95637


    題名: 漸進式運動計畫之街圖管理
    Roadmap Management for Incremental Motion Planning
    作者: 謝揚權
    Hsieh, Yang Chuan
    貢獻者: 李蔡彥
    Li, Tsai Yen
    謝揚權
    Hsieh, Yang Chuan
    日期: 2002
    上傳時間: 2016-05-09 16:46:17 (UTC+8)
    摘要: 　　運動計畫的技術已被廣泛地應用在機器人學及電腦圖學等領域。其基本問題的型態，是在一散佈著障礙物的場景中，給定物體之起點與終點，再利用運動計畫的演算法，來搜尋該物體由起點到終點不會碰撞到障礙物的可行路徑。這類問題的運動計畫方法可分為兩類：單一查詢及多次查詢。前者的好處是可以應用於動態的環境中，而後者的優點是可以透過對環境做事前的處理而減少搜尋所花費的時間。在本論文中，我們延展文獻中快速擴展隨機樹RRT (Rapidly-exploring Random Tree) 的結構，建立一種稱為RRF (Reconfigurable Random Forest) 的資料結構，用來有效解決運動計畫之問題。此方法是以漸進學習的方式，逐步地在場景中建構出運動計畫所需之街圖，並運用一些精簡街圖的策略，可以有效地管理維護街圖之成長。RRF同時具備了單一查詢及多次查詢的優點，我們分別於靜態以及動態的環境下實驗，以觀察其實際運作的情形，並針對精簡街圖之有效性與影響作深入的探討與評估。實驗結果顯示，此方法可有效提昇運動計畫器的效率及其適用的範圍。
    　　The motion-planning techniques have been widely applied to many domains, such as robotics and computer graphics. The basic problem of motion planning is about finding a collision-free path for a robot, moving in a workspace cluttered with obstacles. Traditional approaches to the motion-planning problem can be classified into single-query and multiple-query problems with the tradeoffs on run-time computation cost and adaptability to environment changes. In this paper, we extend the Rapidly-exploring Random Tree (RRT) structure proposed in the literature, to a more flexible data structure, called Reconfigurable Random Forest (RRF). This approach can learn incrementally on every planning query and effectively manage the learned roadmap. This planner is as efficient as other single-query planners and the performance gets improved when the learning process goes on. Our experiments show that the planner can also account for environmental changes and maintain a concise and representative roadmap. Experimental results show that this planner has broadened the applicability of motion planners to problems of different characteristics and complexities.
    致謝
    摘要-----i
    Abstract-----ii
    目錄-----iii
    圖目錄-----iv
    表目錄-----vi
    第一章 緒論-----1
    　　1.1 簡介-----1
    　　1.2 問題描述-----2
    　　1.3 研究動機與目的-----5
    　　1.4 本論文的貢獻-----6
    　　1.5 本論文的章節架構-----7
    第二章 相關研究-----8
    第三章 RRTs與RRT-Connect演算法-----14
    　　3.1 快速擴展隨機樹 (RRTs)-----14
    　　3.2 RRT-Connect演算法-----16
    第四章 漸進式街圖之建立-----21
    　　4.1 整合learning phase 與 query phase-----21
    　　4.2 Reconfigurable Random Forest (RRF)-----23
    　　4.3 實驗-----27
    　　4.4 討論-----30
    第五章 街圖管理-----33
    　　5.1 在動態的環境下修改RRF-----33
    　　5.2 動態場景實驗-----35
    　　5.3 精簡街圖-----37
    　　5.4 精簡街圖實驗-----40
    　　5.5 結果分析與討論-----44
    第六章 應用-----47
    第七章 結論-----53
    　　7.1 結論-----53
    　　7.2 未來發展-----54
    參考文獻-----56

    圖目錄
    圖1.1：虛擬實境中的自動導覽系統-----2
    圖1.2：Robot的組態-----3
    圖1.3：2D的工作空間中，具有四個自由度之robot的例子-----4
    圖1.4：2D場景之運動計畫實例-----5
    圖2.1：Cell decompostion方法-----9
    圖2.2：potential field方法-----10
    圖2.3：Roadmap方法-----11
    圖3.1：RRT建構之概念圖-----14
    圖3.2：快速擴展隨機樹(RRT)之演算法-----15
    圖3.3：三維空間中RRT成長情形之投影圖-----16
    圖3.4：RRT-Connect之運作原理-----17
    圖3.5：RRT-Connect之演算法-----18
    圖3.6：有限制條件之RRT-----19
    圖3.7：以edges間夾角來決定可成長距離之RRT-----20
    圖4.1：兩棵RRTs做merge的情況-----24
    圖4.2：RRF的成長過程-----25
    圖4.3：Merge_RRTs之演算法-----26
    圖4.4：RRF_Planner之演算法-----27
    圖4.5：路徑計畫器之範例一-----28
    圖4.6：路徑計畫器之範例二-----28
    圖4.7：計畫器學習過程中的取樣點數-----29
    圖4.8：Robot鄰接著障礙物的情形-----30
    圖4.9：Narrow passage的例子-----32
    圖5.1：動態修改RRF之演算法(Validate_RRT)-----35
    圖5.2：動態實驗場景-----36
    圖5.3：精簡街圖之例子-----38
    圖5.4：修剪RRF枝葉之演算法(PRUNE_TREE)-----39
    圖5.5：RRF中節點的合併策略-----40
    圖5.6：精簡街圖之實驗結果-----42
    圖5.7：查詢次數與計畫時間和累計節點數之關係圖-----43
    圖6.1：虛擬場景瀏覽系統-----47
    圖6.2：利用Applet所呈現的場景投影圖-----48
    圖6.3：根據使用者的輸入來預測其目的地-----49
    圖6.4：利用RRF所搜尋到的路徑，可能會造成繞遠路的狀況-----52

    表目錄
    表5.1：PRUNE_TREE使用週期實驗數據-----45
    參考文獻: [1] N. M. Amato, O. B. Bayazit, L. K. Dale, C. Jones, and D. Vallejo, “OBPRM: An Obstacle-Based PRM for 3D Workspaces,” Robotics: The Algorithmic Perspective, pp.630-637, 1998.
    [2] R. A. Brooks and T. Lozano-Perez, “A Subdivision Algorithm in Configuration Space for Find-path with Rotation,” IEEE Transaction on System, Man, and Cybernetics, 15:224-244, 1985.
    [3] J. Barraquand, J. Latombe, “Robot Motion Planning: A Distributed Representation Approach,” in International Journal of Robotics Research, 10:628-649,1991.
    [4] J. Barraquand, B. Langlois, and J.C. Latombe, “Numerical Potential Field Techniques for Robot Path Planning,” IEEE Transaction on System, Man, and Cybernetics, 22(2):224-241, 1992
    [5] J. Barraquand, L. Kavraki, J.C. Latombe, T.Y. Li, and P. Raghavan, “A Random Sampling Scheme for Path Planning,” in International Journal of Robotics Research, 16(6), pp.759-774, December, 1997.
    [6] H. Chang and T. Y. Li, “Assembly Maintainability Study with Motion Planning,” in Proceedings of the International Conference on Robotics and Automation, pp.1012-1019, May, 1995..
    [7] P. Khosla and R. Volpe, “Superquadric Artificial Potentials for Obstacle Avoidance and Approach,” in Proceedings of the International Conference on Robotics and Automation, Philadelphia, pp.1178-1184, 1988.
    [8] D. E. Koditschek, “Robot Planning and Control via Potential Functions,” in The Robotics Review 1, Cambridge: MIT Press, O. Khatib, J. J. Craig, and T. Lozano-Perez, editor, pp.349-367, 1989.
    [9] L. Kavraki, P.Svestka, J. Latombe, and M. Overmars, “Probabilistic Roadmaps for Fast Path Planning in High-Dimensional Configuration Spaces,” IEEE Transaction on Robotics and Automation, 12:566-580, 1996.
    [10] J. J. Kuffner, “Autonomous Agents for Real-time Animation,” PhD thesis, Stanford University, 1999.
    [11] J. J. Kuffner and S. M. LaValle, “RRT-Connect: An Efficient Approach to Single-query Path Planning,” in Proceedings of the International Conference on Robotics and Automation, 2:995-1001, 2000.
    [12] J. Lengyel, M. Reichert, B.R. Donald, and P. Greenberg, “Real-time Robot Motion Planning using Rasterizing Computer Graphics Hardware,” in Proceeding SIG-GRAPH’90, pp.327-335, Dallas,TX, 1990.
    [13] J. Latombe, Robot Motion Planning, Kluwer, Boston, MA, 1991.
    [14] S. M. LaValle, “Rapidly-exploring random trees: A new tool for path planning,” Iowa State University, 1998.
    [15] S. M. LaValle and J. J. Kuffner. “Randomized kinodynamic planning,” in Proceedings of the International Conference on Robotics and Automation, May, 1999.
    [16] T.-Y. Li, J.M. Lien, S.Y. Chiu, and T.H. Yu, “Automatically Generating Virtual Guided Tours,” in Proc. of the Computer Animation ``99 Conference, Geneva, Switzerland, pp.99-106, May 1999.
    [17] T.-Y. Li and T.-H. Yu, “Planning Object Tracking Motions,” in Proceedings of the International Conference on Robotics and Automation, May 1999.
    [18] T.-Y. Li, and H.-K Ting, “An Intelligent User Interface with Motion Planning for 3D Navigation,” in Proceedings of the International Conference on Robotics and Automation, March 2000.
    [19] T.-Y. Li, and Y. C. Shie, “An Incremental learning Approach to Motion Planning with Roadmap Management,” Proceedings of the International Conference on Robotics and Automation, May 2002.
    [20] C. Nissoux, T. Simeon, and J. P. Laumond, “Visibility Based Probabilistic Roadmaps,” Proceedings of the IEEE International Conference on Intelligent Robotics and Systems,1999
    [21] M. H. Overmars and P. Svestka, “A Probabilistic Learning Approach to Motion Planning,” in Algorithmic Foundations of Robotics, K. Goldberg, D. Halperin, J. C. Latombe, R. Wilson, editor, pp.19-38, 1994.
    [22] L. Pedersen, “Autonomous Characterization of Unknown Environments,” in Proceedings of the International Conference on Robotics and Automation, May 2001.
    [23] J. T. Schwartz and M. Sharir, “On the ‘Piano Movers’ Problem — II: General Techniques for Computing Topological Properties of Real Algebraic Manifolds,” Advances in Applied Mathematics, 4:298-351, 1983.
    [24] G. Song and N. M. Amato, “Using Motion Planning to Study Protein Folding Pathways,” Proceedings of the Fifth Annual International Conference on Computational Biology, pp.287-296, 2001.
    描述: 碩士
    國立政治大學
    資訊科學學系
    資料來源: http://thesis.lib.nccu.edu.tw/record/#A2010000153
    資料類型: thesis
    顯示於類別:[資訊科學系] 學位論文

    文件中的檔案:

    檔案 大小格式瀏覽次數
    index.html0KbHTML2343檢視/開啟


    在政大典藏中所有的資料項目都受到原著作權保護.


    社群 sharing

    著作權政策宣告 Copyright Announcement
    1.本網站之數位內容為國立政治大學所收錄之機構典藏，無償提供學術研究與公眾教育等公益性使用，惟仍請適度，合理使用本網站之內容，以尊重著作權人之權益。商業上之利用，則請先取得著作權人之授權。
    The digital content of this website is part of National Chengchi University Institutional Repository. It provides free access to academic research and public education for non-commercial use. Please utilize it in a proper and reasonable manner and respect the rights of copyright owners. For commercial use, please obtain authorization from the copyright owner in advance.

    2.本網站之製作，已盡力防止侵害著作權人之權益，如仍發現本網站之數位內容有侵害著作權人權益情事者，請權利人通知本網站維護人員(nccur@nccu.edu.tw)，維護人員將立即採取移除該數位著作等補救措施。
    NCCU Institutional Repository is made to protect the interests of copyright owners. If you believe that any material on the website infringes copyright, please contact our staff(nccur@nccu.edu.tw). We will remove the work from the repository and investigate your claim.
    DSpace Software Copyright © 2002-2004  MIT &  Hewlett-Packard  /   Enhanced by   NTU Library IR team Copyright ©   - 回饋