本論文係探討整合遺傳基因演算法與模糊控制法於自走式機器人(AMR)行走於具障礙環境中之最佳動向研究。基本上最佳動向研究也就是替AMR找最佳的路徑規劃。在論文中，首先介紹路徑規劃中所運用到之模糊演算法與遺傳基因演算法的歷史沿革、動作原理及操作應用流程。其次說明路徑規劃之緣由及其定理，接著我們提出二種最佳動向選擇的方法，第一種是線性頂點選擇機制，第二種則是模糊邏輯選擇機制，並實際運用電腦模擬來比較兩者優缺點。同時也探討不同推論規則數以及歸屬函數對路徑規劃之影響。接下來更進一步我們利用遺傳基因演算法輔佐線性頂點選擇機制去挑選最佳權重因子以及利用遺傳基因演算法結合模糊控制法去學習得出理想之歸屬函數及模糊決策邏輯，並比較驗證經由遺傳基因演算法學習後所得之路徑規劃結果表現。最後利用電腦模擬AMR行走於障礙物環境中以展現其可行性。

The theme of this thesis is to determine the best motion planning for the autonomous mobile robot (AMR) moving in the environment with obstacles. At first, we survey the existed path planning results and introduce the design procedures of the Genetic Algorithm (GAs) and Fuzzy Logic Control (FLC). Second we propose two motion planning methods, one is the linear vertex decision mechanism (LVDM) and the other one is the fuzzy logic decision mechanism (FLDM). Computer simulations are explored to compare the performance of these two mechanisms. Furthermore, we apply the GAs to the LVDM to select the optimal weighting factor and we also adopt the GAs in the FLDM such that the best membership function and/or the number of fuzzy control rules can be obtained. The computer simulations of the evolved LVDM and FLDM are also provided. All the simulations demonstrate that the proposed schemes can indeed guide the AMR even the circumstance is filled with obstacles

第一章 緒論1
1.1 引言研究動機與目的1
1.2 概論1
1.3 本文架構..3
第二章 模糊控制與遺傳基因演算法4
2.1 模糊演算法4
2.1.1 模糊理論5
2.2 遺傳基因演算法17
2.2.1 引言17
2.2.2 GAs架構與簡介18
2.2.3 簡易遺傳基因演算法..26
2.2.4 遺傳基因演算法結合模糊系統 27
第三章 路徑規劃30
3.1 路徑規劃理論架構30
3.1.1 障礙物表示30
3.1.2頂點選取與篩選35
3.1.3障礙物之選取42
3.2 頂點選擇機制47
3.3路徑規劃架構48
3.3.1 線性選擇機制48
3.3.2模糊邏輯選擇機制57
3.4 結論66
第四章 整合基因演算於模糊控制之實驗結果69
4.1 線
性與模糊機制之比較69
4.2 歸屬函數中模糊集合個數之比較74
4.3 遺傳基因演算法學習機制81
4.3.1 利用遺傳基因演算法學習歸屬函數82
4.3.2利用遺傳基因演算法學習決策邏輯規則表93
4.3.3 結言 98
4.4 模擬99
4.5 結論..100
第五章 結論與未來展望102
參考文獻104
圖索引

[1]C. Alexopoulus and P. M. Griffin, “Path planning for a mobile robot,” IEEE Trans. Syst., Man, Cybern., vol. 22, pp. 318-322, 1992.
[2]K-C Fan and P-C Lui, “Solving find path problem in mapped environments using modified algorithm,” IEEE Trans. Syst., Man, and Cybern., vol. 24, No. 9, pp. 1390-1396, September, 1994.
[3]B. J. Oommen, S. S. Iyengar, N. S.V. Rao, and R. L. Kashyap,“Robot navigation in unknown terrains using learned visibility graphs. PartⅠ:the disjoint convex obstacle case,” IEEE Journal of Robotics and Automation, vol. RA-3, No. 6, pp. 672-680, December, 1987.
[4]Vladimir J. Lumelsky and Alexander A. StepaNov, “Dynamic path planning for a mobile automaton with limited information on the environment,” IEEE Trans. Automat., vol. AC-31. No. 11, pp. 672-680, 1986.
[5]J. L. Diaz de Leon S. and J. H. Sossa A., “Automatic path planning for a mobile robot among obstacle of arbitrary shape,” IEEE Trans. Syst., vol. 28, No. 3, pp. 467-471, 1998.
[6]C. J. Taylor and D. J. Kriegman, “Vision-based motion planning and exploration algorithm for mobile robots,” IEEE Trans. Robot. Automat., vol. 14, No. 3, pp. 417-422, 1998.
[7]B. Kuipers and Y.-T. Byun, “A robot exploration and mapping strategy based on a semantic hierarchy of spatial representation,” Robot. Auton. Syst., vol. 8, pp. 47-63, 1991.
[8]B. Kuipers and T. Levitt, “Navigation and Mapping in Large-scale Space,” AI Mag., vol. 9, No. 2, pp. 25-43, 1988.
[9]J. T. Schwartz and M. Shair, “A survey of motion planning and related geometric algorithms,” Artif . Intell., vol. 37, pp. 157-169, 1988.
[10]J. Borestein and Y. Koren, “Real-time obstacle avoidance for fast mobile robots,” IEEE Trans. Syst., Man, Cybern., vol. 19, pp. 75-91, 1990.
[11]J. S. Singh and M. D. Wagh, “Robot path planning using intersecting convex shapes: Analysis and simulation,” IEEE Journal of Robotics and Automation., vol. RA-3, No. 2, 1987.
[12]P. L. Lin and S. Chang, “A shortest path algorithm for a Nonrotating object among obstacles of arbitrary shapes,” IEEE Trans. Syst., Man, Cybern., vol. 23, pp. 825-833, 1993.
[13]W. Li, C. Ma, and F. M. Wahl, “A neuro-fuzzy system architecture for behavior-based control of a mobile robot in unknown environment,” Fuzzy Sets and System, pp. 133-140, 1997.
[14]B. Kreczmer, “Path planning system for car-like robot,” in Proc. IEEE Int . Conf. Robot. Automat., pp. 40-45, 1998.
[15]J.-S. R. Jang, C.-T. Sun, and E.Mizutani,“Neuro-fuzzy and soft computing,” Prentice-Hall International, Inc., 1997.
[16]L. Ingber and B. Rosen,“Genetic algorithms and very fast simulated reannealing:a comprison,” Mathl. Comput Modeling, vol. 16, No. 11, pp . 87-100, 1992.
[17]H. Szu and R. Hartley,“Fast simulated annealing,” Physics Letters, vol. 122, No. 3, pp. 157-162, June, 1987.
[18]S. K. Pal and D. Bhandari, “Genetic Algorithms with Fuzzy Fitness Function for Object Extraction Using Extracting Using Cellular Networks,” Fuzzy Sets and Systems, vol. 65, No. 2/3, pp. 152-160, 1994.
[19]M. Sampei, T. Tamura, T. Kovayashi, and N. Shibui, “Arbitraty path tracking control of articulated vehicles using Nonlinear control theory,” IEEE Transactions on Control Systems TechNology, vol. 3, No. 1, pp. 125 - 131, March 1995.
[20]L.-J. Huang and M. Tomizuka, “A self-paced fuzzy tracking controller for two-dimensional motion control,” IEEE Trans. Syst. Man and Cybernetics, vol. 20, No. 5, pp. 1115-1124, September/October, 1990.
[21]J.-P. Laumond, P.-E. Jacobs, M. Taix, and R.-M. Murry, “A motion planner for NonholoNomic mobile robots,” IEEE Trans. Robot. Automat., vol. 10, No. 5, pp.577-593, 1994.
[22]E.-H. Ruspini, “Fuzzy logic-based planning and reactive control of autoNomous mobile robots,” Proc. of IEEE Int. Conf. on Fuzzy Systems, vol. 3, pp. 1071-1076, 1995
[23]L.A. Zadeh, “Fuzzy set,” Information and Control, Vol. 8, pp. 338-353, 1965.
[24]王進德,蕭大全, 類神經網路與[25]模糊控制理論入門,全華書局, 1994.
[26]張兆旭, Fuzzy 淺談, 松崗,1994.
[27]C.-F. Lin, Advanced Control System Design, Prentice Hall, Inc., 1994.
[28]J. H. Holland, Adaptation in Natural and Artificial Systems, Ann Arbor, MI: The University of Michigan Press, 1975.
[29]D. E. Goldberg, Genetic Algorithms in Search, Optimization, and Machine Learning. Reading, MA: Addison-Wesley, 1989.
[30]M. Mitichel, An Introduction to Genetic Algorithms, Cambridge, MA: MIT Press, 1996.
[31]A. M. Gellies, “Machine learning procedures for generating image domain feature detectors”, Ph.D. dissertation, University of Michigan, Ann Arbor, 1985.
[32]S. Forrest , “Documentation for PRISONER DILEMMA and NORMS programs That use the genetic algorithm”, Unpubilished manuscript, University of Michigan, Ann Arbor, 1985.
[33]J. J. Buckley and Y. Hayashi, “Fuzzy genetic algorithm and applications,” Fuzzy Sets and Systems, vol. 61, pp. 129-136, 1994.
[34]S. K. Pal and D. Bhandari, “Genetic algorithms with fuzzy fitness function for object extraction using cellular networks,” Fuzzy Sets and Systems,” pp. 65-72, 1994.
[35]H. Ishibuchi, K. Nozaki, N. Yamamoto, and H. Tanaka, “Construction of fuzzy classification systems with rectangular fuzzy rules using genetic algorithms,” Fuzzy Sets and Systems,” pp. 69-75, 1994.
[36]W. Pedrycz, “Genetic Algorithms for Learning in Fuzzy Relational Structures,” Fuzzy Sets and Systems, vol. 69, pp. 37-52, 1995.
[37]H. Ishigami, T. Fukuda, T. Shibata and F. Arai, “Structure Optimization of Fuzzy Neural Network By Genetic Algorithm,” Fuzzy Sets and Systems, vol. 71, pp. 257-264, 1995.
[38]C.-C. Wong, S.-M. Feng, “Switching-type fuzzy cont1roller design by genetic algorithms,” Fuzzy Sets and Systems, vol.74, pp. 175-185, 1995.
[39]A. Homaifar and E. McCormick, “Simulataneous design of membership functions and rules sets for fuzzy controllers using genetic algorithms,” IEEE Trans. Fuzzy Syst., vol. 3, No. 2, Ma
[40]K. C. Fan and P. C. Lui, “Solving find path problem in mapped environments using modified A* algorithm,” IEEE Trans. Syst., vol. 24, No. 9, 1994.
[41]M. B. Trabia, “Planning near-minimun-length collision-free paths for robots,” IEEE Trans. Syst., Man, Cybern., vol. 23, pp. 1481-1488, 1993.
[42]C. Alexopoulos and P. M. Griffin,“Path planning for a mobile robot,”IEEE Trans. Syst., Man, and Cybern., vol. 22, No. 2, pp. 318-322, March/April, 1992.
[43]B. J. Oommen, S. S. Iyengar, N. S. V. Rao, amd R. L. Kashyap, “Robot navigation in unknown terrains using learned visibility graphs. Part I: The disjoint convex obstacle case,” IEEE Journal of Robotics and Automation, vol. RA-3, No. 6, 1987.
[44]P. Veelaert and H. Peremans, “Mobil robot navigation based on flexibility maps of the environment,” Proc. of IEEE Int. Conf. on Pattern Recognition, vol. 1, pp. 146-150, 1996.
[45]C. J. Wu,“A Learning fuzzy algorithm for motion planning of mobile robots,” Journal of Intelligent and Robotics Systems 11, pp. 209-221, 1995.
[46]W. Li, C. Ma, and F. M. Wahl, “A neuro-fuzzy system architecture for behavior-based control of a mobile robot in unknown environment,” Fuzzy Sets and System, pp. 133-140, 1997.