請用此 Handle URI 來引用此文件：
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/9679完整後設資料紀錄
| DC 欄位 | 值 | 語言 |
|---|---|---|
| dc.contributor.advisor | 黃漢邦(Han-Pang Huang) | |
| dc.contributor.author | Yi-Chih Tsai | en |
| dc.contributor.author | 蔡乙至 | zh_TW |
| dc.date.accessioned | 2021-05-20T20:35:10Z | - |
| dc.date.available | 2008-08-05 | |
| dc.date.available | 2021-05-20T20:35:10Z | - |
| dc.date.copyright | 2008-08-05 | |
| dc.date.issued | 2008 | |
| dc.date.submitted | 2008-07-29 | |
| dc.identifier.citation | [1] N. M. Amato, O. B. Bayazit, L. K. Dale, C. V. Jones, and D. Vallejo, “OBPRM: An Obstacle-Based PRM for 3D Workspaces,” in Workshop on Algorithmic Foundations of Robotics (WAFR), 1998.
[2] N. M. Amato and Y. Wu, “Randomized roadmap method for path and manipulation planning,” in IEEE International Conference on Robotics and Automation, Minneapolis, MN, USA, vol. 1, pp. 113-120, 1996. [3] A. Atramentov and S. M. LaValle, “Efficient nearest neighbor searching for motion planning,” in Robotics and Automation, 2002. Proceedings. ICRA '02. IEEE International Conference on, vol. 1, pp. 632-637, 2002. [4] J. v. d. Berg, “Path Planning in Dynamic Environments,” Information and Computing Sciences, Universiteit Utrecht, 2007. [5] J. v. d. Berg and M. Overmars, “Planning the Shortest Safe Path amidst Unpredictably Moving Obstacles,” in Proc. Workshop on Algorithmic Foundations of Robotics, 2006. [6] R. Bohlin and L. E. Kavraki, “Path planning using lazy PRM,” in Robotics and Automation, 2000. Proceedings. ICRA '00. IEEE International Conference on, vol. 1, pp. 521-528, 2000. [7] A. Bruce and G. Gordon, “Better Motion Prediction for People-Tracking,” in Proceedings of the IEEE International Conference on Robotics & Automation (ICRA), 2004. [8] J. Bruce and M. Veloso, “Real-time randomized path planning for robot navigation,” in Intelligent Robots and System, 2002. IEEE/RSJ International Conference on, vol. 3, pp. 2383-2388 vol.3, 2002. [9] J. Bruce and M. Veloso, “Real-time randomized path planning for robot navigation,” in Intelligent Robots and System, 2002. IEEE/RSJ International Conference on, vol. 3, pp. 2383-2388, 2002. [10] R. Buckingham, “Multi-arm robots,” Industrial Robot, vol. 23, pp. 16-20, 1996. [11] H. M. Choset, Principles of robot motion : theory, algorithms, and implementation. Cambridge, Mass.: MIT Press, 2005. [12] E. W. Dijkstra, “A Note on Two Problems in Connection with Graphs,” in Numerical Mathematics, pp. 269–271, 1959. [13] Z. Doulgeri and J. Peltekis, “Modeling and dual arm manipulation of a flexible object,” in Robotics and Automation, 2004. Proceedings. ICRA '04. 2004 IEEE International Conference on, vol. 2, pp. 1700-1705, 2004. [14] Y. Fei, D. Fuqiang, and Z. Xifang, “Collision-free motion planning of dual-arm reconfigurable robots,” Robotics and Computer-Integrated Manufacturing, vol. 20, pp. 351-357, 2004. [15] D. Ferguson, N. Kalra, and A. Stentz, “Replanning with RRTs,” in Robotics and Automation, 2006. ICRA 2006. Proceedings 2006 IEEE International Conference on, pp. 1243-1248, 2006. [16] R. Gayle, K. R. Klingler, and P. G. Xavier, “Lazy Reconfiguration Forest (LRF) - An Approach for Motion Planning with Multiple Tasks in Dynamic Environments,” in Robotics and Automation, 2007 IEEE International Conference on, pp. 1316-1323, 2007. [17] D. Gottlieb, “Robots and topology,” in Robotics and Automation. Proceedings. 1986 IEEE International Conference on, vol. 3, pp. 1689-1691, 1986. [18] S. Gottschalk, M. C. Lin, and D. Manocha, “OBB-Tree: A Hierarchical Structure for Rapid Interference Detection,” in ACM SIGGRAPH, pp. 171-180, 1996. [19] D. Hsu, R. Kindel, J.-C. Latombe, and S. Rock, “Randomized kinodynamic motion planning with moving obstacles,” International Journal of Robotics Research, vol. 21, pp. 233-255, 2002. [20] D. Hsu, J. Tingting, J. Reif, and A. Z. S. Zheng Sun, “The bridge test for sampling narrow passages with probabilistic roadmap planners,” in Robotics and Automation, 2003. Proceedings. ICRA '03. IEEE International Conference on, vol. 3, pp. 4420-4426, 2003. [21] L. Jaillet, A. Yershova, S. M. La Valle, and T. A. S. T. Simeon, “Adaptive tuning of the sampling domain for dynamic-domain RRTs,” in Intelligent Robots and Systems, 2005. (IROS 2005). 2005 IEEE/RSJ International Conference on, pp. 2851-2856, 2005. [22] M. Kalisiak and M. van de Panne, “Faster Motion Planning Using Learned Local Viability Models,” in Robotics and Automation, 2007 IEEE International Conference on, pp. 2700-2705, 2007. [23] M. Kalisiak and M. van de Panne, “RRT-blossom: RRT with a local flood-fill behavior,” in Robotics and Automation, 2006. ICRA 2006. Proceedings 2006 IEEE International Conference on, pp. 1237-1242, 2006. [24] M. Kallman and M. Mataric, “Motion planning using dynamic roadmaps,” in Robotics and Automation, 2004. Proceedings. ICRA '04. 2004 IEEE International Conference on, vol. 5, pp. 4399-4404, 2004. [25] L. E. Kavraki, P. Svestka, J.-C. Latombe, and M. H. Overmars, “Probabilistic roadmaps for path planning in high-dimensional configuration spaces,” IEEE Transactions on Robotics and Automation, vol. 12, pp. 566-580, 1996. [26] J. J. Kuffner, Jr. and S. M. LaValle, “RRT-connect: An efficient approach to single-query path planning,” in Robotics and Automation, 2000. Proceedings. ICRA '00. IEEE International Conference on, vol. 2, pp. 995-1001, 2000. [27] A. Lambert and D. Gruyer, “Safe path planning in an uncertain-configuration space,” in IEEE International Conference on Robotics and Automation, Taipei, Taiwan, vol. 3, pp. 4185-4190, 2003. [28] E. Larsen, S. Gottschalk, M. C. Lin, and D. Manocha, “Fast Proximity Queries with Swept Sphere Volumes,” in Robotics and Automation, Robotics and Automation, pp. 3719-3726, 2000. [29] J. C. Latombe, Robot Motion Planning: Kluwer Academic Publishers, 1991. [30] S. M. LaValle, “Planning Algorithms,” Cambridge Univ. Press, 2006. [31] S. M. LaValle, “Rapidly-Exploring Random Trees: A New Tool for Path Planning,” Technical Report, Computer Science Dept, Iowa State University, 1998. [32] S. M. LaValle and J. J. Kuffner, Jr., “Randomized kinodynamic planning,” in Robotics and Automation, 1999. Proceedings. 1999 IEEE International Conference on, vol. 1, pp. 473-479, 1999. [33] S. Lee, H. Moradi, and Y. Chunsik, “A real-time dual-arm collision avoidance algorithm for assembly,” in Assembly and Task Planning, 1997. ISATP 97., 1997 IEEE International Symposium on, pp. 7-12, 1997. [34] T.-Y. Li and Y.-C. Shie, “An incremental learning approach to motion planning with roadmap management,” Journal of Information Science and Engineering, vol. 23, pp. 525-538, 2007. [35] A. Liegeois, “Automatic Supervisory Control of the Configuration and Behavior of Multibody Mechanisms,” Systems, Man and Cybernetics, IEEE Transactions on, vol. 7, pp. 868-871, 1977. [36] M. Likhachev, G. Gordon, and S. Thrun, “ARA*: Anytime A* Search with Provable Bounds on Sub-Optimality,” in Proceedings of Conference on Neural Information Processing Systems (NIPS), 2003. [37] H. T. Lin, “Mechanical Design and Control of the Humanoid Robot Arm,” Master Thesis, Graduate Institute of Mechanical Engineering, National Taiwan University, 2006. [38] M. M. de Berg, M. O. Kreveld, and O. Schwarzkopf, Computational Geometry: Algorithms and Applications. Berlin: Springer, 1997. [39] N. A. Melchior and R. Simmons, “Particle RRT for Path Planning with Uncertainty,” in Robotics and Automation, 2007 IEEE International Conference on, pp. 1617-1624, 2007. [40] J. Miura, Y. Shirai, and N. Shimada, “Development of a Personal Service Robot with User-Friendly Interfaces,” in Field and Service Robotics, 2003, pp. 293-298. [41] D. M. Mount., “ANN programming manual,” Technical report, U. of Maryland 1998. [42] Y. Nakamura and H. Hanafusa, “Inverse Kinematics Solutions with Singularity Robustness for Robot Manipulator Control,” ASME Journal of Dynamic Systems, Measurement and Control, vol. 108, pp. 163-171, 1986. [43] S. J. Russell and P. Norvig, Artificial Intelligence: A Modern Approach, 2nd Edition ed.: Pearson Education, 2003. [44] D. Simon, Optimal State Estimation: Kalman, H-infinity, and Nonlinear Approaches: John Wiley & Sons, 2006. [45] R. C. Smith and P. Cheeseman, “On the representative and estimation of space uncertainty,” International Journal of Robotics Research, vol. 5, pp. 56-68, 1986. [46] R. F. Sproull, “Refinements to nearest-neighbor searching in k-dimensional trees,” Algorithmica (New York), vol. 6, pp. 579-589, 1991. [47] L. Tsai-Yen and S. Yang-Chuan, “An incremental learning approach to motion planning with roadmap management,” in Robotics and Automation, 2002. Proceedings. ICRA '02. IEEE International Conference on, vol. 4, pp. 3411-3416, 2002. [48] L. W. Tsai, The Mechanics of Serial and Parallel Manipulators. New York: John Wiley & Sons, 1999. [49] C. Urmson and R. Simmons, “Approaches for heuristically biasing RRT growth,” in Intelligent Robots and Systems, 2003. (IROS 2003). Proceedings. 2003 IEEE/RSJ International Conference on, vol. 2, pp. 1178-1183, 2003. [50] J. Van Den Berg, D. Ferguson, and J. Kuffner, “Anytime path planning and replanning in dynamic environments,” in IEEE International Conference on Robotics and Automation, Orlando, FL, United States, vol. 2006, pp. 2366-2371, 2006. [51] D. Vasquez, F. Large, T. Fraichard, and C. Laugier, “High-speed autonomous navigation with motion prediction for unknown moving obstacles,” in IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), Sendai, Japan, vol. 1, pp. 82-87, 2004. [52] G. Welch and G. Bishop, “An Introduction to the Kalman Filter,” University of North Carolina at Chapel Hill, 2001. [53] S. A. Wilmarth, N. M. Amato, and P. F. Stiller, “MAPRM: a probabilistic roadmap planner with sampling on the medial axis of the free space,” in Robotics and Automation, 1999. Proceedings. 1999 IEEE International Conference on, vol. 2, pp. 1024-1031, 1999. [54] M. Xie, “Fundamentals of Robotics: Linking Perception to Action,” in Machine Perception Artificial Intelligence: World Scientific, 2003. [55] H. C. Yen, “Path Planning for Mobile Robots in Dynamic Environments,” Master Thesis, Graduate Institute of Mechanical Engineering, National Taiwan University, 2007. [56] A. Yershova, L. Jaillet, T. Simeon, and S. M. LaValle, “Dynamic-Domain RRTs: Efficient Exploration by Controlling the Sampling Domain,” in Robotics and Automation, 2005. ICRA 2005. Proceedings of the 2005 IEEE International Conference on, pp. 3856-3861, 2005. [57] A. Yershova and S. M. LaValle, “Improving Motion-Planning Algorithms by Efficient Nearest-Neighbor Searching,” Robotics, IEEE Transactions on [see also Robotics and Automation, IEEE Transactions on], vol. 23, pp. 151-157, 2007. [58] H. Zghal, R. V. Dubey, and J. A. Euler, “Efficient gradient projection optimization for manipulators with multiple degrees of redundancy,” in Robotics and Automation, 1990. Proceedings., 1990 IEEE International Conference on, vol. 2, pp. 1006-1011, 1990. [59] M. Zucker, J. Kuffner, and M. Branicky, “Multipartite RRTs for Rapid Replanning in Dynamic Environments,” in Robotics and Automation, 2007 IEEE International Conference on, pp. 1603-1609, 2007. [60] M. Saha, P. Isto, and J.-C. Latombe, “Motion planning for robotic manipulation of deformable linear objects,” Springer Tracts in Advanced Robotics, vol. 39, pp. 23-32, 2008. [61] R. Katsuki, J. Ota, T. Mizuta, T. Kito, T. Arai, T. Ueyama, and T. Nishiyama, “Design of an artificial mark to determine 3D pose by monocular vision,” Taipei, Taiwan, vol. 1, pp. 995-1000, 2003. [62] K. Yamazaki, M. Tomono, T. Tsubouchi, and S. i. Yuta, “A grasp planning for picking up an unknown object for a mobile manipulator,” Orlando, FL, United States, vol. 2006, pp. 2143-2149, 2006. [63] wikipedia: Manhattan distance: http://en.wikipedia.org/wiki/Manhattan_distance [64] NewMat C++ Matrix Class: http://ideas.repec.org/c/cod/ccplus/newmat.html [65] NeHe Tutorials, OpenGL tutorials: http://nehe.gamedev.net/ [66] The Path Planning Problem: http://www.cs.cmu.edu/afs/cs/project/jair/pub/volume9/mazer98a-html/node2.html [67] OpenGL official website: http://www.opengl.org/ | |
| dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/9679 | - |
| dc.description.abstract | 本文主要的目的在設計與建立一個機器手臂的自動領導系統，使其能在大部分的環境中運作，例如在家庭中的廚房、工廠自動化…等等。此外我們還透過動態環境演算法來延伸成雙臂的路徑規劃，藉此強化機器人的工作效率。
首先在這篇論文中，我們提出一個關於在狀態空間的運動規劃演算法。它能克服一些困難的靜態環境的運動規劃的問題。由於是採用任意時間規劃(anytime planning)形式，所以在運算時間有限的時候還可以不斷的回傳部份運算完成的軌跡。此外Multi-RRTs 更是利用這項不斷重新規劃軌跡的特點來調整演算法的參數。 然後我們針對在動態環境的軌跡規劃的問題,提出一個CT-RRTs(Bi-direction RRTs in Configuration Time space)演算法，藉由此演算法能使的機械手臂能在部分已知的動態環境中成功的到達目標點。然而此演算法的是在不斷擴大的狀態-時間的空間中做規劃，其中機械手臂組態空間資訊以及移動物體的位置資訊都包含在狀態-時間的空間中。並且利用多種技術去加速規劃的時間以及增強它的安全性。最後我們利用CT-RRTs去發展雙臂的運動規劃，並且將運動規劃的問題推廣至更高階。 實驗部份分為模擬與實作。模擬部分建立一多功能的軟體平台，並且利用虛擬實境的方法來建造環境以及顯現模擬結果。在實作上，整合了影像系統以及馬達控制模組。整體系統可以在靜態環境中即時引導機械手臂。 | zh_TW |
| dc.description.abstract | The main objective of this thesis is to develop an autonomous navigation system for robot arms, which can operate in most of environments, such as kitchen, factory, etc. Furthermore, by extending our planner into a dual-arm planner, we can enhance the work efficiency of the robot.
To begin with, we propose an algorithm about motion planning in the state space. It can overcome some difficult planning problems in static environments. Due to the anytime planning fashion, the partial plan can also be returned when deliberation time is limited. Further, the Multi-RRTs algorithm uses this advantage of continuously re-planning to adjust the parameters. Next, in order to solve the problem of planning in the dynamic environments, we proposed a CT-RRTs (Bi-direction RRTs in Configuration Time space) planner, which can make the robot arm reach goal successfully in the partially known dynamic environment. However it plans in the augmented state-time space of robot arm configuration and the positions of moving objects. Various techniques are used to accelerate planning and enhance its safety. Finally, we utilize the new planner to develop the dual-arm planner, and it can be used as the basis to solve higher level problems in motion planning. A software platform is developed for both simulation and for real-world navigation, where environment and planning results are visualized in 3D. In real-world implementation, a vision module for distance measurement and a motor control module are integrated. In our experiments, the system is able to navigate the robot arm in static environments in real time. | en |
| dc.description.provenance | Made available in DSpace on 2021-05-20T20:35:10Z (GMT). No. of bitstreams: 1 ntu-97-R95522805-1.pdf: 7118699 bytes, checksum: db98f55bde7fae1ccaa9cde57caeafcc (MD5) Previous issue date: 2008 | en |
| dc.description.tableofcontents | 致謝 ii
List of Tables viii List of Figures ix Chapter 1 Introduction 1 1.1 Motivation 1 1.2 Objectives and Contributions 3 1.3 Thesis Organization 5 Chapter 2 Background Knowledge and Relevant Research 7 2.1 Kinematics Analysis 7 2.1.1 Forward Kinematics 8 2.1.2 Inverse Kinematics 9 2.1.3 Singularity Avoidance 10 2.1.4 Joint Limit Avoidance 11 2.2 Planning as a Search Problem 12 2.2.1 Basic Search Strategies 13 2.2.2 Heuristic Search 14 2.2.3 Bidirectional and Multi-Directional Search 16 2.3 Path Planning Problems to Search Problems 17 2.3.1 The Configuration Space 17 2.3.2 Distance Metric 19 2.4 Randomized Path Planning 20 2.4.1 Probabilistic Roadmap 21 2.4.2 Rapidly-Exploring Random Tree 22 Chapter 3 Planning in the State Space 23 3.1 Planning with RRT 24 3.1.1 Basic RRT Planner 24 3.1.2 RRT-Connect and Bi-direction RRT 26 3.2 Random Configuration 27 3.2.1 Dynamic Domain RRT 27 3.3 Nearest-Neighbor Searching 30 3.3.1 K-Dimension tree 31 3.3.2 MPNN 32 3.3.3 Hybrid Nearest-Neighbor Search 34 3.3.4 Summary 37 3.4 Planning in the Dynamic Environments 38 3.4.1 LRF (Lazy Reconfiguration Forest) 38 3.4.2 Dynamic Obstacle Prediction 41 3.5 The Framework of Multi-RRTs 44 Chapter 4 Planning in the State-Time Space 46 4.1 Configuration-Time Space 47 4.2 Modifications of Bi-directions RRTs 48 4.2.1 Inserting Time Information 48 4.2.2 Inserting Cost function 52 4.2.3 Re-planning 56 4.3 Anytime Planning 59 4.4 The Framework of CT-RRTs 60 Chapter 5 Motion planning for Dual-Arm 64 5.1 Based on Multi-RRTs 65 5.2 Based on CT-RRTs 67 Chapter 6 Implementation and Experimental Results 69 6.1 Software Platform 69 6.2 Hardware Platform 72 6.2.1 Humanoid Robot Arm 72 6.2.2 Control modules 73 6.3 Experiment Results 75 6.3.1 “Strict Static-Environment” Scenario 75 6.3.2 “Moving Objects” Scenario 78 6.3.3 “Dual-Arm planning” Scenario 80 6.3.4 “Transport an Object in the Clutter Environment” Scenario 82 6.3.5 Integration on a Real-World Robot 84 Chapter 7 Conclusions and Future Works 86 7.1 Conclusions 86 7.2 Future Works 87 References 89 | |
| dc.language.iso | en | |
| dc.title | 雙臂行動式機器人在複雜環境之路徑規劃 | zh_TW |
| dc.title | Motion Planning of a Dual-Arm Mobile Robot in Complex Environments | en |
| dc.type | Thesis | |
| dc.date.schoolyear | 96-2 | |
| dc.description.degree | 碩士 | |
| dc.contributor.oralexamcommittee | 李蔡彥(Tsai-Yen Li),王傑智(Chieh-Chih Wang) | |
| dc.subject.keyword | 路徑規劃,軌跡規劃,運動規劃,雙臂式機器人, | zh_TW |
| dc.subject.keyword | path planning,planning,motion planning,RRT,CT-RRTs,manipulator, | en |
| dc.relation.page | 113 | |
| dc.rights.note | 同意授權(全球公開) | |
| dc.date.accepted | 2008-07-30 | |
| dc.contributor.author-college | 工學院 | zh_TW |
| dc.contributor.author-dept | 機械工程學研究所 | zh_TW |
| 顯示於系所單位： | 機械工程學系 | |
文件中的檔案：
| 檔案 | 大小 | 格式 | |
|---|---|---|---|
| ntu-97-1.pdf | 6.95 MB | Adobe PDF | 檢視/開啟 |
系統中的文件，除了特別指名其著作權條款之外，均受到著作權保護，並且保留所有的權利。