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.
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