Fast Dynamic Programming
A Numerical Method for Solving Dynamic Programming Problems
G.F. Max (TU Delft - Electrical Engineering, Mathematics and Computer Science)
T Keviczky – Mentor (TU Delft - Team Tamas Keviczky)
Peyman Mohajerin Mohajerin Esfahani – Mentor (TU Delft - Team Tamas Keviczky)
Mohamad Amin Sharifi Sharifi Kolarijani – Graduation committee member (TU Delft - Team Tamas Keviczky)
Alle Jan van der Veen – Graduation committee member (TU Delft - Signal Processing Systems)
More Info
expand_more
Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.
Abstract
A well-established method for finding the optimal control policy for a given dynamical system is to solve the problem iteratively going from its terminal state "backwards" in time, known as Dynamic Programming Algorithm. For a generic problem with discrete state/action space, the algorithm has computational complexity of O(NM) for N states and M actions. In this thesis, we propose a novel numerical algorithm that approaches this problem in the conjugate domain, using the so-called Legendre-Fenchel Transform. In essence, the proposed approach is analogous to, and was inspired by Fast Fourier Transform, and how it can be beneficial to do computations/analysis in the frequency domain. In particular, this approach allows us to exploit the structure of the problem (e.g., in LQ control) to drastically reduce the computational complexity to O(N+M). Of course, this computational gain comes with a cost of introducing error.