Bounded approximate symbolic dynamic programming for hybrid MDPs

Luis Gustavo Rocha Vianna, Scott Sanner, Leliane Nunes De Barros

    Research output: Contribution to conferencePaperpeer-review

    4 Citations (Scopus)

    Abstract

    Recent advances in symbolic dynamic programming (SDP) combined with the extended algebraic decision diagram (XADD) data structure have provided exact solutions for mixed discrete and continuous (hybrid) MDPs with piecewise linear dynamics and continuous actions. Since XADD-based exact solutions may grow intractably large for many problems, we propose a bounded error compression technique for XADDs that involves the solution of a constrained bilinear saddle point problem. Fortuitously, we show that given the special structure of this problem, it can be expressed as a bilevel linear programming problem and solved to optimality in finite time via constraint generation, despite having an infinite set of constraints. This solution permits the use of efficient linear program solvers for XADD compression and enables a novel class of bounded approximate SDP algorithms for hybrid MDPs that empirically offers order-of-magnitude speedups over the exact solution in exchange for a small approximation error.

    Original languageEnglish
    Pages674-683
    Number of pages10
    Publication statusPublished - 2013
    Event29th Conference on Uncertainty in Artificial Intelligence, UAI 2013 - Bellevue, WA, United States
    Duration: 11 Jul 201315 Jul 2013

    Conference

    Conference29th Conference on Uncertainty in Artificial Intelligence, UAI 2013
    Country/TerritoryUnited States
    CityBellevue, WA
    Period11/07/1315/07/13

    Fingerprint

    Dive into the research topics of 'Bounded approximate symbolic dynamic programming for hybrid MDPs'. Together they form a unique fingerprint.

    Cite this