Estudio computacional de algoritmos de optimización de primer orden para la aceleración del control predictivo basado en modelo (MPC) en FPGAs

Abstract

Abstract: Many of the most recent publications in the embedded MPC field choose to use first-order algorithms as a solution to the complexity of accelerating second-order algorithms in systems with restricted computing resources. Thus, the purpose of this project consist on evaluating the response of these first order algorithms and compare their performance with second-order algorithms to have consistent criteria to design specific accelerators optimized in the development of SoCs with application to the high performance embedded MPC. To aim this objective, the first part of the text focuses on explaining a background needed to understand the approach of the optimization algorithms in the solution of a reformulated MPC problem arising from a state-space model. In this chapter, definitions such as Shift and Delta discretisation, System Variable and Dynamics Stacking, and Sparse and Dense formulation are explained. Once the related background is presented, it is analysed in detail the application to the MPC of the most current and efficient first order algorithms, making a study of the proposals published in recent years. In this section, definitions such as optimality, stopping conditions and convergence will be taken into account. After this analysis, the application of these algorithms will be adapted to different MPC formulation options where it will be evaluated their computational performance in different scenarios. Lastly, the results obtained of the previous evaluation will be compared with the performance of the second order algorithms, particularly using a simplified Interior Point which it is optimised for an embedded MPC implementation. This comparison will allow to take appropriate design decisions in the implementation of MPC in embedded systems considering aspects such as hardware simplicity, computational performance and numerical characteristics.

Laburpena: MPC txertatuaren arloko argitalpen berrienetako askok lehen mailako algoritmoak erabiltzen dituzte baliabide informatiko mugatuak dituzten sistemetan bigarren mailako algoritmoen azelerazioaren konplexutasunari aurre egiteko. Beraz, proiektu honen helburua lehen mailako algoritmo horien erantzuna ebaluatzea eta haien errendimendua bigarren mailako algoritmoekin alderatzen da. Horrela, eraginkortasun handiko MPC kontrolagailu txertatuak gauzatzeko SoC arkitektura berriak diseinatzeko beharrezkoak diren azeleragailuak diseinatzeko irizpideak lortu nahi dira. Helburu hori lortzeko, lan honen lehen atalean, egoera-espazioko eredutik sortzen den birformulatutako MPC problemen ebazpenerako beharrezko diren optimizazioalgoritmoen planteamendua ulertzeko beharrezkoak diren aurrekariak azaltzen dira. Kapitulu honetan, zenbait definizio azaltzen dira, hala nola Shift eta Delta diskretizazioa, aldagaien eta sistemen dinamikaren pilaketa, eta formulazio trinko eta sakabanatuak. Aurrekariak aurkeztu ondoren, lehen mailako algoritmo berri eta eraginkorrenak MPC-aren arloan nola aplikatu diren aztertzen da, horretarako azken urteetako argitalpen zientifikoetan agertutako proposamenak aztertuz. Atal honetan optimizazioa, bukaera-baldintzak eta konbergentzia bezalako kontzeptuak kontuan hartuko dira. Ondoren, algoritmo horien aplikazioa MPCren formulazio-aukera desberdinetara egokituko da, haien errendimendu konputazionala hainbat egoera esanguratsuetan ebaluatuz. Azkenik, aurreko ebaluaziotik lortutako emaitzak bigarren mailako algoritmoen errendimenduarekin konparatuko dira, bereziki sistema txertatuetan erabiltzeko optimizatua izan den IP (Interior Point) algoritmo sinplifikatu bat erabilita, MPC txertatua ezartzeko optimizatuta dagoena. Konparazio horri esker, diseinu-erabaki egokiak hartu ahal izango dira sistema txertatuetan MPCa ezartzeko, ondorengo alderdi hauek kontuan hartuta: hardwarearen sinpletasuna, errendimendu konputazionala eta zenbakizko ezaugarriak.

Resumen: Muchas de las publicaciones más recientes en el campo del MPC embebido optan por utilizar algoritmos de primer orden como solución a la complejidad de la aceleración de los algoritmos de segundo orden en sistemas con recursos informáticos restringidos. Por lo tanto, el propósito de este proyecto consiste en evaluar la respuesta de estos algoritmos de primer orden y comparar su rendimiento con los algoritmos de segundo orden con la finalidad de tener criterios consistentes para diseñar aceleradores específicos optimizados en el desarrollo de SoCs con aplicación al MPC embebido de alto rendimiento. Para lograr este objetivo, la primera parte del texto se centra en explicar los antecedentes necesarios para entender el enfoque de los algoritmos de optimización en la solución de un problema de MPC reformulado que surge de un modelo en espacio de estados. En este capítulo, se explican definiciones como la discretización Shift y Delta, el apilamiento de las variables y de la dinámica del sistema, y las formulaciones densa y dispersa. Una vez presentados los antecedentes, se analiza en detalle la aplicación al MPC de los algoritmos de primer orden más actuales y eficientes, haciendo un estudio de las propuestas publicadas en los últimos años. En este apartado se tendrán en cuenta definiciones como la optimización, las condiciones de parada y la convergencia. Tras este análisis, la aplicación de estos algoritmos se adaptará a las diferentes opciones de formulación de MPC donde se evaluará su rendimiento computacional en diferentes escenarios. Por último, los resultados obtenidos de la evaluación anterior se compararán con el rendimiento de los algoritmos de segundo orden, en particular utilizando un IP simplificado que está optimizado para una implementación MPC embebida. Esta comparación permitirá tomar decisiones de diseño adecuadas en la implementación de MPC en sistemas embebidos considerando aspectos como la simplicidad del hardware, el rendimiento computacional y las características numéricas.