A Single-Planner Approach to Multi-Modal Humanoid Mobility

Andrew Dornbush, Karthik Vijayakumar, Sameer Bardapurkar, Fahad Islam, Masayuki Ito, Maxim LikhachevICRA 2018 · DOI

TL;DR

This paper introduces a novel planning framework that allows a single planner to handle diverse humanoid mobility tasks like walking, crawling, and climbing. By adaptively adjusting the dimensionality of the search space and leveraging multiple low-dimensional representations, the planner achieves efficient and robust motion planning for complex, real-world environments.

What Problem Does This Paper Address?

Humanoid robots are increasingly expected to operate in unstructured and human-centric environments, which often require a variety of locomotion skills such as walking, crawling, and climbing. Planning for these diverse skills within a single, unified framework is challenging due to the extremely high dimensionality of a humanoid robot's configuration space. Traditional approaches often rely on hierarchical planning, where a top-level planner decomposes the task and calls specialized planners for each sub-task. This can lead to brittle solutions, as errors in task decomposition or transitions between sub-plans can cause the entire plan to fail. The paper addresses the need for a more integrated and robust approach that can reason about all of a robot's mobility capabilities simultaneously, leading to more reliable and efficient motion planning.

Methods

The core of the paper's contribution lies in its Planning with Adaptive Dimensionality framework, extended to handle Multi-Modal Humanoid Mobility. Here's a breakdown of the key techniques:

  • Adaptive Dimensionality: Instead of always searching in the full, high-dimensional configuration space, the planner adaptively adjusts the dimensionality of the search space. It leverages the observation that many parts of a mobility task can be planned in lower-dimensional spaces (e.g., just foot positions for walking). The planner only increases dimensionality in regions where it's strictly necessary for feasibility.
  • Multiple Low-Dimensional Representations: The framework explicitly incorporates multiple low-dimensional representations, each corresponding to a specific locomotion mode (e.g., bipedal walking, crawling, ladder climbing). This allows the planner to reason about the specific requirements and constraints of each mode.
  • Hybrid Search Space: The planner constructs a hybrid search space that combines states and transitions from both the high-dimensional and multiple low-dimensional representations. This allows for efficient exploration in low-dimensional spaces while ensuring feasibility by incorporating high-dimensional checks when needed.
  • Multi-Heuristic A (MR-MHA): A specialized search algorithm, MR-MHA, is employed. It generalizes the Multi-Heuristic A algorithm to handle multiple low-dimensional representations simultaneously. This allows the search to explore different locomotion modes in parallel, guided by representation-specific heuristics, while maintaining optimality guarantees through an admissible "anchor" heuristic.
  • Experience Graphs (E-Graphs): To further accelerate high-dimensional planning, the approach incorporates Experience Graphs. These leverage prior experience, such as user demonstrations, to guide the search and reuse successful path segments, especially in scenarios where direct controller execution is not feasible.
  • Snap Motions: Adaptive motion primitives are used to handle situations where the robot's state is slightly offset from a demonstrated path. These primitives help the robot quickly adjust to match waypoints, rather than requiring full high-dimensional planning.
  • Interleaved Planning and Execution: To address the typically high planning times, the paper proposes interleaving planning and execution. The planner generates partial plans, which are then sent to the robot's controllers for execution while the planner continues to work on the rest of the path.

Datasets

Not discussed in the paper. The paper focuses on a simulated environment and experimental analysis using a robot's capabilities.

Key Insights and Ideas

  • Unified Planning for Diverse Skills: The most significant insight is that a single, adaptive planner can effectively handle a wide range of humanoid mobility tasks, eliminating the brittleness of hierarchical, multi-planner approaches.
  • Dimensionality is Key: The success hinges on adaptively managing the dimensionality of the search space. By only engaging high-dimensional planning when absolutely necessary, significant computational gains are achieved.
  • Leveraging Controller Capabilities: Explicitly incorporating the capabilities of available controllers into the planning process is crucial for efficiency and robustness. This allows the planner to delegate tasks to specialized controllers when possible.
  • Heuristics for Multi-Representation Search: The MR-MHA* algorithm demonstrates how to effectively guide a search across multiple, distinct low-dimensional representations using tailored heuristics, while still ensuring global optimality.
  • Experience as a Planning Shortcut: Experience Graphs offer a powerful way to inject prior knowledge into the planning process, significantly speeding up the search in complex, high-dimensional spaces.

Key Results

The paper demonstrates the effectiveness of its approach through experimental analysis in a simulated environment.

  • High Success Rates: The planner achieved success rates of 51.52% and 58.87% for two different goals in a complex environment, with planning times of approximately 101.3 and 91.3 seconds, respectively.
  • Reduced Idle Time: By interleaving planning and execution, the robot's idle time is significantly reduced, making the system more responsive and efficient in real-world operation.
  • Practicality Demonstrated: The results show that the approach is practical for real-time execution, especially when combined with interleaved planning and execution.

Limitations and Future Work

  • Limitations:
    • The paper acknowledges that the "tracking" phase (high-dimensional planning) can still be time-consuming, although it's significantly reduced by the adaptive dimensionality and E-Graphs.
  • The success rates, while promising, indicate that there is still room for improvement in planning robustness.
  • The current implementation focuses on specific locomotion modes; extending to even more complex interactions or environments might require further refinement.
  • Future Work:
    • The authors aim to incorporate planning for more complex interactions with the environment.
  • They also plan to address the robustness of scenarios requiring high-dimensional planning.
  • Further exploration of how to integrate more complex controller behaviors and environmental interactions is suggested.

Summary updated

BibTeX
@inproceedings{dornbush2018single,
  author = {Andrew Dornbush and Karthik Vijayakumar and Sameer Bardapurkar and Fahad Islam and Masayuki Ito and Maxim Likhachev},
  title = {{A Single-Planner Approach to Multi-Modal Humanoid Mobility}},
  booktitle = {IEEE International Conference on Robotics and Automation},
  year = {2018},
  doi = {10.1109/icra.2018.8461134},
}
Figure