Open access peer-reviewed chapter - ONLINE FIRST

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

By Van-Tinh Nguyen and Ngoc-Tam Bui

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

DOI: 10.5772/intechopen.98085

Downloaded: 34


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,mare 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/mmand 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.6ssince a cycle is set to 1.2swhile 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.3sin the beginning and stops motion at 3.3s. 00.3speriod is used for preparation and 3.34.8speriod is used for checking stability.


Where θiis the angle assigned to joint i,ai,bi,ci,diare coefficients; t, iare 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 nis a design variable number, n= 16, xiis a design variable, and ap, bp, cp, dpare 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,Rfis 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 r4are different particles selected randomly from [1;NP]; and NP,D, number of individuals and problem dimensions, respectively. Scaling factor Fis set to be high in the beginning iterations and after certain iteration, it automatically becomes smaller for proper exploitation. The value Fis 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 numberiandα.

ISADE gives an addition scaling Fimeanas in Eq. (18).


Where Fmaxand Fminare the lower and upper limitation of F, respectively. Recommended values for Fmax, and Fminare 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 nmaxand nminare selected in the [0, 15] range. nmaxand nminare 0.2 and 6.0, respectively. Finally, scaling factor Fiteriis 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 Xare a trial vector, mutation vector, and current vector, respectively. CRis a crossover parameter within the interval (0,1). jrandis 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 zeroand 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 Uiiterto target vector Xiiteris 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,diin 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 Zfand rotation angle of Rfare 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.11mmto 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 −25oto 25oaround 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.1sis comparable to the human walking behavior in "initialcontact", "midstance", "terminalstance", and "toeoff"periods. Highlight points on the robot posture are "toeoff"periods at 1.5sand 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.

Download for free

chapter PDF

© 2021 The Author(s). Licensee IntechOpen. This chapter is distributed under the terms of the Creative Commons Attribution 3.0 License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

How to cite and reference

Link to this chapter Copy to clipboard

Cite this chapter Copy to clipboard

Van-Tinh Nguyen and Ngoc-Tam Bui (May 31st 2021). Applying Improve Differential Evolution Algorithm for Solving Gait Generation Problem of Humanoid Robots [Online First], IntechOpen, DOI: 10.5772/intechopen.98085. Available from:

chapter statistics

34total chapter downloads

More statistics for editors and authors

Login to your personal dashboard for more detailed statistics on your publications.

Access personal reporting

We are IntechOpen, the world's leading publisher of Open Access books. Built by scientists, for scientists. Our readership spans scientists, professors, researchers, librarians, and students, as well as business professionals. We share our knowledge and peer-reveiwed research papers with libraries, scientific and engineering societies, and also work with corporate R&D departments and government entities.

More About Us