研究生: |
洪誠鋒 Cheng-Feng Hung |
---|---|
論文名稱: |
自我學習蟻群演算法以及在機器人最佳路徑規劃之應用 Study of Self-Learning Ant Colony Optimization with Application to Optimal Robot Path Planning |
指導教授: |
徐勝均
Sendren Sheng-Dong Xu |
口試委員: |
李俊賢
Jin-Shyan Lee 周宏隆 Hung-Lung Chou 胡念祖 none |
學位類別: |
碩士 Master |
系所名稱: |
工程學院 - 自動化及控制研究所 Graduate Institute of Automation and Control |
論文出版年: | 2014 |
畢業學年度: | 102 |
語文別: | 中文 |
論文頁數: | 72 |
中文關鍵詞: | 移動機器人 、路徑規劃 、蟻群演算法 、導航 、柵格法 |
外文關鍵詞: | ant colony optimization, navigation, mobile robot, grid map, path planning |
相關次數: | 點閱:557 下載:2 |
分享至: |
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報 |
本論文提出自我學習蟻群演算法的觀念,並應用於機器人最佳路徑規劃。本方法包含局部費洛蒙更新、螞蟻歸巢法與自我學習費洛蒙更新機制;自我學習費洛蒙更新機制包含了階段式費洛蒙更新機制與自我學習階段選擇機制。當陷入搜索停滯時,這方法能夠使系統自動的切換至新的更新方式以提升搜索效率。同時透過局部費洛更新機制改良禁忌表所產生的鎖死問題,並使用螞蟻歸巢法初步排除冗餘路徑。相較於蟻群系統(ACS)與改良式蟻群系統(IACS),模擬結果證實本文提出的方法於最短路徑長、平均路徑常和最佳路徑成功率皆有較好的表現。
This thesis proposes the concept of Self-Learning Ant Colony Optimization (SLACO), and applies it to the optimal robot path planning. Therein, SLACO includes Partial Pheromone Updating, Ant Homing Method and Self-Learning Pheromone Updating Mechanism (SLPUM). SLPUM includes a phased pheromone updating mechanism and a self-learning stage selection mechanism. When the search stagnation happened, this method allows the system switch automatically to new updated mechanism to improve search efficiency. The other improvements are the strengthening of the Partial Pheromone update algorithm to improve issues arising from the deadlock problems in the taboo table, as well as homing method reduces redundant path preliminarily. Simulation results show the proposed approach has a better performance in terms of shortest distance, mean distance, and successful rate of the optimal paths than those obtained by the Ant Colony System and Improved Ant Colony System.
[1] “ASIMO,” http://world.honda.com/ASIMO/
[2] “Partner Robot,” http://www.toyota-global.com/innovation/partner_robot/
[3] “Robots Scour WTC Wreckage,” http://goo.gl/vp27s3
[4] “BigDog,” http://www.bostondynamics.com/robot_bigdog.html
[5] “Intuitive Surgical,” http://www.intuitivesurgical.com/
[6] H. Wang and K. Kosuge, “Control of a robot dancer for enhancing haptic human-robot interaction in waltz,“ IEEE Transactions on Haptics, vol. 5, no. 3, pp. 264-273, 2012.
[7] S. X. Yang, A. Zhu, G. Yuan, and M. Q. H. Meng, “A bioinspired neurodynamics-based approach to tracking control of mobile robots,“ IEEE Transactions on Industrial Electronics, vol. 59, no. 8, pp. 3211-3220, 2012.
[8] N. R. Ahmed, E. M. Sample, and M. Campbell, “Bayesian multicategorical soft data fusion for human-robot collaboration,” IEEE Transactions on Robotics, vol. 29, no. 1, pp. 189-206, 2013.
[9] J. P. Ferreira, M. M. Crisostomo, and A. P. Coimbra, “Adaptive PD controller modeled via support vector regression for a biped robot,” IEEE Transactions on Control Systems Technology, vol. 21, no. 3, pp. 941-949, 2013.
[10] Z. Hao, C. Reardon, and L. E. Parker, “Real-time multiple human perception with color-depth cameras on a mobile robot,” IEEE Transactions on Cybernetics, vol. 43, no. 5, pp. 1429-1441, 2013.
[11] K.-W. Kwok, K. H. Tsoi, V. Vitiello, J. Clark, G. C. T. Chow, W. Luk, and G.-Z. Yang, "Dimensionality reduction in controlling articulated snake robot for endoscopy under dynamic active constraints," IEEE Transactions on Robotics, vol. 29, no. 1, pp. 15-31, 2013.
[12] K. H. Cho, H. M. Kim, Y. H. Jin, F. Liu, H. Moon, J. C. Koo, and H. R. Choi, "Inspection robot for hanger cable of suspension bridge: mechanism design and analysis," IEEE/ASME Transactions on Mechatronics, vol. 18, no. 6, pp. 1665-1674, 2013.
[13] P. Rouanet, P. Y. Oudeyer, F. Danieau, and D. Filliat, “The impact of human-robot interfaces on the learning of visual objects,” IEEE Transactions on Robotics, vol. 29, no. 2, pp. 525-541, 2013.
[14] C. Sumin and J. Sungho, “Incremental online learning of robot behaviors from selected multiple kinesthetic teaching trials,” IEEE Transactions on Systems, Man, and Cybernetics: Systems, vol. 43, no. 3, pp. 730-740, 2013.
[15] Y. Guan, H. Zhu, W. Wu, X. Zhou, L. Jiang, C. Cai, L. Zhang, and H. Zhang, “A modular biped wall-climbing robot with high mobility and manipulating function,” IEEE/ASME Transactions on Mechatronics, vol. 18, no. 6, pp. 1787-1798, 2013.
[16] Y. Hu and S. X. Yang, “A knowledge based genetic algorithm for path planning of a mobile robot,” IEEE International Conference on Robotics and Automation (ICRA), vol. 5, Barcelona, Spain, April 26-May 1, 2004, pp. 4350-4355.
[17] Z. Zhou, Y. Nie, and M. Gao, “Enhanced ant colony optimization algorithm for global path planning of mobile robots,” International Conference on Computational and Information Sciences (ICCIS), Shiyang, China, June 21-23, 2013, pp. 698-701.
[18] G. Zhang and H. Jia, “3D path planning of AUV based on improved ant colony optimization,” Chinese Control Conference (CCC), Xi'an, China, July 26-28, 2013, pp. 5017-5022.
[19] Y. He, Q. Zeng, J. Liu, G. Xu, and X. Deng, “Path planning for indoor UAV based on Ant Colony Optimization,” Chinese Control and Decision Conference (CCDC), Guiyang, May 25-27, 2013, pp. 2919-2923.
[20] Y. Zhang, Y. Cao, and Z. Han, “Path planning of vehicle based on improved ant colony algorithm,” International Conference on Modelling, Identification & Control (ICMIC), Wuhan, Hubei, China, June 24-26, 2012, pp. 797-801.
[21] Z. Zhu, S. R. Liu, and B. T. Zhang, “Global path planning of mobile robot based on improved ant colony algorithm,” Chinese Control Conference (CCC), Yantai, July 22-24, 2011, pp. 4083-4088.
[22] Q. Han, Q. Wang, X. Zhu, and J. Xu, “Path planning of mobile robot based on improved ant colony algorithm,” International Conference on Consumer Electronics, Communications and Networks (CECNet 2011), Xian'Ning, China, April 16-18, 2011, pp. 531-533.
[23] Y. Shen, M. Yuan, and Y. Bu, “Study on adaptive planning strategy using ant colony algorithm based on predictive learning,” Chinese Control and Decision Conference (CCDC), Guilin, China, June 17-19, 2009, pp. 3030-3035.
[24] J. W. Lee, J. J. Kim, and J. J. Lee, “Improved ant colony optimization algorithm by path crossover for optimal path planning,” IEEE International Symposium on Industrial Electronics (IEEE ISIE 2009), Seoul, July 5-8, 2009, pp. 1996-2000.
[25] J. W. Lee, J. J. Kim, B. S. Choi, and J. J. Lee, “Improved Ant Colony Optimization algorithm by potential field concept for optimal path planning,” IEEE-RAS International Conference on Humanoid Robots (Humanoids 2008), Daejeon, Dec. 1-3, 2008, pp. 662-667.
[26] Y. Peng, Z. Wang, J. Jin, P. Huang, and W. Lu, “The global trajectory programming of robot based on adaptive ant colony algorithm,” International Conference on Intelligent Human-Machine Systems and Cybernetics (IHMSC), vol. 1, Hangzhou, China, Aug. 26-27, 2013, pp. 108-111.
[27] Y. Liu, W. Zhang, G. Li, and J. Shi, “UAV path planning in dynamic environment,” Chinese Control Conference (CCC), Xi'an, China, July 26-28, 2013, pp. 4894-4897.
[28] N. Ganganath and C. T. Cheng, “A 2-dimensional ACO-based path planner for Off-Line robot path planning,” International Conference on Cyber-Enabled Distributed Computing and Knowledge Discovery (CyberC), Beijing, China, Oct. 10-12, 2013, pp. 302-307.
[29] C. C. Hsu, R. Y. Hou, and W. Y. Wang, “Path planning for mobile robots based on improved ant colony optimization,” 2013 IEEE International Conference on Systems, Man, and Cybernetics (SMC), Manchester, Oct. 13-16, 2013, pp. 2777-2782.
[30] J. Kou, S. Xiong, Z. Fang, X. Zong, and F. Bian, “Positive point charge potential field based ACO algorithm for multi-objective evacuation routing optimization problem,” 2012 IEEE Congress on Evolutionary Computation (CEC), Brisbane, QLD, June 10-15, 2012, pp. 1-8.
[31] Y. Zhang, L. Wu, and S. Wang, “UCAV path planning by fitness-scaling adaptive chaotic particle swarm optimization,” Mathematical Problems in Engineering, vol. 2013, 2013.
[32] M. Pedemonte, S. Nesmachnow, and H. Cancela, “A survey on parallel ant colony optimization,” Applied Soft Computing Journal, vol. 11, no. 8, pp. 5181-5197, 2011.
[33] C. H. Hsu and C. F. Juang, “Multi-objective continuous-ant-colony- optimized FC for robot wall-following control,” IEEE Computational Intelligence Magazine, vol. 8, no. 3, pp. 28-40, 2013.
[34] H. C. Huang, “SoPC-based parallel ACO algorithm and its application to optimal motion controller design for intelligent omnidirectional mobile robots,” IEEE Transactions on Industrial Informatics, vol. 9, no. 4, pp. 1828-1835, 2013.
[35] F. Gonzalez Bulnes, R. Usamentiaga, D. Fernando Garcia, and J. Molleda, “A Parallel Genetic Algorithm for Optimizing an Industrial Inspection System,” IEEE Latin America Transactions, vol. 11, no. 6, pp. 1338-1343, 2013.
[36] L. Kawecki and T. Niewierowicz, “Hybrid genetic algorithm to solve the two point boundary value problem in the optimal control of induction motors,” IEEE Latin America Transactions, vol. 12, no. 2, pp. 176-181, 2014.
[37] Q. Ma and X. Lei, “Application of improved particle swarm optimization algorithm in ucav path planning,” International Conference on Artificial Intelligence and Computational Intelligence (AICI), vol. 5855, Shanghai, China, Nov. 7-8, 2009, pp. 206-214.
[38] A. Soroudi and M. Afrasiab, “Binary PSO-based dynamic multi-objective model for distributed generation planning under uncertainty,” IET Renewable Power Generation, vol. 6, no. 2, pp. 67-78, 2012.
[39] H. Duan, X. Wei, and Z. Dong, “Multiple UCAVs cooperative air combat simulation platform based on PSO, ACO, and game theory,” IEEE Aerospace and Electronic Systems Magazine, vol. 28, no. 11, pp. 12-19, 2013.
[40] J. Yin, Y. Wang, and J. Hu, “A new dimensionality reduction algorithm for hyperspectral image using evolutionary strategy,” IEEE Transactions on Industrial Informatics, vol. 8, no. 4, pp. 935-943, 2012.
[41] T. Jing and C. Li, “Image noise estimation using a variation-adaptive evolutionary approach,” IEEE Signal Processing Letters, vol. 19, no. 7, pp. 395-398, 2012.
[42] B. Zhang, J. Gao, L. Gao, and X. Sun, “Improvements in the ant colony optimization algorithm for endmember extraction from hyperspectral images,” IEEE Journal of Selected Topics in Applied Earth Observations and Remote Sensing, vol. 6, no. 2, pp. 522-530, 2013.
[43] J. Liang, X. Liu, K. Huang, X. Li, D. Wang, and X. Wang, “Automatic registration of multisensor images using an integrated spatial and mutual information (SMI) metric,” IEEE Transactions on Geoscience and Remote Sensing, vol. 52, no. 1, pp. 603-615, 2014.
[44] S. Guo, H. Z. Huang, Z. Wang, and M. Xie, “Grid service reliability modeling and optimal task scheduling considering fault recovery,” IEEE Transactions on Reliability, vol. 60, no. 1, pp. 263-274, 2011.
[45] J. W. Lee and L. Ju Jang, “Ant-colony-based scheduling algorithm for energy-efficient coverage of WSN,” IEEE Sensors Journal, vol. 12, no. 10, pp. 3036-3046, 2012.
[46] G. Wu, M. Ma, J. Zhu, and D. Qiu, “Multi-satellite observation integrated scheduling method oriented to emergency tasks and common tasks,” Journal of Systems Engineering and Electronics, vol. 23, no. 5, pp. 723-733, 2012.
[47] W. N. Chen and J. Zhang, “Ant colony optimization for software project scheduling and staffing with an event-based scheduler,” IEEE Transactions on Software Engineering, vol. 39, no. 1, pp. 1-17, 2013.
[48] J. B. Wang, M. Chen, X. Wan, and C. Wei, “Ant-colony-optimization-based scheduling algorithm for uplink CDMA nonreal-time data,” IEEE Transactions on Vehicular Technology, vol. 58, no. 1, pp. 231-241, 2009.
[49] M. Dorigo, V. Maniezzo, and A. Colorni, “Ant system: optimization by a colony of cooperating agents,” IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics, vol. 26, no. 1, pp. 29-41, 1996.
[50] M. Dorigo and L. M. Gambardella, “Ant colonies for the travelling salesman problem,” Biosystems, vol. 43, no. 2, pp. 73-81, 1997.