Planning in Factored State and Action Spaces with Learned Binarized Neural Network Transition Models

Buser Say, Scott Sanner

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.

Unrolling the BNN transition model over time steps t, t+1, and t+2 for planning.

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.

Logarithmic total runtime across Navigation, Inventory, and SysAdmin domains for BLP and BLP+ variants.

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

Abstract

In this paper, we leverage the efficiency of Binarized Neural Networks (BNNs) to learn complex state transition models of planning domains with discretized factored state and action spaces. In order to directly exploit this transition structure for planning, we present two novel compilations of the learned factored planning problem with BNNs based on reductions to Boolean Satisfiability (FD-SAT-Plan) as well as Binary Linear Programming (FD-BLP-Plan). Experimentally, we show the effectiveness of learning complex transition models with BNNs, and test the runtime efficiency of both encodings on the learned factored planning problem. After this initial investigation, we present an incremental constraint generation algorithm based on generalized landmark constraints to improve the planning accuracy of our encodings. Finally, we show how to extend the best performing encoding (FD-BLP-Plan+) beyond goals to handle factored planning problems with rewards.
BibTeX
@inproceedings{say2018planning,
  author = {Buser Say and Scott Sanner},
  title = {{Planning in Factored State and Action Spaces with Learned Binarized Neural Network Transition Models}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2018},
  doi = {10.24963/ijcai.2018/669},
}
Figure