This paper proposes an evolutionary optimization approach for optimal hopping of humanoid robots. In the proposed approach, the hopping trajectory is generated by a central pattern generator (CPG). The CPG is one of the biologically inspired approaches, and it generates rhythmic signals by using neural oscillators. During the hopping motion, the disturbance caused by the ground reaction forces is compensated for by utilizing the sensory feedback in the CPG. Posture control is essential for a stable hopping motion. A posture controller is utilized to maintain the balance of the humanoid robot while hopping. In addition, a compliance controller using a virtual springdamper model is applied for stable landing. For optimal hopping, the optimization of the hopping motion is formulated as a minimization problem with equality constraints. To solve this problem, twophase evolutionary programming is employed. The proposed approach is verified through computer simulations using a simulated model of the smallsized humanoid robot platform DARwInOP.
1. Introduction
Research on humanoid robots has made rapid progress in dexterous motions along with hardware development
[1

5]
. Stable walking and running motions are especially representative research issues in humanoid robotics. The running motion is composed of flight phases and support phases, thus the jumping motion is a very important issue for the flight phase. In other words, the jumping motion is the prerequisite for the running motion. As research on jumping and hopping motions of the humanoid robot, running pattern generation based on a zero moment point has been studied by expanding the concept of the zero moment point to running control
[6
,
7]
. To maintain dynamic stability while hopping or running, online balance controllers have been proposed
[8]
. Moreover, approaches have been proposed to generate a hopping trajectory for humanoid robots with passively compliant structures
[9

11]
. Although the jumping and hopping motions of the humanoid robot have been successfully implemented in the previous researches, it is necessary to formulate the hopping motion of the humanoid robot as an optimization problem for optimal hopping. The optimization problem can be solved by evolutionary algorithms
[12
,
13]
, which have been applied to walking
[14
,
15]
, footstep planning
[16
,
17]
, and posture control
[18]
of the humanoid robot.
For optimal hopping, there should be complex considerations, along with guaranteed stability, while hopping. While hopping, rocking back and forth of the humanoid robot occurs and should be minimized for stability. In addition, oscillation of the ground reaction forces (GRFs) on the feet should be minimized, and the actual flight time should be maximized for efficient hopping. This complicated optimization problem can be solved by the evolutionary algorithm. This paper proposes an evolutionary optimization approach for optimal hopping of humanoid robots. In the proposed approach, the hopping trajectory is generated by a central pattern generator (CPG). The CPG is one of the biologically inspired approaches, and it generates rhythmic signals by using neural oscillators
[19
,
20]
. During the hopping motion, the disturbance caused by the GRFs is compensated for by utilizing the sensory feedback in the CPG. Posture control is essential for a stable hopping motion. Therefore, a posture controller is utilized to maintain the balance of the humanoid robot while hopping. In addition, a compliance controller, which utilizes a virtual springdamper model for the pitch motion of the feet, is applied for stable landing. The optimization of the hopping motion is formulated as a minimization problem with equality constraints. To solve this problem, twophase evolutionary programming (TPEP) is employed
[21]
. The proposed approach is verified through computer simulations with a simulated model of the smallsized humanoid robot platform DARwInOP.
This paper is organized as follows. Section 2 describes the hopping pattern generation. The CPG structure is reviewed and the hopping pattern generation using the CPG is explained, along with the sensory feedback of the CPG. Section 3 describes the posture controller and the compliance controller for hopping control. Section 4 describes the evolutionary optimization with the objective function design. The validity of the proposed approach is verified through computer simulations, as described in Section 5. Lastly, conclusions are addressed in Section 6.
2. Hopping Trajectory Generation
 2.1 CPG structure
The sequence of extension and flexion of joints enables rhythmic biological locomotion. When one side of the body part extends, the other side flexes, and the extension and flexion continue alternately during rhythmic motion. For the modeling of this biological system, Taga devised the CPG structure
[19]
. In the CPG, multidimensional rhythmic signals are generated endogenously without a rhythmic sensory or central input, and these signals are adapted to environmental perturbations using sensory feedback. To generate the rhythmic signals, Matsuoka’s neural oscillator is utilized, the neuron of which is described as follows
[20]
:
with
[
u
]
^{+}
= max(0,
u
)
where the subscripts
i
and
j
denote the indexes of the neurons,
u
_{i}
and
v
_{i}
are the inner state and selfinhibition state, respectively, and
c
is the external input signal that affects the output amplitude. 𝛽 and
w
_{ij}
denote respectively the selfinhibition weight and the connecting weight which decides the phase difference between the
i
th and
j
th neurons.
f
_{i}
is the sensory feedback signal.
τ
and
τ
' denote the time constants that have an effect on the shape and period of the output signal, and
n
is the number of neurons.
Fig. 1
shows the neuron structure. The detailed description of the parameters of the neuron is provided in
[20].
In
[20]
, the rhythmic control in several neural oscillators consisting of two to six neurons was discussed and by the computer simulation, the mathematical conditions for the neural oscillators to produce a stable rhythmic signal were obtained.
Neuron structure.
In the CPG structure, rhythmic signals are generated by Matsuoka’s neural oscillators (in (1)), each of which consists of an extensor neuron (EN) and a flexor neuron (FN). These are interconnected in the same neural oscillator and produce flexion and extension signals, as shown in
Fig. 2.
Through the effects of this relationship, rhythmic signals are obtained as follows
[19]
:
Neural oscillator structure for CPG.
where the subscripts
e
and
f
denote the EN and FN, respectively.
w
_{ef}
and
w
_{fe}
are the connecting weights between the EN and the FN, and
o
_{cpg}
is the output signal.
 2.2 Hopping trajectory generation using CPG
For a hopping motion, the vertical center of mass (COM) trajectory of the humanoid robot is generated using the CPG, as shown in
Fig. 3.
The COM trajectory
z
_{com}
is computed as follows:
Hopping trajectory generation using CPG.
with
where
Z
_{c}
is the initial COM height.
A
_{flight}
and
A
_{support}
denote the amplitude scaling factors for the flight phase and the support phase, respectively. In the neural oscillator, when the magnitude of the output signal is negative,
ατ
and
ατ
' are used instead of
τ
and
τ
' , respectively, to adjust the period of the output signals, where
α
is the scaling factor.
To compensate for the disturbance from the ground during the hopping motion, sensory feedback of the neural oscillator is utilized. If the robot stands motionlessly, the sum of the GRFs on the feet is equal to the robot’s weight. On the other hand, the sum of the GRFs oscillates around the value of the weight of the robot during the hopping motion. Thus, the following sensory feedback is designed to improve the robot’s stability during the hopping motion by minimizing the oscillation of the GRFs on the feet:
where
k
_{f}
denotes the scaling factor,
F
_{l}
and
F
_{r}
indicate the GRFs on the left and right feet, respectively, and
M
is the mass of the humanoid robot.
3. Hopping Control
 3.1 Posture controller
A posture controller is utilized to maintain the balance of the humanoid robot while hopping. For the posture controller, the humanoid robot is simplified as shown in
Fig. 4
, and the ankle pitch angle is controlled as follows:
Structure for posture controller.
with
where
is the reference ankle pitch trajectory by the hopping pattern generation and
denotes the modified reference ankle trajectory by the posture control. 𝜽
_{desired}
is the desired body angle of the robot and 𝜽
_{body}
is the actual body angle of the robot, which is measured by the posture sensor. The posture controller uses a proportionalderivative (PD) controller.
k
_{p}
and
k
_{d}
are the coefficients of the PD controller.
 3.2 Compliance controller
When the humanoid robot is hopping, either the toe or the heel of the robot could contact the ground sooner while landing, which would cause the robot to become unstable. To solve this problem, a virtual springdamper model is used, as shown in
Fig. 5.
A rotational virtual springdamper model is utilized for the pitch motion of the foot, and the rotational foot displacement Δ𝜽
_{ankle}
is governed by the following equation:
Virtual springdamper model for foot.
where
k
_{vsd}
and
b
_{vsd}
are the spring and damper coefficients, respectively.
τ_{ankle}
is the pitch torque on the foot, and is obtained as follows:
where
l
_{f}
and
l
_{b}
denote the front and back foot lengths from the center of the foot, respectively.
f
_{i}
(i=1, 2, 3, and 4) are the GRFs measured by the force sensing resistors (FSRs). The sole of each foot is equipped with four FSRs.
4. Evolutionary Optimization
Optimization of the hopping motion is formulated as a constrained optimization problem to generate the desired output signal from the CPG, and ensure a stable and efficient hopping motion of the humanoid robot. To solve this problem, the objective function is designed, along with the equality constraints. To generate the desired output signal from the CPG, the time period of the trajectory generated by the evolutionary optimized CPG should satisfy the equality constraints on the flight and support times while hopping. Note that the trajectory generated by the evolutionary optimized CPG oscillates around zero. When the magnitude of the trajectory generated by the evolutionary optimized CPG is positive, the corresponding time
T
_{p}
should be equal to the flight time of the hopping,
T
_{flight}
. In contrast, when the magnitude is negative, the time
T
_{n}
should be equal to the support time
T
_{support}
. This is because the vertical COM trajectory should move up during the flight phase and down during the support phase. These constraints make the magnitude of the trajectory positive and negative during the flight and support phases, respectively. When the magnitude of the trajectory reaches the maximum value, the corresponding time
T
_{max}
should be equal to half of
T
_{flight}
. Similarly, when it reaches the minimum value, the time
T
_{min}
should be equal to half of
T
_{support}
. The amplitude of the trajectory obtained by the evolutionary optimized CPG at each period either increases, decreases, or remains constant with respect to time, according to
τ
and
τ
' . Since the hopping of the humanoid robot repeats the same motion, the amplitudes of the trajectory at every period should be equal to each other. If the amplitudes of the trajectory in the initial and final periods,
A
_{i}
and
A
_{f}
, are equivalent, the amplitudes of the trajectory at every period are equal. In addition, for normalization, the amplitude of the trajectory should equal one. For stable hopping, the rocking back and forth of the humanoid robot while hopping should be minimized. In addition, the oscillation of the GRFs on the feet while hopping should be minimized. For efficient hopping, the actual flight time should be maximized.
Considering the objectives and constraints mentioned above,
c
,
τ
,
τ
' , and
α
in the neural oscillator,
A
_{flight}
and
A
_{support}
in the hopping trajectory generator,
k
_{f}
in the sensory feedback of the neural oscillator,
k
_{p}
and
k
_{d}
in the posture controller, and
k
_{vsd}
and
b
_{vsd}
in the compliance controller are optimized by TPEP to minimize the following objective function, while satisfying the equality constraints:
with
subject to constraints
where
k
_{pos}
,
k
_{grf}
,
k_{flight,1}
, and
k_{flight,2}
are scaling factors. In the objective function
f
, the first term on the righthand side is the sum of the posture errors between the desired and actual body angles of the robot while hopping. This minimizes the rocking back and forth of the robot while hopping. The second term is the sum of the difference between the GRFs and the robot’s weight while hopping. This minimizes the oscillation of the GRFs on the feet while hopping. The third term is the difference between the scaling factor and the sum of the actual flight time
while hopping. This makes the robot hop with the maximum flight time. The fourth term
P
is a penalty value, which is assigned when the robot falls down while walking, because the constrained optimization problem is a minimization problem. To solve the above constrained optimization problem, TPEP is employed. TPEP is highly suitable for problems with diverse types of constraints and gives a better result with respect to the solution accuracy, convergence stability, and computation time
[21]
.
5. Computer Simulations
 5.1 Robot model
To verify the performance of the proposed method, we used a simulated model of the smallsized humanoid platform DARwInOP, depicted in
Fig. 6(a)
. The height and mass of this platform are 45.5 cm and 2.8 kg, respectively. The front and back foot lengths from the center of the foot are 5.2 cm. The simulated model of DARwInOP was produced using Webots, which is a 3D robotics simulation software that enables users to perform physical and dynamical simulations
[22]
. In other words, the physical and dynamical characteristics of the real DARwInOP were reflected in the evolutionary optimization of the hopping motion using the simulated model of DARwInOP. The model is depicted in
Fig. 6(b)
. To measure the GRFs on the feet, the sole of each foot was equipped with four FSRs. A posture sensor, which is composed of an accelerometer, a gyro, and a complementary filter, was installed on the robot’s torso to measure the body angle of the robot.
(a) DARwInOP. (b) Simulation model.
 5.2 Evolutionary optimization results
The initial inner states and selfinhibition states
u
_{e}
,
u
_{f}
,
v
_{e}
, and
v
_{f}
were obtained from computer simulation as 0.484, 0.508, 0.240, and 0.752, respectively, in order to force the initial value of
z
_{cpg}
to zero. The connecting weights and selfinhibition weight
w
_{ef}
,
w
_{fe}
, and 𝛽 were set as 1.5, 1.5, and 2.5, respectively, to cause the phase difference between [
u
_{e}
]
^{+}
and [
u
_{f}
]
^{+}
to equal π
[20]
. The initial COM height
Z
_{c}
was set to 18.35 cm and the desired body angle of the robot was set to 5.0° at which the front and back GRFs on the foot were equal to each other. The flight time and support time were set to 0.1 s and 0.2 s, respectively. The scaling factors
k
_{pos}
,
k
_{grf}
,
k
_{flight,1}
, and
k
_{flight,2}
were set as 10.0, 0.007, 1000.0 and 100.0, respectively, to make the scales of the terms in the objective function similar, which ensures similar priorities for the three objectives in the hopping motion. That is, the hopping motion was optimized with similar priorities for the minimization of the rocking back and forth of the robot, the minimization of the oscillation of the GRFs on the feet, and the maximization of the actual flight time while hopping.
P
was set to +∞. The population size and the number of generations for TPEP were set to 25 and 200, respectively.
Fig. 7
shows the variation of the objective function value with respect to the number of generations during the evolutionary optimization using the simulation model of the DARwInOP. The evolutionary optimization was executed on PC with 4.0 GHz quadcore processor and it took about 7.5 hours. The optimized parameters afforded by TPEP are given in
Table 1
. Consequently,
T
_{p}
and
T
_{n}
were obtained as 0.1 s and 0.2 s, respectively, and were equal to the flight and support times
T
_{flight}
and
T
_{support}
, respectively.
T
_{max}
and
T
_{min}
were obtained as 0.05 s and 0.1 s, respectively, and were equal to half of
T
_{flight}
and
T
_{support}
, respectively.
A
_{i}
and
A
_{f}
had the same value of 1.0 cm.
Fig. 8
shows the vertical COM trajectory of the humanoid robot for the hopping motion generated by the evolutionary optimized CPG.
Variation of objective function value with respect to the number of generations.
Optimized parameters generated by TPEP
Optimized parameters generated by TPEP
Vertical COM trajectory of humanoid robot for hopping motion, generated by evolutionary optimized CPG.
 5.3 Hopping simulation results
Dynamic hopping simulations were performed to verify the proposed approach.
Fig. 9
shows the posture error trajectory between the desired and actual body angles of the robot while hopping without and with the posture controller. At this time, the sensory feedback in the CPG and the compliance controller were working. As seen in the figure, the posture error gradually increased without the posture controller, and the robot eventually fell down. On the other hand, with the posture controller, the posture error was minimized by the evolutionary optimization and it varied between 2.0° and 2.0° while hopping. Thus, the robot was able to maintain its balance while hopping because of the posture controller.
Posture error trajectory between desired and actual body angles of robot while hopping: (a) without and (b) with posture controller.
The measured GRF trajectory while hopping without and with sensory feedback in the CPG can be examined in
Fig. 10.
During this simulation, the posture and compliance controllers were working. As shown in the figure, without sensory feedback in the CPG, there were two large peaks at the beginning and end of the support phase. The first peak was caused by the impact at touchdown, and the second peak came from the impact at liftoff. Because of these peaks, the GRF oscillated during the support phase, and the sum of the differences between the GRFs and the robot’s weight while hopping,
f
_{grf}
, was 86628.45 N for fifty hopping steps. On the other hand, with sensory feedback in the CPG, the peak at the beginning of the support phase was relatively reduced compared with the result without sensory feedback in the CPG. In addition, the peak at the end of the support phase was almost entirely removed, and consequently, the oscillation of the GRFs on the feet while hopping was minimized (
f
_{grf}
=69347.14 N for fifty hopping steps).
Measured GRF trajectory while hopping: (a) without and (b) with sensory feedback in CPG.
Fig. 11
shows snapshots of the hopping simulation. As shown in the figure, the humanoid robot was able to hop successfully, with an actual flight time of 0.095 s. The actual flight time was maximized and was almost equal to the desired flight time of 0.1 s. In addition, the hopping simulations on the inclined terrain were performed. As a result, the humanoid robot was able to hop on the inclined terrain and the allowable inclination was from 3.0° to 6.0°. Because the hopping motion was optimized on the flat terrain, the allowable inclination was limited.
Snapshots of hopping simulation: (a) Beginning of support phase; (b) Support phase; (c) Liftoff; (d) Flight phase; (e) Touchdown.
6. Conclusion
The main contribution of this paper is a novel evolutionary optimization approach that can be applied to the optimal hopping of humanoid robots. In the proposed approach, a hopping trajectory generation method by the CPG with sensory feedback was devised. Moreover, a hopping controller composed of a posture controller and a compliance controller was utilized for stable hopping. The proposed approach formulated the hopping motion as a constrained optimization problem, which was successfully solved by TPEP. The effectiveness of the proposed approach was demonstrated through computer simulations. The simulation results indicate that the proposed approach enables a humanoid robot to hop with minimum posture error, minimum oscillation of the GRFs on the feet, and maximum flight time.
Acknowledgements
This work was supported by the new faculty research fund of Ajou University.
BIO
YoungDae Hong received the B.S., M.S., and Ph.D. degrees in electrical engineering from KAIST, Daejeon, Korea, in 2007, 2009, and 2013 respectively. Since 2014, he has been with the department of electrical and computer engineering, Ajou University, Suwon, Korea, where he is currently an Assistant Professor. His current research interests include humanoid robotics, especially in bipedal walking pattern generation, footstep planning, multi/single objective evolutionary optimization, and biologically inspired control.
Sakagami Y.
,
Watanabe R.
,
Aoyama C.
,
Matsunaga S.
,
Higaki N.
,
Fujimura K.
2002
“The intelligent ASIMO: System overview and integration,”
Proc. IEEE/RSJ Int. Conf. Intell. Robots Syst.
2478 
2483
Akachi K.
,
Kaneko K.
,
Kanehira N.
,
Ota S.
,
Miyamori G.
,
Hirata M.
,
Kajita S.
,
Kanehiro F.
2005
“Development of humanoid robot HRP3P,”
Proc. IEEERAS Int. Conf. Humanoid Robots
50 
55
Hong Y.D.
,
Kim J.H.
2013
“3D command statebased modifiable bipedal walking on uneven terrain,”
IEEE/ASME Trans. Mechatron.
18
(2)
657 
663
DOI : 10.1109/TMECH.2012.2182777
Hong Y.D.
,
Lee B.J.
,
Kim J.H.
2011
“Command statebased modifiable walking pattern generation on an inclined plane in pitch and roll directions for humanoid robots,”
IEEE/ASME Trans. Mechatron.
16
(4)
783 
789
DOI : 10.1109/TMECH.2010.2089530
Hong Y.D.
,
Lee B.J.
2015
“Experimental study on modifiable walking pattern generation for handling infeasible navigational commands,”
J. Elect. Eng. Technol.
(to be published)
Kajita S.
,
Kaneko K.
,
Morisawa M.
,
Nakaoka A.
,
Hirukawa H.
2007
“ZMPbased biped running enhanced by toe springs,”
Proc. IEEE Int. Conf. Robot. Autom.
3963 
3969
Kajita S.
,
Nagasaki T.
,
Kaneko K.
,
Hirukawa H.
2007
“ZMPbased biped running control,”
IEEE Robot. Autom. Mag
14
(2)
63 
72
DOI : 10.1109/MRA.2007.380655
Cho B.
,
Kim J.
,
Oh J.
2011
“Online balance controllers for a hopping and running humanoid robot,”
Adv. Robot.
25
(910)
1209 
1225
DOI : 10.1163/016918611X574687
Ugurlu B.
,
Kawamura A.
2010
“ZMPbased online jumping trajectory generation for a onelegged robot,”
IEEE Trans. Ind. Electron.
57
(5)
1701 
1709
Ugurlu B.
,
Kawamura A.
2014
“On the backwards problem of legged robots,”
IEEE Trans. Ind. Electron.
61
(3)
1632 
1634
DOI : 10.1109/TIE.2013.2259776
Ugurlu B.
,
Saglia J. A.
,
Tsagarakis N. G.
,
Morfey S.
,
Caldwell D. G.
2014
“Bipedal hopping pattern generation for passively compliant humanoids: exploiting the resonance,”
IEEE Trans. Ind. Electron.
61
(10)
5431 
5443
DOI : 10.1109/TIE.2014.2300060
Han K.H.
,
Kim J.H.
2002
“Quantuminspired evolutionary algorithm for a class of combinatorial optimization,”
IEEE Trans. Evol. Comput.
6
(6)
580 
593
DOI : 10.1109/TEVC.2002.804320
Han K.H.
,
Kim J.H.
2004
“Quantuminspired evolutionary algorithms with a new termination criterion, Hε gate, and two phase scheme,”
IEEE Trans. Evol. Comput.
8
(2)
156 
169
DOI : 10.1109/TEVC.2004.823467
Hong Y.D.
,
Park C.S.
,
Kim J.H.
2014
“Stable bipedal walking with a vertical center of mass motion by an evolutionary optimized central pattern generator,”
IEEE Trans. Ind. Electron.
61
(5)
2246 
2355
Park C.S.
,
Hong Y.D.
,
Kim J.H.
2014
“Evolutionary optimized central pattern generator for stable modifiable bipedal walking,”
IEEE/ASME Trans. Mechatron.
19
(6)
1374 
1383
DOI : 10.1109/TMECH.2013.2281193
Hong Y.D.
,
Kim Y.H.
,
Han J.H.
,
Yoo J.K.
,
Kim J.H.
2011
“Evolutionary multiobjective footstep planning for humanoid robots,”
IEEE Trans. Syst. Man. Cybern. C, Appl. Rev.
41
(4)
520 
532
DOI : 10.1109/TSMCC.2010.2063700
Hong Y.D.
,
Kim J.H.
2012
“An evolutionary optimized footstep planner for the navigation of humanoid robots,”
Int. J. Humanoid Robot.
9
(1)
Park I.W.
,
Lee K.B.
,
Kim J.H.
2012
“Multiobjective evolutionary algorithmbased optimal posture control of humanoid robots,”
Proc. IEEE Congr. Evol. Comput.
1 
7
Taga G.
1995
“A model of the neuromusculoskeletal system for human locomotion,”
Biol. Cybern.
73
(2)
97 
111
DOI : 10.1007/BF00204048
Matsuoka K.
1987
“Mechanisms of frequency and pattern control in the neural rhythm generators,”
Biol. Cybern.
56
(5)
345 
353
Kim J.H.
,
Myung H.
1997
“Evolutionary programming techniques for constrained optimization problems,”
IEEE Trans. Evol. Comput.
1
(2)
129 
140
DOI : 10.1109/4235.687880
Michel O.
2004
“Cyberbotics Ltd. WebotsTM: Professional mobile robot simulation,”
Int. J. Adv. Robot. Syst.
1
(1)
39 
42