Online footstep planning is essential for bipedal walking robots, allowing them to walk in the presence of
disturbances and sensory noise. Most of the literature on the topic has focused on optimizing the footstep
placement while keeping the step timing constant. In this work, we introduce a footstep planner capable of
optimizing footstep placement and step time online. The proposed planner, consisting of an Interior Point
Optimizer (IPOPT) and an optimizer based on Augmented Lagrangian (AL) method with analytical gradient descent, solves the full dynamics of the Linear Inverted Pendulum (LIP) model in real time to optimize for footstep location as well as step timing at the rate of 200 Hz. We show that such asynchronous real-time optimization with the AL method (ARTO-AL) provides the required robustness and speed for successful online footstep planning. Furthermore, ARTO-AL can be extended to plan footsteps in 3D, allowing terrain-aware footstep planning on uneven terrains. Compared to an algorithm with no footstep time adaptation, our proposed ARTO-AL demonstrates increased stability in simulated walking experiments as it can resist pushes on flat ground and on a 10◦ ramp up to 120 N and 100 N respectively. Videos2 and open-source code3 are released.