臺灣博碩士論文加值系統

本論文是提出移動式機器人在複雜的環境下,使用人工免疫演算法(artificial immune algorithm)並結合A*演算法(A* algorithm)的改良型類免疫演算法來控制移動式機器人閃避障礙物並找尋目標物.當動態障礙物接近移動式機器人時,即時由人工免疫演算法來作出閃躲障礙物的動作,並且由A*演算法來找尋移動式機器人到達目標的最佳路徑.由人工免疫演算法來彌補A*演算法在遇到移動式障礙物時,無法搜尋出最短路徑的缺點,也由A*演算法來彌補人工免疫演算法在閃躲障礙物之後行走多餘路徑的缺點,讓移動式機器人能夠安全無碰撞障礙物的情況下,以最快最佳的路徑到達目標.最後經由Matlab撰寫程式來使用電腦模擬結果得知,使用改良型類免疫演算法對於移動式機器人閃躲障礙物且搜尋目標物確實能有效減少消耗時間與步數而達到不錯的效果.

In this study, the Improved Artificial Immune Algorithm is combined of Artificial Immune Algorithm with A* Algorithm. When obstacle will comes closing to mobile robot, immediately use of artificial immune algorithm to dodge the obstacle and path planning for A* Algorithm. The mobile robot can reach the goal in complex environment. This study proposes a safe navigation scheme to reduce the risk of collision due to unexpected dynamic obstacles. Finally, uses simulation to prove that can perform kinds of Improved Artificial Immune Algorithm effective avoiding obstacle and capturing target.

摘 要 i
Abstract ii
誌謝 iii
目錄 iv
表目錄 vi
圖目錄 vii
第一章 緒論 1
1.1 前言 1
1.2 研究動機與目的 1
1.3 文獻探討 4
1.3.1 基因演算法相關文獻探討 4
1.3.2 A*演算法相關文獻探討 4
1.3.3 人工免疫演算法相關文獻探討 5
1.4 論文架構 5
第二章 基因演算法 7
2.1 前言 7
2.2 基因演算法之演化過程 7
2.2.1 初始群體 8
2.2.2 編碼 8
2.2.3 適應函數 9
2.2.4 複製 9
2.2.5 交配 10
2.2.6 突變 12
2.2.7 結束演化 12
2.3 Tu基因演算法文獻探討 12
2.3.1 訂定理想染色體長度 13
2.3.2 染色體與基因編碼的方式 13
2.3.3 適應函數設計 14
2.3.4 相關參數設定 14
2.4基因演算法之模擬 15
2.5 本章結論 15
第三章 人工免疫演算法 17
3.1 前言 17
3.2 人工免疫演算法基本理論 17
3.2.1 生物免疫系統 17
3.2.2 人工免疫演算法設計與流程 19
3.2.3 獨特型網路假說 21
3.3 Ishiguro文獻之人工免疫演算法理論 22
3.3.1 人工免疫演算法數學模型 23
3.3.2 人工免疫演算法之模擬結果 26
3.4本章結論 27
第四章 A*搜尋演算法 28
4.1 前言 28
4.2 A*演算法基本理論 28
4.2.1 A*演算法搜尋 29
4.3 A*演算法模擬 33
4.4 安全間距設定 34
4.4.1 增加安全間距之模擬 35
4.5 本章結論 36
第五章 改良型類免疫演算法 37
5.1 前言 37
5.2 移動式機器人控制設計 38
5.3 改良型類免疫演算法控制流程 40
5.4 速度障礙設計 42
5.5 改良型類免疫演算法模擬 44
5.6 本章結論 46
第六章 模擬結果分析與探討 47
6.1 前言 47
6.2 靜態環境之模擬 47
6.3 全動態環境之模擬 52
6.4 動態與靜態混合環境之模擬 56
6.5 本章結論 62
第七章 結論與未來展望 63
7.1 結論 63
7.2 未來展望 64
參考文獻 65

[1]Pimenta, L.C.A., A.R. Fonseca, G.A.S. Pereira, R.C.Mesquita, E.J. Silva, W.M. Caminhas, M.F.M. Campos, “Robot navigation based on electrostatic field computation, ”Magnetics, IEEE Transactions on, Vol. 42, Issue 4, pp. 1459-1462, April 2006.
[2]Willms, A.R., S.X. Yang, “An efficient dynamic system for real-time robot-path planning, ”Systems, Man and Cybernetics, Part B, IEEE Transactions on, Vol. 36, Issue 4, pp. 755-766, Aug. 2006.
[3]Ishiguro, A., R. Watanabe, and Y. Uchikawa, “Animmunological approach to dynamic behavior control for autonomous mobile robots,” Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems, Vol.1, pp. 495-500, Aug.1995.
[4]Jerne, N. K., “Idiotypic networks and other preconceived ideas,” Immunological Rev., Vol.79, pp. 5-24, 1984.
[5]Jerne, N. K., “The immune system,” Scientific American, Vol. 229. No.1, pp. 52-60, 1973.
[6]Hart, P. E.; Nilsson, N. J.; Raphael, B. “A Formal Basis for the Heuristic Determination of Minimum Cost Paths”. IEEE Transactions on Systems Science and Cybernetics SSC4 (2): 100–107. doi:10.1109 / TSSC.1986.
[7]Cho, Y. J.; Hong, J. P.; Park, K. W. “Obstacle avoidance using active window and flexible vector field with a laser range finder” Control, Automation and Systems. ICCAS '07. International Conference on: 17-20 Oct. 2007 Page(s):2123 - 2128 Digital Object Identifier 10.1109/ICCAS.2007.
[8]Maxim Likhachev, David Ferguson, Geoffrey Gordon, Anthony (Tony) Stentz and Sebastian Thrun, “Anytime dynamic A*: an anytime, replanning algorithm.” Proceedings of the International Conference on Automated Planning and Scheduling (ICAPS), June, 2005.
[9]Kubota, N., T. Morioka, and F. Kojima, T. Fukuda, “Learning of mobile robots using perception-based genetic algorithm,” Measurement: Journal of the International Measurement Confederation, vol. 29, pp. 237-248, Apr. 2001.
[10]Tu, J., S.X. Yang, “Genetic algorithm based path planning for a mobile robot,” Robotics and Automation, 2003. Proceedings. ICRA '03. IEEE International Conference on, Vol. 1, pp. 1221-1226, 14-19 Sept. 2003.
[11]Han, W.-G., S.-M. Baek, T.-Y. Kuc, “GA based online path planning of mobile robots playing soccer games,” Circuits and Systems, 1997. Proceedings of the 40th Midwest Symposium on, Vol. 1, pp. 522-525, 3-6 Aug. 1997.
[12]Han, W.-G., S.-M. Baek, T.-Y. Kuc, “Genetic algorithm based path planning and dynamic obstacle avoidance of mobile robots,” Systems, Man, and Cybernetics, 1997. 'Computational Cybernetics and Simulation', 1997 IEEE International Conference on, Vol. 3, pp. 2747-2751, 12-15 Oct. 1997.
[13]Kim, S. H., C. Park, F. Harashima,“A self-organized fuzzy controller for wheeled mobile robot by using an evolutionary algorithm,”Industrial Electronics, IEEE Transactions on, Vol. 48, Issue 2, pp. 467-474,April 2001
[14]Wang, C., Y.C. Soh, H. Wang, H. Wang, “A hierarchical genetic algorithm for path planning in a static environment with obstacles,” Evolutionary Computation, 2002. CEC '02. Proceedings of the 2002 Congress on, Vol. 1, pp. 500-505, 12-17 May 2002.
[15]Patrick Lester , A* Pathfinding for Beginners,
http://www.policyalmanac.org/games/aStarTutorial.htm
[16]Ishiguro, A., T. Kondo, Y. Watanabe, Y. Shirai, Y. Uchikawa, “Emergent construction of artificial immune networks for autonomous mobile robots,”Systems, Man, and Cybernetics, 1997. 'Computational Cybernetics and Simulation'., 1997 IEEE International Conference on, Vol. 2, pp. 1222-1228, 12-15 Oct. 1997.
[17]Ishiguro, A., Y. Watanabe, T. Kondo and Y. Uchikawa, “Decentralized consensus-making mechanisms based on immune system-application to a behavior arbitration of an autonomous mobile robot,” Evolutionary Computation, 1996., Proceedings of IEEE International Conference on, pp. 82-87, May 1996.
[18]Ishiguro, A., T. Kondo, Y. Watanabe and Y. Uchikawa, “Dynamic behavior arbitration of autonomous mobile robots using immune networks,” Evolutionary Computation, 1995., IEEE International Conference on, Vol. 2, pp. 722-727, Dec. 1995.
[19]Ishiguro, A., R. Watanabe, Y. Uchikawa, “An immunological approach to dynamic behavior control for autonomous mobile robots,” Intelligent Robots and Systems 95. 'Human Robot Interaction and Cooperative Robots', Proceedings. 1995 IEEE/RSJ International Conference on, Vol. 1, pp. 495-500, 5-9 Aug. 1995.
[20]Wang, Y.-N., T.-S. Lee, T.-F. Tsao, “Plan in obstacle-avoiding path for mobile robots based on artificial immune algorithm,” Lecture Notes in Computer Science (LNCS) of Springer-Verlag, Vol.4497, pp. 698-707, 2007.
[21]Gong Tao, and Zixing Cai, “Mobile immune-robot model,” Proceedings of the IEEE International Conference on Robotics, Intelligent Systems and Signal Processing, vol.2, pp. 1091-1096, Oct. 2003.
[22]Shi, Enxiu, Tao Cai and Changlin He, Junjie Guo, “Study of the New Method for Improving Artifical Potential Field in Mobile Robot Obstacle Avoidance,” Proceedings of the IEEE International Conference on Automation and Logistics, August 18-21, 2007.
[23]Holland, John H., “Adaptation in natural and Artificial System.,” Ann Arbor: University of Michigan Press, 1975.
[24]Tanaka, K., and K. Yoshioka, “Fuzzy trajectory control and GA-based obstacle
avoidance of a truck with five trailers,” IEEE International Conference on Systems, Man and Cybernetics, vol. 5, pp. 4378-4382, Oct. 1995.
[25]Vargas, P.A., L.N. de Castro, R.Michelan,and F.J. Von Zuben, “Implementation of an immuno-genetic network on a real Khepera II robot,” Proceedings of the Congress on Evolutionary Computation vol.1, pp. 420-426, Dec.2003.
[26]Luh, Guan-Chuh, Wei-Wen Liu, “Potential Field Based Immune Network for Dynamic Motion Planning of Mobile Robots, ”Strategic Technology, The 1st International Forum, pp. 151-155,18-20 Oct. 2006.
[27]Daniel Castro, Urbano Nunes, Antonio Ruano, “OBSTACLE AVOIDANCE IN LOCAL NAVIGATION, ” Proceedings of the 10th Mediterranean Conference on Control and Automation - MED2002 Lisbon, Portugal, July 9-12, 2002.
[28]Cang Ye, Johann Borenstein, Charaterization of a 2-D Laser Scanner for Mobil Robot ObstalceNegotiaion, Proceedings of the 2002 IEEE International Conference on Robotics and Automation.Washington DC, USA, 10-17 May 2002.
[28]徐浩軒, “以類免疫演算法為基礎之移動式機器人避障路徑規劃,” 龍華科技大學電子工程系碩士論文, July 2005.
[29]李謹州, “應用類免疫演算法於移動式機器人之路徑規劃,” 國立臺灣科技大學電機工程系碩士論文, June 2006.
[30]王延年, 李再生, “實現類免疫演算法於移動式機器人之避障路徑規劃,” 第十一屆人工智慧與應用研討會, pp. 1658-1664, Dec. 2006.
[31]王延年, 卓新怡, “結合人工免疫網路與人工勢場於移動式機器人之路徑規劃,”第三屆智慧生活科技研討會, pp. 453-460, June 2008.
[32]王延年, 林合豐, “人工智慧系統應用於移動式機器人之路徑規劃,” 第四屆智慧生活科技研討會, pp. 935-942, June 2009.