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.
2. Hybrid Branch-and-Bound Search
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.
- 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