In order to accomplish complex navigational commands, humanoid robot should be able to modify its walking period, step length and direction independently. In this paper, a novel walking pattern generation algorithm is proposed to satisfy these requirements. Modification of the walking pattern can be considered as a transition between two periodic walking patterns, which follows each navigational command. By assuming the robot as a linear inverted pendulum, the equations of motion between ZMP(Zero Moment Point) and CM(Center of Mass) state is easily derived and analyzed. After navigational command is translated into the desired CM state, corresponding CM motion is generated to achieve the desired state by using simple ZMP functions. Moreover, when the command is not feasible, feasible command is alternated by using binary search algorithm. Subsequently, corresponding CM motion is generated. The effectiveness of the proposed algorithm is verified by computer simulation.
1. Introduction
In the field of humanoid research, control algorithm of walking pattern plays a significant role. There were approaches based on batch type processed to predesign the walking trajectory and/or control policy. These approaches commonly needed iterative computation to design either entire trajectories or piecewise trajectories over some time interval. As the computing power grows, these approaches became implementable and many successful results were produced
[1

3]
. To implement the walking pattern in real time, reduced dynamic model such as a single linear inverted pendulum was adopted
[4
,
5]
. In addition, there were some approaches to reduce the complexity of the equation of motion by assuming that the ZMP(Zero Moment Point) trajectory has a specific form
[6

9]
. In several methods, explicit walking trajectories were not used. These were mainly focused on a sensory feedback algorithm with several intuitive rules
[10
,
11]
.
Improving the ability to walk according to the navigational commands is as important as improving the stability. Especially, this is important to deal with navigation within a complex environment
[12
,
13]
. In this paper, to generate walking pattern which satisfies the complex navigational commands, such as walking period, step length and walking direction, a novel algorithm is introduced and resolves the following key points:
● Generation of Periodic Walking Patterns: Ability to generate a periodic walking pattern from the given navigational command.
● Transition between Two Walking Patterns: Ability to modify a walking pattern by the transition from current pattern to the desired one.
● Decision on Feasibility about Navigational Commands: Ability to judge whether or not a navigational command is feasible.
In order to address these subjects, analytical solutions of the equation of motion for the simplified dynamics are utilized. In addition, by adopting the ZMP variation scheme, the proposed algorithm includes the ability to modify the walking pattern without any extra step for adjusting the CM motion. Note that the proposed algorithm is focused on the feedforward pattern generation. To make robot walk stably, it is essential to adopt some feedback controller sintroduced in
[14

17]
.
The iteration based method such as a preview control scheme utilizes the reference ZMP trajectory as a preview data to give locally optimized walking pattern
[3]
. In this method, navigational command is implicitly utilized to design the reference ZMP trajectory. Since the proposed method utilizes the predefined ZMP functions on the convex hull within the sole, however, the walking patterns are derived from a navigational command explicitly as a closedform
[18]
. Consequently, the generated walking patterns satisfy the navigational command exactly if it is feasible. Moreover, it provides a criterion which indicates the navigational command is reachable or not from the current walking state. In this paper, the previous work is further developed to handle the infeasible navigational command by introducing the binary search algorithm.
This paper is organized as follows. In Section 2, walking motion is analyzed in the view of periodic motion and transition between the different periodic motions. Desired goal state for the transition,
desired walking state
is derived in Section 3. The ZMP variation scheme is reviewed in Section 4. Feasibility of the navigational command is considered in Section 5. Section 6 presents example walking pattern using computer simulation. Conclusion is provided in Section 7.
2. Periodic Nature of Walking Pattern
To perform a complex navigational task, the algorithm requires a minimal command set that allows for configuration of the walking pattern. The set of parameters includes single and double supporting times, forward and side step lengths, and walking directions. This instructional set is defined as a
command state
.
Definition 1 Command State(
CS
) is a minimal set to represent navigational commands as follows:
where
T_{sl}
,
T_{dl}
,
F_{l}
,
S_{l}
and
θ_{l}
represent single support time, double support time, forward step length, side step length and walking direction, respectively, for the left side. Similarly,
T_{sr}
,
T_{dr}
,
F_{r}
,
S_{r}
and
θ_{r}
are for the right side. Note that the side step lengths in the lateral plane are for sideways movement.
Since a
walking
is a periodic motion, it can be represented as a
limit cycle
. When a certain
CS
is specified, the consequent walking pattern is determined. In other words,
walking
according to a given
C
can be analyzed as a movement of state along the periodic orbit which stands for the
walking pattern
. Therefore, in order to handle complex navigational commands, corresponding walking pattern should be figured out.
Fig. 1
describes this periodic walking pattern conceptually. Dashed line and dashdot line represent two different walking patterns, A and B conceptually. When the new navigational command,
c
_{B}
, is given during a robot walks according to the current navigational command,
c
_{A}
, new walking pattern B is designed according to the
c
_{B}
. Subsequently, the robot tries to trans it from the current state, which is depicted as a triangle, to the desired state on the new walking pattern B. In other words, when
CS
is changed into
c
_{B}
from
c
_{A}
, a corresponding walking pattern B is resolved. Subsequently, the current state travels to the desired one thereby the walking pattern is modified.
Transition between two different walking patterns.
where
c
(
t
) and
s
(
t
) are abbreviation of cosh (
t/T_{c}
) and sinh (
t/T_{c}
) with a time constant
and a constant height
Z_{c}
, respectively, and
p
(
t
) and
q
(
t
) represent the ZMP function on the sagittal and the lateral plane, respectively, lastly, is convolution operator. In spite of conciseness, Eq. (1) characterizes dominant dynamics as well as it separate sagittal and lateral motion.
Note that when the homogeneous solution part in Eq. (1) is only used, namely, the ZMP is assumed that it stays at the center of foot polygon, the CM motion is predetermined by given time,
t
. Consequently, it is unmodifiable throughout the single support phase. This equivalently means that the humanoid robot cannot accelerate or decelerate its CM. Therfore it can not vary its step length, walking period and direction in the same manner that humans do. The particular solution part, however, relaxes this restriction. By allowing a variation of ZMP over the convex hull on the bounded foot region, it is possible to change the position and the velocity of the CM independently throughout the single support phase.
For the sake of convenience, a state of walking pattern at a given time is defined as a
Walking State
(
WS
). Since in the linear inverted pendulum model, the mass of the robot is considered as a point mass, its walking motion can be represented in terms of the position and the linear velocity. Consequently, the position and the velocity of the CM become the
WS
as follows:
Definition 2 Walking State (
WS
) for the linear inverted pendulum represents the CM state as follows:
Note that the velocity term is weighted with the time constant,
T_{c}
. From now on, walking motion is analyzed in terms of the
WS
.
3. Desired Walking State
Modification of a walking pattern can be characterized into two parts: generation of another periodic walking pattern which satisfies a given new
CS
and transition of
WS
from a current state to a desired state on the new trajectory.
Fig. 3
represents two different walking patterns and transitions between them, where the limit cycle means a new walking pattern which is generated by the new
CS
. The triangle and the circle represent current and
desired WS
, respectively. Lastly, solid line from the triangle to the circle indicates transitional walking pattern. As shown in
Fig. 3 (a)
, transition from the current state can be accomplished in various ways. In other words, a lot of
desired WS
and transitional walking patterns are possible. Therefore it arise an optimization issue. In practical manner,
desired WS
is restricted to a final state of single support phase which is depicted as a circle on a solidline for the single support phase. While a dashedline means double support phase on walking pattern B as shown in
Fig. 3 (b)
. Moreover, it is assumed that the ZMP variation carries out only during the transition. Consequently,
WS
on the limit cycle is characterized by only the homogeneous solution part of Eq. (1). Using this strategy, the
desired WS
is uniquely determined from a given
CS
and a
current WS
as shown in
Fig. 4
which describes a periodic walking pattern according to the
CS
.
Transitions of WS. (a) Various possible transitions. (b) Proposed transition strategy
Foot print of steady walking.
In the figure,
and subscripts,
l_{i(f)}
and
r_{i(f)}
, mean left initial(final) and right initial(final) state of the single support, respectively. Lastly,
θ
implies walking direction.From Eq. (1), motions of the single support phase are derived as follows:
As mentioned above, during the periodic motion ZMP does not vary and stays at the center of foot polygon. Consequently, the motion of equation is characterized with only homogeneous part. Also, double support motions which are controlled with constant velocity are obtained as follows:
where
By eliminating the
initial WS
from Eq. (2) and (3), homogeneous solutions of the steady motion are given as follows:
Using the
Kronecker Product
, Eq. (4) is transformed into the familiar linear equation form as follows:
where
Finally, solving Eq. (5) for the final
WSs
, 𝛇
_{lf}
and 𝛇
_{rf}
, desired
WSs
are given as follows:
Eq. (6) expresses the mapping relationship between the
CS
and the
desired
WS
. Note that the information of the
CS
is involved in the matrix
A
* and
B
*. Whenever the
CS
is changed, it translates into the
desired WS
form. Subsequently, 𝛇
_{lf}
or 𝛇
_{rf}
becomes the
desired WS
for the left or right support phase, respectively.
4. ZMP Variation Scheme
After the
desired WS
is calculated, it is necessary to adjust the ZMP trajectory to transfer the
current WS
to the desired one. Via the variation of the ZMP with closedform function, it is possible to modify the walking pattern as intended by the
CS
. In a practical manner, a constant function(
Fig. 5 (a)
) and a step function(
Fig. 5 (b)
) are proposed for sagittal motion and lateral motion, respectively. Detailed analysis of these two ZMP functions is covered in the previous work
[18]
.
Proposed ZMP functions. (a) Constant function for the sagittal motion. (b) Step function for the lateral motion.
The control parameters (
T
,
P
,
T_{sw}
and
Q
) which characterize the proposed ZMP functions are now solved to ensure that the desired
WS
is attainable.
 4.1 Sagittal motion
By substituting
t
=
T
and
p(t)
=
P
into Eq. (1), following solutions are obtained:
where the subscripts
c
and
d
and represent
current
and
desired
state, respectively. Note that
T
represents the requiredtransition time from the
current WS
to the
desired WS
.
 4.2 Lateral motion
Since the homogeneous part of Eq. (1) for the lateral motion is determined by the
current WS
and the transition time
T
, it is only necessary to consider the particular part. Similarly to the sagittal motion, by letting
the particular solution of the lateral equation of motion is derived. Solving this for the unknowns,
T_{sw}
and
Q
, gives
where
Using Eq. (7) and Eq. (8), control parameters are directly obtained from the current and the
desired WS
. Subsequently,
WS
is transited by the ZMP variation.
5. Modification of Infeasible Command State and Desired Walking State
As explained in the previous section, a
desired WS
is achieved by the ZMP variation. Due to the several kinematical and/or dynamical constraints, however, sometimes
desired WS
is not attainable. For instance, when the magnitude of the ZMP function for the sagittal and/or lateral motion is larger or smaller than the maximum or the minimum limit, there is no way to achieve the
desired WS
. In this case, the
WS
should be substituted to the nearest one.This is illustrated in
Fig. 6
, where the empty circle means an infeasible
desired WS
whereas the solid circle means a feasible desired
WS
substituted from the original one.
Modification of desired WS corresponding to infeasible CS. (a) Infeasibility of desired WS. (b) New walking pattern from the modified CS
Since the substituted
WS
is not on the desired walking pattern B (see
Fig. 6 (a).
), it is necessary to recompute a new walking pattern B* through the new
WS
(see
Fig. 6 (b).
). To do so, however, modification of the original
CS
has to be preceded because the walking pattern is dependent on the
CS
. Subsequently, the
current WS
can travel to the replaced feasible
WS
on the new walking pattern.
In this paper, infeasible
CS
and
desired WS
are simultaneously modified by using
Binary Search Algorithm
as shown in Algorithm 1, where subscripts
p
and
d
represent
previous
and
desired
state, respectively, and
m
and
f
represent
modified
and
feasible
state, respectively, lastly,
f
(·) means a function gives a
desired WS
from a
CS
by Eq. (6). After initialization,
CS
is updated as a mean value between previous and desired
CS
. Note that the
modified CS
is always feasible because the current
WS
is on the walking pattern generated by the previous
CS
. Subsequently, if the modified
desired WS
is feasible then the modified
desired WS
moves to the desired one, else it moves to the previous one until the iteration reaches to the maximum. This
Binary Search Algorithm
is simple and intuitive. Moreover it is sufficiently fast to execute in real time.
6. Example Walking Pattern
The proposed algorithm was simulated to verify the effectiveness with several example walking patterns including
forward walking
,
backward walking
,
sideways walking
, and
turning motion
. Parameters used in simulation are shown in
Table 1
, where
Z_{c}
means constant CM height in the linear inverted pendulum model (see
Fig. 2
.) and,
P_{max(min)}
and
Q
_{max(min)}
represent maximum(minimum) ZMP variation region for sagittal and lateral motion, respectively. Note that all length units are given in meters.
Simulation parameters.
Linear inverted pendulum model.
 6.1 Forward walking
Forward walking patterns were realized from the following
CS
list (see the Definition 1):

InitialCS,

c= [0.4 0.4 0.1 0.1 0.2 0.2 0.2 − 0.2 0.0° 0.0°]T

After the 2ndstep,

c= [0.3 0.3 0.05 0.05 0.4 0.4 0.2 − 0.2 0.0° 0.0°]T

After the 5thstep,

c= [0.4 0.4 0.1 0.1 0.2 0.2 0.2 − 0.2 0.0° 0.0°]T

After the 6thstep,

c= [0.4 0.4 0.1 0.1 0.0 0.0 0.2 − 0.2 0.0° 0.0°]T
where time and length units are given in seconds and meters, respectively, and angle unit is given in degree. Note that the
CS
after the k
^{th}
step is not delivered until the double support phase of the k
^{th}
step is finished. In other words, the proposed algorithm does not use preview data. In the all example walking patterns during this simulation, robot was commanded to stop after accomplishing the final
CS
.
Fig. 7
shows the walking pattern generated by the proposed method. The solid curve and the rectangle indicate the CM trajectory and the foot polygon, respectively. The circle and the number mean the center of foot and the step number, respectively. The initial foot positions are (0, 0) for the right foot and (0, 0.2) for the left foot, respectively. As the
CS
list intended, robot lengthened its stride after the 2
^{nd}
step and shortened after the 5
^{th}
step. Although the robot was commanded to lengthen its step length as 0.4m after the2
^{nd}
step, however, the step length is increased smoothly for 0.3108(= 0.7108 — 0.4) m at the 3
^{rd}
step and 0.3792(= 1.09 — 0.7108) m at the 4
^{th}
step, respectively. It finally achieved the commanded step length, 0.4(= 1.49 — 1.09) m, at the 5
^{th}
step. Also it can be seen that similar result is observed at the 6
^{th}
step. These were caused by that the infeasible
CS
s delivered after the2
^{nd}
and the 5
^{th}
steps were substituted for the relaxed
CS
which is thereby feasible.
Example pattern (forward walking).
 6.2 Backward walking
Backward walking patterns were realized from the following
CS
list:

Initial CS,

c= [0.4 0.4 0.1 0.1 0.2 0.2 0.2 −0.2 0.0° 0.0°]T

After the 2ndstep,

c= [0.4 0.4 0.1 0.1 −0.1 −0.1 0.2 −0.2 0.0° 0.0°]T

After the 5thstep,

c= [0.4 0.4 0.1 0.1 0.0 0.0 0.2 −0.2 0.0° 0.0°]T
Fig. 8
shows the backward walking pattern generated from the
CS
list. According to the
CS
list, walking patterns were generated to walk backward and stop after the 5
^{th}
step. Similar with the forward walking case, although the commanded backward step length was 0.3 m after the 2
^{nd}
step, it is not satisfied until the 4
^{th}
step. It is finally achieved for the step length at the 4
^{th}
step.
Example pattern (backward walking).
 6.3 Sideways walking
Sideways walking patterns were realized from the following
CS
list:

Initial CS,

After the 2ndstep,

After the 5thstep,

c= [0.4 0.4 0.1 0.1 0.2 0.2 0.2 −0.2 0.0° 0.0°]T

After the 6thstep,

c= [0.4 0.4 0.1 0.1 0.0 0.0 0.2 −0.2 0.0° 0.0°]T
Fig. 9
shows the sideways walking pattern. According to the
CS
list, side step lengths are designed as different as 0.2 m and −0.4 m for the left and the right step, respectively. Via the 3
^{rd}
step, which has a small difference between the commanded and the generated side step lengths due to the relaxation of the infeasible
CS
, subsequent footsteps were followed the given
CS
s accurately.
Example pattern (sidewayswalking).
 6.4 Turning motion
Turning motions were realized from the following
CS
list:

Initial CS,

= [0.4 0.4 0.1 0.1 0.2 0.2 0.2 −0.2 0.0° 0.0°]T

After the 2ndstep,

= [0.4 0.4 0.1 0.1 0.2 0.2 0.2 −0.2 0.0° −60.0°]T

After the 5thstep,

= [0.4 0.4 0.1 0.1 0.2 0.2 0.2 −0.2 0.0° 0.0°]T

= [0.4 0.4 0.1 0.1 0.0 0.0 0.2 −0.2 0.0° 0.0°]T
Fig. 10
shows the turning motion. After the 2
^{nd}
step, it started to turn 30° to the right and stopped after the6
^{th}
step.
Example walking (turning motion).
 6.5 Complex walking
Complex walking patterns including forward, backward, sideways and turning motion were realized from the following
CS
list:

Initial CS,

c= [0.4 0.4 0.1 0.1 0.2 0.2 0.2 − 0.2 0.0°0.0°]T

After the 2ndstep,

c= [0.4 0.4 0.1 0.1 0.2 0.2 0.2 − 0.2 0.0° − 30.0°]T

After the 4ndstep,

c= [0.4 0.4 0.1 0.1 − 0.2 − 0.2 0.4 − 0.2 0.0° − 30.0°]T

After the 7thstep,

c= [0.4 0.4 0.1 0.1 − 0.2 − 0.2 0.2 − 0.2 0.0° 0.0°]T

After the 8thstep,

c= [0.4 0.4 0.1 0.1 0.0 0.0 0.2 − 0.2 0.0° 0.0°]T
Fig. 11
shows the generated walking pattern. After the 2
^{nd}
step, the wakling direction was changed to the right. After the 4
^{th}
step, it started to walk backward with different side step length. Subsequently, it stopped after the 8
^{th}
step.
Example pattern (complex walking).
7. Conclusion
The modifiable walking pattern generation algorithm was proposed. By varying the ZMP(Zero Moment Point) while in a single support phase, it is possible to move the current walking state, the position and the velocity of the CM(Center of Mass), to the desired one. Consequently, the humanoid robot could change its step length, walking period and direction, independently. In addition, when the navigational command is infeasible, it is substituted for the relaxed one by the binary search algorithm and thereby becomes feasible. As a result, walking pattern could be successfully generated even though the command was infeasible. Since the proposed method utilizes the closedform functions and simple search algorithm to generate walking pattern, it is possible to compute in real time.
Acknowledgements
This work was supported by Unmanned Technology Research Centre (UTRC).
BIO
BumJoo Lee received the B.S. degree in electrical engineering from Yonsei University, Seoul, Korea, in 2002, and the M.S. and Ph.D. degrees in electrical engineering from Korea Advanced Institute of Science and Technology (KAIST), Korea, in 2004 and 2008, respectively. Since 2012, he has been with the Department of Electrical Engineering, Myongji University, Korea, where he is currently an Assistant Professor. His research interests include the areas of Humanoid Robotics, especially in motion planning and control algorithm.
Kab Il Kim graduated Seoul National University (SNU) for B.S. in 1979, Korea Advanced Institute of Science and Technology (KAIST) for M.S. in 1981, and Clemson University in South Carolina (USA) for Ph.D. in 1990, respectively. Since 1991, he has been with the Department of Electrical Engineering, Myongji University, Korea, where he is currently a Professor. He studied Two Arm Coordination, Load Distribution, and Humanoid Robotics as a main research topic. On the practical aspect, he is currently interested in the area of Field Robotis and Military robotics.
Liu C.
,
Atkeson C.
2012
“Biped walking control using a trajectory library,”
robotica
Whitman E.
,
Atkeson C.
2009
“Control of a walking biped using a combination of simple policies,”
in IEEE/RAS Int. Conf. Humanoid Robot
Paris, France
520 
527
Kajita S.
,
Kanehiro F.
,
Kaneko K.
,
Fujiwara K.
,
Harada K.
,
Yokoi K.
,
Hirukawa H.
2003
“Biped walking pattern generation by using preview control of zeromoment point,”
in Proc. IEEE Int. conf. Robot. Autom.
Taipei, Taiwan
14 
19
Kajita S.
,
Kanehiro F.
,
Kaneko K.
,
Fujiwara K.
,
Yokoi K.
,
Hirukawa H.
2002
'A realtime pattern generator for Biped walking'
Proc.IEEE Int. Conf. Robot. Autom.
Washington, DC
1
31 
37
Sugihara T.
,
Nakamura Y.
,
Inoue H.
2002
“Realtime humanoid motion generation through ZMP manipulation based on inverted pendulum control,”
in Proc. IEEE Int. Conf. Robot. Autom.
Washington, DC
2
1404 
1409
Nagasaka K.
,
Kuroki Y.
,
Suzuki S.
,
Itoh Y.
,
Yamagushi J.
2004
“Integrated motion control for walking, jumping and running on a small bipedal entertainment robot,”
in EEE Int. Conf. robot. Autom.
New Orleans, LA
4
3189 
3194
Harada K.
,
Kajita S.
,
Kaneko K.
,
Hirukawa H.
2004
“An analytical method on realtime gait planning for a humanoid robot,”
in Proc. IEEERAS/RSJ Int. Conf. Humanoid Robots
Los Angeles, CA
2
640 
655
Sugihara T.
,
Nakamura Y.
2005
“A fast online gait planning with boundary condition relazation for humanoid robots,”
in Proc. IEEE Int. Conf. Robot. Autom.
Barcelona, Spain
305 
310
Kurazume R.
,
Hasegawa T.
,
Yoneda K.
2003
“The sway compendation trajectory for a biped robot,”
in Proc. IEEE int. Conf. Robot. Autom.
Taipei, Taiwan
1
925 
931
Yin KK.
,
Loken K.
,
Panne M.
2007
“Simbicon: simple biped locomotion control,”
ACM Trans. on Graphics
26
(3)
Yin KK.
,
Coros S.
,
Beaudoin P.
,
Panne M.
2008
“Continuation method for adapting simulated skills,”
ACM Trans. on Graphics
27
(3)
Michel P.
,
Chestnutt J.
,
Kagami S.
,
Nishiwaki K.
,
Kuffner J.
,
Kanade T.
2006
“Online environment reconbstruction for biped navigation,”
in Proc. IEEE Int. Conf. Robot. Autom.
Orlando, FL
3089 
3094
Chestnutt J.
,
Michel P.
,
Nishiwaki N.
,
Kuffner J.
,
Kagami S.
2006
“An intelligent joystic for biped control,”
in Proc. IEEE Int. conf. Robot. Autom.
Orlando, FL
860 
865
Kim Y.D.
,
Lee B.J.
,
Ryu J.H.
,
Kim J.H.
2007
“Landing force control for humanoid robot by time domain passivity approach,”
IEEE Trans. Robot.
23
(6)
1294 
1301
DOI : 10.1109/TRO.2007.906250
Hashimoto K.
,
Sugahara Y.
,
Sunazuka H.
,
Tanaka C.
,
Ohta A.
,
Kawase M.
,
Lim H. O.
,
Takanish A.
2006
“Biped landing pattern modification method with nonlinear compliance control,”
in Proc. IEEE Int. conf. Robot. Autom.
Orlando, FL
1213 
1218
Lim S.
,
Oh S.N.
,
Kim K.I.
2012
'Balance control for biped walking robotsusing only zeromomentpoint position signal'
Electronics Letters
48
(1)
19 
20
DOI : 10.1049/el.2011.3091
Lee B.J.
,
Stonier D.
,
Kim Y.D.
,
Yoo J.K.
,
Kim J.H.
2008
'Modifiable Walking Pattern of a Humanoid Robot by Using Allowable ZMP Variation'
IEEE Trans. on Robotics
24
(4)
917 
925
DOI : 10.1109/TRO.2008.926859