Hierarchies of Planning and Reinforcement Learning for Robot Navigation

Jan Wöhlke, Felix Schmitt, Herke van Hoof

TL;DR

This paper introduces VI-RL, a hierarchical framework that combines high-level (HL) path planning with low-level (LL) reinforcement learning for robot navigation. By learning a transition model that reflects the robot's actual physical capabilities and environmental constraints, the system can plan smarter paths that avoid "difficult" areas the robot might struggle to navigate, significantly outperforming standard RL and non-adaptive hierarchical methods.

What Problem Does This Paper Address?

Reinforcement Learning (RL) is notoriously difficult for robot navigation because rewards are usually "sparse"—the robot only knows it did a good job once it actually reaches the goal. In a large environment, a robot might wander aimlessly for ages before stumbling upon the target.

While we often have "high-level" information like floor plans or maps, simply following the shortest path on a map isn't enough. Why? Because maps often ignore dynamics. A shortest-path planner might tell a car-like robot to make a sharp U-turn it physically can't manage, or lead a robot across a patch of slippery/slow terrain. Standard hierarchical RL (HRL) often fails to bridge this gap between abstract planning and the messy reality of robot physics.

Methods

The authors propose a two-layer hierarchy:

  1. The High-Level (HL) Planner: This operates on a discrete grid (like a floor plan). Instead of just finding the shortest path, it uses Value Iteration (VI). Crucially, it uses a learned transition model. It observes how often the low-level policy succeeds in moving between grid cells and updates its "beliefs" about which moves are easy or hard.
  2. The Low-Level (LL) Policy: This is a goal-conditioned RL agent (trained using TRPO) that handles the continuous control (e.g., motor torques, accelerations). It receives "intrinsic rewards" for reaching the sub-goals set by the HL planner.

The standout feature is VI-RL (Value Iteration with Reinforcement Learning). Unlike "optimistic" planners that assume every adjacent cell is reachable, VI-RL learns the probability of success for every transition. If the LL policy consistently fails to reach a specific sub-goal (perhaps due to an obstacle or complex physics), the HL planner learns to route around it.

Datasets (Simulation Environments)

The researchers evaluated their approach across three simulated continuous-dynamics domains:

  • Four Rooms: A point-mass robot navigating a grid. One room contains "hard-to-traverse" terrain that slows the robot down.
  • MuJoCo Ant Mazes: A complex, quadruped "ant" robot navigating 25 different randomly generated maze layouts. This tests the ability to generalize across different environments.
  • Vehicle Parking: A car-like (non-holonomic) robot that must park in a specific spot with a specific orientation. This is particularly challenging because the robot cannot move sideways and has a limited turning radius.

Key Insights and Ideas

  • Dynamics Matter in Planning: A key "aha" moment is that shortest-path planning is suboptimal when the robot's capabilities are non-uniform. In the "Four Rooms" task, the shortest path goes through slow terrain. VI-RL learns that this path is "expensive" (takes too many timesteps) and eventually chooses a longer but faster route.
  • Closing the Loop: Most hierarchical systems are "top-down"—the planner dictates, and the RL agent tries to follow. This paper makes it a feedback loop: the RL agent's performance data is used to "teach" the planner what is actually possible.
  • Handling Non-Holonomic Constraints: In the parking task, the orientation of the car matters. The authors found that the HL transition model must consider both the current state and the chosen sub-goal to accurately predict success, as some turns are physically impossible from certain angles.

Key Results

  • Superiority over Vanilla RL: In all tasks, the hierarchical approach (VI-RL) reached the goal much faster and more reliably than "flat" RL (BSL), which often failed to learn at all due to the sparse rewards.
  • Outperforming Shortest-Path Planners: In the "Four Rooms" with terrain, an optimistic shortest-path planner (VI-RL OM) failed because it kept timing out in the slow terrain. VI-RL successfully learned to take the longer, clear path.
  • The Parking Challenge: The parking task was the most decisive. While other state-of-the-art HRL methods (like HiRO) and differentiable planners (MVProp-RL) struggled to reach even a 40% success rate, VI-RL achieved over 80% success by explicitly learning the transition constraints of the car's physics.

Limitations and Future Work

The primary limitation is the reliance on a pre-defined high-level state space. The authors assume the HL state (the grid) and the mapping from the robot's continuous position to that grid are already known.

Future Work: * Learning the Abstraction: The authors suggest that instead of designing the grid manually, future versions could learn to "discretize" the environment into an HL representation automatically from raw sensor data. * Broader Applicability: Testing the system on real-world robots where environmental noise and sensor uncertainty are higher than in MuJoCo simulations.

Summary updated

Abstract

Solving robotic navigation tasks via reinforcement learning (RL) is challenging due to their sparse reward and long decision horizon nature. However, in many navigation tasks, high-level (HL) task representations, like a rough floor plan, are available. Previous work has demonstrated efficient learning by hierarchal approaches consisting of path planning in the HL representation and using sub-goals derived from the plan to guide the RL policy in the source task. However, these approaches usually neglect the complex dynamics and sub-optimal sub-goal-reaching capabilities of the robot during planning. This work overcomes these limitations by proposing a novel hierarchical framework that utilizes a trainable planning policy for the HL representation. Thereby robot capabilities and environment conditions can be learned utilizing collected rollout data. We specifically introduce a planning policy based on value iteration with a learned transition model (VI-RL). In simulated robotic navigation tasks, VI-RL results in consistent strong improvement over vanilla RL, is on par with vanilla hierarchal RL on single layouts but more broadly applicable to multiple layouts, and is on par with trainable HL path planning baselines except for a parking task with difficult non-holonomic dynamics where it shows marked improvements.
BibTeX
@inproceedings{wohlke2021hierarchies,
  author = {Jan Wöhlke and Felix Schmitt and Herke van Hoof},
  title = {{Hierarchies of Planning and Reinforcement Learning for Robot Navigation}},
  booktitle = {IEEE International Conference on Robotics and Automation},
  year = {2021},
  url = {https://openreview.net/forum?id=TXVLWTsgx4b},
}

Loading related content...

Figure