Planning with Learned Binarized Neural Networks Benchmarks for MaxSAT Evaluation 2021

Buser Say, Scott Sanner, Jo Devriendt, Jakob Nordström, Peter J. StuckeyarXiv 2021 · arXiv

Abstract

Traditional automated planning often relies on hand-coded transition functions, which are difficult to define for complex environments. This paper presents a framework that learns these dynamics using Binarized Neural Networks (BNNs) and formulates the planning task as a Weighted Partial MaxSAT problem. This approach enables the discovery of provably optimal plans in environments where rules are learned from data.

Introduction: The Challenge of Unknown Dynamics

In automated planning, the state transition function—the "rules of the world"—is typically defined by human experts using formal languages. However, real-world scenarios often involve dynamics too complex to hand-code or that are entirely unknown. While Deep Neural Networks (DNNs) can learn these rules from observation, planning with standard DNNs is computationally expensive due to their continuous values and non-linear activations.

To bridge the gap between deep learning and formal symbolic reasoning, the authors utilize Binarized Neural Networks (BNNs). BNNs restrict weights and activations to discrete values (typically -1 and 1), making them highly compatible with combinatorial optimization tools like MaxSAT.

Methodology

The proposed framework follows a two-stage data-driven process:

  1. Learning Phase: A BNN is trained to approximate the state transition function ($\tilde{T}$), predicting the subsequent state based on the current state and action.
  2. Planning Phase: The planning problem—comprising the learned BNN, initial state, goals, and reward function—is translated into a Weighted Partial MaxSAT model.

Technical Implementation

  • Decision Variables: Boolean variables represent actions, state variables, and neuron activations across time steps.
  • Hard Clauses: These enforce the logic of the BNN (using Cardinality Networks for weighted sums) and the requirement to reach goal states.
  • Soft Clauses: These encode the reward function, where the MaxSAT solver maximizes the weight of satisfied clauses to find the optimal plan.

Datasets & Benchmarks

The authors submitted four distinct domains as benchmarks for the MaxSAT Evaluation 2021. These domains vary in complexity and BNN architecture size, as detailed in the table below.

BNN architectures for the evaluated planning domains.
  1. Navigation: An agent navigates an $N \times N$ maze to reach a goal.
  2. Inventory Control: Managing stock levels under cyclic demand, using bit-vector approximations for integer values.
  3. System Administrator: Maintaining a network of computers by rebooting machines to keep as many running as possible.
  4. Cellda: A complex environment inspired by The Legend of Zelda, requiring navigation, enemy avoidance, and item retrieval.

Key Insights

  • BNNs as Logic-Friendly Models: BNNs offer a "sweet spot" by providing non-linear expressive power while remaining directly mappable to SAT clauses, unlike standard DNNs that often require more complex Mixed-Integer Programming (MIP).
  • Provable Optimality: By casting planning as MaxSAT, the framework guarantees that the resulting plan is mathematically optimal relative to the learned BNN model.
  • Discrete Approximation of Continuous Values: The use of bit-vectors in domains like Inventory Control demonstrates how discrete optimization can handle continuous-like quantities.

Results and Evaluation

The paper primarily serves as a benchmark specification for the 2021 MaxSAT competition. Finding a feasible plan within this framework is NP-complete. The benchmarks include planning horizons ($H$) from 2 to 12 steps, presenting a significant challenge for modern solvers to find optimal solutions within competitive timeframes.

Limitations and Future Work

The effectiveness of the plan is strictly tied to the accuracy of the learned BNN; inaccuracies in the model can lead to plan failure in the real environment. Additionally, scalability remains a concern, as the number of clauses grows with the planning horizon and network size. While approximations exist for integers, high-precision continuous control remains a target for future research.

Summary updated

Abstract

This document provides a brief introduction to learned automated planning problem where the state transition function is in the form of a binarized neural network (BNN), presents a general MaxSAT encoding for this problem, and describes the four domains, namely: Navigation, Inventory Control, System Administrator and Cellda, that are submitted as benchmarks for MaxSAT Evaluation 2021.
BibTeX
@misc{say2021planning,
  author = {Buser Say and Scott Sanner and Jo Devriendt and Jakob Nordström and Peter J. Stuckey},
  title = {{Planning with Learned Binarized Neural Networks Benchmarks for MaxSAT Evaluation 2021}},
  year = {2021},
  eprint = {2108.00633},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2108.00633},
}
Figure