# Footstep Planning for Autonomous Walking Over Rough Terrain

arXiv: https://arxiv.org/abs/1907.08673 · HTML: https://mlsanity.com/paper/1907.08673/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Jul 2019.

## Built on by (most cited first, 8 of 8)

- [DTC: Deep Tracking Control](https://mlsanity.com/paper/2309.15462/) (2023)
- [BeamDojo: Learning Agile Humanoid Locomotion on Sparse Footholds](https://mlsanity.com/paper/2502.10363/) (2025)
- [Learning Humanoid Locomotion over Challenging Terrain](https://mlsanity.com/paper/2410.03654/) (2024)
- [A Unified and General Humanoid Whole-Body Controller for Versatile Locomotion](https://mlsanity.com/paper/2502.03206/) (2025)
- [Autonomous Navigation of Underactuated Bipedal Robots in Height-Constrained Environments](https://mlsanity.com/paper/2109.05714/) (2021)
- [Mind Your Steps: A General Learning Framework for Accurate Humanoid Foothold Tracking](https://mlsanity.com/paper/2606.08253/) (2026)
- [Multi-Resolution Planar Region Extraction for Uneven Terrains](https://mlsanity.com/paper/2311.12562/) (2023)
- [AiSDF: Structure-aware Neural Signed Distance Fields in Indoor Scenes](https://mlsanity.com/paper/2403.01861/) (2024)

## Abstract (arXiv)

To increase the speed of operation and reduce operator burden, humanoid robots must be able to function autonomously, even in complex, cluttered environments. For this to be possible, they must be able to quickly and efficiently compute desired footsteps to reach a goal. In this work, we present a new A* footstep planner that utilizes a planar region representation of the environment enable footstep planning over rough terrain. To increase the number of available footholds, we present an approach to allow the use of partial footholds during the planning process. The footstep plan solutions are then post-processed to capture better solutions that lie between the lattice discretization of the footstep graph. We then demonstrate this planner over a variety of virtual and real world environments, including some that require partial footholds and rough terrain using the Atlas and Valkyrie humanoid robots.