Autonomous humanoid navigation over discontinuous terrain via ALIP-based dynamic footstep planning

Achieving autonomous navigation to a specific target on discontinuous terrain remains a significant challenge for humanoid robots. Footstep-based navigation methods offer a promising solution by treating the target pose as a hard constraint, yet their practical deployment is hindered by the lack of dynamic stability guarantees in existing kinematic-based footstep planners. In this paper, we propose an ALIP (Angular Momentum Linear Inverted Pendulum)-based dynamic footstep planner that constructs an analytical state-transition model explicitly coupling the current Center of Mass (CoM) state, planned footsteps, and the navigation goal within a mixed-integer optimization, thereby generating footstep sequences that are both dynamically stable and kinematically feasible. To enable autonomous navigation on discontinuous terrain, we further develop a gait-cycle-synchronized perception-planning-control pipeline around this planner, in which a probabilistic elevation mapping module supplies complete terrain information and the entire perception-planning-control loop completes within a gait cycle, enabling continuous and real-time replanning. The integrated system is validated through simulations and real-world experiments on the EFC humanoid platform, demonstrating enhanced dynamic stability and successful autonomous navigation over discontinuous terrain.