Compact and Efficient Encodings for Planning in Factored State and Action Spaces with Learned Binarized Neural Network Transition Models

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 planningproblem with BNNs based on reductions to Weighted Partial Maximum Boolean Satisfiability (FD-SAT-Plan) as well as Binary Linear Programming (FD-BLP-Plan).Theoretically, we show that our SATbased Bi-Directional Neuron Activation Encoding is asymptotically the most compact encoding in the literature and maintains the generalized arc-consistency property throughunit propagation - an important property that facilitates efficiency in SAT solvers. Experimentally, we validate the computational efficiency of our Bi-Directional Neuron Activation Encoding in comparison to an existing neuron activationencoding and demonstrate the effectiveness of learning complex transition models with BNNs. We test the runtime efficiency of both FD-SAT- Plan and FD-BLP-Plan on the learned factored planning problem showing that FD-SAT-Plan scales better with increasing BNN size and complexity. Parts of this work appeared in preliminary form in Say and Sanner, 2018 [1]. Preprint submitted to AIJ December 11, 2018 our encodings through simulated or real-world interaction. Keywords: data-driven planning, binarized neural networks, Weighted Partial Maximum Boolean Satisfiability, Binary Linear Programming 1. Introduction Deep neural networks (DNNs) have significantly improved the ability of autonomous systemsto perform complex tasks, such as image recognition [2], speech recognition [3] and natural language processing [4], and can outperform humans and human-designed superhuman systems in complex planning tasks such as Go [5] and Chess [6]. In the area of learning and planning, recent work on HD-MILP-Plan [7] has explored a two-stage framework that (i) learns transitions models from data with ReLUbased DNNs and (ii) plans optimally with respect to the learned transition models using Mixed-Integer Linear Programming, but did not provide encodingsthat are able to learn and plan with discrete state variables.