學術產出-學位論文
文章檢視/開啟
書目匯出
-
題名 漸進式運動計畫之街圖管理
Roadmap Management for Incremental Motion Planning作者 謝揚權
Hsieh, Yang Chuan貢獻者 李蔡彥
Li, Tsai Yen
謝揚權
Hsieh, Yang Chuan日期 2002 上傳時間 9-五月-2016 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 dc.contributor.advisor 李蔡彥 zh_TW dc.contributor.advisor Li, Tsai Yen en_US dc.contributor.author (作者) 謝揚權 zh_TW dc.contributor.author (作者) Hsieh, Yang Chuan en_US dc.creator (作者) 謝揚權 zh_TW dc.creator (作者) Hsieh, Yang Chuan en_US dc.date (日期) 2002 en_US dc.date.accessioned 9-五月-2016 16:46:17 (UTC+8) - dc.date.available 9-五月-2016 16:46:17 (UTC+8) - dc.date.issued (上傳時間) 9-五月-2016 16:46:17 (UTC+8) - dc.identifier (其他 識別碼) A2010000153 en_US dc.identifier.uri (URI) http://nccur.lib.nccu.edu.tw/handle/140.119/95637 - dc.description (描述) 碩士 zh_TW dc.description (描述) 國立政治大學 zh_TW dc.description (描述) 資訊科學學系 zh_TW dc.description.abstract (摘要) 運動計畫的技術已被廣泛地應用在機器人學及電腦圖學等領域。其基本問題的型態，是在一散佈著障礙物的場景中，給定物體之起點與終點，再利用運動計畫的演算法，來搜尋該物體由起點到終點不會碰撞到障礙物的可行路徑。這類問題的運動計畫方法可分為兩類：單一查詢及多次查詢。前者的好處是可以應用於動態的環境中，而後者的優點是可以透過對環境做事前的處理而減少搜尋所花費的時間。在本論文中，我們延展文獻中快速擴展隨機樹RRT (Rapidly-exploring Random Tree) 的結構，建立一種稱為RRF (Reconfigurable Random Forest) 的資料結構，用來有效解決運動計畫之問題。此方法是以漸進學習的方式，逐步地在場景中建構出運動計畫所需之街圖，並運用一些精簡街圖的策略，可以有效地管理維護街圖之成長。RRF同時具備了單一查詢及多次查詢的優點，我們分別於靜態以及動態的環境下實驗，以觀察其實際運作的情形，並針對精簡街圖之有效性與影響作深入的探討與評估。實驗結果顯示，此方法可有效提昇運動計畫器的效率及其適用的範圍。 zh_TW dc.description.abstract (摘要) 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. en_US dc.description.abstract (摘要) 致謝 摘要-----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 - dc.description.tableofcontents 致謝 摘要-----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 zh_TW dc.source.uri (資料來源) http://thesis.lib.nccu.edu.tw/record/#A2010000153 en_US dc.title (題名) 漸進式運動計畫之街圖管理 zh_TW dc.title (題名) Roadmap Management for Incremental Motion Planning en_US dc.type (資料類型) thesis en_US dc.relation.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. zh_TW
