Symmetry reduction for dynamic programming

John Maidens , Axel Barrau , Silvère Bonnabel (1) , Murat Arcak

1 CAOR - Centre de Robotique

We present a method of exploiting symmetries of discrete-time optimal control problems to reduce the dimensionality of dynamic programming iterations. The results are derived for systems with continuous state variables, and can be applied to systems with continuous or discrete symmetry groups. We prove that symmetries of the state update equation and stage costs induce corresponding symmetries of the optimal cost function and the optimal policies. We then provide a general framework for computing the optimal cost function based on gridding a space of lower dimension than the original state space. This method does not rely on explicitly transforming the state update equations and can therefore be applied in circumstances where this is difficult. We illustrate these results on two six-dimensional optimal control problems that are computationally difficult to solve by dynamic programming without symmetry reduction.

Mots clés: Dynamic programming; Invariant systems; Model reduction; Optimal control; Path planning; Medical applications

Domaines: Sciences de l'ingénieur [physics]; Automatique / Robotique

John Maidens, Axel Barrau, Silvère Bonnabel, Murat Arcak. Symmetry reduction for dynamic programming. Automatica, 2018, ⟨10.1016/j.automatica.2018.08.024⟩. ⟨hal-01982793⟩