Value Iteration Networks on Multiple Levels of Abstraction

Daniel Schleich, Tobias Klamt, Sven Behnke

Abstract: Learning-based methods are promising to plan robot motion without performing extensive search, which is needed by many non-learning approaches. Recently, Value Iteration Networks (VINs) received much interest since—in contrast to standard CNN-based architectures—they learn goal-directed behaviors which generalize well to unseen domains. However, VINs are restricted to small and low-dimensional domains, limiting their applicability to real-world planning problems. To address this issue, we propose to extend VINs to representations with multiple levels of abstraction. While the vicinity of the robot is represented in sufficient detail, the representation gets spatially coarser with increasing distance from the robot. The information loss caused by the decreasing resolution is compensated by increasing the number of features representing a cell. We show that our approach is capable of solving significantly larger 2D grid world planning tasks than the original VIN implementation. In contrast to a multiresolution coarse-to-fine VIN implementation which does not employ additional descriptive features, our approach is capable of solving challenging environments, which demonstrates that the proposed method learns to encode useful information in the additional features. As an application for solving real-world planning tasks, we successfully employ our method to plan omnidirectional driving for a search-and-rescue robot in cluttered terrain.

Introduction

In robot motion planning, traditional search-based algorithms like A or RRT provide optimality and completeness guarantees but often struggle with the "curse of dimensionality" in high-dimensional state spaces. Recent advances in deep learning have introduced Convolutional Neural Networks (CNNs) as a potential alternative for fast, parallelizable planning. A significant milestone was the Value Iteration Network (VIN)*, which embeds a differentiable planning module—approximating the Bellman equation—directly within the neural architecture. This allows the network to learn explicit goal-directed behavior rather than simple reactive mapping.

Despite their theoretical elegance, standard VINs scale poorly. Because they perform iterative updates over the entire state space, memory and compute requirements explode as map sizes increase. Consequently, original VIN implementations were largely restricted to small toy problems, such as 28x28 grids. This work introduces Abstract Value Iteration Networks (AVINs) to bridge the gap between neural planning and the scale required for real-world robotics.

The AVIN Approach

The core innovation of AVINs is the use of multiple levels of spatial abstraction to represent the environment. Instead of a single high-resolution map, the network maintains several maps that vary in resolution based on their distance from the agent.

Conceptual overview of AVIN: The environment is represented at multiple levels of spatial abstraction, where coarser levels use more features to preserve information.

Spatial Abstraction and Feature Compensation

In the AVIN architecture, "Level 1" provides a high-resolution view of the robot's immediate vicinity. Subsequent levels cover exponentially larger areas at progressively lower resolutions. To maintain a constant computational footprint, the grid size (e.g., 8x8 cells) remains the same across all levels.

To prevent the catastrophic information loss typically associated with downsampling—where a narrow doorway might disappear in a coarse grid—AVINs employ feature compensation. As spatial resolution decreases, the number of feature channels increases. For example, a single cell in a coarse level might use 10 features to encode complex topological data, such as whether a region is traversable from specific directions. This allows the network to learn to "summarize" spatial bottlenecks into semantic feature vectors.

Architecture and Implementation

The AVIN pipeline consists of several integrated modules: an Abstraction Module, a Reward Module, a Value Iteration (VI) Module, and a Reactive Policy.

The full AVIN pipeline, processing occupancy and goal maps through abstraction, reward, and value iteration modules to produce action probabilities.
  1. Abstraction Module: Generates the multi-level environment and goal maps from raw occupancy data.
  2. Reward Module: Maps the abstract environment and goal representations to a reward signal for each level.
  3. VI Module: Performs the differentiable value iteration. To ensure information flows from distant, coarse maps down to local, fine maps, the edges of lower-level maps are padded with state-values derived from the corresponding higher-level maps.
  4. Reactive Policy: Converts the final state-value maps into action probabilities for the robot.

Training these complex architectures required specific optimization strategies. The authors found that standard optimizers often stalled in local minima. Implementing a cyclic learning rate (cosine annealing with warm restarts) was crucial for stabilizing training and achieving high success rates.

Experimental Results

The AVIN was evaluated on 2D grid worlds, complex mazes, and 3D robot locomotion tasks (x, y, and orientation) for the Centauro search-and-rescue robot.

  • Memory Efficiency: On 128x128 grids, AVIN reduced graphics memory requirements by 86% compared to standard VINs (1.1 GB vs. 8.2 GB).
  • Planning Performance: On 128x128 random grids, AVIN achieved an 88.7% success rate, vastly outperforming the standard VIN's 31.5%. In 64x64 mazes, AVIN's feature compensation proved vital, achieving a 59.3% success rate compared to just 14.2% for hierarchical VINs without extra features.
  • Real-World Application: For the 3D Centauro locomotion task, AVIN successfully planned paths through cluttered terrain with a 74.2% success rate. Notably, its planning time (~0.28s) was comparable to an optimized A* expert (~0.26s), demonstrating that neural planners can be competitive in high-dimensional spaces.

Conclusion

Abstract Value Iteration Networks demonstrate that neural planning can scale to large, complex environments by leveraging hierarchical representations. By replacing raw spatial resolution with learned feature depth, AVINs retain critical environmental information while drastically reducing memory overhead. While not yet reliable enough for standalone safety-critical use, AVINs show immense potential as fast, learned heuristics that can guide traditional search-based planners, combining the speed of deep learning with the guarantees of classical algorithms.

Summary updated

Abstract

Learning-based methods are promising to plan robot motion without performing extensive search, which is needed by many non-learning approaches. Recently, Value Iteration Networks (VINs) received much interest since---in contrast to standard CNN-based architectures---they learn goal-directed behaviors which generalize well to unseen domains. However, VINs are restricted to small and low-dimensional domains, limiting their applicability to real-world planning problems. To address this issue, we propose to extend VINs to representations with multiple levels of abstraction. While the vicinity of the robot is represented in sufficient detail, the representation gets spatially coarser with increasing distance from the robot. The information loss caused by the decreasing resolution is compensated by increasing the number of features representing a cell. We show that our approach is capable of solving significantly larger 2D grid world planning tasks than the original VIN implementation. In contrast to a multiresolution coarse-to-fine VIN implementation which does not employ additional descriptive features, our approach is capable of solving challenging environments, which demonstrates that the proposed method learns to encode useful information in the additional features. As an application for solving real-world planning tasks, we successfully employ our method to plan omnidirectional driving for a search-and-rescue robot in cluttered terrain.
BibTeX
@inproceedings{schleich2019value,
  author = {Daniel Schleich and Tobias Klamt and Sven Behnke},
  title = {{Value Iteration Networks on Multiple Levels of Abstraction}},
  booktitle = {Robotics: Science and Systems},
  year = {2019},
  url = {https://openreview.net/forum?id=OiDdaBld4E},
}
Figure