Modeling and understanding the seemingly simple process of human walking remains as one of the more difficult research problems in multibody systems and robotics due to its complexity and high dimension. There are many variations of walking in humans, though we will concern ourselves only with the periodic motion associated with moving at a constant average speed on a flat surface. Due to the complexity of the problem, compromising simplifying modeling assumptions were often made in previous work to make it more tractable. Even a simple 5-link biped robot with all rotational joints and full motion degrees of freedom will have a 14 dimensional state space when represented with respect to generalized coordinates. One also encounters a differential-algebraic system when contact constraints of the leg with the ground are considered.
A very thorough investigation into minimum energy walking with numerical methods was undertaken early on in  using a highly simplified model which resulted in a 2-link manipulator. The idea of searching for a passive walking motion which can approximate better the minimum energy motion witnessed in humans was also expressed in the work of McGeer  and later with Goswami et al. . The minimum energy path is desirable for it exhibits stabilizing, attractive properties. Our experiments have shown that many walking trajectories, naively chosen to approximate walking motion, can require a huge increase in energy over that of the optimally calculated minimum energy motion. Other recent work also investigating minimum energy motion with simplified models may be found in . Very interesting walking machines were constructed by McGeer  and also by Kajita . Kajita modeled the biped dynamics as an inverted pendulum with point masses whose simplicity forced an interesting and unusual construction of the biped.
To properly model walking, one should consider explicitly both phases of walking. The first phase has one leg in contact, while in the shorter second phase both legs are in contact with the ground. The difficulty with this perspective, however, is that one is faced with a differential-algebraic system with a varying number of algebraic constraints. The collision of the leg with the ground results in jump conditions on the velocities while there also exists saturation constraints on the state variables and the actuators.
In this paper, we explain how our numerical approach is able to produce solutions which satisfy these and other constraints. The first step towards reducing the complexity of the problem was made in modeling the dynamical system very efficiently using recently developed recursive, symbolic algorithms . This allows one to change the model ``easily'' and to greatly speed (the very many) function evaluations which occur in running an optimization code (or even a simulation). This is described in  and in this paper we briefly sketch how recursive symbolic dynamics are used on the biped.
Another important step was the creation of a reduced dynamics algorithm for evaluating the unconstrained reduced-dimensional dynamics of the biped which account for the contact constraints . This makes it possible to integrate in time the reduced system rather than the full differential-algebraic dynamical system. This algorithm was first presented in the description of this work found in .
The last component of our solution approach involves the use of powerful numerical optimal control software (DIRCOL) [14, 15, 16]. This recently developed software can handle control problems of high dimension with many forms of constraints. We describe how we successfully apply these calculational tools to our problem. Our description includes coordinate selections which proved essential for ours and possibly for other numerical approaches, see Section . We also indicate numerical experience with the use of DIRCOL in Section .
We finally discuss our experimental findings and compare a few of them to medical findings on humans. Noteworthy are:
Minimum energy walk for biped model (without explicit modeling of the feet) has a much slower walk than the optimal human walk.
The optimal model walk has shorter steps than the optimal human walk; however, step length comparisons with the human walk are difficult because our model has no feet. These findings suggest an area for future work.
The curve ``energy of optimal walk (resp. optimal step length) vs average forward velocity,'' which we obtained numerically, has the same qualitative shape as the hyperbolic (resp. linearly) relationship clinically observed in humans.
In an attempt to add actuation which might resemble the action of feet we included two forces. First we allowed an additional liftoff force which acts as an impulse directed upward on the bottom of the swing leg when it lifts off of the ground. This resembles the upward thrust imparted by the foot at liftoff. Secondly, we allowed ankle torques at the point of contact of the legs with the ground.
In the discussion of our numerical experiments, we studied many different model variations and present here a few of them. For example, we turn the liftoff impulse and ankle torques on and off. Other parameters which are varied are the biped's step length, the time of one step, and the proportion of time corresponding to the contact phase. We also discuss the effect of these parameters on the system energy. Findings on the liftoff impulse and the ankle torques are:
Impulsive liftoff forces help prevent torque saturation, smooth the walking motion, and reduce the energy consumed.
Ankle actuation smooths the walking step and distributes the required input torques more equally among the hip, the knee, and the ankle.
Preliminary results for the solution of this problem were first presented in  while the whole paper is based on .