Note: This content is accessible to all versions of every browser. However, this browser does not seem to support current Web standards, preventing the display of our site's design details.


Approximate Dynamic Programming via Sum of Squares Programming


T.H. Summers, Konstantin Kunz, N. Kariotoglou, M. Kamgarpour, S. Summers, J. Lygeros

European Control Conference (ECC), Zurich, Switzerland, pp. 191-197, July 17-19, 2013

We describe an approximate dynamic programming method for stochastic control problems on infinite state and input spaces. The optimal value function is approximated by a linear combination of basis functions with coefficients as decision variables. By relaxing the Bellman equation to an inequality, one obtains a linear program in the basis coefficients with an infinite set of constraints. We show that a recently introduced method, which obtains convex quadratic value function approximations, can be extended to higher order polynomial approximations via sum of squares programming techniques. An approximate value function can then be computed offline by solving a semidefinite program, without having to sample the infinite constraint. The policy is evaluated online by solving a polynomial optimization problem, which also turns out to be convex in some cases. We experimentally validate the method on an autonomous helicopter testbed using a 10-dimensional helicopter model.


Type of Publication:


J. Lygeros

File Download:

Request a copy of this publication.
(Uses JavaScript)
% Autogenerated BibTeX entry
@InProceedings { SumEtal:2013:IFA_4256,
    author={T.H. Summers and Konstantin Kunz and N. Kariotoglou and M.
	  Kamgarpour and S. Summers and J. Lygeros},
    title={{Approximate Dynamic Programming via Sum of Squares
    booktitle={European Control Conference (ECC)},
    address={Zurich, Switzerland},
Permanent link