Open access peer-reviewed chapter

Applying Improve Differential Evolution Algorithm for Solving Gait Generation Problem of Humanoid Robots

Written By

Van-Tinh Nguyen and Ngoc-Tam Bui

Submitted: April 14th, 2021 Reviewed: April 28th, 2021 Published: May 31st, 2021

DOI: 10.5772/intechopen.98085

Chapter metrics overview

329 Chapter Downloads

View Full Metrics


This chapter addresses an approach to generate 3D gait for humanoid robots. The proposed method considers gait generation matter as optimization problem with constraints. Firstly, trigonometric function is used to produce trial gait data for conducting simulation. By collecting the result, we build an approximation model to predict final status of the robot in locomotion, and construct optimization problem with constraints. In next step, we apply an improve differential evolution algorithm with Gauss distribution for solving optimization problem and achieve better gait data for the robot. This approach is validated using Kondo robot in a simulated dynamic environment. The 3D gait of the robot is compared to human in walk.


  • Humanoid robot
  • control data
  • differential algorithm
  • gait
  • optimization

1. Introduction

Humanoid robot is a complex machine with a series of joint and links. Biped motion asserts surpass advantage than the others due to flexibility and good adaption when moving on unpredictable surface. Difference from human beings, the humanoid robots have a limitation of structure and number of degree of freedom. Moreover, legged walking behavior requires an action of many active joints and is much more challenge in synthetic gait to keep balance. To solve this matter, the traditional approaches consider that ensuring Zero Moment Point within support polygon is important key. For example, Firstly, states of art is the works of Kajita [1, 2, 3] with the Linear Inverted Pendulum Model. Recently, Monje et al. [4] integrated the dynamic steadiness while moving in real time. Samadi and Moghadam-Fard [5] applied Gravity Compensated Inverted Pendulum Mode (GCIPM) with proposing that trajectory of ZMP is created by a first-order function. Kai Hu et al. [6] designed Compensative Zero-Moment Point Trajectory from the reference ZMP to decrease the effect of disturbances. Likewise, Yang et al. [7] presented bivariate-stability-margin-based control model to compensate zero moment point and modeling error, opposition-based learning algorithm is applied to generated gait pattern.

In the other direction, a number of researchers concentrate on central pattern generator (CPG)-based walking. Alongside the very common studies in [8, 9, 10], we can mention some up-to-date prominent instances such that JimmyOr [11] proposed an approach based on combination of CPG and ZMP to control spine motion, it is promising way to enable natural walk of the robot. Wei Li et al. [12] developed a mechanism to generate muscle forces for biped motion, this method designed a feedback controller which is formed by a dynamic neural network with CPGs.

A optimization-based approach considering stability and walking speed was introduced by Goswami Dip et al. [13]. Likewise, In-sik Lim et al. [14] addressed a gait generation technique for legged walking up and down stairs, in which, genetic algorithm and the human motion data were used to produce the optimal trajectory. Newly, Ho Pham Huy Anh and Tran Thien Huan [15] optimized walking gait by modified Jaya optimization algorithm.

Other scholars are interested in model-predictive methods. For example, Zamparelli [16] et al. designed a stable model predictive control to generate CoM trajectory for the robot on uneven surface. Scianca [17] presented a prediction model with stability constraints. Hildebrandt et al. [18] proposed a model-predictive approach for generating walking gait of the robots with redundant kinematic design.

In this chapter, we proposed a novel gait generation method, in which, trigonometric function with randomized coefficients is used to produce trial gait data for conducting simulation. The result is collected to build approximation function of output: rotation angle value, lateral and walking distance. Then, we designed an optimization problem with constraints and applied an improve differential algorithm for solving it. Optimal coefficients is returned to trigonometric function and define it exactly. By setting up cycle time, walking gait data will be generated by explicit trigonometric function and can be used for reference data in control.

Next part of this chapter is organized into five divisions: The first section introduces the subject of this research named Kondo KHR-3. The second section assigns gait functions to actuator joints. Thirdly, optimization problem with constraint is built to optimize gait trajectory. The novel differential evolution algorithm with Gauss distribution is developed in Section 4 to solve optimization problem. Section 5 includes results and discussions. The final section summarizes achievements of this research.


2. Biped model of Kondo

2.1 Physical configuration

The subject is presented in this chapter which is based on a humanoid robot named Kondo KHR-3 as depicted in Figure 1a. This robot consists of 22 degrees of freedom (DoF) However, we concentrated on lower body with 10 DoFs, in which 5 is the number of DoFs for each leg. The linkage configuration is shown in Figure 1b, where θ,d,m are rotation angle, length and weight of each link, respectively. Specially, the weigh of upper body is represented by mo. The structure parameters of the robot are described in Table 1.

Figure 1.

Biped of Kondo: a) real robot; b) linkage model.

do90.6 (mm)
d138.5 (mm)
d266.5 (mm)
d362 (mm)
d466 (mm)
d5168 (mm)
mo999.4 (g)
m11,1214 (g)
m21,22100 (g)
m31,3265 (g)
m41,4271.3 (g)

Table 1.

Structure parameters of humanoid robot.

2.2 Foot structure with toe mechanism

Review on the works of foot structure for humanoid robots, we can list very old papers such as [19, 20, 21]. Recently, Sadedel et al. proposed a passive toe design. This mechanism improves energy efficiency of ankle and knee joints [22]. Likewise, Nerakae and Hasegawa simulated human-like foot structure which consist of big and tip toe to enhance biped walking gait in toe-off period [23]. In the other direction, Magistris et al. studied soft sole to minimize effect of the ground reaction force on stability during heel-strike period [24]. In [25], Daichi developed topology-based foot design to reduce weight and energy consumption, this research is specially meaningful for biped robot with limited physical parameters [26]. Our research presents a foot structure as shown in Figure 2, which is a combination of proposals mentioned in two papers [23, 26]. This sketch is built based on the following considerations: Firstly, all external forces acting on foot is at three areas consisting of heel, tip and big toe. Secondly, a passive toe joint mechanism with spring is applied to reduce impact of ground reaction force on foot. The material of foot is ABS plastic and design parameters are described in Table 2a.

Figure 2.

Novel foot design.

iOptimal design variables.

Table 2.

Design variable value.

2.3 Arm swing mechanism

Review on previous papers, we witness an arm swing mechanism which has been introduced and modeled using Adams in [27] as shown in Figure 3, the shoulder joint is linked to the hip joint by two linear springs. This mechanism is expected to generate the reaction moment from the arms to the trunk which eliminates ground reaction torque [28]. It makes the robot stable in motion. Our research applies this structure for the robot and characteristic parameters of the linear spring are stiffness of 0.8 newton/mm and damping of 0.008 newton.sec/mm.

Figure 3.

Principle of arm swing: a) mechanism with linear spring; b) integration in simulation model.


3. Assignment of motion

The biped walking is a repeated physical action, thus, joint angle of the robot will follow up some circular principle. In this chapter, we adopt the trigonometric functions, which are the sine and the cosine, is widely applied for studying periodic problem. The general trigonometric function is proposed by Eq. (1). In motion, each leg of the robot performs walking behavior similarly to the other one, thus, we will use same gait function for each corresponding joint. In addition, the trajectory in sagittal plane of left leg is slower than right leg by 0.6s since a cycle is set to 1.2s while the hip and ankle joint gait data in frontal plane is identical for both of leg. We assign trajectories to all joints of the robot as described in Eq. (2)(8). As can be seen that posture of the robot is defined at 0.3s in the beginning and stops motion at 3.3s. 00.3s period is used for preparation and 3.34.8s period is used for checking stability.


Where θi is the angle assigned to joint i,ai,bi,ci,di are coefficients; t, i are time and index of joint, respectively; ω is an angular velocity, ω = 5.236 (rad/s)


4. Optimization problem with predictive function

4.1 Response surface methodology

Response surface model (RSM) is a mathematical model which is used for an approximation of stochastic process and is firstly introduced by Box and Wilson [27]. Our research adopts 3rd-order RSM to predict output value of simulation such as lateral and walking distance, rotation angle. The expression of 3rd-order RSM is displayed by Eq. (9).


Where n is a design variable number, n = 16, xi is a design variable, and ap, bp, cp, dp are the coefficients of terms. Number of sampling for initialization is calculated by Eq. 10.


With n = 16, we determine Ns = 169 samples.

4.2 Optimization of gait trajectory

The goal of biped robot is to gain maximum walking distance with stable gait. This first problem is solved by a set of objective function, to apply optimization algorithm, we convert a maximum problem to minimum one as Eq. (11). The second issue is controlled by constraint functions as Eqs. (12) and (13).


Subject to:


Where Zf,Xf,Rf is walking, lateral distance and rotation angle, respectively. Their values are approximated by mentioned 3rd-order RSM.


5. Self-adaptive differential evolution with gauss distribution

This section introduce an modified self-adaptive differential evolution named G-SADE which is an improve version of Tam bui’s algorithm (ISADE) proposed in [28].

5.1 Improve self-adaptive differential evolution

Reviewing on ISADE, it adopts an adaptive scaling factor of mutation process and adaptive mechanism for crossover control parameter. Scaling factor is generated by a sigmoid function with ranking individual in population. ISADE mainly consists of three operations.

5.1.1 Mutation operation

In [28], Tam Bui et al. randomly selected three mutation operation, which are DE/best/1, DE/best/2, and DE/rand to best/1. Among DE’s operations, DE/best/1 and DE/best/2 are perceived for good convergence possession and DE/rand to best/1 is realized for good diversity property. Eqs. (14)(16) shows the formula of chosen schemes.


Where V, mutation vector; X, current vector; Xbest, best vector in current population; iter, number of iterations; i, index of individual in population, NP;j, index of dimensions, D;r1,r2,r3, and r4 are different particles selected randomly from [1;NP]; and NP,D, number of individuals and problem dimensions, respectively. Scaling factor F is set to be high in the beginning iterations and after certain iteration, it automatically becomes smaller for proper exploitation. The value F is generated by a Sigmoid function as in Eq. (17).


Where α is the parameter that controls the value of scaling factor Fi as shown in Figure 4.

Figure 4.

Value of scale factor F depends on rank number i and α.

ISADE gives an addition scaling Fimean as in Eq. (18).


Where Fmax and Fmin are the lower and upper limitation of F, respectively. Recommended values for Fmax, and Fmin are 0.8 and 0.15, respectively. itermax, and niter denote the maximum iteration, and the nonlinear modulation index. Niter is defined in Eq. (19).


Where nmax and nmin are selected in the [0, 15] range. nmax and nmin are 0.2 and 6.0, respectively. Finally, scaling factor Fiteri is calculated for each particle in each iteration as Eq. (20). The particle in population will receive different scaling factor. This mechanism maintains the balance of exploration and exploitation process in mutation operation.


5.1.2 Crossover operation

After mutation operation, ISADE adopts a crossover operation as Eq. (21).


Where U,V, and X are a trial vector, mutation vector, and current vector, respectively. CR is a crossover parameter within the interval (0,1). jrand is an integer random number selected from set {1, 2, …, D}.

5.1.3 Selection operation

This stage will choose the better fitness between trial vector U and target vector X for the next generation as Eq. (22).


5.2 Self-adaptive differential evolution with gauss distribution

Gauss distributions play an important role in statistics and are often used to generate real-valued random variables. Gaussian distribution gives a fantastic possibility to control the exploiting zone in optimization based on complexity of each considered problem. Our proposed strategy generates a new trial vectors in mutation operation by multiply Gauss random variable to a vector difference (Xr1,jiterXr2,jiter) in Eq. (14) and (Xr3,jiterXr4,jiter) in Eq. (15).

The formula of schemes in mutation operation is modified as the following Eq. (23) and (24).


Where N(0,σ2) is a Gauss random variable with mean zero and standard deviation σ. Recommended value for σ is 0.1. The new proposed DE is implemented as in Pseudocode 1 and The optimization process is described in Pseudocode 2.

Pseudocode 1: Implement of proposed DE
  1. Initialization: Generating randomly NP initial populations inside the bounds.

  2. Evaluation and ranking population: Evaluating and ordering all individuals based on their fitness value. Next, the first best NP individuals are selected to survive and kept for the next generation.

  3. Adaptive scaling factor: Computing scale factors F by Eqs. (17) to (20).

  4. Mutation operation: Mutation vectors V are created by applying adaptive selection learning strategy through Eq. (23) to (24).

  5. Crossover operation: Calculating trial vector U using Eq. (21).

  6. Selection Operation: Comparing trial vector Uiiter to target vector Xiiter is implemented based on evaluating their fitness value.

    The better candidate will be chosen for propagating new offspring in the next generation by Eq. (22).

  7. Steps 2 to 6 is repeated while termination condition is checked

Pseudocode 2: Implement of optimization
  1. Achieving the first simulation in Adams by Trial and Error method.

  2. Design of experiment.

  3. While termination condition is not reached;

    Making 3rd order response surface model;

    Applying ISADE with objective function 11 and constraint function 12, 13

    Analyzing the result through dynamic simulation in Adams.

  4. The optimal value of design variable is achieved


6. Results and discussions

Surfaces shown in Figure 5 is employed to present the walking process of biped robot. This is a absolutely flat terrain.

Figure 5.

Considered surface for simulation.

To observe the effect of arm swing mechanism on walking behavior, we build the 3D robot model in dynamic simulated environment of Adams software. Two configurations of the robot with different arm mechanism are considered as the following: firstly, we lock shoulder joint of the arm or in other respects the upper body is a static block with no movement. Second configuration is designed with a 1-32DoF shoulder joint which is set in sagittal plane. The biped motion is studied and evaluated on an above-mentioned environment. After applying G-SADE algorithm to solve optimization problem, we gain the optimal design variable is presented in Table 2. By replacing the term coefficients of i,ai,bi,ci,di in Eq. (1) with these optimal value, we will define four gait functions for all joints of the legs and trajectory is ruled by the principle shown by Eqs. (2)(8). To be clear, we can see these gait patterns in Figure 6. After all, results of simulation are presented in Figure 7.

Figure 6.

Gait pattern: (a) hip joint angle in frontal plane; (b) hip joint angle in sagittal plane; (c) knee joint angle; (d) ankle joint angle.

Figure 7.

Simulation result: (a) CoM trajectory in horizontal plane; (b) rotation angle of robot.

After implementing the simulation with achieved control data, we attain the final position of the robot as the following: For configuration 1 with no shoulder joint, lateral distance of Xf, walking distance of Zf and rotation angle of Rf are 6.17mm, 172.11mm, and 9.19o, respectively; meanwhile these value are 9.21mm, 184.66mm, and 3.98o, respectively for configuration 2 with 1-DoF shoulder joint.

To be particular, Figure 7a depicts the CoM trajectory of the robot, which has a approximately periodic waveform. Comparing to the humans described in [29], this performance is similar. Moreover, model with arm swing mechanism witnesses an improvement of about 9% in walking distance from 172.11mm to 184.66mm.

Figure 7b presents the rotation angle of the robot depending on time axis of the motion process. As can be seen that this line chart undergoes a fluctuation about from −25o to 25o around center line. It means that the robot’s feet rotate significantly in the locomotion. This phenomenon is due to an impact of friction force between foot and ground. Furthermore, the angle rotation of configuration 2 fluctuates with smaller amplitude of 5%, at the final position, this angle decreases by about 55%. (3.0s - 3.3s) period is prepared for landing and checking stability then, the rotation angle of the robot rapidly declines. In (3.3s - 4.8s) period, this angle is constant which expresses the success of the simulation and the robot stands steadily on the ground. Totally, above discussions address that the model with 1-DoF shoulder joint performs a better exhibition and should be applied in real robot.

Next discussion is to compare 3D gait on flat ground of both configurations with the humans in a cycle. The walking behavior is shown in Figure 8. As can be seen that posture of the simulation model at 1.2s,1.5s,1.8s,2.1s is comparable to the human walking behavior in "initialcontact", "midstance", "terminalstance", and "toeoff" periods. Highlight points on the robot posture are "toeoff" periods at 1.5s and 2.1s. This behavior is very clear and has pros on the contact between foot and ground in phase transferring stage.

Figure 8.

3D gait in a cycle.


7. Conclusions

Trajectory generation matter for biped walking is always one of the most challenges. Thus, researches on this field is very attractive and is implemented ceaselessly until now. In the same direction, our chapter one again relates to an 3D gait generation method for the biped robot. This approach constructs an optimization problem with constraint to create gait data of the robot. In addition, the modified differential evolution algorithm is introduced to solve an optimization problem. In the next stage, this chapter confirms that the arm swing mechanism enhances the biped walking performance by improving walking distance and reducing rotation angle when the robot moves on the flat ground. The effectiveness of this method is validated by dynamic simulation in Adams environment (MSC software).


Conflict of interest

The authors declare no conflict of interest.


  1. 1. Kajita, S., and Tanie, K. (1991). “Study of dynamic biped locomotion on rugged terrain – derivation and application of the linear inverted pendulum mode”, in Robotics and Automation, 1991. Proceedings. 1991 IEEE International Conference on, Vol. 2 (Sacramento, CA: Institute of Electrical Engineers, IEEE), 1405–1411
  2. 2. Kajita, S., Kanehiro, F., Kaneko, K., Yokoi, K., and Hirukawa, H. (2001). “The 3d linear inverted pendulum mode: a simple modeling for a biped walking pattern generation,” in Intelligent Robots and Systems, 2001. Proceedings. 2001 IEEE/RSJ International Conference on, Vol. 1 (Maui: Institute of Electrical Engineers, IEEE), 239–246
  3. 3. Kajita, S., Kanehiro, F., Kaneko, K., Fujiwara, K., Harada, K., Yokoi, K., et al. (2003). “Biped walking pattern generation by using preview control of zero moment point”, in Robotics and Automation, 2003. Proceedings. ICRA ‘03. IEEE International Conference on, Vol. 2 (Taipei: Institute of Electrical Engineers, IEEE), 1620–1626
  4. 4. Majied Mokhtari, Mostafa Taghizadeh, Mahmood Mazare (2021). “Impedance control based on optimal adaptive high order super twisting sliding mode for a 7-DOF lower limb exoskeleton”, in Meccanica 56:3, pages 535-548
  5. 5. Samadi, Farshad; Moghadam-Fard, Hamid (2014). “Pattern generation for humanoid robot with natural ZMP trajectory”, in IEEE 2014 Second RSI/ISM International Conference on Robotics and Mechatronics (ICRoM) - , 570–575, Tehran, Iran
  6. 6. K. Hu, C. Ott and D. Lee (2016). “Learning and Generalization of Compensative Zero-Moment Point Trajectory for Biped Walking”, in IEEE Transactions on Robotics, vol. 32, no. 3, pp. 717-725, June 2016, doi: 10.1109/TRO.2016.2553677
  7. 7. Liang Yang, Zhi Liu, Yong Chen (2018). “Bipedal walking pattern generation and control for humanoid robot with bivariate stability margin optimization”, in Advances in Mechanical Engineering, Volume 10 issue: 9
  8. 8. Endo G, Morimoto J, Matsubara T, Nakanishi J, Cheng G. (2008). “Learning CPG-based Biped Locomotion with a Policy Gradient Method: Application to a Humanoid Robot”, in the International Journal of Robotics Research;27(2):213-228. doi:10.1177/0278364907084980
  9. 9. Takeshi Mori, Yutaka Nakamura, Masa-aki Sato, Shin Ishii (2004). “Reinforcement Learning for a CPG-driven Biped Robot”, in AAAI’04: Proceedings of the 19th national conference on Artifical intelligence, pp. 623–630
  10. 10. Yutaka Nakamura, Takeshi Mori, Masa-aki Sato, Shin Ishii (2007). “Reinforcement learning for a biped robot based on a CPG-actor-critic method”, in Neural Networks, Volume 20, Issue 6, Pages 723-735
  11. 11. Jimmy Or (2010). “A hybrid CPG–ZMP control system for stable walking of a simulated flexible spine humanoid robot”, in Neural Networks, Volume 23, Issue 3, Pages 452-460
  12. 12. Li W., Szczecinski N.S., Hunt A.J., Quinn R.D. (2016). “A Neural Network with Central Pattern Generators Entrained by Sensory Feedback Controls Walking of a Bipedal Model”, In: Lepora N., Mura A., Mangan M., Verschure P., Desmulliez M., Prescott T. (eds) Biomimetic and Biohybrid Systems. Living Machines 2016. Lecture Notes in Computer Science, vol 9793. Springer, Cham.
  13. 13. Dip, G., Prahlad, V., & Kien, P. (2009). “Genetic algorithm-based optimal bipedal walking gait synthesis considering tradeoff between stability margin and speed”, in Robotica, 27(3), 355-365. doi:10.1017/S026357470800475X
  14. 14. In-sik Lim, Ohung Kwon, Jong Hyeon Park (2014). “Gait optimization of biped robots based on human motion analysis”, in Robotics and Autonomous Systems, Volume 62, Issue 2, Pages 229-240
  15. 15. Ho Pham Huy Anh and Tran Thien Huan (2020). “Optimal Walking Gait Generator for Biped Robot Using Modified Jaya Optimization Technique”, in International Journal of Computational Intelligence Systems, Volume 13, Issue 1, pp. 382 - 399
  16. 16. Alessio Zamparelli, Nicola Scianca, Leonardo Lanari, Giuseppe Oriolo (2018). “Humanoid Gait Generation on Uneven Ground using Intrinsically Stable MPC”, in IFAC-PapersOnLine, Volume 51, Issue 22, pp. 393-398
  17. 17. Hildebrandt, AC., Schwerd, S., Wittmann, R. et al. (2019). “Kinematic optimization for bipedal robots: a framework for real-time collision avoidance”, in Auton Robot 43, pp. 1187–1205
  18. 18. R. Sellaouti, O. Stasse, S. Kajita, K. Yokoi, and A. Kheddar (2006). “Faster and smoother walking of Humanoid HRP-2 with passive toe joints”, in Proceedings of IEEE/RSJ international conference on intelligent robots and systems, pp. 4909-4914
  19. 19. S. Lohmeier, T. Buschmann, H. Ulbrich, and F. Pfeiffer (2006). “Modular joint design for performance enhanced humanoid robot LOLA”, in Proceedings of IEEE international conference on robotics and automation, pp. 88-93
  20. 20. K. Yamane and L. Trutoiu (2009). “Effect of Foot Shape on Locomotion of Active Biped Robots, a study on effect of two-arch structure of foot for biped robots”, Proceedings of 9th IEEE-RAS International Conference on Humanoid Robots, pp.BIBLIOGRAPHY 74 2230-2236
  21. 21. Sadedel, M., Yousefi-Koma, A., Khadiv, M., & Mahdavian, M. (2017). “Adding low-cost passive toe joints to the feet structure of SURENA III humanoid robot”, in Robotica, 35(11), 2099-2121. doi:10.1017/S026357471600059X
  22. 22. K. Nerakae and H. Hasegawa (2014). “Big toe sizing design of small biped robot by using gait generation method”,in Applied Mechanics and Materials, volume 541-542, pp. 1079-1086
  23. 23. Giovanni de Magistris, Sylvain Miossec, Adrien Escande, Abderrahmane Kheddar (2017). “Design of optimized soft soles for humanoid robots”, in Robotics and Autonomous Systems, Elsevier, 95, pp.129-142
  24. 24. K. Daichi (2016). “Optimization of the biped robot for stable walking on rough terrain”, in Master’s thesis, Shibaura Institute of Technology
  25. 25. F. Naoki (2017). “Energy saving of biped robots aiming for 24-hour continuous operation”, in Master’s thesis, Shibaura Institute of Technology, Japan
  26. 26. J. Park (2008). “Synthesis of natural arm swing motion in human bipedal walking”, in Journal of Biomechanics, vol. 41, No. 7, pp. 1417-1426
  27. 27. Box, G. E. P., & Wilson, K. B. (1951). “On the experimental attainment of optimum conditions”, in Journal of the Royal Statistical Society, Series B (Methodological), Vol. XIII, No. 1
  28. 28. T. Bui, H. Pham, and H. Hasegawa (2013). “Improve self-adaptive control parameters in differential evolution for solving constrained engineering optimization problems”, Journal of Computational Science and Technology, vol. 7, no. 1, pp. 59-74
  29. 29. M. S. Orendurff, A. D. Segal, J. S. Berge, K. C. Flick, D. Spanier, and G. K. Klute (2006). “The kinematics and kinetics of turning: limb asymmetries associated with walking a circular path”, Gait and Posture, vol. 23, pp. 106-111

Written By

Van-Tinh Nguyen and Ngoc-Tam Bui

Submitted: April 14th, 2021 Reviewed: April 28th, 2021 Published: May 31st, 2021