kth.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Exact Worst-Case Execution-Time Analysis for Implicit Model Predictive Control
Uppsala Univ, Div Syst & Control, S-75310 Uppsala, Sweden..
KTH, School of Electrical Engineering and Computer Science (EECS), Computer Science, Software and Computer systems, SCS.ORCID iD: 0000-0001-8457-4105
Linköping Univ, Div Automat Control, S-58183 Linköping, Sweden..
2024 (English)In: IEEE Transactions on Automatic Control, ISSN 0018-9286, E-ISSN 1558-2523, Vol. 69, no 10, p. 7190-7196Article in journal (Refereed) Published
Abstract [en]

We propose the first method that determines the exact worst-case execution time (WCET) for implicit linear model predictive control (MPC). Such WCET bounds are imperative when MPC is used in real time to control safety-critical systems. The proposed method applies when the quadratic programming solver in the MPC controller belongs to a family of well-established active-set solvers. For such solvers, we leverage a previously proposed complexity certification framework to generate a finite set of "archetypal" optimization problems; we prove that these archetypal problems form an execution-time equivalent cover of all possible problems; that is, that they capture the execution time for solving any possible optimization problem that can be encountered online. Hence, by solving just these archetypal problems on the hardware on which the MPC is to be deployed, and by recording the execution times, we obtain the exact WCET. In addition to providing formal proofs of the methods efficacy, we validate the method on an MPC example where an inverted pendulum on a cart is stabilized. The experiments highlight the following advantages compared with classical WCET methods: first, in contrast to classical static methods, our method gives the exact WCET; second, in contrast to classical measurement-based methods, our method guarantees a correct WCET estimate and requires fewer measurements on the hardware.

Place, publisher, year, edition, pages
Institute of Electrical and Electronics Engineers (IEEE) , 2024. Vol. 69, no 10, p. 7190-7196
Keywords [en]
Execution time analysis, optimization methods, predictive control for linear systems, real time systems
National Category
Control Engineering Computer Systems
Identifiers
URN: urn:nbn:se:kth:diva-354786DOI: 10.1109/TAC.2024.3395521ISI: 001322635200001Scopus ID: 2-s2.0-85192183692OAI: oai:DiVA.org:kth-354786DiVA, id: diva2:1905663
Note

QC 20241015

Available from: 2024-10-15 Created: 2024-10-15 Last updated: 2024-10-15Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus

Authority records

Broman, David

Search in DiVA

By author/editor
Broman, David
By organisation
Software and Computer systems, SCS
In the same journal
IEEE Transactions on Automatic Control
Control EngineeringComputer Systems

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 91 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf