Scalable Planning with Deep Neural Network Learned Transition Models

Ga Wu, Buser Say, Scott SannerJAIR 2020 · DOI · OpenReview

Introduction

Planning in complex, continuous environments often faces a significant hurdle: the lack of precise "first-principles" physics equations. In domains like reservoir management or large-scale HVAC control, system dynamics are frequently captured through sensor data rather than analytical models. While Deep Neural Networks (DNNs) excel at learning these dynamics from data, using them for planning is challenging due to the high-dimensional, continuous action spaces that frustrate traditional methods like Monte Carlo Tree Search (MCTS).

This paper addresses the "gray-box" planning problem—finding optimal action sequences when the world model is a complex, non-linear neural network. The authors introduce two novel methods: HD-MILP-Plan, an optimal planner that compiles the problem into a mathematical program, and TF-Plan, a highly scalable alternative that leverages gradient descent for plan optimization.

Methodology

Learned Transition Models

The core of the approach is learning a transition model $P(\bar{S}_{t+1} | \bar{S}_t, \bar{A}_t)$ using a DNN. To enhance planning efficiency, the authors utilize architectures with skip connections that allow the model to bypass non-linear layers when the dynamics are locally linear.

Transition model architecture with skip connections (orange dashed lines). The model predicts the next state $\bar{S}_{t+1}$ given the current state $\bar{S}_t$ and action $\bar{A}_t$.

HD-MILP-Plan: Hybrid Deep MILP Planner

HD-MILP-Plan targets optimality by exploiting the piecewise linear nature of Rectified Linear Unit (ReLU) activation functions. A DNN composed of ReLUs can be translated into a Mixed-Integer Linear Program (MILP) using "big-M" constraints to represent the activation state of each neuron. This allows the use of powerful off-the-shelf solvers like CPLEX. To improve performance, the authors introduce "strengthened" constraints that help the solver prune the search space more effectively.

TF-Plan: TensorFlow Planner

TF-Plan is designed for scalability. It reinterprets the planning horizon as a single Recurrent Neural Network (RNN) where the initial state is the input, the learned transition models serve as the "cells," and the actions are the trainable parameters. By "freezing" the network weights and using backpropagation, TF-Plan optimizes the actions to maximize a reward function, effectively treating planning as an inference problem.

Evaluation and Results

The planners were evaluated on three non-linear domains: Reservoir Control, HVAC management (up to 60 rooms), and 2D Navigation with non-linear deceleration zones. Key findings include:

  • Optimality vs. Scalability: HD-MILP-Plan provides optimal solutions for small-to-medium problems, while TF-Plan scales to much larger domains (e.g., 60-room HVAC) with near-optimal performance and significantly lower latency.
  • Performance Gains: Both planners outperformed manual "rule-of-thumb" policies by up to 15%, particularly in the Navigation domain where manual tuning is difficult.
  • The Power of Strengthening: In deeper networks, the "strengthened" MILP encoding was vital; without it, standard encodings often failed to find solutions within reasonable time limits.

Conclusion and Future Work

The research demonstrates that neural networks should be viewed as "gray-boxes" whose internal structure can be exploited for planning. While HD-MILP-Plan offers optimality and handles discrete choices well, TF-Plan provides the scalability needed for large-scale systems. Future work aims to address TF-Plan's limitations with discrete actions and "hard" global constraints, potentially exploring Binarized Neural Networks (BNNs) for discrete state spaces.

Summary updated

Abstract

In many complex planning problems with factored, continuous state and action spaces such as Reservoir Control, Heating Ventilation and Air Conditioning (HVAC), and Navigation domains, it is difficult to obtain a model of the complex nonlinear dynamics that govern state evolution. However, the ubiquity of modern sensors allows us to collect large quantities of data from each of these complex systems and build accurate, nonlinear deep neural network models of their state transitions. But there remains one major problem for the task of control – how can we plan with deep network learned transition models without resorting to Monte Carlo Tree Search and other black-box transition model techniques that ignore model structure and do not easily extend to continuous domains? In this paper, we introduce two types of planning methods that can leverage deep neural network learned transition models: Hybrid Deep MILP Planner (HD-MILP-Plan) and Tensorflow Planner (TF-Plan). In HD-MILP-Plan, we make the critical observation that the Rectified Linear Unit (ReLU) transfer function for deep networks not only allows faster convergence of model learning, but also permits a direct compilation of the deep network transition model to a Mixed-Integer Linear Program (MILP) encoding. Further, we identify deep network specific optimizations for HD-MILP-Plan that improve performance over a base encoding and show that we can plan optimally with respect to the learned deep networks. In TF-Plan, we take advantage of the efficiency of auto-differentiation tools and GPU-based computation where we encode a subclass of purely continuous planning problems as Recurrent Neural Networks and directly optimize the actions through backpropagation. We compare both planners and show that TF-Plan is able to approximate the optimal plans found by HD-MILP-Plan in less computation time. Hence this article offers two novel planners for continuous state and action domains with learned deep neural net transition models: one optimal method (HD-MILP-Plan) and a scalable alternative for large-scale problems (TF-Plan).
BibTeX
@article{wu2020scalable,
  author = {Ga Wu and Buser Say and Scott Sanner},
  title = {{Scalable Planning with Deep Neural Network Learned Transition Models}},
  journal = {J. Artif. Intell. Res.},
  year = {2020},
  doi = {10.1613/jair.1.11829},
}
Figure