Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

Theoretical and Experimental Results for Planning with Learned Binarized Neural Network Transition Models

Say, Buser ; Devriendt, Jo LU ; Nordström, Jakob LU and Stuckey, Peter J. (2020) 26th International Conference on Principles and Practice of Constraint Programming, CP 2020 In Lecture Notes in Computer Science 12333. p.917-934
Abstract

We study planning problems where the transition function is described by a learned binarized neural network (BNN). Theoretically, we show that feasible planning with a learned BNN model is NP-complete, and present two new constraint programming models of this task as a mathematical optimization problem. Experimentally, we run solvers for constraint programming, weighted partial maximum satisfiability, 0–1 integer programming, and pseudo-Boolean optimization, and observe that the pseudo-Boolean solver outperforms previous approaches by one to two orders of magnitude. We also investigate symmetry handling for planning problems with learned BNNs over long horizons. While the results here are less clear-cut, we see that exploiting... (More)

We study planning problems where the transition function is described by a learned binarized neural network (BNN). Theoretically, we show that feasible planning with a learned BNN model is NP-complete, and present two new constraint programming models of this task as a mathematical optimization problem. Experimentally, we run solvers for constraint programming, weighted partial maximum satisfiability, 0–1 integer programming, and pseudo-Boolean optimization, and observe that the pseudo-Boolean solver outperforms previous approaches by one to two orders of magnitude. We also investigate symmetry handling for planning problems with learned BNNs over long horizons. While the results here are less clear-cut, we see that exploiting symmetries can sometimes reduce the running time of the pseudo-Boolean solver by up to three orders of magnitude.

(Less)
Please use this url to cite or link to this publication:
author
; ; and
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
keywords
Automated planning, Binarized neural networks, Cutting planes reasoning, Mathematical optimization, Pseudo-Boolean optimization, Symmetry
host publication
Principles and Practice of Constraint Programming - 26th International Conference, CP 2020, Proceedings
series title
Lecture Notes in Computer Science
editor
Simonis, Helmut
volume
12333
pages
18 pages
publisher
Springer
conference name
26th International Conference on Principles and Practice of Constraint Programming, CP 2020
conference location
Louvain-la-Neuve, Belgium
conference dates
2020-09-07 - 2020-09-11
external identifiers
  • scopus:85091310124
ISSN
0302-9743
1611-3349
ISBN
9783030584740
DOI
10.1007/978-3-030-58475-7_53
language
English
LU publication?
yes
id
dfe6a76b-540c-4526-b038-f42c7e91cd08
date added to LUP
2020-10-28 14:28:53
date last changed
2024-06-12 22:29:57
@inproceedings{dfe6a76b-540c-4526-b038-f42c7e91cd08,
  abstract     = {{<p>We study planning problems where the transition function is described by a learned binarized neural network (BNN). Theoretically, we show that feasible planning with a learned BNN model is NP-complete, and present two new constraint programming models of this task as a mathematical optimization problem. Experimentally, we run solvers for constraint programming, weighted partial maximum satisfiability, 0–1 integer programming, and pseudo-Boolean optimization, and observe that the pseudo-Boolean solver outperforms previous approaches by one to two orders of magnitude. We also investigate symmetry handling for planning problems with learned BNNs over long horizons. While the results here are less clear-cut, we see that exploiting symmetries can sometimes reduce the running time of the pseudo-Boolean solver by up to three orders of magnitude.</p>}},
  author       = {{Say, Buser and Devriendt, Jo and Nordström, Jakob and Stuckey, Peter J.}},
  booktitle    = {{Principles and Practice of Constraint Programming - 26th International Conference, CP 2020, Proceedings}},
  editor       = {{Simonis, Helmut}},
  isbn         = {{9783030584740}},
  issn         = {{0302-9743}},
  keywords     = {{Automated planning; Binarized neural networks; Cutting planes reasoning; Mathematical optimization; Pseudo-Boolean optimization; Symmetry}},
  language     = {{eng}},
  pages        = {{917--934}},
  publisher    = {{Springer}},
  series       = {{Lecture Notes in Computer Science}},
  title        = {{Theoretical and Experimental Results for Planning with Learned Binarized Neural Network Transition Models}},
  url          = {{http://dx.doi.org/10.1007/978-3-030-58475-7_53}},
  doi          = {{10.1007/978-3-030-58475-7_53}},
  volume       = {{12333}},
  year         = {{2020}},
}