pith. sign in

arxiv: 1907.08673 · v1 · pith:DBCTXPODnew · submitted 2019-07-19 · 💻 cs.RO

Footstep Planning for Autonomous Walking Over Rough Terrain

Robert J. Griffin , Georg Wiedebach , Stephen McCrory , Sylvain Bertrand , Inho Lee , Jerry Pratt This is my paper

Pith reviewed 2026-05-24 19:01 UTC · model grok-4.3

classification 💻 cs.RO
keywords footstep planningA* searchhumanoid robotsrough terrainpartial footholdsautonomous locomotion
0
0 comments X

The pith

A new A* footstep planner uses planar regions to enable autonomous walking over rough terrain.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The authors aim to let humanoid robots plan their own steps in messy environments without constant human guidance. They do this with an A* planner that treats the ground as connected planar patches rather than a full 3D map. Partial footholds on region edges are explicitly allowed to open more possible steps. After finding a coarse plan the system refines the foot positions to lie between the discrete choices. Tests in simulation and on two real robots confirm the plans succeed on rough and cluttered surfaces.

Core claim

By representing the environment with planar regions the A* planner can search efficiently for footstep sequences that reach a goal while respecting stability and reachability constraints even when only parts of a foot can be placed on a surface.

What carries the argument

A* search over a footstep graph derived from planar region segmentation of the terrain.

If this is right

  • Footstep plans can be computed quickly enough for autonomous operation in cluttered spaces.
  • Robots gain the ability to use more surfaces by stepping partially on obstacles or edges.
  • Post-processing refines lattice-based plans into continuous better solutions.
  • Real-world tests confirm the plans execute on physical humanoid platforms over varied terrain.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The method could support online replanning if plane segmentation runs in real time from onboard sensors.
  • Partial foothold logic might extend to other contact problems such as ladder climbing or manipulation.
  • Tighter coupling with whole-body balance controllers could allow the planner to account for dynamic recovery steps.

Load-bearing premise

The environment can be segmented accurately into planar regions and partial footholds provide sufficient stability for the robot to balance.

What would settle it

A scenario where the planar segmentation misidentifies a non-flat surface leading to an invalid plan, or where execution of a partial-foothold sequence causes the robot to lose balance.

Figures

Figures reproduced from arXiv: 1907.08673 by Georg Wiedebach, Inho Lee, Jerry Pratt, Robert J. Griffin, Stephen McCrory, Sylvain Bertrand.

Figure 1
Figure 1. Figure 1: Results of the footstep planner going up and back down a pile of [PITH_FULL_IMAGE:figures/full_fig_p001_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Example of node expansion. Left: The parent node (red), with [PITH_FULL_IMAGE:figures/full_fig_p003_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Example of our representation of the environment as planar regions. [PITH_FULL_IMAGE:figures/full_fig_p003_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: To map the R 3 node location to the R 6 foot spatial location, we snap the foot polygon to the highest planar region in space. The snap always go to the highest region [PITH_FULL_IMAGE:figures/full_fig_p003_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Different edge checks, where red is rejected and blue is accepted. [PITH_FULL_IMAGE:figures/full_fig_p004_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Left: To verify that the robot isn’t attempting to step over too high [PITH_FULL_IMAGE:figures/full_fig_p004_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: The cost of each edge is determined by a variety of cost factors, [PITH_FULL_IMAGE:figures/full_fig_p005_7.png] view at source ↗
Figure 9
Figure 9. Figure 9: The node placement when aligned with the grid may result in the [PITH_FULL_IMAGE:figures/full_fig_p005_9.png] view at source ↗
Figure 10
Figure 10. Figure 10: If the footstep lattice lines up with a small planar region, it can [PITH_FULL_IMAGE:figures/full_fig_p005_10.png] view at source ↗
Figure 11
Figure 11. Figure 11: Results of the footstep planner in several of our sample environments. The start and goal positions are shown by the red and green spheres, [PITH_FULL_IMAGE:figures/full_fig_p006_11.png] view at source ↗
Figure 13
Figure 13. Figure 13: Images of the robot executing several plans generated by the [PITH_FULL_IMAGE:figures/full_fig_p007_13.png] view at source ↗
Figure 12
Figure 12. Figure 12: Resulting plan of Valkyrie planning between a narrow gap, using [PITH_FULL_IMAGE:figures/full_fig_p007_12.png] view at source ↗
Figure 14
Figure 14. Figure 14: Resulting plan of Valkyrie using the anytime capabilities of the footstep planner. The robot dynamically avoided objects placed in its path, [PITH_FULL_IMAGE:figures/full_fig_p008_14.png] view at source ↗
read the original abstract

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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 1 minor

Summary. The manuscript presents a new A* footstep planner for humanoid robots that represents the environment via planar regions to enable planning over rough terrain. It incorporates an approach for using partial footholds to expand available options, applies post-processing to refine solutions beyond the footstep graph's lattice discretization, and reports demonstrations in virtual and real environments on the Atlas and Valkyrie platforms.

Significance. If the core assumptions hold and the planner is shown to be robust, the work could meaningfully advance autonomous humanoid locomotion by reducing operator burden in cluttered, uneven settings. The planar-region representation and partial-foothold mechanism are practical engineering contributions that address real constraints in field deployment.

major comments (2)
  1. [Abstract] Abstract: the central claim that the planner enables footstep planning over rough terrain rests on the assumptions that the environment can be accurately segmented into planar regions and that partial footholds remain stable; however, the manuscript provides no quantitative metrics on segmentation error tolerance, stability margins under partial contact, or failure cases when these assumptions are violated.
  2. [Abstract] The demonstrations on Atlas and Valkyrie are described but lack reported success rates, timing data, or ablation studies that would confirm the planner's performance gains are attributable to the planar representation and partial-foothold extensions rather than other factors.
minor comments (1)
  1. [Abstract] The abstract contains a grammatical omission: 'utilizes a planar region representation of the environment enable footstep planning' should read 'to enable'.

Simulated Author's Rebuttal

2 responses · 2 unresolved

We thank the referee for the constructive feedback. We address each major comment below, providing the strongest honest response based on the manuscript's scope and available results. The work centers on the planning algorithm assuming a planar region map is supplied by perception.

read point-by-point responses

  1. Referee: [Abstract] Abstract: the central claim that the planner enables footstep planning over rough terrain rests on the assumptions that the environment can be accurately segmented into planar regions and that partial footholds remain stable; however, the manuscript provides no quantitative metrics on segmentation error tolerance, stability margins under partial contact, or failure cases when these assumptions are violated.

    Authors: The manuscript's contribution is the A* planner that operates on a given planar region representation to enable planning over rough terrain; it does not include or evaluate the upstream segmentation process. Partial-foothold support expands the search space with the assumption that the low-level controller maintains stability under partial contact. We will revise the abstract and add a dedicated assumptions section discussing reliance on accurate mapping and potential failure modes. However, the original experiments did not collect quantitative data on segmentation error tolerance or stability margins. revision: partial

  2. Referee: [Abstract] The demonstrations on Atlas and Valkyrie are described but lack reported success rates, timing data, or ablation studies that would confirm the planner's performance gains are attributable to the planar representation and partial-foothold extensions rather than other factors.

    Authors: The demonstrations validate feasibility across virtual and real rough-terrain scenarios, including cases using partial footholds. We can incorporate any logged timing data from the Atlas and Valkyrie trials into a revision. Ablation studies isolating the planar representation and partial-foothold contributions were not performed in the original work, so we cannot attribute performance gains quantitatively without new experiments. revision: partial

standing simulated objections not resolved
  • Quantitative metrics on segmentation error tolerance, stability margins under partial contact, or failure cases
  • Success rates, timing data, and ablation studies confirming performance gains from the planar representation and partial-foothold extensions

Circularity Check

0 steps flagged

No circularity: algorithmic description with no derivational chain

full rationale

The paper presents an A* footstep planner using planar region representations and partial footholds, followed by post-processing and robot demonstrations. No equations, fitted parameters, uniqueness theorems, or self-citations appear in the abstract or description that could reduce a claimed result to its own inputs by construction. The work is self-contained as an engineering contribution; assumptions about segmentation and stability are stated as requirements rather than derived quantities. This matches the default non-circular outcome for papers lacking mathematical derivations.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract describes an algorithmic system without introducing new mathematical constants, axioms, or postulated entities.

pith-pipeline@v0.9.0 · 5677 in / 997 out tokens · 21001 ms · 2026-05-24T19:01:49.332600+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

22 extracted references · 22 canonical work pages · 1 internal anchor

  1. [1]

    Adaptive level-of-detail planning for efficient humanoid navigation,

    A. Hornung and M. Bennewitz, “Adaptive level-of-detail planning for efficient humanoid navigation,” in 2012 IEEE International Confer- ence on Robotics and Automation (ICRA) . IEEE, 2012, pp. 997– 1002

    work page 2012

  2. [2]

    Any- time search-based footstep planning with suboptimality bounds,

    A. Hornung, A. Dornbush, M. Likhachev, and M. Bennewitz, “Any- time search-based footstep planning with suboptimality bounds,” in 12th IEEE-RAS International Conference on Humanoid Robots (Hu- manoids), 2012, pp. 674–679

    work page 2012

  3. [3]

    Planning biped navigation strategies in complex environments,

    J. Chestnutt, J. Kuffner, K. Nishiwaki, and S. Kagami, “Planning biped navigation strategies in complex environments,” in 3rd IEEE- RAS International Conference on Humanoid Robots (Humanoids), Oct 2003

    work page 2003

  4. [4]

    Footstep planning for the Honda Asimo humanoid,

    J. Chestnutt, M. Lau, G. Cheung, J. Kuffner, J. Hodgins, and T. Kanade, “Footstep planning for the Honda Asimo humanoid,” in 2005 IEEE International Conference on Robotics and Automation (ICRA). IEEE, 2005, pp. 629–634

    work page 2005

  5. [5]

    An adaptive action model for legged navigation planning,

    J. Chestnutt, K. Nishiwaki, J. Kuffner, and S. Kagami, “An adaptive action model for legged navigation planning,” in 2007 7th IEEE-RAS International Conference on Humanoid Robots (Humanoids) . IEEE, 2007, pp. 196–202

    work page 2007

  6. [6]

    Su- pervised footstep planning for humanoid robots in rough terrain tasks using a black box walking controller,

    A. Stumpf, S. Kohlbrecher, D. C. Conner, and O. von Stryk, “Su- pervised footstep planning for humanoid robots in rough terrain tasks using a black box walking controller,” in 2014 IEEE-RAS International Conference on Humanoid Robots (Humanoids). IEEE, 2014, pp. 287– 294

    work page 2014

  7. [7]

    Footstep planning on uneven terrain with mixed-integer convex optimization,

    R. Deits and R. Tedrake, “Footstep planning on uneven terrain with mixed-integer convex optimization,” in 14th IEEE-RAS International Conference on Humanoid Robots (Humanoids) , 2014, pp. 279–286

    work page 2014

  8. [8]

    Real-time footstep planning using a geometric approach,

    P. Karkowski and M. Bennewitz, “Real-time footstep planning using a geometric approach,” in 2016 IEEE International Conference on Robotics and Automation (ICRA) . IEEE, 2016, pp. 1782–1787

    work page 2016

  9. [9]

    Humanoid navigation in uneven terrain using learned estimates of traversability,

    Y .-C. Lin and D. Berenson, “Humanoid navigation in uneven terrain using learned estimates of traversability,” in 2017 IEEE-RAS 17th International Conference on Humanoid Robotics (Humanoids). IEEE, 2017, pp. 9–16

    work page 2017

  10. [10]

    Efficient Humanoid Contact Planning using Learned Centroidal Dynamics Prediction

    Y .-C. Lin, B. Ponton, L. Righetti, and D. Berenson, “Efficient hu- manoid contact planning using learned centroidal dynamics predic- tion,” arXiv preprint arXiv:1810.13082 , 2018

    work page internal anchor Pith review Pith/arXiv arXiv 2018

  11. [11]

    Real-time footstep planning in 3d environments,

    P. Karkowski, S. Oßwald, and M. Bennewitz, “Real-time footstep planning in 3d environments,” in 2016 IEEE-RAS 16th International Conference on Humanoid Robots (Humanoids) . IEEE, 2016, pp. 69– 74

    work page 2016

  12. [12]

    CHOMP: Gradient optimization techniques for efficient motion planning,

    N. Ratliff, M. Zucker, J. A. Bagnell, and S. Srinivasa, “CHOMP: Gradient optimization techniques for efficient motion planning,” in 2009 IEEE International Conference on Robotics and Automation (ICRA). IEEE, 2009

    work page 2009

  13. [13]

    Gait and trajectory optimization for legged systems through phase-based end- effector parameterization,

    A. W. Winkler, C. D. Bellicoso, M. Hutter, and J. Buchli, “Gait and trajectory optimization for legged systems through phase-based end- effector parameterization,” IEEE Robotics and Automation Letters , vol. 3, no. 3, pp. 1560–1567, 2018

    work page 2018

  14. [14]

    A convex model of humanoid momentum dynamics for multi-contact motion genera- tion,

    B. Ponton, A. Herzog, S. Schaal, and L. Righetti, “A convex model of humanoid momentum dynamics for multi-contact motion genera- tion,” in 2016 IEEE-RAS 16th International Conference on Humanoid Robots (Humanoids). IEEE, 2016, pp. 842–849

    work page 2016

  15. [15]

    Online walking motion generation with automatic footstep placement,

    A. Herdt, H. Diedam, P.-B. Wieber, D. Dimitrov, K. Mombaur, and M. Diehl, “Online walking motion generation with automatic footstep placement,” Advanced Robotics, vol. 24, no. 5-6, pp. 719–737, 2010

    work page 2010

  16. [16]

    A reactive walking pattern generator based on nonlinear model predictive control,

    M. Naveau, M. Kudruss, O. Stasse, C. Kirches, K. Mombaur, and P. Sou`eres, “A reactive walking pattern generator based on nonlinear model predictive control,” IEEE Robotics and Automation Letters , vol. 2, no. 1, pp. 10–17, 2016

    work page 2016

  17. [17]

    A versatile and efficient pattern generator for generalized legged locomotion,

    J. Carpentier, S. Tonneau, M. Naveau, O. Stasse, and N. Mansard, “A versatile and efficient pattern generator for generalized legged locomotion,” in 2016 IEEE International Conference on Robotics and Automation (ICRA). IEEE, 2016, pp. 3555–3561

    work page 2016

  18. [18]

    Weighted A* search-unifying view and application,

    R. Ebendt and R. Drechsler, “Weighted A* search-unifying view and application,” Artificial Intelligence, vol. 173, no. 14, pp. 1310–1342, 2009

    work page 2009

  19. [19]

    Computing large convex regions of obstacle- free space through semidefinite programming,

    R. Deits and R. Tedrake, “Computing large convex regions of obstacle- free space through semidefinite programming,” in Algorithmic foun- dations of robotics XI . Springer, 2015, pp. 109–124

    work page 2015

  20. [20]

    3d perception and environment map generation for humanoid robot navigation,

    J.-S. Gutmann, M. Fukuchi, and M. Fujita, “3d perception and environment map generation for humanoid robot navigation,” The International Journal of Robotics Research, vol. 27, no. 10, pp. 1117– 1134, 2008

    work page 2008

  21. [21]

    Humans exploit the biomechanics of bipedal gait during visually guided walking over complex terrain,

    J. S. Matthis and B. R. Fajen, “Humans exploit the biomechanics of bipedal gait during visually guided walking over complex terrain,” Proceedings of the Royal Society B: Biological Sciences , vol. 280, no. 1762, p. 20130700, 2013

    work page 2013

  22. [22]

    ARA*: Anytime A* with provable bounds on sub-optimality,

    M. Likhachev, G. J. Gordon, and S. Thrun, “ARA*: Anytime A* with provable bounds on sub-optimality,” in Advances in neural information processing systems, 2004, pp. 767–774

    work page 2004