Reward Potentials for Planning with Learned Neural Network Transition Models

Buser Say; Scott Sanner; Sylvie Thiébaux

doi:10.1007/978-3-030-30048-7_39

Reward Potentials for Planning with Learned Neural Network Transition Models

Buser Say^*, Scott Sanner, Sylvie Thiébaux

^*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

2 Citations (Scopus)

Abstract

Optimal planning with respect to learned neural network (NN) models in continuous action and state spaces using mixed-integer linear programming (MILP) is a challenging task for branch-and-bound solvers due to the poor linear relaxation of the underlying MILP model. For a given set of features, potential heuristics provide an efficient framework for computing bounds on cost (reward) functions. In this paper, we model the problem of finding optimal potential bounds for learned NN models as a bilevel program, and solve it using a novel finite-time constraint generation algorithm. We then strengthen the linear relaxation of the underlying MILP model by introducing constraints to bound the reward function based on the precomputed reward potentials. Experimentally, we show that our algorithm efficiently computes reward potentials for learned NN models, and that the overhead of computing reward potentials is justified by the overall strengthening of the underlying MILP model for the task of planning over long horizons.

Original language	English
Title of host publication	Principles and Practice of Constraint Programming - 25th International Conference, CP 2019, Proceedings
Editors	Thomas Schiex, Simon de Givry
Publisher	Springer
Pages	674-689
Number of pages	16
ISBN (Print)	9783030300470
DOIs	https://doi.org/10.1007/978-3-030-30048-7_39
Publication status	Published - 2019
Event	25th International Conference on Principles and Practice of Constraint Programming, CP 2019 - Stamford , United States Duration: 30 Sept 2019 → 4 Oct 2019

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	11802 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	25th International Conference on Principles and Practice of Constraint Programming, CP 2019
Country/Territory	United States
City	Stamford
Period	30/09/19 → 4/10/19

Access to Document

10.1007/978-3-030-30048-7_39

Cite this

Say, B., Sanner, S., & Thiébaux, S. (2019). Reward Potentials for Planning with Learned Neural Network Transition Models. In T. Schiex, & S. de Givry (Eds.), Principles and Practice of Constraint Programming - 25th International Conference, CP 2019, Proceedings (pp. 674-689). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11802 LNCS). Springer. https://doi.org/10.1007/978-3-030-30048-7_39

Say, Buser ; Sanner, Scott ; Thiébaux, Sylvie. / Reward Potentials for Planning with Learned Neural Network Transition Models. Principles and Practice of Constraint Programming - 25th International Conference, CP 2019, Proceedings. editor / Thomas Schiex ; Simon de Givry. Springer, 2019. pp. 674-689 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{d63d20bbb85443e38a6d2cb0b48a971d,

title = "Reward Potentials for Planning with Learned Neural Network Transition Models",

abstract = "Optimal planning with respect to learned neural network (NN) models in continuous action and state spaces using mixed-integer linear programming (MILP) is a challenging task for branch-and-bound solvers due to the poor linear relaxation of the underlying MILP model. For a given set of features, potential heuristics provide an efficient framework for computing bounds on cost (reward) functions. In this paper, we model the problem of finding optimal potential bounds for learned NN models as a bilevel program, and solve it using a novel finite-time constraint generation algorithm. We then strengthen the linear relaxation of the underlying MILP model by introducing constraints to bound the reward function based on the precomputed reward potentials. Experimentally, we show that our algorithm efficiently computes reward potentials for learned NN models, and that the overhead of computing reward potentials is justified by the overall strengthening of the underlying MILP model for the task of planning over long horizons.",

keywords = "Constraint generation, Neural networks, Planning, Potential heuristics",

author = "Buser Say and Scott Sanner and Sylvie Thi{\'e}baux",

note = "Publisher Copyright: {\textcopyright} 2019, Springer Nature Switzerland AG.; 25th International Conference on Principles and Practice of Constraint Programming, CP 2019 ; Conference date: 30-09-2019 Through 04-10-2019",

year = "2019",

doi = "10.1007/978-3-030-30048-7_39",

language = "English",

isbn = "9783030300470",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "674--689",

editor = "Thomas Schiex and {de Givry}, Simon",

booktitle = "Principles and Practice of Constraint Programming - 25th International Conference, CP 2019, Proceedings",

address = "Germany",

}

Say, B, Sanner, S & Thiébaux, S 2019, Reward Potentials for Planning with Learned Neural Network Transition Models. in T Schiex & S de Givry (eds), Principles and Practice of Constraint Programming - 25th International Conference, CP 2019, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 11802 LNCS, Springer, pp. 674-689, 25th International Conference on Principles and Practice of Constraint Programming, CP 2019, Stamford , United States, 30/09/19. https://doi.org/10.1007/978-3-030-30048-7_39

Reward Potentials for Planning with Learned Neural Network Transition Models. / Say, Buser; Sanner, Scott; Thiébaux, Sylvie.
Principles and Practice of Constraint Programming - 25th International Conference, CP 2019, Proceedings. ed. / Thomas Schiex; Simon de Givry. Springer, 2019. p. 674-689 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11802 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Reward Potentials for Planning with Learned Neural Network Transition Models

AU - Say, Buser

AU - Sanner, Scott

AU - Thiébaux, Sylvie

PY - 2019

Y1 - 2019

N2 - Optimal planning with respect to learned neural network (NN) models in continuous action and state spaces using mixed-integer linear programming (MILP) is a challenging task for branch-and-bound solvers due to the poor linear relaxation of the underlying MILP model. For a given set of features, potential heuristics provide an efficient framework for computing bounds on cost (reward) functions. In this paper, we model the problem of finding optimal potential bounds for learned NN models as a bilevel program, and solve it using a novel finite-time constraint generation algorithm. We then strengthen the linear relaxation of the underlying MILP model by introducing constraints to bound the reward function based on the precomputed reward potentials. Experimentally, we show that our algorithm efficiently computes reward potentials for learned NN models, and that the overhead of computing reward potentials is justified by the overall strengthening of the underlying MILP model for the task of planning over long horizons.

AB - Optimal planning with respect to learned neural network (NN) models in continuous action and state spaces using mixed-integer linear programming (MILP) is a challenging task for branch-and-bound solvers due to the poor linear relaxation of the underlying MILP model. For a given set of features, potential heuristics provide an efficient framework for computing bounds on cost (reward) functions. In this paper, we model the problem of finding optimal potential bounds for learned NN models as a bilevel program, and solve it using a novel finite-time constraint generation algorithm. We then strengthen the linear relaxation of the underlying MILP model by introducing constraints to bound the reward function based on the precomputed reward potentials. Experimentally, we show that our algorithm efficiently computes reward potentials for learned NN models, and that the overhead of computing reward potentials is justified by the overall strengthening of the underlying MILP model for the task of planning over long horizons.

KW - Constraint generation

KW - Neural networks

KW - Planning

KW - Potential heuristics

UR - http://www.scopus.com/inward/record.url?scp=85075746345&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-30048-7_39

DO - 10.1007/978-3-030-30048-7_39

M3 - Conference contribution

AN - SCOPUS:85075746345

SN - 9783030300470

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 674

EP - 689

BT - Principles and Practice of Constraint Programming - 25th International Conference, CP 2019, Proceedings

A2 - Schiex, Thomas

A2 - de Givry, Simon

PB - Springer

T2 - 25th International Conference on Principles and Practice of Constraint Programming, CP 2019

Y2 - 30 September 2019 through 4 October 2019

ER -

Say B, Sanner S, Thiébaux S. Reward Potentials for Planning with Learned Neural Network Transition Models. In Schiex T, de Givry S, editors, Principles and Practice of Constraint Programming - 25th International Conference, CP 2019, Proceedings. Springer. 2019. p. 674-689. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-30048-7_39

Reward Potentials for Planning with Learned Neural Network Transition Models

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this