Timestep:  0.7272    0.4639    0.4639    0.4639    0.4639    0.4639    0.4639    1.3652

XFootstep: 0 .0000   0.3992    0.8380    1.3645    1.9906    2.5230    3.0184    3.5000

YFootstep: 0.0000   -0.076    0.0789   -0.078    0.0830   -0.075    0.0814    0.0000

Our modified cost function produces a trajectory which completes in half the time. It seems that we have developed two useful gaits. The first is great for traveling at slow, but highly energy efficient speed. The trajectory takes advantage of using momentum to maintain its trajetory as it transfers from step to step. The second trajectory has the same tendencies, but with an urgency towards  maintaining a constant, higher speed. The duration weight seems to be great for adding a sense of urgency to the gait, although compensations in torque consumption are inevitable.

Part 4

In this final portion of the assignment, we aren't given a set number of steps. The only information we have about the system is the com initial and final location along with the LIPM dynamics. 

Our optimal solution will now contain an a number of steps. The process by which to determine this is very open ended. We suggest that it would be helpful to condense the number of step choices to a dynamically feasible range. To do this we would test to find the minimum and maximum stable step lengths. Our range of steps would then be a ceiling function of [length_path/length_max,length_path/length/min]. This will greatly reduce the space of possible footstep plans.

A more exhaustive approach is to tailor a new optimization routine for each footstep number, effectively creating the Part 3 optimization routine, but changing the parameter number for footstep count. The minimum cost derived after testing all these points would be chosen.

A more efficient method could involve some time up front on a minimum torque step length. Use this step length as a general starting place to sample optimizers tailored around this step length.

Alternative Method: Let's say we feel very confident in planning a route for a known step number and distance to traverse (Part 3). We can fit a high order polynomial (or sinusoid) to this trajectory, and generalize it such that the amplitdue, frequency, and number of oscillations, is fit to the step number and distance required. Instead of supplying the footstep locations as parameters, we fit them to their 'known' optimal placing along the trajetory. Here we consider the footstep placement as a direct function of step number, so simply supply step number as a parameter to the optimization. This should generate a good com trajectory across a large set of step numbers.

Timestep:   2.0667    1.1692    1.1692    1.1692    1.1692      1.1692    1.1692    2.0764

XFootstep: 0.000     0.2465    0.7845    1.3984    2.0539    2.7013    3.2462    3.5000

YFootstep:  0.000   -0.049    0.0371   -0.042    0.0401    -0.037    0.0491    0.0000

We see a more conservative oscillation in the y direction. For the x footstep plan, it appears that a small first step forward is better than the sideways steps at the beginning and end of the plan. This is not surprising, as it does not appear to be the most direct route for takeoff or stabilizing at the finishing point.

Finally, we optimize with the cost function derived in Part 2, adding a penalty for acceleration and run duration. Our results are the following:

Footstep Location: New Cost + Planned Location Bias

Timestep: 4.6235    1.1586    1.1586    1.1586    0.7250    0.7250    0.7250    3.1191

The introduction of this penalty appears to smooth out the x(t) trajectory, we see less oscillation along the transition period. This results in a much higher torque output along the this period. It seems as though maintaining the smoothness of the curve is taxing on the ankle actuators. We also observe extension of the duration to 13.4 seconds. This solution appears to be driven by acceleration minimization rather than energy efficiency. 

Next we optimize while adding the duration penalty to the original cost function:

​Variable Duration: Cost + Duration Penalty

Here we see the duration stretch to 9.06 seconds! It could be suggested that the velocity penalty is the key factor in extending the duration, but it appears that the torque penalty also play a role. We see a significant increase in y directional torque, but about 50% of the previously applied x directional torque. The longer step time may allow for the contact force in the x direction to aid the acceleration of the COM, alleviating dependency on torque in the x direction.

Revisiting the Cost Function

- Guiding the Optimization Process Towards Desired Results

We are going to adjust our cost function to help produce behavior we feel is qualitative of an optimal COM trajectory. These qualities include:

  • ​Minimize Acceleration:
    • Large accelerations in the x direction are likely to induce configurations which require high torques to maintain stability.
  • ​Penalize Duration:
    • ​A longer duration allows more time for penalties to accumulate. It is more likely that ideal trajectories are efficient and fast.
  • ​Step Length:
    • This is a key factor in producing an effective trajectory, but for now this characteristic is fixed.
  • ​Oscillatory Movement in y-direction:
    • ​We don't want to eliminate this gait characteristic by penalizing acceleration in the y direction. For this reason acceleration will only be penalized in the x direction.

First we add a penalty to acceleration in the x direction. We observe its affects on the newly planned trajectory:

​Variable Duration: Cost + Acceleration Penalty


The figures look almost identical to those presented in Part 1, but there are some key differences. The timestep for trasitions betweeen the right and left foot increases from the 0.5 seconds specified in the Part 1 plan to 0.62 seconds for the first 3 step transitions and 0.65 seconds for the latter 3, as shown above.  The extended time step is likely a product of the the velocity penalty. In further analysis we will introduce other penalties such that velocity will not drive our results. Additionally we see that the extended step also lowers the amplitude of our applied torque in the x direction.

Now we remove the constraint that our duration remain 6 seconds long. We observe the following:

Variable Duration: Original Cost Function

Part 1: 

For Part 1 we find a COM trajectory which minimizes the provided cost function given a plan with footstep location and timing. We construct our optimization with the constraints and parameters described, yielding the following results:

Known Timestep & Foot Location

The location for each step also comes with a duration over which the corresponding leg is in stance as the other leg swings. The location and times are listed in the plan here:

Cost Function

We penalize horizontal distance of the COM from the foot location, the COM velocity, and the torque output. Here is the numerical breakdown.

A larger weight is placed on torque so that the magnitude of the energy cost is comparable to the position and velocity penalties.


The parameters for our trajectory optimization involve the explicit positions of the COM over a sequence of linearly spaced time intervals spanning the duration of the run. We split up the duration into 100 intervals, optimizing for 101 COM positions in the x and y directions. Similarly we simultaneously optimize for the torques at the foot contact required to produce this trajectory. (These torques can be derived directly from the xy trajectory and its numerical derivatives, but supplying them as parameters allows us to incorporate dynamic modeling constraints and explicitly extract a torque trajectory through the optimization.)


Across each interval we ensure that the torque and acceleration of the COM respect the dynamics of the LIPM. Finally we constraint the starting and ending point of the COM to that described by the plan.

Foot Step Plan

The plan below includes footstep locations for the right (red) and left (blue) feet, along with initial and final locations (magenta), where  both feet are placed as the COM either starts at rest or comes to a stop.

Dynamic Model - Linear Inverted Pendulum

LIPM is one of the simplest ways to model a bipedal walker. Massless legs require that only the dynamics of the stance leg be considered at once. The stance leg can apply a torque at the contact point. This torque and the contact force determine the movement of the the com, located at the point mass at the top of the leg.

For this model we maintain the height of the COM, despite the true dynamics of an inverted pendulum. This linearization allows us to neglect balance issues which arise when larger contact angles (larger speeds) are obtained.

The model updates foot placement values each time the stance legs switch. A new inverted pendulum is created extending from the new foot placement to the COM.

Dynamic Optimization: Assignment 3
Quan Nguyen, Brian Bittner

For Assignment 3, we optimize center of mass (COM) trajectories for a simplistic walking model (LIPM). We are provided a footstep location plan with timing information. Our goal is to minimize a cost function that penalizes torque output, COM distance from foot location, and COM velocity. The specifics of  our model and cost function are included below. Code to search for various trajectory types is located here.

x,y =position of the center of mass

z = height, maintained at length l

g =gravitational force

P_x,y = foot placement

u_x,y = ankle torques

Timestep: 0.9872    0.3887    0.3887    0.3887    0.5580    0.5580    0.5580    1.3949

Here we achieve some nice results. Our x(t) is smoothed out and we eliminate the unnecessary waiting time at the beginning and end of the run. Interestingly, we achieve our shortest step times for the first half of the transitions (0.38s). It appears that we are still wasting more energy than we need to. Optimization with respect to the original cost function used about a tenth of the energy.

We run the optimizer again, but multiply the torque penalty by 30. We hope to see whether our intuitive optimal gait characteristics can match up with an energy efficient gait:

Variable Duration: New Cost With Increased Torque Penalty​​

Timestep =   0.4542    0.4091    0.4091    0.4091    0.5160    0.5160    0.6790    0.8111

Predictably, our walker wastes less time at the beginning and end of the runs. Timestep shrinks to around 0.40 seconds for the first few steps.

Now we test with the addition of both penalties, building what we hope is a smooth, quick, energy efficient trajectory.

Variable Duration: Cost + Acceleration & Duration Penalty

The trajectories determined  follow our intuition about how the walker should behave.

The behavior at the beginning and end of the simulation correspond with the torque and velocity penalties. For the initial and final 1.5 seconds, the COM has no incentive to move other than to lessen the position based penalty that will occur at the neighboring footstep location. This leads to asymptotic behavior ore 'stand still' behavior. When the velocity is zero and the COM hovers over the foot placement, no penalty is accumulated for that time interval.

The minimilly-actuated gait seems to accelerate in as few instances as possible. We see an actuation spike at the take-off and slow-down points. Otherwise we see relatively constant velocity, whether the behavior be standing still or walking with constant time step and step length.

The oscillatory motion in the y direction allows for the foot placement to transition with more reliance on the contact force than the y-direction torque actuated at the contact point. This can be seen by the low amplitude y-torque oscillation in the bottom right plot. 

Part 2:

​Now our problem becomes more open ended. We remove timing information from the planner. Now we only have information about the sequence of footstep locations. We pass the 8 placement times as additional parameters to our optimization. We add one constraint that these timesteps sum to the same duration of six seconds. We maintain the same cost function for initial experimentation. Here are the results:

Fixed Duration - Original Cost Function

Timestep =  1.0790    0.5291    0.5291    0.5291    0.5262    0.5300    0.5322    1.3695

To gain an energy efficient gait we loose some trajectory smoothness and speed. From what we can deduceit appears that there will remain a trade off between maintaining constant velocity, quickness, and energy output efficiency.

Part 3: Footstep Location Optimization

Now we look to optimize our COM trajectory with even less planning information. We provide the footstep locations as a set of additional parameters to our optimizer. Our only constraints are that their be 8 steps, and the start/end positions. We initially optimize with the original cost function, with an added penalty which penalizes square difference between footstep choice and the original plan.

​FootStep Location: Original Cost + Planned Location Bias