Abstract
Traditional AI planning often relies on manually defined symbolic models, which can be difficult to construct for complex, real-world systems. This paper presents a framework that learns transition dynamics using Binarized Neural Networks (BNNs) and compiles them into Boolean Satisfiability (SAT) or Binary Linear Programming (BLP) problems. This approach enables optimal planning in discrete, factored state-action spaces while maintaining high expressiveness and computational efficiency.
Introduction
In classical AI planning, domain experts typically use languages like PDDL to describe state transitions. However, hand-coding these models for complex environments is often impractical. While deep learning offers a path to learning transition models from data, planning through standard neural networks is computationally intensive due to non-linear activations like ReLU.
This research addresses two primary challenges: efficiently representing neural networks as logical constraints for solvers and handling the inherent inaccuracies of learned models to prevent "hallucinated" plans. The proposed solution utilizes BNNs, which use binary weights and activations, making them naturally compatible with discrete planning environments.
Methodology
The framework consists of three core components: learning, compilation, and refinement.
BNN Transition Models
Binarized Neural Networks are trained to predict the next state given the current state and action. Because BNNs operate on binary values (+1/-1), they are well-suited for factored spaces where states are represented by sets of binary or integer variables.
Compilation for Planning
To find a plan, the trained BNN is "unrolled" over a planning horizon $H$ and translated into a solver-friendly format. The authors developed two primary methods:
- FD-SAT-Plan: Converts BNN layers into Conjunctive Normal Form (CNF) for SAT solvers.
- FD-BLP-Plan: Translates the network into linear constraints for Binary Linear Programming (BLP) solvers.
Incremental Repair
To mitigate model inaccuracies, an incremental algorithm is employed. If a generated plan fails in the actual environment, the system identifies the failure point, generates a "generalized landmark constraint" to block that specific invalid sequence, and re-plans. This ensures robustness even when the learned model is not 100% accurate.
Experimental Evaluation
The approach was evaluated on three deterministic domains from the International Probabilistic Planning Competition (IPPC): Navigation (maze traversal), Inventory (stock management), and SysAdmin (network maintenance). These domains feature factored state spaces, requiring the model to capture complex, concurrent interactions.
Key Results and Insights
The study revealed several critical findings regarding the efficiency and expressiveness of BNN-based planning.
Performance and Scalability
The BLP encoding proved significantly more efficient than the SAT-based approach. BLP solvers are better equipped to handle the weighted sums and thresholding logic inherent in neural network structures.
As shown in the runtime analysis, the BLP-based planners consistently found solutions within seconds, often outperforming SAT-based versions by two orders of magnitude. The BLP+ variant further extends this capability to maximize reward functions over time.
Model Accuracy and Robustness
BNNs achieved high accuracy in learning transition dynamics, with test errors ranging from 2.12% to 8.99%. Crucially, the incremental repair algorithm was highly effective; most problems were solved in zero or one iterations, demonstrating that a perfect model is not a prerequisite for finding a valid plan.
Conclusion
This work demonstrates a successful integration of deep learning and symbolic planning. By leveraging the structural properties of Binarized Neural Networks, the framework provides a scalable method for planning in complex discrete environments. Future research will focus on scaling to longer planning horizons and extending the methodology to stochastic environments where action outcomes are probabilistic.
Summary updated