政大機構典藏-National Chengchi University Institutional Repository(NCCUR):Item 140.119/95637

政大機構典藏-National Chengchi University Institutional Repository(NCCUR):Item 140.119/95637

English | 正體中文 | 简体中文 | Post-Print筆數 : 27 | Items with full text/Total items : 113324/144300 (79%)
Visitors : 51118765 Online Users : 1026

RC Version 6.0 © Powered By DSPACE, MIT. Enhanced by NTU Library IR team.

Scope

please add "double quotation mark" for query phrases to get precise results

please goto advance search for comprehansive author search

Adv. Search

Home ‧ Login ‧ Upload ‧ Help ‧ About ‧ Administer

Goto mobile version

政大典藏 > College of Informatics > Department of Computer Science > Theses > Item 140.119/95637

Please use this identifier to cite or link to this item: https://nccur.lib.nccu.edu.tw/handle/140.119/95637

Title:	漸進式運動計畫之街圖管理 Roadmap Management for Incremental Motion Planning
Authors:	謝揚權 Hsieh, Yang Chuan
Contributors:	李蔡彥 Li, Tsai Yen 謝揚權 Hsieh, Yang Chuan
Date:	2002
Issue Date:	2016-05-09 16:46:17 (UTC+8)
Abstract:	運動計畫的技術已被廣泛地應用在機器人學及電腦圖學等領域。其基本問題的型態，是在一散佈著障礙物的場景中，給定物體之起點與終點，再利用運動計畫的演算法，來搜尋該物體由起點到終點不會碰撞到障礙物的可行路徑。這類問題的運動計畫方法可分為兩類：單一查詢及多次查詢。前者的好處是可以應用於動態的環境中，而後者的優點是可以透過對環境做事前的處理而減少搜尋所花費的時間。在本論文中，我們延展文獻中快速擴展隨機樹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
Reference:	[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.
Description:	碩士國立政治大學資訊科學學系
Source URI:	http://thesis.lib.nccu.edu.tw/record/#A2010000153
Data Type:	thesis
Appears in Collections:	[Department of Computer Science ] Theses

Files in This Item:

File	Size	Format
index.html	0Kb	HTML2	343	View/Open

All items in 政大典藏 are protected by copyright, with all rights reserved.

社群 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 © - Feedback