Hierarchical Planning and Learning for Robots in Stochastic Settings Using Zero-Shot Option Invention

Naman Shah, Siddharth SrivastavaAAAI 2024 · OpenReview

Abstract

This paper addresses the problem of inventing and using hierarchical representations for stochastic robot-planning problems. Rather than using hand-coded state or action representations as input, it presents new methods for learning how to create a high-level action representation for long-horizon, sparse reward robot planning problems in stochastic settings with unknown dynamics. After training, this system yields a robot-specific but environment independent planning system. Given new problem instances in unseen stochastic environments, it first creates zero-shot options (without any experience on the new environment) with dense pseudo-rewards and then uses them to solve the input problem in a hierarchical planning and refinement process. Theoretical results identify sufficient conditions for completeness of the presented approach. Extensive empirical analysis shows that even in settings that go beyond these sufficient conditions, this approach convincingly outperforms baselines by 2x in terms of solution time with orders of magnitude improvement in solution quality.

Introduction

Robot planning is notoriously difficult when three factors collide: long horizons, sparse rewards, and stochasticity. Traditional Reinforcement Learning (RL) is often sample-inefficient in these settings, while classical motion planning methods like RRT are brittle when faced with movement noise, requiring frequent and computationally expensive re-planning.

This paper introduces SHARP (Stochastic Hierarchical Abstraction-guided Robot Planner), a framework designed to bridge this gap. SHARP automatically abstracts complex, continuous environments into discrete "rooms" and "doorways," allowing a robot to plan at a high level while utilizing robust local policies at the low level.

Methodology: Zero-Shot Option Invention

The core innovation of SHARP is its ability to "invent" high-level actions (options) for a new environment without prior experience. This process, termed Zero-Shot Option Invention, consists of several integrated stages:

  1. Critical Region Prediction: A pre-trained U-Net identifies "critical regions"—bottlenecks like doorways or hubs like room centers—from a map of the environment.
  2. State Abstraction: These regions guide the construction of a Region-based Voronoi Diagram (RBVD), partitioning the continuous space into discrete abstract states.
  3. Option Invention: The system defines sub-policies (options) for moving between region centroids and across interfaces.
  4. Zero-Shot Option Guides: To overcome the sparse-reward problem, SHARP generates "dense pseudo-rewards" for each option. It calculates a geometric path and rewards the robot for staying near it, effectively guiding the low-level RL agent.
The SHARP pipeline for Zero-Shot Option Invention and Hierarchical Planning.

At the high level, SHARP employs A* search to sequence these options. At the low level, it uses Soft Actor-Critic (SAC) to learn the precise motor controls required to execute them in a stochastic environment.

Experimental Setup

The critical region predictor was trained on 20 environments. The full system was then evaluated on 7 unseen environments, ranging from 15m x 15m to 75m x 75m. Testing involved three distinct robot models: the Husky and Limo ground robots, and the Fetch manipulator arm. SHARP was compared against two primary baselines: end-to-end SAC and RRT-Replan (classical planning with re-execution).

Results and Discussion

SHARP demonstrates superior scalability and reliability compared to existing methods. In large 75m x 75m environments, SHARP was the only approach to consistently solve the tasks, as the horizon length caused SAC to fail completely.

Performance comparison of SHARP vs. baselines in two environments for the Husky robot.

Key findings include:

  • Efficiency: SHARP achieved a 2× speedup in solution time over RRT-Replan.
  • Reliability: SHARP maintained a success rate exceeding 90%, whereas RRT-Replan's success fell below 33% in large, noisy environments due to accumulated stochastic drift.
  • Generalization: The system is robot-specific but environment-independent; once trained for a robot's kinematics, it can be deployed in any new map to invent its own plan zero-shot.

Conclusion

SHARP highlights that geometric bottlenecks are universal features that can be leveraged for zero-shot generalization in robot navigation. By combining deep learning for abstraction with hierarchical planning and RL, it provides a robust solution for long-horizon tasks in noisy environments. While currently dependent on the accuracy of the critical region predictor, future work aims to extend these abstractions to even more complex, high-dimensional tasks.

Summary updated

Abstract

This paper addresses the problem of inventing and using hierarchical representations for stochastic robot-planning problems. Rather than using hand-coded state or action representations as input, it presents new methods for learning how to create a high-level action representation for long-horizon, sparse reward robot planning problems in stochastic settings with unknown dynamics. After training, this system yields a robot-specific but environment independent planning system. Given new problem instances in unseen stochastic environments, it first creates zero-shot options (without any experience on the new environment) with dense pseudo-rewards and then uses them to solve the input problem in a hierarchical planning and refinement process. Theoretical results identify sufficient conditions for completeness of the presented approach. Extensive empirical analysis shows that even in settings that go beyond these sufficient conditions, this approach convincingly outperforms baselines by 2x in terms of solution time with orders of magnitude improvement in solution quality.
BibTeX
@inproceedings{shah2024hierarchical,
  author = {Naman Shah and Siddharth Srivastava},
  title = {{Hierarchical Planning and Learning for Robots in Stochastic Settings Using Zero-Shot Option Invention}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2024},
  url = {https://openreview.net/forum?id=IBmEgAO8RQ},
}
Figure