臺灣博碩士論文加值系統

本篇論文提出一個階層式的路徑規劃演算法，來規劃出一序列性的機械手臂移動軌跡。所提出的階層式路徑規劃演算法先以空間切割方式找出機械手臂的移動軌跡，再以瀰集進化演算法為基礎作為機械手臂移動規劃之全域搜尋方法，搜尋出區域的最佳化機械手臂組態，且採用簡易位能場模型作為區域搜尋方法，細部調整手臂姿態，來加速機械手臂最佳組態的演化，以達到完全避碰效果。不同以往的路徑規劃演算法需要大量的計算來建構組態空間，本篇論文所提出的演算法直接使用工作空間的場景資訊，並且搜尋的效率也較以往的路徑規劃演算法更能適用於高自由度的機械手臂。由實驗證明，本篇論文所提出的方法能在短時間內將高自由度的機械手臂路徑規劃出來，且路徑具有高安全性。

In this thesis, an heirarchical algorithm is proposed for path planning of manipulators. The proposed algorithm consists of a global planner and a local planner. The cell-decomposition approach is adopted as the former to plan a trajectory for robot end-effector. The Memetic algorithm with local search is adopted to plan the local motion of the manipulator. The local search procedure reduces the search space and speedups the evolution significantly. In this thesis, the local research is implemented by a potential minimization algorithm. The algorithm locally adjusts the robot configuration to search for minimum potential configurations using the repulsive force between manipulator and obstacles. Simulation results show that the proposed algorithm works well, in terms of collision avoidance and computation efficiency.

摘要 I
ABSTRACT II
目錄 IV
表目錄 V
圖目錄 VI
1. 緒論 1
1.1. 研究背景與動機 1
1.2. 研究目的 2
1.3. 論文結構 3
2. 機械手臂路徑規劃相關研究 4
2.1. 組態空間的作法 4
2.2. 工作空間的作法 6
2.2.1. 位能場方法 6
2.2.2. 細胞切割規劃法 7
2.3. 其他相關作法 8
3. 階層式路徑規劃演算法 11
3.1. 全域路徑規劃法 12
3.2. 區域路徑規劃法 15
3.2.1. 全域搜尋法 17
3.2.2. 區域搜尋法 21
4. 實驗結果 24
4.1. 實驗結果與分析 24
4.1.1. 階層式路徑規劃結果 24
4.1.2. 演化收斂速率比較 28
整體組態移動軌跡平順度比較 30
5. 結論 32
參考文獻 33

[1]ABB Website，http://www.abb.com.tw/.
[2]Intuitive Surgical, Inc，http://www.intuitivesurgical.com/index.aspx.
[3]J. H. Reif, "Complexity of the mover's problem and generalizations", Proceedings of foundations of Computer Science, pp. 421-427, 1979.
[4]T. Lozano-Perez and M. A. Wesley, “An Algorithm for planning collision-Free paths among polyhedral obstacles,” Communications of the ACM, vol. 22, pp. 560-570, 1979.
[5]T. Loza no-Perez, “Spatial Planning : a configuration space approach,” IEEE Transactions on Computers, vol. C-32, pp. 108-120, 1983.
[6]L. E. Kavraki, P. Svestka, J. C. Latombe, and M. H. Overmars, “Probabilistic Roadmap for path planning in high-dimensional configuration spaces,” IEEE Transactions on Robotics & Automation, vol. 12, no. 4, pp. 566-580, 1996.
[7]T. Lozano-Perez, “A simple motion-planning algorithm for general robot manipulator,” IEEE Journal of Robotics and Automation, vol.3, no.3, pp.224-238, 1987.
[8]S. M. LaValle, “Rapidly-exploring random tree: A new tool for path planning,” Technology Report, no. 98-11, 1998.
[9]J. J. Kuffner and S. M. LaValle, “RRT-connect: An efficient approach to single-query path planning,” Proceedings of. IEEE International Conference on Robotics and Automation, pp. 995-1001, 2000.
[10]T. Laliberte and C. Gosselin, “Efficient algorithms for the trajectory planning for redundant manipulators with obstacle avoidance,” Proceedings of IEEE International Conference on Robotics and Automation, vol. 3, pp.2044-2049, 1994.
[11]E. Ralli and G. Hirzinger, “Fast path planning for robot manipulators using numerical potential fields in the configuration space,” Proceedings of the IEEE/RSJ/GI Intl. Conf. on Intelligent Robots and Systems, Advanced Robotic System and the Real World, vol. 3, pp. 1922-1929, 1994.
[12]J. Barraquand and J. C. Lotombe, “Robot motion planning: a distributed representation approach,” International Journal of Robotics Research, vol. 10, no. 6, pp. 628-649, 1991.
[13]O. Khatib, “Real-time obstacle avoidance for manipulators and mobile robots,” International Journal of Robotics Research, vol. 5, no. 1, pp. 90-98, 1986.
[14]J. C. Latombe, “Motion planning : A journey of robots, molecules, digital actors, and other artifacts,” International Journal of Robotics Research, vol. 18, no. 11, pp. 1119-1128, 1999.
[15]J. Barraquand, B. Langois, and J. C. Latombe, “Numerical potential field techniques for robot path planning,” IEEE Transactions on Robotics and Automation, vol. 22, pp. 224-241, 1992.
[16]A. A. Masoud, M. M. Bayoumi, “Intercepting a maneuvering target in a multidimensional stationary environment using a ware equation potential field strategy”, IEEE International Symposium on Intelligent Control, pp. 243-248, 1994.
[17]Jen-Hui Chuang, Chien-Chou Lin and Cheng-Tieng Hsieh, "A Potential-Based Path Planning of Articulated Robots with 2-DOF joints", Proceedings of the IEEE International Conference on Robotics and Automation, pp. 1827-1832, 2005.
[18]Chien-Chou Lin, Chi-Chun Pan and Jen-Hui Chuang, "A Novel Potential-Based Path Planning of 3-D Articulated Robots with Moving Bases", Robotica, vol. 22, no. 4, pp. 359-367, 2004.
[19]Jen-Hui Chuang, Chien-Chou Lin and Lo-Wei Kuo, "Potential-Based Path Planning for Robot Manipulators", Proceeding of IEEE International Conference on Method and Models in Automation and Robotics, pp. 1031-1036, 2002.
[20]Chien-Chou Lin and Jen-Hui Chuang, "Potential-Based Path Planning for Robot Manipulators in 3D Workspace", Proceedings of. IEEE International Conference on Robotic and Automation, vol. 3, pp. 3353-3358, 2003.
[21]Chien-Chou Lin, Chi-Chun Pan and Jen-Hui Chuang, "A Novel Potential-Based Path Planning of 3-D Articulated Robots with Moving Bases", Proceedings of. IEEE International Conference on Robotic and Automation, pp. 3365-3370, 2004.
[22]J. H. Chuang, "Potential-Based Modeling of Three-Dimensional Workspace for Obstacle Avoidance", IEEE Transactions on Robotics and Automation, vol. 14, no. 5, pp. 778-785, 1998.
[23]R. Brooks and T. Lozano-Perez, “A subdivision algorithm in configuration space for findpath with rotation,” IEEE Transcations on System, Man & Cybernetics, vol. 15, no. 2, pp. 224-233, 1985.
[24]O. Aron, T. Lozano-Perez, “Visible Decomposition: Real-Time path Planning in Large Planar Environments,” AI Memo 1638, 1996.
[25]E. J. Solterio Pires and J. A. Tenrerio Machado, “A trajectory planner for manipulators using genetic algorithm,” Proceedings of the IEEE International Symposium on Assembly and task planning, pp. 163-168, 1999.
[26]Parker, J., K., Khoogar, A., R., and Goldberg, D., E., "Inverse Kinematics of redundant robots using genetic algorithms", Proceedings of IEEE International Conference on Robotics and Automation, pp. 271-276, 1989.
[27]Khoogar, A., R. and Parker, J., K., "Obstacle avoidance of redundant manipulators using genetic algorithms", Proceedings of IEEE International Conference on Robotic and Automation, pp. 317-320, 1991.
[28]Huahua Chen, Xin Du, WeiKang Gu, “Global Path Planning Based on Neural Network and Genetic Algorithm in a Static Environment,” Artificial Neural Networks, pp. 34-42, 2004.
[29]M. Gill and A. Zomaya, "A parallel collision-avoidance algorithm for robot manipulators", IEEE Concurrency, vol. 6, no. 1, pp.68-78, 1998.
[30]Habib, M.K. and Asama, H., “Efficient method to generate collision Free paths for an autonomous mobile robot based on new Free space structuring approach”, Proceedings of IEEE/RSJ International Workshop on Intelligent Robots and Systems, vol. 2, pp. 563-567, 1991.
[31]Moscato, P., “On evolution, search, optimization, genetic algorithms and martial arts：Towards memetic algorithms,” Technology Report, 1989.
[32]L. E. Kavraki, P. Svestka and et al, “Probabilistic roadmaps for path planning in high-dimensional configuration spaces,” IEEE Transaction on Robotics and Automation, vol. 12, pp. 566-580, 1996.
[33]T. Lozano-Perez and M. A. Wesley, “An algorithm for planning collision-Free paths among polyhedral obstacles.” Communications of the ACM, vol. 22, pp. 560-570, 1979.
[34]T. Laliberte and C. Gosselin, “Efficient algorithms for the trajectory planning for redundant manipulators with obstacle avoidance.” Proceedings of IEEE International Conference on Robotic and Automation, pp. 2044-2049, 1994.
[35]Chien-Chou Lin, Lo-Wei Kuo and Jen-Hui Chuang, "Potential-Based Path Planning for Robot Manipulators", Journal of Robotic Systems, vol. 22, no. 6, pp. 313-322, 2005.