A Unified Framework for Planning with Learned Neural Network Transition Models

Buser SayAAAI 2021 · DOI

Introduction

Automated planning is a cornerstone of artificial intelligence, requiring an agent to determine a sequence of actions to achieve a specific goal. Traditional planning methods rely on hand-coded transition models that define the environment's dynamics. However, in many real-world scenarios, the "physics" of the environment are unknown and must be learned from data using neural networks.

While neural network transition models offer flexibility, they introduce a significant optimization challenge: finding an optimal plan within the learned model. Existing approaches typically fall into two categories: Mixed-Integer Linear Programming (MILP), which is mathematically rigorous but lacks scalability, and Recurrent Neural Network (RNN) gradient-based optimization, which is fast but prone to local minima and struggles with global constraints. This paper introduces a unified framework that bridges this gap, combining the reliability of MILP with the efficiency of deep learning.

Methodology: The Unified Framework

The proposed framework introduces two key technical innovations to solve the scalability-reliability trade-off.

1. Lagrangian RNN Architecture

Standard RNN-based planners often struggle with hard constraints, such as fuel limits or specific goal states, because these discrete boundaries are difficult to differentiate. The authors address this by incorporating constraints as Lagrangian functions. By adding penalty terms to the loss function that represent constraint violations, the RNN can use gradient descent to "learn" to stay within the feasible region. The use of ReLU units to model "max" operators in Lagrangian multipliers ensures that piecewise-linear constraint violations remain entirely differentiable.

The core of the framework is a hybrid algorithm that uses a standard Branch-and-Bound (B&B) search as its backbone. At strategic intervals, the search calls the Lagrangian RNN as a primal heuristic. This creates a powerful synergy: the MILP provides a "warm start" for the RNN by passing it values from a linear relaxation. The RNN then uses gradient descent to rapidly find a high-quality feasible solution. This solution allows the MILP to "prune" the search tree more aggressively, significantly accelerating the overall search process.

Experimental Evaluation

The framework was evaluated on three challenging planning domains characterized by non-linear dynamics:

  • Navigation: 2D maze traversal with exponential transitions.
  • Reservoir Control: Water management across multiple reservoirs using trigonometric functions.
  • Inventory Control: Supply chain management with trigonometric demand cycles and integer constraints.

The researchers generated 64 new instances across these domains to rigorously test the limits of the unified solver against standalone MILP and RNN baselines.

Key Results

The unified framework demonstrated significant improvements in both coverage and solution quality across all tested domains. As shown in the performance plots below, the hybrid approach consistently outperforms the baseline MILP solver in both the number of problems solved and the quality of the solutions found within the time limit.

Performance comparison across Navigation, Reservoir, and Inventory domains. The plots show (a, c, e) the cumulative number of problems solved and (b, d, f) the solution quality (total reward) as a function of runtime.
  • Superior Coverage: The hybrid approach solved 80% more problem instances than the standalone MILP model within a one-hour time limit. In domains like Navigation and Inventory, the MILP often failed to find any solution, while the unified framework found its first valid solution in under 500 seconds.
  • Solution Quality: In the Navigation and Inventory domains, the framework improved total reward by 5% to 20% compared to baseline methods.
  • Real-World Reliability: When validated against a "ground truth" simulator, 95% of the generated plans were verified as feasible, with a duality gap of at most 4%, indicating solutions very close to the theoretical optimum.

Discussion and Future Work

The success of this framework highlights that deep learning can be most effective when integrated as a component within traditional optimization structures rather than replacing them entirely. By using an RNN as a heuristic, the system gains the speed of gradient-based optimization without sacrificing the formal search structure.

However, some challenges remain. The framework is currently sensitive to hyperparameter initialization for Lagrangian multipliers, which can affect convergence. Additionally, the current model assumes a deterministic environment. Future research will focus on extending this framework to stochastic environments and integrating formal verification methods to ensure the robustness of learned transition models against adversarial errors.

Summary updated

BibTeX
@inproceedings{say2021unified,
  author = {Buser Say},
  title = {{A Unified Framework for Planning with Learned Neural Network Transition Models}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.1609/aaai.v35i6.16635},
}
Figure