Online Joint Trajectory Generation of Human-like Biped Walking

Abstract

Biped walking has long been studied in the area of gait analysis and robotic locomotion. The goal of this paper is to establish a systematic methodology for human-like natural walking by fusing the measured human joint data and optimal pattern generation techniques based on a full-body humanoid model. To this end, this paper proposes an adaptive two-stage gait pattern by which the step length and walking velocity can be changed with two scaling factors. In addition, to cope with the situations involving passing over a small obstacle, the joint trajectories of the swing foot can be adjusted with a novel concept of differential angle trajectory using a reliable optimization method, viz. particle swarm optimization. The feasibility of the proposed walking scheme is validated by walking experiments with the robot platform DARwIn-OP.

Keywords

Biped Walking Trajectory Generation Humanoid Robot Particle Swarm Optimization

1. Introduction

Recently, humanoid robots have gained increased attention in research, education and entertainment. Biped walking is one of the essential techniques required for a humanoid's free locomotion, which has long been studied in the area of gait analysis. Gait analysis is the systematic study of human walking, augmented by measuring body movement based on body mechanics and the activity of muscles [1 –6].

From the viewpoint of robotics theory, dynamic walking strategies has been developed in relation to offline walking pattern generation, online pattern adjustment, and real-time balance control [7 –11]. In general, basic patterns are designed offline by planning the zero moment points (ZMPs) of the humanoid to be placed inside the convex hull of the stance foot while walking [7] and ascending/descending stairs [8]. For online pattern adjustment, the cycloid function and third-order polynomial interpolation are employed to describe the reference position trajectories of the swing leg's ankle and centre of pelvis, respectively [9]. Despite this functional simplicity, the generated gaits are somewhat unnatural, since humans sway their feet with a Gaussian-like trajectory [10].

A more advanced real-time pattern generation methodology was developed by combining the offline optimization of free parameters and real-time walking pattern generation from given footstep locations [11]. The system was complicated with a hierarchical structure using a simplified robot model, which is prone to yield modelling errors in generating asymmetric whole-body human motions, such as yoga postures [12].

Winter reported a set of joint angle data measured for a period of a human's normal walk, which is vividly used in the field of rehabilitation [5]. It is apparent that the human joint angle data - with functional approximation and suitable modifications - can be applied to the natural biped walking of a humanoid, which is the motivation for this study. The present study newly enables the applicability of human joint data to robotic walking by employing kinematic relationships and modifying the human data to fulfil a level-landing condition.

The humanoid should be able to walk with different step lengths and/or different walking speeds by slightly altering the joint angle data attained for standard walking conditions. Once the joint angle sequences are transformed to interpolation functions, changing the walking conditions becomes simple and straightforward with merely scaling the angle magnitude and sample period. The present study examines this novel scalability effect and reveals that the magnitude ratio of the leg joint angles is proportional to the step length, while extended sample periods make the robot walk slower.

In addition, an online angle trajectory generation scheme for joint actuators in the swing leg is proposed in this paper for humanoids in passing over small obstacles. To this end, a novel concept of differential angle trajectory, which supplements the reference trajectory, is proposed, and the function coefficients are tuned by the reliable optimization method, namely particle swarm optimization (PSO) [13]. PSO is also applied to the identification of the best fitting coefficients of the joint functions for the human joint data, and for solving the inverse kinematics of the intermediate postures of the humanoid. The effectiveness of the proposed trajectory generation scheme is validated through several walking experiments with the child-sized humanoid robot DARwIn-OP.

This paper is composed of three sections; Section 2 describes the fundamentals of human-like biped walking including a whole-body model of the humanoid, two-stage gait scheme, the coordination of the human joint data to robotic walking, and the principle of PSO. Section 3 provides a novel scaling principle of joint angle trajectory for various walks. Section 4 provides online pattern generation results for biped walks that meet several target peak altitudes of the swing foot. Section 5 concludes the present work and introduces future research topics.

2. Fundamentals of Human-like Biped Walking

2.1 Whole-body Model of a Humanoid Robot

For the generation of arbitrary walking motions, it is necessary to describe a robot's motion with respect to its joint spaces based on kinematic relationships. This work is based on a newly completed 3-D whole-body model of a humanoid using both the Denavit-Hartenberg (DH) convention [14] and the projection principle [8] for the DARwIn-OP platform, as shown in Figure 1, where the double-scripted symbols (such as l^c_i and l^s_i) denote the length of the i-th link projected on the coronal plane and the sagittal plane, respectively. M_i and (X_i, Y_i, Z_i) represent the point mass of the i-th link and the world coordinate of the i-th joint, respectively.

Figure 1.

3-D whole-body humanoid robot model described with absolute and relative joint angles and point masses

The present model contains 20 joint angle variables classified into three groups according to the orthogonal planes to which they belong: sagittal angle variables denoted by θ₁ to θ₁₁ in the X-Z coordinate frame; coronal angle variables designated by φ₁ to φ₆ in the Y-Z coordinate frame; and transversal angle variables, ψ₁ to φ₃, in the X-Y coordinate frame. These joint variables are relative geometric angles associated with the reference coordinate frame (X₀, Y₀, Z₀), which is located on the ankle of the stance leg.

A humanoid walks by swapping the stance leg, and thus the relative joint angle variables in both legs are not uniquely assigned at each joint. Therefore, absolute joint variables designated with double-scripted symbols, such as θ^l_kn, are also assigned to each joint per plane, where the superscript l or r denotes that the joint is placed on the left or right, and the subscripts an, kn, hp, sh, el, nk represent ankle, knee, hip, shoulder, elbow and neck, respectively. All the absolute angles are defined as zero when the robot stands erect, and the sign of rotation direction for coronal and transversal variables follows the general right-hand rule around the X- and Z-axes. Since the absolute joint variables are more convenient to treat and analyse for a certain motion, joint trajectory optimization and implementation with the robot platform are carried out in terms of them.

2.2 Gait Cycle

A human walks with a periodic gait cycle composed of stance and swing periods. It is reported that a gait cycle contains five functional phases for the stance period and three phases for the swing period, as shown in Figure 2 [4].

Figure 2.

Functional division of a gait cycle [4]

Huang et al. define the step cycle as beginning with the heel of the swing foot leaving the ground and ending with the heel making first contact with the ground [7]. Since the joint trajectories of the next step are attained throughout the exchange of them in the opposite leg, a pair of successive step cycles comprise a gait cycle. Moreover, considering that the humanoid has to walk on rough terrain, it needs to adapt the angle of the landing foot at every end-of-step. Therefore, the step cycle is selected as a unit of a walking pattern in this paper. Near the end of the swing phase, the present work constrains the ankle angle to land the foot level with the ground so as to prevent the robot from tipping over.

A k -th step cycle composed of two stages and three component postures with a cycle period, T_c, and double support period, T_d, are shown in Figure 3, where the right leg is in the stance period (for example). In the first stage, from kT_c to kT_c + T_d, the humanoid transfers its body forward a little into a double support phase (DSP) by progressing from posture P1 to P2. Meanwhile, the right leg passes through the initial contact and loading response phases, and the left leg takes the terminal stance and pre-swing phases sequentially.

Figure 3.

Proposed two-stage step cycle composed of three component postures in right support

In the second stage, from kT_c + T_d to (k + 1)T_c, the robot walks forward by moving the left leg from P2 to P3 in the single support phase (SSP). The period of the right leg elapses from the loading response phase to the terminal stance phase, whereas the left leg moves from the pre-swing phase to the terminal swing phase.

The three postures, P1, P2 and P3, are configured using inverse kinematics or optimization, which will be discussed in Section 2.5.

2.3 Mixture of Human Joint Data

For the implementation of natural biped walking with the humanoid, the present work refers to the joint angle data measured for human subjects, which is tabulated in Winter's book [5]. Figure 4 shows trajectories of the selected data set corresponding to the swing phase (i.e., from toe-off to heel contact). The sampling interval is 0.0143 s and the number of data points is 28.

Figure 4.

Joint angle trajectories measured during the swing phase of a human's normal walking

These joint angle figures, however, cannot be directly applied to humanoids, which have different lower body link specifications from humans. Moreover, in the present work the humanoid is constrained to land its foot level with the ground, unlike a human. Therefore, it is necessary to modify the human joint data using the kinematic relationship of the humanoid.

For the humanoid to land its foot with a specified angle trajectory, the sum of the relative sagittal joint angles θ_i, i = 1, …, 6 in the lower body should be such that:

θ_{1} (t) + θ_{2} (t) + θ_{3} (t) + θ_{4} (t) + θ_{5} (t) + θ_{6} (t) = θ_{f t} (t)

(1)

where θ_ft (t) denotes the desired angle trajectory of the swing foot. When the foot is level with the ground, θ_ft corresponds to – π/2.

As can be seen in Figure 1, in the case of left-leg support, the relative joint variables in the lower body have the following relationship with the absolute joint variables:

\begin{array}{l} θ_{1} = \frac{π}{2} - θ_{a n}^{l}, θ_{2} = θ_{k n}^{l}, θ_{3} = - θ_{h p}^{l}, \\ θ_{4} = θ_{h p}^{r} + π, θ_{5} = - θ_{k n}^{r}, θ_{6} = θ_{a n}^{r} . \end{array}

(2)

Substituting (1) with (2) leads to the following ankle angle condition near landing:

θ_{a n}^{r} (t) = - θ_{h p}^{r} (t) + θ_{k n}^{r} (t) + θ_{f t} (t) - θ_{t r} + π

(3)

where θ_tr (= θ₁ + θ₂ + θ₃) denotes the torso angle in the sagittal plane. In the same manner, when the humanoid supports its body with the right leg, the ankle angle has the following relationship:

θ_{a n}^{l} (t) = - θ_{h p}^{l} (t) + θ_{k n}^{l} (t) + θ_{f t} (t) - θ_{t r} + π

(4)

To combine the human joint data and the landing condition, let θ^H_an and θ^R_an represent the absolute ankle joint variables in the swing leg for a human and the robot, respectively. Following the angular definition shown in Figure 1, θ^R_an becomes θ^r_an in left support, while θ^R_an=θ^l_an in right support. The modification of the original joint data with the level-landing constraint can be described by the weighted average of the two joint angle variables, such that:

\begin{array}{l} {\tilde{θ}}_{a n} (t) = α (t) θ_{a n}^{R} (t) + β (t) θ_{a n}^{H} (t), \\ α (t) + β (t) = 1, 0 \leq α (t), β (t) \leq 1, \\ k T_{c} + T_{d} \leq t \leq (k + 1) T_{c} \end{array}

(5)

where ${\tilde{θ}}_{a n} (t)$ is the combined ankle joint variable during the swing period, and α(t) and β(t) denote weight coefficients for the robotic and human-like gait patterns, respectively.

Since the robot is expected to lift up and swing the leg in as natural a manner as a human at the beginning of the second stage, and to land the foot on the ground as level as possible near the end of the step period, the weight coefficient α(t) should vary from 0 to 1 in a smooth manner. The sigmoid function is suitable for this purpose, which is described as:

α (t) = 1 / (1 + e^{- a t (t - t_{m})})

(6)

where a and t_m represent the time scale factor and the transition time, respectively. In the present work, a and t_m are set at 10 and −0.1, respectively. Figure 5 shows the shape of the selected α(t) with reference to the sample points.

Figure 5.

Coefficient profile for the level landing of the swing foot

2.4 Joint Angle Trajectory

For a natural and energy-efficient walk, the leg joints need to rotate in a smooth and seamless manner. A blending polynomial (BP) is composed of more than two segments, which are described by cubic or quintic polynomials with angular conditions on via points. Since most curved trajectories can be shaped effectively with these conditions by intuition, this work describes the joint trajectory using a BP.

Instantaneous joint angle variables in the i-th segment of BP are described with the following cubic polynomial function:

\begin{array}{l} q^{i} (t) = a_{0}^{i} + a_{1}^{i} (t - t_{0}^{i}) + a_{2}^{i} (t - t_{0}^{i})^{2} + a_{3}^{i} (t - t_{0}^{i})^{3}, \\ t_{0}^{i} \leq t \leq t_{f}^{i} \end{array}

(7)

where the four coefficients aⁱ₀,aⁱ₁,aⁱ₂,aⁱ₃ are calculated from the specified boundary condition as:

q^{i} (t_{0}^{i}) = q_{0}^{i}, q^{i} (t_{f}^{i}) = q_{f}^{i}, {\dot{q}}^{i} (t_{0}^{i}) = v_{0}^{i}, {\dot{q}}^{i} (t_{f}^{i}) = v_{f}^{i}

(8)

where qⁱ₀, qⁱ_f, and vⁱ₀, vⁱ_f are the initial and final angles/angular velocities of the i-th segment, respectively. Solving the four boundary constraints leads to the following relationship [15]:

\begin{array}{c} a_{0}^{i} = q_{0}^{i}, a_{1}^{i} = v_{0}^{i}, \\ a_{2}^{i} = \frac{3 (q_{f}^{i} - q_{0}^{i}) - (2 v_{0}^{i} + v_{f}^{i}) (t_{f}^{i} - t_{0}^{i})}{{(t_{f}^{i} - t_{0}^{i})}^{2}}, \\ a_{3}^{i} = \frac{2 (q_{0}^{i} - q_{f}^{i}) + (v_{0}^{i} + v_{f}^{i}) (t_{f}^{i} - t_{0}^{i})}{{(t_{f}^{i} - t_{0}^{i})}^{3}} . \end{array}

(9)

Therefore, the four initial and final angle-related values determine the shape of the cubic polynomial. In the case of a multi-segment trajectory, continuity at the i-th via point dictates the two adjacent conditions to be equal, i.e., t^′_s = y^t_s Thus, an m-segment trajectory requires 2(m + 1) angular parameters of a BP in total to generate the whole trajectory q(t), such that:

\begin{array}{l} q (t_{0}^{1}) = q_{0}^{1}, q (t_{f}^{1}) = q_{f}^{1}, q (t_{f}^{2}) = q_{f}^{2}, \dots, q (t_{f}^{m}) = q_{f}^{m} \\ \dot{q} (t_{0}^{1}) = v_{0}^{1}, \dot{q} (t_{f}^{1}) = v_{f}^{1}, \dot{q} (t_{f}^{2}) = v_{f}^{2}, \dots, \dot{q} (t_{f}^{m}) = v_{f}^{m} \end{array}

(10)

2.5 Particle Swarm Optimization (PSO)

PSO is a global optimization method motivated by the social activities of flocks of birds and schools of fish, which frequently share their information on food and messages [13]. The underlying principle of PSO holds that a flock of birds communicates with their best-so-far individual information as well as the current global best information, whose equation is written as below:

v_{k}^{n e x t} = w v_{k}^{n o w} + c_{1} r_{1} (p_{b e s t}^{k} - s_{k}^{n o w}) + c_{2} r_{2} (g_{b e s t} - s_{k}^{n o w}),

(11)

s_{k}^{n e x t} = s_{k}^{n o w} + v_{k}^{n e x t}, k = 1, 2, \dots, N .

(12)

where V^now_k and S ^now_k denote the present velocity vector and position vector of the k-th agent, while V^next_k and S^next_k are the next velocity and position vectors calculated after

an iteration based on each agent's best position vector p ^k _best and the population's global best position vector g_best. The coefficients c₁, c₂, and W represent two learning factors associated with the search history and inertial weight, respectively. r₁ and r₂ are uniformly distributed random numbers. Figure 6 illustrates the above-mentioned position update principle of an agent at the next iteration.

Figure 6.

Position update principle of PSO at the next iteration

In the present work, PSO plays a key role in posture setup, function approximation and the online adjustment of joint trajectory parameters.

3. Trajectory Generation for Various Walks

To enable the high mobility of the humanoid, the step length and walking speed need to be adjusted with ease. The step length is associated with the three component postures and the magnitude of the joint angles, and the walking speed is related to the angular velocity of the joints. Therefore, it is convenient to modify the ratio of the time interval and magnitude quantities of the reference joint trajectories for changing walk conditions rather than making new joint angle profiles.

3.1 Change of Step Length

In this paper, the first step in simulating biped walking with a humanoid is to set up the component postures. When the absolute leg joint angles in the sagittal plane are used to form a posture, scaling them up or down results in an increase or decrease in step length, respectively.

Figure 7 compares postures of standing erect to step lengths of 10 cm, 7 cm and 5 cm, simulated with the body specifications of the child-size humanoid platform DARwIn-OP, whose concise information is written in Table 1. They are attained by multiplying scale factors of 1.0, 0.7 and 0.5 to the six absolute joint angles for a step length of 10 cm. This is due to the fact that the absolute joint angles are defined on the basis of erect standing.

Figure 7.

Standing postures of the humanoid attained by scaling down the reference leg joint angles in the sagittal plane with factors of 1, 0.7 and 0.5 from the left

Table 1.

DARwIn-OP specification

Height	45 cm
Weight	2.9 kg
Joint Mobility	5DOF/leg2, 3DOF/arm2, 1DOF/waist*2, 2DOF/neck
Sensors	gyroscope sensor, acceleration sensor, FSR

This interesting relationship can be written algebraically, as in the following:

Θ^{'} = κ [θ_{a n}^{l} θ_{k n}^{l} θ_{h p}^{l} θ_{h p}^{r} θ_{k n}^{r} θ_{a n}^{r}]

(13)

where κ represents the scale factor of the angular magnitude.

The postures in Figure 7 correspond to P1 and P3 in Figure 3, and the intermediate posture P2 can be established to lift the heel appropriately by inverse kinematics or numerical optimization. In the present work, human joint data shown in Figure 4 are applied to DARwIn-OP for a 10 cm-long step. However, controlling DARwIn-OP with this step length is difficult without well-designed balance control.

Therefore, 7 cm is chosen as the actual step length for biped walking which implies that κ in (16) is 0.7. Figure 8 shows the resultant three postures, which will be used in this paper.

Figure 8.

Three boundary postures of the proposed step cycle for a step length of 7 cm

3.2 Change of Walking Speed

The walking speed is associated with the angular velocity of the leg joints, which is a derivative of the joint angle trajectory. Since reference angle profiles are used in this work, the modification of them in terms of the sample period is proposed based on the property of a polynomial function.

Assume that an actuator rotates with the trajectory of a three-segment BP with a sample time t_s described as:

q (t) = B P_{3} (t, t_{s}, t_{0}, t_{m 1}, t_{m 2}, t_{f}, q_{0}, q_{m 1}, q_{m 2}, q_{f}, ω_{0}, ω_{m 1}, ω_{m 2}, ω_{f})

(14)

where the symbols t, q and ω represent the percentage time, angle and angular velocity, respectively. The subscripts 0, m1, m2 and f denote the initial, first medium, second medium and final times, respectively at four via points. When the actuator is required to rotate γ times slower, i.e., t^′_s = y^t_s, the BP expression is to be modified like the following:

q^{'} (t) = B P_{3} (t, {t^{'}}_{s}, t_{0}, t_{m 1}, t_{m 2}, t_{f}, q_{0}, q_{m 1}, q_{m 2}, q_{f}, \frac{ω_{0}}{γ}, \frac{ω_{m 1}}{γ}, \frac{ω_{m 2}}{γ}, \frac{ω_{f}}{γ})

(15)

where γ stands for the timescale factor. It is worth noting that time quantities are invariant because their units are the percentage time of the overall period. Figure 9 shows the effect of a decrease in velocity with γ = 2 for the following BP parameters as an example:

\begin{array}{c} t_{0} = 0 %, t_{m 1} = 30 %, t_{m 2} = 70 %, t_{f} = 100 %, \\ q_{0} = 0 °, q_{m 1} = 20 °, q_{m 2} = 15 °, q_{f} = 30 °, \\ ω_{0} = 0 \deg / s, ω_{m 1} = - 2 \deg / s, ω_{m 2} = 4 \deg / s, ω_{f} = 10 \deg / s . \end{array}

Figure 9.

Velocity extension of a three-segment BP trajectory

3.3 Parameterization of Human joint Angle Trajectories

As mentioned above, joint angle quantities can be modified from reference quantities merely by changing the two scaling factors, κ and γ, to cope with various walking conditions. For convenience of management, it is necessary to approximate the reference angle profiles with BPs. PSO is also used in this task.

Figure 10 shows trajectory fitting results for human data with the original sample period, 0.0143 s, which is attained with PSO. The cost function for this task is set to minimize the sum of the approximation errors, such that:

J_{f i t} = \sum_{k = 1}^{28} | q_{r e f} (k) - q_{f i t} (k t_{s}) |

(16)

where q_ref(k) is the k-th value of the human joint angle sequence, and q_fit (kt_s) is the k-th sample point of the fitted BP.

Figure 10.

Fitted joint angle profiles with three-segment blending polynomials

The variation of curvature is highest for the ankle joint trajectory, which signifies that a three-segment BP is suitable. Since the BP parameters at two boundary via points are attained from those of human data, the six internal parameters, including the two mid-time quantities, two mid-angles and two mid-velocities, should be found by PSO. All the optimal parameters defined in (14) are listed in Table 2. Despite the high curvature of the original trajectories, the fitted functions are acceptable with good approximation.

Table 2.

Optimal internal parameters attained by fitting human joint angle sequences with a three-segment blending polynomial when the sample period is 0.0143 s

	t^_m1* (%)	t^_m2* (%)	q^_m1* (deg)	q^_m2* (deg)	ɷ^_m1* (deg/s)	ɷ^_m2* (deg/s)
Ankle	47.2	85.0	−0.49	−2.50	−7.55	−20.0
Knee	23.9	88.8	67.30	0	20.0	−20.0
Hip	31.2	51.0	20.71	24.1	20.0	−20.0

4. Online Pattern Generation

The goal of the present work is to adjust the leg joint angles for the robot to swing the foot with the desired maximum height in real-time, as shown in Fig 11. To this end, the reference joint angle pattern is firstly constructed by adopting human joint data with some modification to DARwIn-OP. Next, PSO is used in tuning the human joint trajectories to meet a specified peak altitude of the swing foot. Each case is simulated with a stability check and validated with experiments on the DARwIn-OP platform.

Figure 11.

Overall flowchart for the proposed online human-like biped walking

4.1 Human-like Walking

Regarding the specification of DARwIn-OP, the reference condition for normal walking listed below is set a little slower, with a narrower step length than normal human walking.

sample time (t_s): 0.07 s (γ = 4.89)

step length: 0.07m (κ = 0.7)

stage period ratio = 1:3 (human ratio is 1:4 [6])

In the first stage of a robotized walk, all the sagittal joint trajectories are expressed with one-segment BPs. In the second stage, however, the joint trajectories of the swing leg employ three-segment BPs, whereas one-segment BPs are assigned to the joints of the support leg. Specifically, the trajectory equations for the swing leg's joints in the second stage are written in the context of (14) as:

\begin{array}{l} θ_{i}^{H} (t) = B P_{3} (t, t_{s}, 0, t_{m 1}^{i *}, t_{m 2}^{i *}, t_{f}, κ q_{0}^{i}, κ q_{m 1}^{i *}, κ q_{m 2}^{i *}, κ q_{f}^{i}, \\ κ \frac{ω_{0}^{i}}{γ}, κ \frac{ω_{m 1}^{i *}}{γ}, κ \frac{ω_{m 2}^{i *}}{γ}, 0), t_{f} = 28 t_{s}, i = a n, k n, h p \end{array}

(17)

where the final angular velocities are set to zero for a smooth landing. The parameters with an asterisk are those in Table 2, and the other angular parameters are determined from the angles of the optimized postures and human data.

Figure 12 shows absolute angle trajectories of the sagittal and coronal joint variables generated by the proposed synthesis scheme. The coronal joints are planned to rotate from zero degree to their maximum magnitude of 15 degrees at a quarter of the cycle period, maintain the angle during a half of the period, and return to their home angle of zero degrees. Therefore, the joint trajectories are expressed with three-segment BPs.

Figure 12.

Absolute angle trajectories of the sagittal and coronal joints in the legs generated by the proposed trajectory synthesis scheme

Figures 13 and 14 show the trace motion of human-like biped walking and the corresponding ZMP trajectory simulated on MATLAB, which satisfies the ZMP stability criterion. Figure 15 depicts the altitude trajectory of the swing foot in normal walking. It is apparent that the spatial distribution of the foot's swing trajectory is skewed to the left.

Figure 13.

Simulation of a step cycle in the right leg's support based on DARwIn-OP parameters

Figure 14.

ZMP profiles calculated during walking simulation

Figure 15.

Altitude trajectory of the swing foot in a normal human walk when the sample period is 0.07 s

The features of the human-like biped walk are such that:

period of a step cycle (T_c): 2.66 s

gait velocity: 0.054 m/s

maximum height of the swing foot: 0.023 m.

4.2 Online Adjustment of Foot Altitude

A distinct feature of this paper is the in situ adjustment of the maximum altitude of the swing foot using the reliable optimization method, PSO. Although PSO is classified as a population-based method demanding considerable computation time, a high-performance CPU in the embedded computer and an elaborate strategy of bounding the search space around the previous local minima enable PSO to be applicable to local search.

For an efficient local search, a differential angle trajectory is generated and added to the reference trajectory expressed in (17). To avoid redundancy and save on run time, the two time variables are fixed to 33.3% and 66.7% of the swing period t_f. Therefore, PSO optimizes four variables per joint, which is a total of 12 variables described as:

\begin{array}{l} Χ = [Δ q_{m 1}^{a n}, Δ q_{m 2}^{a n}, Δ ω_{m 1}^{a n}, Δ ω_{m 2}^{a n}, Δ q_{m 1}^{k n}, Δ q_{m 2}^{k n}, Δ ω_{m 1}^{k n}, Δ ω_{m 2}^{k n}, \\ Δ q_{m 1}^{h p}, Δ q_{m 2}^{h p}, Δ ω_{m 1}^{h p}, Δ ω_{m 2}^{h p}] \end{array}

(18)

The differential angle trajectory is described with a three-segment BP as:

\begin{array}{l} Δ θ_{i}^{H} (t) = B P_{3} (t, t_{s}, 0, 0.33 t_{f}, 0.67 t_{f}, t_{f}, 0, Δ q_{m 1}^{i *}, Δ q_{m 2}^{i *}, 0, \\ 0, Δ ω_{m 1}^{i *}, Δ ω_{m 2}^{i *}, 0), i = a n, k n, h p \end{array}

(19)

The actual angle trajectory of the i-th joint is thus expressed as:

{\bar{θ}}_{i}^{H} (t) = θ_{i}^{H} (t) + Δ θ_{i}^{H} (t), i = a n, k n, h p

(20)

where θ^H_i (t) is the joint trajectory for the reference gait, which is expressed in (17).

The cost function for the adjustment of foot height is calculated in terms of the Euclidean distance between the desired foot coordinates and actual ones, like the following:

J_{h} (Χ) = \frac{1}{h_{g}} \sum_{k = 1}^{28} \sqrt{{(x_{r} (k t_{s}) - X_{6} (k t_{s}))}^{2} + {(z_{r} (k t_{s}) - Z_{6} (k t_{s}))}^{2}}

(21)

where h_g is the normalization factor representing the ratio of the desired foot height to the reference one, and (X₆(t), Z₆(t)) denotes the world coordinate of the swing foot depicted in Figure 1.

In this experiment, the desired foot trajectory (x_r(t), z_r(t)) is expressed with a one-segment BP for the x-axis coordinate and a three-segment BP for the z-axis coordinate to make a symmetric and smooth transition, such that:

\begin{array}{l} x_{r} (t) = B P_{1} (t, t_{s}, 0, t_{f}, x_{0}, x_{f}) \\ z_{r} (t) = B P_{3} (t, t_{s}, 0, 0.45 t_{f}, 0.55 t_{f}, t_{f}, 0, f h_{\max}, f h_{\max}, 0, \\ 0, 0, 0, 0) \end{array}

(21)

where fh_max denotes the desired maximum foot height set online. Figure 16 depicts the desired foot trajectory when fh_max is 0.023.

Figure 16.

Reference trajectory of the swing foot, which is scaled up or down for the adjustment of maximum foot altitude

In a local optimization routine, care must be taken in bounding the search space with reference to the current-best local minima. The 12 optimization variables in (18) are classified into angle values and angular velocity values. In the current PSO routine, the angle values are optimized around the previous optimal ones with a variation of ± δ. However, optimal angular velocities are merely searched inside the boundary of ± λ deg/sec to preserve smoothness. Consequently, upper and lower boundaries of the search variables are determined in a hybrid fashion as:

\begin{array}{l} h_{Χ} = [Δ q_{m 1}^{a n} + δ, Δ q_{m 2}^{a n} + δ, λ, λ, Δ q_{m 1}^{k n} + δ, Δ q_{m 2}^{k n} + δ, λ, λ, \\ Δ q_{m 1}^{h p} + δ, Δ q_{m 2}^{h p} + δ, λ, λ] \\ l_{X} = [Δ q_{m 1}^{a n} - δ, Δ q_{m 2}^{a n} - δ, - λ, - λ, Δ q_{m 1}^{k n} - δ, Δ q_{m 2}^{k n} - δ, - λ, - λ, \\ Δ q_{m 1}^{h p} - δ, Δ q_{m 2}^{h p} - δ, - λ, - λ] \end{array}

(22)

A scenario of foot height adjustment is such that the humanoid raises its foot highly from 3 cm to 5 cm, as written in Table 3.

Table 3.

Target maximum heights of the swing foot for online adjustment with PSO

	fh _max1	fh _max2	fh _max3
Maximum height (m)	0.03	0.04	0.05

The optimization of PSO is conducted on DARwIn-OP. The main controller of DARwIn-OP is a fit-PC2i equipped with a 1.6 GHz Intel Atom Z530 CPU, 1GB RAM and 4GB storage. The operating system is Linux, and the source codes for optimization and robot kinematics and dynamics are programmed in C++.

For local optimization, the PSO is configured with the following parameters:

population size: 10

maximum iteration number: 50

boundary parameters in (22): δ = 20°, λ = 10°/s

Figure 17 shows the search aspect of PSO performed on DARwIn-OP when the reference foot altitude is altered, as in the scenario after 10 seconds. Owing to the dynamically adapted upper and lower boundaries of the search variables, PSO succeeds in locating local minima within five seconds. This search time is reduced to one second when the projection-based humanoid modelling in [8] is used, which is nearer to real-time.

Figure 17.

Minimization of the cost function with PSO for different reference foot altitudes, which is changed after 10 seconds

Figure 18 compares the optimal trajectories of the swing leg's joints, whose combination matches well with the desired foot trajectories of the commanded heights. It is apparent from the figure that the altitude of the swing foot is proportional to the hip joint angle. Figure 19 shows that the optimized joint rotations make the swing foot lift up to the desired altitudes.

Figure 18.

Optimal joint angle profiles of the swing leg for maximum altitudes of 3 cm, 4 cm and 5 cm

Figure 19.

Comparison of the swing foot's altitude trajectories optimized by PSO for three different desired peak altitudes of the foot (solid line: actual, dashed line: reference)

Figure 20 compares walking experiments with the attained optimal joint trajectories and the proposed gait synthesis technique, which validates that DARwIn-Op walks well with the reference foot trajectories and with a human-like gait. Figure 21 compares the proposed human-like walk with the conventional one-stage walk whose joint trajectories are descried with BPs and optimized with PSO. The humanoid must shift its centre of mass faster for the one-stage walk because of the shorter DSP period than that of the two-stage walk, which leads to an increase in lateral angular momentum. Therefore, the proposed two-stage walk retains more stability, with the smooth and natural motion of the swing leg.

Figure 20.

Comparison of biped walking experiments with the optimized joint trajectories for each desired peak altitude of the foot

Figure 21.

Comparison of biped walking experiments for the conventional one-stage walk and the proposed two-stage walk

5. Conclusion

This study proposes an online trajectory generation method for biped walking using PSO based on a three-dimensional full-body humanoid robot model. To implement more natural walking, human kinematic data is adopted and modified with the robot condition. The maximum height of the swing foot is commanded with variation, and the humanoid robot DARwIn-OP searched the 12 optimal joint parameters within a few seconds, which is applicable to real-time walking.

Future work will be to extend the online pattern generation to various motions, such as ascending/descending stairs, dancing, kicking and object carrying.

Footnotes

6. Acknowledgments

This work (Grant No. 00046013) was partly supported by Business for Academic-Industrial Cooperative Establishments, funded by the Korea Small and Medium Business Administration, in 2011. It was also supported by the Human Resources Development Program (No. 20134010200550) of the Korea Institute of Energy Technology Evaluation and Planning (KETEP) grant funded by the Korea government Ministry of Trade, Industry and Energy.

References

Marey

E J

(1895) Movement. Appleton. New York..

Winter

D A

Sidwall

H G

Hobson

D A

(1974) Measurement and Reduction of Noise in Kinematics of locomotion. J. Biomechanics. 7:157–159.

Zarrugh

M Y

Radcliffe

C W

(1979), Computer Generation of Human Gait Kinematics. J. Biomechanics. 12: 99–111.

Pathokinesiology Service and Physical Therapy Department (2001) Observational Gait Analysis. 4th ed. Downey, CA: Los Amigos Research and Education Institute, Inc, Rancho Los Amigos National Rehabilitation Center.

Winter

D A

(2009) Biomechanics and Motor Control of Human Movement. John Wiley & Sons, Inc., New Jersey.

Perry

Burnfield

J M

(2010) Gait Analysis: Normal and Pathological Function, 2nd ed. SLACK Inc.

Huang

Yokoi

Kajita

Kaneko

Arai

Koyachi

Tanie

(2001) Planning Walking Patterns for a Biped Robot. IEEE Trans. Robotics and Automation. 17(3): 280–289.

Kim

S-W

Kim

J-W

(2010) Trajectory Generation Schemes for Bipedal Ascending and Descending Stairs Using Univariate Dynamic Encoding Algorithm for Searches (uDEAS). Int. Journal of Control, Automation and Systems. 8(5): 1061–1071.

Park

I-W

Kim

J-Y

Lee

J-H

(2006) Online Free Walking Trajectory Generation for Biped Humanoid Robot KHR-3 (HUBO). Int. Conf. On Robotics and Automation. 1231–1236.

10.

Chevallereau

Bessonnet

Abba

Aoustin

(2009) Bipedal Robots. John Wiley & Sons, Inc.

11.

Buschmann

Lohmeier

Bachmayer

Ulbrich

Pfeiffer

(2007) A Collocation Method for Real-time Walking Pattern Generation. Humanoids.1–6.

12.

Hettiarachchi

D S

Iba

(2012) An Evolutionary Computational Approach to Humanoid Motion Planning. Int J Adv Robotic Sys. 9: 167.

13.

Kennedy

Eberhart

(1995) Particle Swarm Optimization. IEEE International Conf. on Neural Networks. 4:1942–1948.

14.

Denavit

Hartenberg

R S

(1955) A Kinematic Notation for Lower-Pair Mechanisms Based on Matrices. Journal of Applied Mechanics. 77: 215–221.

15.

Spong

M W

Hutchinson

Vidyasagar

(2006) Robot Modeling and Control. John Wiley & Sons, Inc.