Temporal Parallelization of Dynamic Programming and Linear Quadratic Control

Simo Särkkä; Angel F. Garcia-Fernandez

doi:10.1109/TAC.2022.3147017

Temporal Parallelization of Dynamic Programming and Linear Quadratic Control

Simo Särkkä
, Angel F. Garcia-Fernandez

University of Liverpool
Universidad Antonio de Nebrija

Research output: Contribution to journal › Article › Scientific › peer-review

8 Citations (Scopus)

195 Downloads (Pure)

Abstract

This article proposes a general formulation for temporal parallelization of dynamic programming for optimal control problems. We derive the elements and associative operators to be able to use parallel scans to solve these problems with logarithmic time complexity rather than linear time complexity. We apply this methodology to problems with finite state and control spaces, linear quadratic tracking control problems, and to a class of nonlinear control problems. The computational benefits of the parallel methods are demonstrated via numerical simulations run on a graphics processing unit.

Original language	English
Pages (from-to)	851-866
Number of pages	16
Journal	IEEE Transactions on Automatic Control
Volume	68
Issue number	2
Early online date	Jan 2022
DOIs	https://doi.org/10.1109/TAC.2022.3147017
Publication status	Published - 1 Feb 2023
MoE publication type	A1 Journal article-refereed

Keywords

Approximation algorithms
Associative operator
Cost function
dynamic programming
Dynamic programming
graphics processing unit
Heuristic algorithms
multi-core processing
Optimal control
optimal control
parallel computing
Time complexity
Trajectory

Access to Document

10.1109/TAC.2022.3147017Licence: CC BY

Temporal_Parallelization_of_Dynamic_Programming_and_Linear_Quadratic_ControlFinal published version, 921 KBLicence: CC BY

Cite this

@article{07df2752e668460d90570984efd8023e,

title = "Temporal Parallelization of Dynamic Programming and Linear Quadratic Control",

abstract = "This article proposes a general formulation for temporal parallelization of dynamic programming for optimal control problems. We derive the elements and associative operators to be able to use parallel scans to solve these problems with logarithmic time complexity rather than linear time complexity. We apply this methodology to problems with finite state and control spaces, linear quadratic tracking control problems, and to a class of nonlinear control problems. The computational benefits of the parallel methods are demonstrated via numerical simulations run on a graphics processing unit.",

keywords = "Approximation algorithms, Associative operator, Cost function, dynamic programming, Dynamic programming, graphics processing unit, Heuristic algorithms, multi-core processing, Optimal control, optimal control, parallel computing, Time complexity, Trajectory",

author = "Simo S{\"a}rkk{\"a} and Garcia-Fernandez, \{Angel F.\}",

note = "Tallenna OA-artikkeli kun julkaistu",

year = "2023",

month = feb,

day = "1",

doi = "10.1109/TAC.2022.3147017",

language = "English",

volume = "68",

pages = "851--866",

journal = "IEEE Transactions on Automatic Control",

issn = "0018-9286",

publisher = "IEEE",

number = "2",

}

TY - JOUR

T1 - Temporal Parallelization of Dynamic Programming and Linear Quadratic Control

AU - Särkkä, Simo

AU - Garcia-Fernandez, Angel F.

N1 - Tallenna OA-artikkeli kun julkaistu

PY - 2023/2/1

Y1 - 2023/2/1

N2 - This article proposes a general formulation for temporal parallelization of dynamic programming for optimal control problems. We derive the elements and associative operators to be able to use parallel scans to solve these problems with logarithmic time complexity rather than linear time complexity. We apply this methodology to problems with finite state and control spaces, linear quadratic tracking control problems, and to a class of nonlinear control problems. The computational benefits of the parallel methods are demonstrated via numerical simulations run on a graphics processing unit.

AB - This article proposes a general formulation for temporal parallelization of dynamic programming for optimal control problems. We derive the elements and associative operators to be able to use parallel scans to solve these problems with logarithmic time complexity rather than linear time complexity. We apply this methodology to problems with finite state and control spaces, linear quadratic tracking control problems, and to a class of nonlinear control problems. The computational benefits of the parallel methods are demonstrated via numerical simulations run on a graphics processing unit.

KW - Approximation algorithms

KW - Associative operator

KW - Cost function

KW - dynamic programming

KW - Dynamic programming

KW - graphics processing unit

KW - Heuristic algorithms

KW - multi-core processing

KW - Optimal control

KW - optimal control

KW - parallel computing

KW - Time complexity

KW - Trajectory

UR - https://www.scopus.com/pages/publications/85124219841

U2 - 10.1109/TAC.2022.3147017

DO - 10.1109/TAC.2022.3147017

M3 - Article

AN - SCOPUS:85124219841

SN - 0018-9286

VL - 68

SP - 851

EP - 866

JO - IEEE Transactions on Automatic Control

JF - IEEE Transactions on Automatic Control

IS - 2

ER -

Temporal Parallelization of Dynamic Programming and Linear Quadratic Control

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Science-IT

Findings from Aalto University Update Knowledge of Technology (Temporal Parallelization of Dynamic Programming and Linear Quadratic Control)

Cite this

Temporal Parallelization of Dynamic Programming and Linear Quadratic Control

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Equipment

Science-IT

Press/Media

Findings from Aalto University Update Knowledge of Technology (Temporal Parallelization of Dynamic Programming and Linear Quadratic Control)

Cite this