臺灣博碩士論文加值系統

　　本論文採用基因演算法與免疫基因演算法，來探討機器人自主性移動之路徑規劃，使其能閃避障礙物且選擇最佳路徑使其在最短時間抵達終點。
　　地圖模型設計兩種大小情況來討論，包含了四種不同的地形變化，經過這些不同地形變化的區塊時，機器人會有不同的移動速度，使得最短路徑未必是最短時間。此外，更進一步考慮開放是車輛路徑問題。除了起點與終點之外，還增加了數個必須要經過的中繼站，同時考慮中繼站先後順序與最短時間需求來規劃路徑。
　　模擬結果顯示，基因演算法與免疫基因演算法皆可達成最佳化路徑規劃，而免疫基因演算法能以較少迭代次數求得較佳結果。

　　This dissertation adopt Genetic Algorithm (GA) and Immune Genetic Algorithm (IGA) to discuss the path planning for a mobile robot, it means that we try to avoid the obstacles and to find the optimal path, i.e., the minimum time cost form the start point to the end point.
　　We design two classes of maps with two different sizes and four types of terrain changes. The shortest past will not necessarily be the path costs minimum time while a robot passes different terrains with different velocities. Moreover, we incorporate the Vehicle Routing Problem (VRP) in the path planning. Besides the start point and the end point, we add several way points in the middle way and design the path planning considering the sequence of way point and minimum time cost.
　　Simulation results indicate that GA and IGA can get the optimal path planning, and IGA can obtain better result than GA by using less iteration numbers.

摘要
Abstract
誌謝
目錄
圖目錄
表目錄

第一章 緒論

第二章 預備知識
　　　　2.1 基因演算法(Genetic Algorithm, GA)
　　　　　　　　2.1.1 適應函數
　　　　　　　　2.1.2 複製
　　　　　　　　2.1.3 交配
　　　　　　　　2.1.4 突變
　　　　2.2 免疫基因演算法(Immune Genetic Algorithm, IGA)

第三章 路徑規劃之演算法設計
　　　　3.1 基因演算法設計
　　　　　　　　3.1.1 刪除式子
　　　　　　　　3.1.2 插入式子
　　　　　　　　3.1.3 適應函數
　　　　　　　　3.1.4 複製
　　　　　　　　3.1.5 交配
　　　　　　　　3.1.6 突變
　　　　3.2 免疫基因演算法設計
　　　　　　　　3.2.1 相似度
　　　　　　　　3.2.2 期望繁殖率
　　　　　　　　3.2.3 選擇機率
　　　　　　　　3.2.4 基因篩選

第四章 開放式車輛路徑問題之演算法設計
　　　　4.1 基因演算法設計
　　　　4.2 免疫基因演算法設計

第五章 實驗模擬結果與討論
　　　　5.1 30x30 case 1. 路徑規劃之模擬結果
　　　　5.2 30x30 case 2. 路徑規劃之模擬結果
　　　　5.3 30x30 case 3. 路徑規劃之模擬結果
　　　　5.4 50x50 case 1. 路徑規劃之模擬結果
　　　　5.5 50x50 case 2. 路徑規劃之模擬結果
　　　　5.6 50x50 case 3. 路徑規劃之模擬結果
　　　　5.7 50x50 case 4. 路徑規劃之模擬結果
　　　　5.8 50x50 case 5. 路徑規劃之模擬結果
　　　　5.9 30x30 開放式車輛路徑問題之模擬結果
　　　　5.10 50x50 開放式車輛路徑問題之模擬結果
　　　　5.11 模擬結果比較

第六章 結論與未來研究方向
　　　　6.1 結論
　　　　6.2 未來展望

參考文獻

 

[1]“ASIMO,” http://world.honda.com/ASIMO/
[2]“Partner Robot,” http://www.toyota-global.com/innovation/partner_robot/
[3]“Robots Scour WTC Wreckage,” http://www.wired.com/science/discoveries/news/2001/09/46930?currentPage=all
[4]“Telemax Explosive Ordnace (EOD) Robot,” http://www.defensie.nl/english/army/materiel/vehicles/engineer_vehicles/telemax_eod_robot
[5]“Intuitive Surgical,” http://www.intuitivesurgical.com/
[6]Yao Zhenwang and Kamal Guta, “Distributed Roadmaps for Robot Navigation in Sensor Networks,” Robotics, IEEE Transactions on, vol. 27, no. 5, pp. 997-1004, Oct. 2011.
[7]Luis Moreno, Jose M. Armingol, Santiago Garrido, Arturo de la Escalera, and Miguel A. Salichs, “A Genetic Algorithm for Mobile Robot Localization Using Ultrasonic Sensors,” Journal of Intelligent and Robotic Systems, vol. 34, no. 2, pp.135-154, June 2002
[8]Graziano Chesi and Y.S. Hung, “Global Path-Planning for Constrained and Optimal Visual Servoing,” Robotics, IEEE Transactions on, vol. 23, no. 5, pp. 1050-1060, Oct. 2007.
[9]O. Hachour, “The Proposed Fuzzy Logic Navigation Approach of Autonomous Mobile Robots in Unknown Environments,” International journal of mathematical models and methods in applied sciences, vol. 3, no. 3, pp. 204-218, 2009 .
[10]O. Hachour, “The Proposed Hybrid Intelligent System for Path Planning of Intelligent Autonomous Systems,” International journal of mathematics and computers in simulation, vol. 3, no. 3, pp. 133-145, 2009.
[11]O. Hachour, “Path Planning of Autonomous Mobile Robot,” International Journal of Systems Applications, Engineering & Development, vol. 2, no. 4, pp. 178-190, 2008.
[12]M.A. Porta Garcia, Oscar Montiel , Oscar Castillo , Roberto Sepu’ lveda, and Patricia Melin, “Path Planning for Autonomous Mobile Robot Navigation with Ant Colony Optimization and Fuzzy Cost Function Evaluation,” Applied Soft Computing, vol. 9, no. 3, pp. 1102-1110, June 2009.
[13]Xuaoyu Yang, Merhdad Moallem, and Rajni V. Patel, “A Layered Goal-Oriented Fuzzy Motion Planning Strategy for Mobile Robot Navigation,” Systems, Man, and Cybernetics, Part B: Cybernetics, IEEE Transactions on, vol. 35, no. 6, pp. 1214-1224, Dec. 2005.
[14]Gianluca Antonelli, Stefano Chiaverini, and Giuseppe Fusco, “A Fuzzy-Logic-Based Approach for Mobile Robot Path Tracking,” Fuzzy Systems, IEEE Transactions on, vol. 15, no. 2, pp. 211-221, April 2007.
[15]Simon X. Yang and Chaomin Luo, “A Neural Network Approach to Complete Coverage Path Planning,” Systems, Man, and Cybernetics, Part B: Cybernetics, IEEE Transactions on, vol. 31, no. 1, pp. 718-724, Feb. 2004.
[16]Hong Qu, Simon X. Yang, Allan R. Willms, and Zhang Yi, “Real-Time Robot Path Planning Based on a Modified Pulse-Coupled Neural Network Model,” Neural Networks, IEEE Transactions on, vol. 20, no. 11, pp. 1724-1739, Nov. 2009.
[17]Chengtao Cai, Chunsheng Yang, Qidan Zhu, and Yanhua Liang, “A Fuzzy-Based Collision Avoidance Approach for Multi-Robot Systems,” Robotics and Biomimetics (ROBIO), Sanya, China, Dec. 15-18, 2007, pp. 1012-1017.
[18]Rodolphe Le Riche and Raphael T. Haftka, “Optimization of Laminate Stacking Sequence for Buckling Load Maximization by Genetic Algorithm,” AIAA Journal, vol. 31, no. 5, pp. 951-956, 1993.
[19]Xiaojuan Wang, Liang Gao, Chaoyong Zhang, and Xinyu Shao, “A Multi-Objective Genetic Algorithm Based on Immune and Entropy Principle for Flexible Job-Shop Scheduling Problem,” The International Journal of Advanced Manufacturing Technology, vol. 51, no. 5-8, pp. 757-767, Nov. 2010.
[20]Xiao-Dong Xu and Cong-Xin Li, “Research on Immune Genetic Algorithm for Solving the Job-Shop Scheduling Problem,” The International Journal of Advanced Manufacturing Technology, vol. 34, no. 7-8, pp. 783-789, Oct. 2007.
[21]Jingui Lu, Ning Fang, Dinghong Shao, and Congyan Liu, “An Improved Immune-Genetic Algorithm for the Traveling Salesman Problem,” International Conference on Nuclear Criticality Safety (ICNC), vol. 4, Haikou, China, Aug. 24-27, 2007, pp. 297-301.
[22]Mehdi Azimipour, Mohammad Reza Bonyadi, and Mohammad Eshghi, “Using Immune Genetic Algorithm in ATPG,” Australian Journal of Basic and Applied Sciences, vol. 2, no. 4, pp. 920-928, 2008.
[23]Dingwei Wang, Rcihard Y.K. Fung, and W.G. Ip, “An Immune-Genetic Algorithm for Introduction Planning of New Products,” Computers & Industrial Engineering, vol. 56, no. 3, pp. 902-917, April 2009.
[24]Zhi-Gang Su, Pei-Hong Wang, and Xiang-Jun Yu, “Immune Genetic Algorithm-Based Adaptive Evidential Model for Estimating Unmeasured Parameter: Estimating Levels of Coal Powder Filling in Ball Mill,” Expert Systems with Applications, vol. 37, no. 7, pp. 5426-5258, July 2010.
[25]Zhihong Peng and Zixing Cai, “Cooperative Coevolutionary Adaptive Genetic Algorithm in Path Planning of Cooperative Multi-Mobile Robot Systems,” Journal of Intelligent and Robotic Systems, vol. 33, no. 1, pp. 61-71, 2002.
[26]T.W. Manikas , K. Ashenayi, and R.L. Wainwright, “Genetic Algorithms for Autonomous Robot Navigation,” IEEE Instrumentation & Measurement Magazine, vol. 10, no. 6, pp. 26-31, Dec. 2007.
[27]Ismail AL-Taharwa, Alaa Sheta, and Mohammed Al-Weshah, “A Mobile Robot Path Planning Using Genetic Algorithm in Static Environment,” Journal of Computer Science, vol. 4, no. 4, pp. 341-344, 2008.
[28]Xuanzi Hu and Cunxi Xie, “Niche Genetic Algorithm for Robot Path Planning,” International Conference on Nuclear Criticality Safety (ICNC), vol. 2, Haikou, China, Aug. 24-27, 2007, pp.774-778.
[29]Darrell Whitley, “A Genetic Algorithm Tutorial,” Statistics and Computing, vol. 4, no. 2, pp. 65-68, 1994.
[30]Licheng Jiao and Lei Wang, “A Novel Genetic Algorithm Based on Immunity,” Systems, Man and Cybernetics, Part A: Systems and Humans, IEEE Transactions on, vol. 30, no. 5, pp. 552-561, Sep. 2000.
[31]Wenjian Luo, Xianbin Cao, and Xufa Wang, “An Immune Genetic Algorithm Based on Immune Regulation,” Congress on Evolutionary Computation (CEC), vol. 1, Honolulu, Hawaii, United Sates, May 12-17, 2002, pp. 801-806.
[32]Lei Wang and Licheng Jiao, “The Immune Genetic Algorithm and Its Convergence,” International Conference on Signal Processing (ICSP), vol. 2, Beijing, China, Oct. 12-16 1998, pp. 1347-1350.
[33]Dipankar Dasgupta, An Overview of Artificial Immune Systems and Their Applications, Springer Berlin Heidelberg, 1999.
[34]L.N. de Castro and J. Timmis, “An Artificial Immune Network for Multimodal Function Optimization,” Congress on Evolutionary Computation (CEC), vol. 1, Honolulu, Hawaii, United Sates, May 12-17, 2002, pp. 699-704.
[35]Steven A. Hofmeyr and Stephanie Forrest, “Architecture for An Artificial Immune System,” Evolutionary Computation, vol. 8, no. 4, pp. 443-473, Winter 2000.
[36]D. Dasgupta, “Advances in Artificial Immune Systems,” Computational Intelligence Magazine, vol. 1, no. 4, pp. 40-49, Nov. 2006.
[37]D. Dasgupta and N. Attoh-Okine, “Immunity-Based Systems: A Survey,” Systems, Man, and Cybernetics, 1997. Computational Cybernetics and Simulation., 1997 IEEE, vol. 1, Orlando, Florida, United Sates, Oct. 12-15, 1997, pp. 369-374.
[38]John H Holland, Adaptation in Natural and Artificial Systems, The University of Michigan Press, Ann Arbor, 1975.
[39]Gunter Rudolph, “Convergence Analysis of Canonical Genetic Algorithms,” IEEE Trans. Neural Networks, vol. 5, no. 1, pp. 96-101, Jan. 1994.
[40]Kenneth Alan De John, “An Analysis of the Behavior of a Class of Genetic Adaptive System,” Doctoral Dissertation, The University of Michigan Ann Arbor, USA, 1975.
[41]Niels K. Jerne, The Immune System, Science American, 1973.
[42]PH. Richter, “A Network Theory of the Immune System,” European Journal of Immunology, vol. 5, no. 5, pp. 350-354, May 1975.
[43]Dipanker Dasgupta, “Artificial Neural Networks and Artificial Immune Systems: Similarities and Differences,” Systems, Man, and Cybernetics, vol. 1, Orlando, Florida, USA, Oct 1997, pp. 873-878.
[44]Yasuhiko Dote, “Soft Computing (Immune Networks) In Artificial Intelligence,” Systems, Man, and Cybernetics, vol. 2, San Diego, California, USA, Oct 1998, pp. 1382-1387.
[45]“免疫學原理,” http://www2.nsysu.edu.tw/Bio/images/commen/immu98.pdf
[46]Alan S Perelson, Norman H Packard, and J. Doyne Farmer, The Immune System, Adaptation, and Machine Learning, Physica D: Nonlinear Phenomena, vol. 22, no. 1-3, pp. 187-204, 1986.
[47]Jonathan Timmis, and Leandro Nunes de Castro, Artificial Immune Systems: A New Computational Intelligence Approach, Springer, 2002.
[48]Denise E. Cooke, and John E. Hunt, “Learning Using an Artificial Immune System,” Network and Computer Applications, vol. 19, no. 2, pp. 189-212, April 1996.
[49]Frank Macfarlane Burnet, “The Clonal Selection Theory of Acquired Immunity,” Nashville, Vanderbilt University Press, 1959.
[50]Leandro Nunes De Castro and Fernando J. Von Zuben, “The Clonal Selection Algorithm with Engineering Applications,” Genetic and Evolutionary Computation Conference, vol. 30, New York, United Sates, July 9-13, 2002, pp. 39-37.
[51]Xi CHEN, Guan-Zheng TAN, and Bin JIANG, “Real-time optimal path planning for mobile robots based on immune genetic algorithm,” Journal of Central South University, vlo. 39, no. 3, Jun. 2008