Bounded Approximate Symbolic Dynamic Programming for Hybrid MDPs
  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.
