Nonlinear Hybrid Planning with Deep Net Learned Transition Models and Mixed-Integer Linear Programming

Buser Say, Ga Wu, Yu Qing Zhou, Scott Sanner

Abstract

Planning in hybrid domains with discrete-continuous state spaces and nonlinear dynamics is a fundamental challenge in automated reasoning. This paper presents HD-MILP-PLAN, a novel framework that integrates deep learning with mathematical optimization. By utilizing Rectified Linear Unit (ReLU) based deep neural networks (DNNs) to learn system transition models, we exploit their piecewise linear structure to compile the planning problem into a Mixed-Integer Linear Program (MILP). This approach allows for the use of state-of-the-art MILP solvers to find optimal plans over fixed horizons. We introduce strengthened encoding and network sparsification techniques to enhance computational efficiency. Evaluations on reservoir control, HVAC, and navigation domains demonstrate that our method significantly outperforms traditional heuristics and black-box search techniques.

Introduction

Hybrid systems, characterized by the interaction of discrete decisions and continuous physical processes, are ubiquitous in engineering and environmental management. Examples include managing water levels in interconnected reservoirs or optimizing thermal comfort in buildings. Planning in these environments is notoriously difficult because state transitions are often nonlinear and high-dimensional. Traditional approaches typically rely on simplified linear approximations or treat the system as a black box, using sampling-based methods like Monte Carlo Tree Search (MCTS). However, linear models often fail to capture essential dynamics, while black-box methods struggle with the infinite search space of continuous actions.

Methods

The HD-MILP-PLAN framework addresses these limitations by learning a transition model $T(s, a) = s'$ from data using a densely-connected DNN.

The "Gray Box" Approach

A key insight of this work is that DNNs with ReLU activations are piecewise linear functions. This property allows the network to be treated as a "gray box" whose internal logic can be explicitly encoded into a MILP.

Neural network architecture for learning transition models.

MILP Compilation and Optimization

The learned weights and ReLU activation patterns are translated into linear constraints and binary variables. To ensure the resulting MILP remains tractable, two primary optimizations are employed:

  1. Strengthened Encoding: By introducing auxiliary variables that tighten the linear relaxation of the ReLU constraints, we enable the MILP solver to more effectively prune the search space.
  2. Network Sparsification: We apply a thresholding technique to zero out small weights that do not significantly impact the model's predictive accuracy but reduce the number of constraints in the MILP formulation.

Experimental Evaluation

The framework was evaluated across three benchmark domains representing common engineering challenges:

  • Reservoir Control: Managing water levels across multiple connected reservoirs where evaporation is a nonlinear function of the water level.
  • HVAC: Controlling heaters in multiple rooms where heat transfer is bilinear (depending on both air volume and temperature differences).
  • Navigation: Moving an agent through a 2D space where "slippage" makes movement nonlinear and harder to predict in certain regions.

Results

HD-MILP-PLAN demonstrated superior performance, achieving up to a 42% improvement in total reward in the Navigation task by successfully learning and avoiding nonlinear "slippage" zones that simple greedy policies ignored.

The computational benefits of the proposed optimizations are evident in the runtime analysis. As shown in the figure below, the combination of strengthened encoding and sparsification significantly reduces the total run time across all problem instances, making the approach more feasible for real-time planning applications. In the Navigation domain, these optimizations improved the planner's runtime by up to 80%.

Total run time comparison across test domains.

Conclusion

HD-MILP-PLAN provides a robust methodology for planning in complex hybrid domains by bridging the gap between deep learning and mathematical optimization. By leveraging the piecewise linear nature of ReLUs, the framework offers bounded optimality guarantees based on learned models. Future research will focus on extending the planning horizon and exploring methods to scale the MILP compilation to handle even deeper neural architectures.

Summary updated

Abstract

In many real-world hybrid (mixed discrete continuous) planning problems such as Reservoir Control, Heating, Ventilation and Air Conditioning (HVAC), and Navigation, it is difficult to obtain a model of the complex nonlinear dynamics that govern state evolution. However, the ubiquity of modern sensors allow us to collect large quantities of data from each of these complex systems and build accurate, nonlinear deep 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 mixed discrete and continuous domains? In this paper, we make the critical observation that the popular Rectified Linear Unit (ReLU) transfer function for deep networks not only allows accurate nonlinear deep net model learning, but also permits a direct compilation of the deep network transition model to a Mixed-Integer Linear Program (MILP) encoding in a planner we call Hybrid Deep MILP Planning (HD-MILP-PLAN). We identify deep net specific optimizations and a simple sparsification method for HD-MILP-PLAN that improve performance over a naive encoding, and show that we are able to plan optimally with respect to the learned deep network.
BibTeX
@inproceedings{say2017nonlinear,
  author = {Buser Say and Ga Wu and Yu Qing Zhou and Scott Sanner},
  title = {{Nonlinear Hybrid Planning with Deep Net Learned Transition Models and Mixed-Integer Linear Programming}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2017},
  doi = {10.24963/ijcai.2017/104},
}
Figure