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

Forskningsoutput: Kapitel i bok/rapport/Conference proceedingKonferenspaper i proceeding

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 symmetries can sometimes reduce the running time of the pseudo-Boolean solver by up to three orders of magnitude.

Detaljer

Författare
Enheter & grupper
Externa organisationer
  • Monash University
  • University of Copenhagen
Forskningsområden

Ämnesklassifikation (UKÄ) – OBLIGATORISK

  • Beräkningsmatematik

Nyckelord

Originalspråkengelska
Titel på värdpublikationPrinciples and Practice of Constraint Programming - 26th International Conference, CP 2020, Proceedings
RedaktörerHelmut Simonis
FörlagSpringer
Sidor917-934
Antal sidor18
ISBN (tryckt)9783030584740
StatusPublished - 2020
PublikationskategoriForskning
Peer review utfördJa
Evenemang26th International Conference on Principles and Practice of Constraint Programming, CP 2020 - Louvain-la-Neuve, Belgien
Varaktighet: 2020 sep 72020 sep 11

Publikationsserier

NamnLecture Notes in Computer Science
FörlagSpringer
Volym12333
ISSN (tryckt)0302-9743
ISSN (elektroniskt)1611-3349

Konferens

Konferens26th International Conference on Principles and Practice of Constraint Programming, CP 2020
LandBelgien
OrtLouvain-la-Neuve
Period2020/09/072020/09/11