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