This paper proposes novel realtime footstep planning and following methods for the navigation of humanoid robots. A footstep command is defined by a walking direction and step lengths for footstep planning. The walking direction is determined by a univector field navigation method, and the allowable yawing range caused by hardware limitation is considered. The lateral step length is determined to avoid collisions between the two legs while walking. The sagittal step length is modified by a binary search algorithm when collision occurs between the robot body and obstacles in a narrow space. If the robot body still collides with obstacles despite the modification of the sagittal step length, the lateral step length is shifted at the next footstep. For footstep following, a walking pattern generator based on a 3D linear inverted pendulum model is utilized, which can generate modifiable walking patterns using the zeromoment point variation scheme. Therefore, it enables a humanoid robot to follow the footstep command planned for each footstep. The effectiveness of the proposed method is verified through simulation and experiment.
1. Introduction
For navigation of humanoid robots in real human environments, footstep planning in such environment with obstacles is one of the most important issues in the field of humanoid robot research. Attempts to use sets of predetermined step lengths and walking patterns have been introduced
[1
,
2]
. Using A* search algorithm, several methods have computed footstep sequences in which feasible regions of foot positions were predefined, and a few foot positions were then selected as a discrete set
[3
,
4]
. In addition, by using a rapidly exploring random tree algorithm, randomized samplingbased methods have solved the complexity problem of the A* search algorithm for footstep planning
[5

7]
. However, these previous methods must precalculate the discrete set of feasible footstep positions and corresponding legjoint trajectories for footstep transition. In addition, they did not consider the elements for footstep following, such as the hardware limitation of the robot, collisions between the two legs, and collisions between the robot body and obstacles while walking. Meanwhile, an evolutionary optimization algorithm has been employed to plan the optimal footstep sequences
[8
,
9]
. However, realtime footstep planning was impossible because of the high computing power requirement of evolutionary optimization.
Therefore, the present paper proposes novel realtime footstep planning and following methods for the navigation of humanoid robots. A footstep command is defined by a walking direction and step lengths for footstep planning. The walking direction is determined by a univector field navigation method
[10]
, and the allowable yawing range due to hardware limitation is considered. The lateral step length is determined to avoid collision between the two legs while walking by maintaining the same distance between the left and right feet. The sagittal step length is predefined, and it is modified by a binary search algorithm when collision between the robot body and obstacles occurs in a narrow space. If the robot body still collides with obstacles despite the modification of the sagittal step length, the lateral step length is shifted at the next footstep. For footstep following, a walking pattern generator based on a 3D linear inverted pendulum model (LIPM)
[11]
is utilized, which can generate modifiable walking patterns using the zeromoment point (ZMP) variation scheme
[12

14]
. Therefore, it enables a humanoid robot to follow the footstep command planned for each footstep.
This paper is organized as follows. Section 2 describes the proposed footstep planning method. Section 3 presents the footstep following method, and Section 4 explains the overall procedure of the proposed method. Section 5 presents the verification of the effectiveness of the proposed method through simulation and experiment. Finally, Section 6 provides the conclusion.
2. Footstep Planning
For the footstep planning, walking direction
θ
_{r/l}
, sagittal step length
S
_{r/l}
, and lateral step length
L
_{r/l}
of the right/left swing leg are defined as a footstep command, which is expressed as follows:
The footstep command for each footstep is generated by the proposed footstep planning method.
 2.1 Determination of walking direction
A univector field navigation method is adopted to determine the walking direction. It is appropriate for execution in realtime owing to its low computing power
[10]
.
Fig. 1
shows a movetogoal univector field (MUF) that enables the robot to arrive at the goal and an avoidobstacle univector field (AUF) that makes the robot avoid obstacles. The MUF and AUF are generated by an attractive univector field and a hyperbolic spiral univector field, respectively, as follows:
Univector fields: (a) MUF; (b) AUF.
with
where
θ
_{m}
(
p
) and
θ
_{a}
(
p
) denote the angles from the
x
axis of goal
g
and the obstacle center
o
to position
p
, respectively;
φ_{h}
(
p
) denotes the hyperbolic spiral univector field;
d_{o}
,
d_{e}
, and
d_{b}
are the radius of the obstacle, the predefined radius that determines the size of the spiral, and the size of the boundary of the AUF, respectively;
ρ
_{ij}
denotes the distance between positions
i
and
j
. The + and – signs are determined according to the robot position relative to the obstacle and goal, where, – indicates a clockwise motion and + indicates a counterclockwise motion. Variable
K_{r}
determines the smoothness of the contour of the spiral.
Base position
p
_{B}
is defined as the midpoint between the left and right feet, and the walking direction at each footstep is then determined by the direction of the total univector field at base position
u
_{uf}
(
p
_{B}
) as follows:
with
where
n
is the total number of obstacles.
The walking direction determined by the univector field navigation method can exceed the allowable yawing range, which is restricted according to the hardware limitations of the robot. Thus, for footstep following in this case, the walking direction should be modified as follows:
where
θ
_{max}
and
θ
_{min}
denote the maximum and minimum allowable yawing ranges, respectively.
 2.2 Determination of step lengths
Collisions between the two legs can occur while the walking direction is changed during walking. Therefore, to solve this problem, the distance between the left and right feet should be maintained at the same value by determining the lateral step length of each footstep, as shown in
Fig. 2
, which is calculated as follows:
Modification of the lateral step length to maintain the same distance between the left and right feet.
where
f_{f}
/
f_{b}
and
f_{o}
/
f_{i}
denote the front/back foot length and outer/inner foot width from the center of the foot, respectively.
Basically, if the robot follows the footsteps planned by the univector field navigation method, obstacle collisions do not occur because the AUF prevents collision with obstacles. However, because the footsteps of the humanoid robot are discrete, the robot can still collide with obstacles in a narrow space. To solve this problem, the sagittal step length
S
_{r/l}
at each footstep is determined by a binary search algorithm, as shown in Algorithm 1, where
N
is the number of iterations. The binary search algorithm is sufficiently fast for execution in realtime because it is intuitive and simple. The robot body is simplified as a cylinder with radius
d_{r}
. The sagittal step length is initially predetermined as normal step length
S_{n}
. If the robot body collides with the obstacle, the sagittal step length is modified until collision does not occur. When the robot body still collides with the obstacle in spite of the modification of the sagittal step length, the lateral step length at the next footstep is shifted as a constant value.
3. Footstep Following
To make a humanoid robot follow the footstep command planned by the proposed footstep planning method, a walking pattern generator based on the 3D LIPM is utilized, as shown in
Fig. 3
[12

14]
. The centerofmass (COM) motion equations of the 3D LIPM is given by the ZMP functions
p
(
t
) and
q
(
t
) as follows:
3D LIPM.
where (
x_{i}
,
v_{i}
)/(
x_{f}
,
v_{f}
) and (
y_{i}
,
w_{i}
)/(
y_{f}
,
w_{f}
) denote the initial/final COM positions and velocities in the sagittal and lateral planes, respectively.
C
(
t
) and
S
(
t
) denote sinh(
t
/
T_{c}
) and cosh(
t
/
T_{c}
), respectively, where
. * denotes the convolution operator. To follow the footstep commands in which the sagittal and lateral step lengths and the walking direction are varied at every footstep, the walking pattern generator should generate modifiable walking patterns without any additional footsteps to adjust the COM motion in realtime. At the righthand side of (7), the first and second terms represent the homogeneous solution component and the particular solution component of the dynamic equation of the 3D LIPM, respectively. In this walking pattern generator, the particular solution component is utilized for the realtime ZMP variation. Itallows the ZMP to be varied over the convex hull of the bounded foot region by the ZMP functions
p
(
t
) and
q
(
t
). From the ZMP variation, the COM position and velocity can be changed throughout a single support motion. Consequently, generating modifiable walking patterns becomes possible. Note that the single and double support times for the footstep following are properly assigned as constant values. It is possible because the walking pattern generator is able to generate the modifiable walking patterns in which the sagittal and lateral step lengths, and the walking direction are independently changed while maintaining the same walking period at each footstep.
The footstep command is entered into the walking pattern generator at every sampling time. Then, the desired COM position and velocity of the 3D LIPM for the footstep command are derived
[12

14]
. Because walking of the humanoid robot is a periodic motion, it can be described by identifying certain particular COM position and velocity of the 3D LIPM. At the end of each single support phase, the COM position and velocity are identical. Thus, they are regarded as the desired COM position and velocity of the 3D LIPM. It is assumed that the COM position and velocity are in a steady state and that the ZMP does not vary during the conversion of the footstep command into the desired COM position and velocity of the 3D LIPM. For the conversion of the footstep command into the desired COM position and velocity, one period of the walking configuration is considered in a steady state. The walking configuration can be fully described by the initial or final COM position and velocity of the 3D LIPM for both the left and right support phases because the COM position and velocity is in a steady state with no ZMP variation. Next, the COM trajectory that satisfies the desired COM motion is generated by the COM motion equations, and every legjoint trajectory is provided by inverse kinematics. As a result, the walking pattern generator generates the walking patterns that satisfy the footstep command.
4. Overall Procedure
The overall procedure of the proposed footstep planning and following methods is summarized as shown in
Fig. 4
, where
P
denotes the pelvis length of the humanoid robot.
ρ_{pBg}
and
d
_{g}
denote the distance between the base position and goal, and the radius of the goal, respectively. For footstep planning, parameters
d_{e}
,
d_{b}
, and
K_{r}
in the AUF are set, and the base position is initialized to (
S_{n}
,
P
/2). At each footstep, sagittal step length
S
_{r/l}
is set as normal step length
S
_{n}
, and lateral step length
L
_{r/l}
is set to zero. Walking direction
θ
_{r/l}
is determined by the direction of
u
_{uf}
(
p
_{B}
) and modified by (5) when it exceeds the allowable yawing range. Lateral step length
L
_{r/l}
is determined by (6) for the same distance between the left and right feet. Sagittal step length
S
_{r/l}
is changed by the binary search algorithm when collision occurs between the robot body and the obstacle until the robot body does not collide with the obstacle anymore. If collision still occurs, the lateral step length at the next footstep
L
_{l/r}
is shifted as constant step length
L
_{s}
. For the footstep following, the footstep command determined by the proposed footstep planning method at each footstep is entered into the walking pattern generator, which generates the legjoint trajectories for the footstep command. Then, the robot walks with the constant walking period following the planned footsteps. If the robot arrives at the goal, the sagittal and lateral step lengths are set to zero, and walking is terminated. Consequently, the proposed method can plan the footsteps in realtime and simultaneously make the robot follow the planned footsteps without precalculating the discrete set of feasible footstep positions and corresponding trajectories of every legjoint for the footstep transition.
Flowchart of the overall procedure.
5. Simulation and Experiment
The effectiveness of the proposed method is verified through simulation and experiment using the smallsized humanoid robot platform DARwInOP, as shown in
Fig. 5(a)
. Its height and weight were 45.5 cm and 2.8 kg, respectively. It has twenty degrees of freedom (DOFs) with MX28 actuators (two DOFs for head, six DOFs for arms, and twelve DOFs for legs). As the main controller, an Intel Atom Z530 central processing unit, running Linux Ubuntu, is utilized. It communicates with the sub controller, ARM 32bit CortexM3 through universal serial bus connections. The simulated model of DARwInOP was produced using Webots, as shown in
Fig. 5(b)
, which is a 3D robotic simulation software that enables users to perform physical and dynamical simulations
[15]
.
Tables 1
and
2
list the summary of the parameters for footstep planning and those of DARwInOP, respectively. The single and double support times were set as 0.4 sec and 0.2 sec, respectively.
(a) DARwInOP; (b) Simulation model.
Parameters for footstep planning
Parameters for footstep planning
Parameters of DARwInOP
Fig. 6
shows the footsteps planned by the proposed method in two environments. In
Fig. 6(a)
, the footsteps were planned in an environment with cylindrical obstacles. In
Fig. 6(b)
, rectangular obstacles were made up of several cylindrical obstacles, and the footsteps were planned in an environment with a narrow passage and a local loop. The figures show that the planned footsteps made the robot arrive at the goal without obstacle collision. The walking direction at each footstep was determined by the value within the allowable yawing range, and the lateral step length was determined to maintain the same distance between the left and right feet. In addition, for collision avoidance between the robot body and obstacles in a narrow space, the sagittal and lateral step lengths were varied. In
Fig. 6(a)
, the sagittal step length was changed six times to 1.9, 2.1, 0.0, 3.0, 0.0, and 0.0 cm at the 3
^{rd}
, 4
^{th}
, 5
^{th}
, 41
^{st}
, 42
^{nd}
, and 43
^{rd}
footsteps, respectively, by the binary search algorithm to avoid collision between the robot body and the obstacles. We note that the thick circles depict the robot body at the footstep when the sagittal step length was changed. The robot body still collided with the obstacle at the 42
^{nd}
footstep in spite of the change in the sagittal step length to 0.0 cm. Accordingly, the lateral step length at the 43
^{rd}
footstep was shifted to 3.0 cm. Consequently, the robot avoided the obstacle in the narrow space, and it was then able to arrive at the goal.
Planned footsteps in environments with (a) cylindrical obstacles and (b) a narrow passage and a local loop.
Fig. 7
shows snapshots of the walking simulation results in the two environments. The humanoid robot successfully followed each footstep planned by the proposed method in realtime. The walking directions were not restricted by the hardware limitations of the robot because the footstep was planned considering the allowable yawing range. Collision between the two legs did not occur while walking, and the robot body did not collide with the obstacles by adjusting the step lengths.
Fig. 8
shows snapshots of the walking experiment result in the environment with cylindrical obstacles. Small position errors existed because of the slip between the sole of the robot and the floor surface compared with the walking simulation result shown in
Fig. 7(a)
. However, the humanoid robot successfully arrived at the goal without obstacle collisions following the planned footsteps in realtime.
Snapshots of the walking simulation results in environments with (a) cylindrical obstacles and (b) a narrow passage and a local loop. (left to right and top to bottom).
Snapshots of the walking experiment result in the environment with cylindrical obstacles. (left to right and top to bottom).
6. Conclusion
This paper has proposed a method for planning the footsteps of humanoid robots and following them in realtime. The univector field navigation method was utilized to determine the walking direction, and the walking direction was varied according to the allowable yawing range. The lateral step length was determined to maintain the same distance between the left and right feet for collision avoidance between the two legs while walking. The sagittal step length was determined by the binary search algorithm, and the lateral step length was shifted to avoid collision between the robot body and the obstacles in a narrow space. The walking pattern generator based on the 3D LIPM generated the modifiable walking patterns for the following planned footsteps. The effectiveness of the proposed method was demonstrated through simulation and experiment using the smallsized humanoid robot platform DARwInOP. As a result, the proposed method enables a humanoid robot to arrive at the goal without obstacle collisions following the planned footsteps in realtime.
Acknowledgements
This work was supported by the new faculty research fund of Ajou University.
BIO
YoungDae Hong received 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 at Ajou University, Suwon, Korea, where he is currently an Assistant Professor. His current research interests include humanoid robotics, especially bipedal walking pattern generation, footstep planning, multi/singleobjective evolutionary optimization, and biologically inspired control.
Yagi M.
,
Lumelsky V.
1999
“Biped robot locomotion in scenes with unknown obstacles,”
Proc. IEEE Int. Conf. Robot. Autom.
375 
380
Wong E. T.
,
Jarvis R.
2004
“Real time obstacle detection and navigation planning for a humanoid robot in an indoor environment,”
Proc. IEEE Conf. Robot. Autom. Mechatron.
693 
698
Chestnutt J.
,
Lau M.
,
Cheung G.
,
Kuffner J.
,
Hodgins J.
,
Kanade T.
2005
“Footstep planning for the honda asimo humanoid,”
Proc. IEEE Int. Conf. Robot. Autom.
629 
634
Chestnutt J.
,
Michel P.
,
Nishiwaki K.
,
Kuffner J.
,
Kagami S.
2006
“An intelligent joystick for biped control,”
Proc. IEEE Int. Conf. Robot. Autom.
860 
865
Xia Z.
,
Xiong J.
,
Chen K.
2010
“Parameter selfadaptation in biped navigation employing nonuniform randomized footstep planner,”
Robotica
28
(6)
929 
936
DOI : 10.1017/S0263574709990804
Xia Z.
,
Xiong J.
,
Chen K.
2011
“Global navigation for humanoid robots using samplingbased footstep planners,”
IEEE/ASME Trans. Mechtron.
16
(4)
716 
723
DOI : 10.1109/TMECH.2010.2051679
Perrin N.
,
Stasse O.
,
Baudouin L.
,
Lamiraux F.
,
Yoshida E.
2012
“Fast humanoid robot collisionfree footstep planning using swept volume approximations,”
IEEE Trans. Robot.
28
(2)
427 
439
DOI : 10.1109/TRO.2011.2172152
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)
Kim Y.J.
,
Kim J.H.
,
Kwon D.S.
2001
“Evolutionary programming based univector field navigation method for fast mobile robots,”
IEEE Trans. Syst., Man,Cybern. B, Cybern.
31
(3)
450 
458
DOI : 10.1109/3477.931544
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.
1
31 
37
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. Robot.
24
(4)
917 
925
DOI : 10.1109/TRO.2008.926859
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.
,
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
Michel O.
2004
“Cyberbotics Ltd.WebotsTM: Professional mobile robot simulation,”
Int. J. Adv. Robot. Syst.
1
(1)
39 
42