本論文旨在利用萬有引力搜尋演算法應用在雙足機器人的步態軌跡學習方式。為了減少馬達的組裝花費並使動作訓練更為便利，本論文使用MATLAB開發雙足機器人動作的模擬器。首先，本文將萬有引力搜尋法與粒子群演算法用在三個測試函數做比較，以確認萬有引力搜尋法比粒子群演算法有較佳的表現。接著，將引力搜尋最佳化法應用在簡化的二維五連桿雙足機器人的步態學習，以機器人單邊腳底移動的軌跡與所設計的軌跡之差作為適應值，自動搜尋最佳的步態。最後，用於在三維八連桿雙足機器人的步態學習上，以機器人質心移動與參考軌跡的差作為適應值，引力搜尋演算法可以成功地獲得一個穩定的移動步態。
所有的模擬結果說明，基於引力搜尋演算法產生的步態可以使雙足機器人行走順利和穩定。

This thesis mainly applies the gravitational search algorithm (GSA) to optimize gait trajectory of a biped robot. In order to reduce the motor assembly costs and allow the motion training to being more convenient, a robotic simulator for biped robots is developed in the thesis, where MATLAB software is adopted. First, the gravitational search algorithm is compared with the particle swarm optimization (PSO) by testing three standard functions to confirm whether it performs better than PSO or not. Then, for a simplified two-dimensional five-link biped robot, the GSA can autonomously learn the gait trajectory suppose the fitness function is described by a quadratic summation of the differences between the sole trajectory of the biped robot and its desired one. Finally, for a three-dimensional eight-link biped robot, if the fitness function is defined by the specified center of mass of the robot, then GSA can successfully obtain a stable moving gait. All the simulation results illustrate that the GSA based gait generator can make biped robots walk smoothly and stably.

[1] E. Rashedi, H. Nezamabadi-Pour, and S. Saryazdi, ‘‘GSA: A Gravitational Search Algorithm,’’ Information Science, Vol.179, No.13, pp. 2232–2248, 2009.
[2] K. Erbatur, A. Okazaki, and K. Obiya, T. Takahashi and A. Kawamura, “ A Study on the Zero Moment Point Measurement for Biped Walking Robots,” in Proc. 7th IEEE Int’l Workshop on Advanced Motion Contorl, pp. 431-436, 2002.
[3] D. Kim, S.-J. Seo, and G.-T. Park, “Zero-Moment Point Trajectory Modelling of a Biped Walking Robot Using an Adaptive Neuro-Fuzzy System,” IEE Proc. on Control Theory and Applications, Vol. 152, No. 4, pp. 411-426, 2005.
[4] S. Kajita, F. Kanehiro, K. Kaneko, K. Fujiwara, K. Yokoi, and H. Hirukawa, “ A Realtime Pattern Generation for Biped Walking,” in Proc. ICRA ’02, IEEE Int’l Conf. on Robotics and Automation, Vol. 1, pp.31-37, 2002.
[5] D. Ito, T. Murakami, and K. Ohnishi, “An Approach to Generation of Smooth walking Pattern for Biped Robot,” in Proc. 7th IEEE Int’l Workshop on Advanced Motion Control, pp.98 -103 , 2002 .
[6] S. Kagami, T. Kitagawa, and K. Nishiwaki, “A Fast Dynamically Equilibrated Walking Trajectory Generation Method of Humanoid Robot,” Autonomous Robotics, vol. 12, no. 1, pp. 71-82, 2002.
[7] E. R. Westervelt and J. W. Grizzle, “ Design of Asymptotically Stable Walking for a 5-Link Planar Biped Walker via Optimization, ” in Proc. ICRA ’02, IEEE Int’l Conf. on Robotics and Automation, Vol. 3, pp. 3117-3122, 2002.
[8] I. W. Park, J. Y. Kim, J. Lee, and J. H. Oh, “Online free walking trajectory generation for biped humanoid robot KHR-3(HUBO), ” in Proc. IEEE Int’l Conf. on Robotics and Automation, pp. 1231-1236, 2006.
[9] Q. Huang, K. Yokoi, S. Kajita, K. Kaneko, H. Arai, N. Koyachi, and K. Tanie“Planning Walking Patterns for a Biped Robot,” IEEE Transactions on Robotics and Automation, Vol. 17, No. 3, pp.280-289, 2001
[10] W. Wang, C. Christine, R. Carlos F., “Walking and steering control for a 3D biped robot considering ground contact and stability,” Robotics and Autonomous Systems Vol. 60,pp. 962–977,2012.
[11] A. Chatterjee, G. K. Mahanti. “Comparative performance of gravitational search algorithm and modified particle swarm optimization algorithm for synthe- sis of thinned scanned concentric ring ar-ray antenna” Progress In Electromagnetics Research B, Vol. 25, pp. 331-348, 2010.
[12] H. A. Shayanfar ,N. Mohammad S., O. Abedinia, A. Ghasemi, ‘‘GSA to Tune Fuzzy Controller for Damping Power System Oscillation” Electrical Eng. Department, Islamic Azad University, South Tehran Branch, Tehran, Iran
[13] A. Chatterjee, G. K. Mahanti, and N Pathak, “Comparative Performance of Gravitational Search Algorithm and Modified Particle Swarm Optimization Algorithm for Synthesis of Thinned Scanned Concentric Ring Array Antenna,” in Proc Electromagnetics Research B, Vol. 25, pp.331–348, 2010.
[14] Z. Zhi-Hui, Z. Jun, L. Yun and C. Henry S-H. “Adaptive particle swarm optimization,” IEEE Trans. Systems, Man, and Cybernetics, Vol. 39, No.6, pp. 1362-1381, 2009.
[15] J. Kennedy, “The particle swarm: social adaptation of knowledge,” in Proc. IEEE Int. Conf. Evolutionary Computation, pp. 303-308, 1997
[16] R. Mansouri, F. Nasseri, M. Khorrami, “Effective time variation of G in a model universe with variable space dimension,” Physics Letters Vol. 259, pp. 194–200, 1999.
[17] G. You-Zhen, ‘‘Design and Implement Ring Potential Field Control for a Three-on-Three Robot Soccer Game System” Department of Electrical Engineering National Cheng Kung University, Master, Thesis Tainan, Taiwan, R.O.C. June 2002.
[18] L. Shao-Wei, “Design and implementation of reinforce learning based fuzzy gait controller for humanoid robot,” Master Thesis, National Cheng Kung University, Tainan, Taiwan, R.O.C, 2009.
[19] L. Kai-Fan, ”Design and Implementation of Particle Swarm Optimization Gait Learning Method for Adult-sized Humanoid Robots,” Master Thesis, Department of Electrical Engineering National Cheng Kung University, Tainan, Taiwan, R.O.C. ,2012.
[20] R. Nizar, A. Adel M, ‘‘IK-PSO, PSO Inverse Kinematics Solver with Application to Biped Gait Generation” International Journal of Computer Applications, Vol.58, No.22, November 2012.
[21] C. Hamzaçebi, “Improving genetic algorithms’ performance by local search for continuous function optimization” Applied Mathematics and Computation. Vol.196, pp. 309–317, 2008.
[22] S. Z. Zhao, J. J. Liang and P. N. Suganthan, “Dynamic Multi-Swarm Particle Swarm Optimizer with Local Search for Large Scale Global Optimization” CEC Proc. Congress on Evolutionary Computation, pp. 3845-3852, 2008
[23] P. Buschka, A. Saffiotti, and Z. Wasik, “Fuzzy landmark-based localization for a legged robot,” in Proc. Int. on Intelligent Robots and Systems, pp. 1205-1210, 2000.
[24] H. Po-Chun, “Design and Implementation of a Series of Small-sized Humanoid
Robots,” Master Thesis, National Cheng Kung University, Tainan, Taiwan, R.O.C. 2011.
[25] D. Rosen, "Automated Construction of Robotic Manipulation Programs," The Robotics Institute, Carnegie Mellon University Pittsburgh, Pennsylvania, 2010.
[26] S. Lenser, M. Veloso, “Sensor resetting localization for poorly modeled mobile robots,” in Proc. of the IEEE International Conference on Robotics and Automation
(ICRA), 2002.
[27] H. Yasuhisa, A. Takemasa, F. Toshio, “Trajectory generation for biped locomotion robot”, Department of Micro System Engineering, Nagoya University, Japan, Mechatronics 10, pp. 67–89, 2000.
[28] T. Nikos C. ,V. Kimon P. ,and H. Timothy, "Autonomous Vehicle Navigation Utilizing Electrostatic Potential Fields and Fuzzy Logic," IEEE Transactions on Robotics and Automation, Vol. 17, No. 4, 2001.
[29] T. Chi-Yang and K. I-Wei, “Particle swarm optimization with selective particle regeneration for data clustering,” Expert Systems with Applications, Vol. 38, pp. 6565-6576, 2011.
[30] S. Kirkpatrick, C. D. Gelatt, M. P. Vechi, “Optimization by Simulated Annealing” Science, Vol. 220, pp. 671-680, 1983.
[31] M. Ammar W. ,S. Nirod Chandra, and G. Tan Kim, “Solving shortest path problem using particle swarm optimization,” Applied Soft Computing, Vol. 8, pp. 1643-1653, 2008.
[32] L. Xu, TW. Chow, “Self-Organizing Potential Field Network: A New Optimization Algorithm,” IEEE Transactions on Neural Networks, Vol. 21, No. 9, 2010.
[33] K. Mohammad, E. Mahdiyeh, “Gravitational search algorithm for optimization of retaining structures,” Indian Journal of Science and Technology, Vol. 5, No. 1, pp. 1821-1827, 2012.
[34] D. Herrero-Perez, H. Martinez-Barbera, “Fast and robust recognition of field line intersections,” in Robotics Symposium, LARS‘06. IEEE 3rd Latin American, pp. 115-119, 2006.
[35] R. A. Formato, “Central force optimization: a new metaheuristic with applications in applied electromagnetics” in Proc. Electromagnetics Research, PIER 77,pp. 425–491, 2007.