Search-based planning for a legged robot over rough terrain

Paul Vernaza, Maxim Likhachev, Subhrajit Bhattacharya, Sachin Chitta, Aleksandr Kushleyev, Daniel D. LeeICRA 2009 · OpenReview

TL;DR

This paper presents a novel search-based planning approach for quadrupedal robots navigating rough terrain. By combining a global footstep planner (R* search) with a reactive controller, the system generates robust and efficient trajectories, significantly improving success rates compared to traditional methods.

What Problem Does This Paper Address?

Controlling legged robots, especially quadrupedal ones, to traverse complex and uneven terrain is a significant challenge. While robots like Boston Dynamics' LittleDog are capable of dynamic locomotion, planning safe and efficient paths over rough terrain remains difficult. Traditional approaches often fall into local minima or require computationally expensive real-time replanning. This paper tackles the problem of generating complete, executable joint trajectories for a quadrupedal robot to move from a start to a goal position on rough terrain, assuming accurate knowledge of the terrain and robot pose. The core challenge lies in navigating the high-dimensional state and action spaces of legged robots while ensuring stability and efficiency.

Methods

The authors propose a two-phase approach:

  1. Global Planning (Footstep Trajectory): This phase uses a search-based algorithm called R* search to plan a sequence of foot placements (a footstep trajectory). R is a modified version of A that constructs a sparse graph of states and edges. It efficiently explores the high-dimensional footstep space by generating a limited number of "good" successor states (K states at a distance A) rather than all immediate successors. This approach balances the benefits of deterministic search (optimality guarantees) and randomized search (efficiency in high dimensions). The cost function for R* is carefully designed to encourage stable, robust, and efficient trajectories, considering factors like center of mass travel, incircle radius, reachability, and collision avoidance.
  2. Execution Phase (Joint Trajectory): Once a footstep trajectory is planned, a reactive controller takes over. This controller is responsible for generating time-parameterized joint trajectories to execute the planned footstep sequence. It dynamically computes body trajectories and leg movements, ensuring static stability, avoiding collisions, and adapting to minor deviations from the plan. The controller focuses on controlling the projected center of gravity, body orientation (roll, pitch, yaw), and the flight leg's trajectory.

Datasets

Not discussed in the paper. The paper describes using a Vicon optical motion capture system to track the poses of LittleDog and the terrain, and the terrain itself is composed of scanned "terrain boards." This is more of an experimental setup than a dataset in the traditional sense.

Key Insights and Ideas

  • R* Search for Footstep Planning: Using R* search in the high-dimensional footstep space is a key innovation. It allows for efficient exploration and generation of globally optimal (or near-optimal) footstep sequences, avoiding local minima that plague purely local planners.
  • Cost Function Design: The detailed cost function is crucial. It explicitly penalizes factors that lead to instability and inefficiency, such as large center of mass travel, small incircle radii, and potential collisions. This careful design directly influences the quality and success rate of the generated plans.
  • Decomposition of Planning and Control: Separating the global footstep planning from the low-level joint trajectory generation simplifies the problem. The global planner focuses on "where to step," while the controller handles "how to step" and "how to move the body," making the overall system more manageable and robust.
  • Static Stability as a Primary Constraint: The paper emphasizes static stability, which, while slower than dynamic locomotion, is more error-tolerant and crucial for reliable navigation over rough terrain.

Key Results

  • High Success Rates: In experiments on the LittleDog robot, the R-based planner achieved significantly higher success rates across various challenging terrains (sloped logs with gaps, slopes, steps, rocks with gaps) compared to a weighted A planner. For instance, the "Sloped logs w/ gap" scenario saw a 90% success rate with R versus 0% with weighted A.
  • Efficient Planning: While R* planning time was set to 85 seconds, the resulting plans were executable at reasonable speeds (e.g., 2.95 cm/s for sloped logs with gaps).
  • Robustness: The system demonstrated robustness to terrain variations, successfully navigating complex scenarios with gaps, slopes, and rocks.

Limitations and Future Work

  • Failure Modes: The authors identified common failure modes, including leg collisions with the terrain (beyond just foot collisions) and slippage, particularly on rocky surfaces.
  • Future Work:
    • Reactive Recovery: Developing better reactive recovery methods is highlighted as a key area for improving reliability and robustness.
  • Improved Collision Modeling: More sophisticated collision modeling for the entire leg (not just feet) could mitigate some failure modes.
  • Computational Cost: While R* is efficient, further improvements in computational effort might be needed for faster overall performance or to handle more complex scenarios.
  • Dynamic Locomotion: Extending the approach to dynamic locomotion would be a significant future step.

Summary updated

BibTeX
@inproceedings{vernaza2009search,
  author = {Paul Vernaza and Maxim Likhachev and Subhrajit Bhattacharya and Sachin Chitta and Aleksandr Kushleyev and Daniel D. Lee},
  title = {{Search-based planning for a legged robot over rough terrain}},
  booktitle = {IEEE International Conference on Robotics and Automation},
  year = {2009},
  url = {https://openreview.net/forum?id=lGOJF4hhur},
}
Figure