Abstract
In model predictive control, the control action is found at each sampling time by solving an online optimization problem. Computationally, this step is very demanding, especially if compared to the evaluation of traditional control laws. This has limited the application of model predictive control to systems with slow dynamics for many years. Recently, several methods have been proposed in the literature which promise a substantial reduction of the computation time by either running the computation in parallel (distributed model predictive control) or exploiting the problem structure (fast model predictive control). A combination of these methods has not yet been considered in the literature. To achieve this goal, different optimization techniques need to be employed at once. The order of how these methods are applied matters. This paper considers fast distributed model predictive control combining the alternating direction method of multipliers (ADMM), the interior point method (IPM) and the Riccati iteration for a particular class of multi-agent systems for which the order of the methods can be arbitrarily changed. This leads to two different solver schemes where a trade-off arises between computation time and number of communications required to reach consensus. A simplified problem involving the formation control of a fleet of vehicles is considered at the end.
Zusammenfassung
Bei der modellprädiktiven Regelung wird die Stellgröße in jedem Abtastschritt durch Lösen eines Optimierungsproblems ermittelt. Das Lösen des Optimierungsproblems ist überaus rechenintensiv und damit äußerst zeitaufwändig, insbesondere im Vergleich zu klassischen Regelungsmethoden. Die modellprädiktive Regelung war dadurch über lange Jahre auf Systeme mit langsamer Dynamik beschränkt. In letzter Zeit wurden in der Literatur verschiedene Methoden vorgeschlagen, die eine maßgebliche Verringerung der Rechenzeit versprechen, entweder durch eine Ausführung der Berechnungen in parallelisierter Form (verteilte modellprädiktive Regelung) oder durch eine Ausnutzung der Struktur des Optimierungsproblems (schnelle modellprädiktive Regelung). Eine Kombination dieser Methoden wurde bislang noch nicht betrachtet. Für eine solche Kombination müssen verschiedene Optimierungsmethoden miteinander verknüpft werden. Hierbei ist insbesondere die Reihenfolge, in welcher die Optimierungsmethoden angewendet werden, von Bedeutung. Dieser Beitrag stellt ein Verfahren für die schnelle verteilte modellprädiktive Regelung basierend auf einer Kombination der Methode der alternierenden Richtung der Multiplikatoren, des Innere-Punkte-Verfahrens und der Riccati-Iteration für eine spezifische Klasse von Multiagentensystemen vor, bei denen die Reihenfolge der Methoden beliebig verändert werden kann. Dies führt zu zwei verschiedenen Lösungsschemata, mit denen ein Kompromiss zwischen Rechen- und Kommunikationsaufwand ermöglicht wird. Das Verfahren wird für die Formationsregelung einer Fahrzeugflotte am Ende des Beitrags veranschaulicht.
About the authors
M.Sc. Giuliano Costantini is researcher in the Division of Electromobility at the University of Kaiserslautern. His research interests include numerical optimization methods, networked systems, distributed control, model predictive control, and their application to vehicular systems.
apl. Prof. Dr.-Ing. Daniel Görges is research group leader at the German Research Center for Artificial Intelligence (DFKI). His research interests include methods for model predictive control, distributed control and learning control and their applications in vehicular systems, transportation systems, mechatronic systems, and power systems.
References
1. R. R. Negenborn and J. M. Maestre, “Distributed model predictive control: An overview and roadmap of future research opportunities,” IEEE Control Systems Magazine, vol. 34, no. 4, pp. 87–97, 2014.10.1109/MCS.2014.2320397Search in Google Scholar
2. R. Halvgaard, L. Vandenberghe, N. K. Poulsen, H. Madsen and J. B. Jørgensen, “Distributed model predictive control for smart energy systems,” IEEE Transactions on Smart Grid, vol. 7, no. 3, pp. 1675–1682, 2016.10.1109/TSG.2016.2526077Search in Google Scholar
3. S. Leirens, C. Zamora, R. Negenborn and B. De Schutter, “Coordination in urban water supply networks using distributed model predictive control,” in Proceedings of the 2010 American Control Conference, pp. 3957–3962, IEEE, 2010.10.1109/ACC.2010.5530635Search in Google Scholar
4. W. B. Dunbar and S. Desa, “Distributed nonlinear model predictive control for dynamic supply chain management,” in Proceedings of the Int. Workshop on Assessment and Future Directions of Nonlinear MPC, 2005.Search in Google Scholar
5. R. Olfati-Saber and R. M. Murray, “Distributed cooperative control of multiple vehicle formations using structural potential functions,” in Proceedings of the IFAC World Congress, pp. 242–248, 2002.10.3182/20020721-6-ES-1901.00244Search in Google Scholar
6. R. Scattolini, “Architectures for distributed and hierarchical model predictive control–a review,” Journal of Process Control, vol. 19, no. 5, pp. 723–731, 2009.10.1016/j.jprocont.2009.02.003Search in Google Scholar
7. Y. Wang and S. Boyd, “Fast model predictive control using online optimization,” IEEE Transactions on Control Systems Technology, vol. 18, no. 2, pp. 267–278, 2009.10.1109/TCST.2009.2017934Search in Google Scholar
8. C. V. Rao, S. J. Wright and J. B. Rawlings, “Application of interior-point methods to model predictive control,” Journal of Optimization Theory and Applications, vol. 99, no. 3, pp. 723–757, 1998.10.1023/A:1021711402723Search in Google Scholar
9. A. Domahidi, A. U. Zgraggen, M. N. Zeilinger, M. Morari and C. N. Jones, “Efficient interior point methods for multistage problems arising in receding horizon control,” in Proceedings of the 2012 IEEE 51st IEEE Conference on Decision and Control (CDC), pp. 668–674, IEEE, 2012.10.1109/CDC.2012.6426855Search in Google Scholar
10. G. Frison and J. B. Jørgensen, “Efficient implementation of the Riccati recursion for solving linear-quadratic control problems,” in Proceedings of the 2013 IEEE International Conference on Control Applications (CCA), pp. 1117–1122, 2013.10.1109/CCA.2013.6662901Search in Google Scholar
11. E. Camponogara, D. Jia, B. H. Krogh and S. Talukdar, “Distributed model predictive control,” IEEE Control Systems Magazine, vol. 22, no. 1, pp. 44–52, 2002.10.1109/37.980246Search in Google Scholar
12. C. Conte, T. Summers, M. N. Zeilinger, M. Morari and C. N. Jones, “Computational aspects of distributed optimization in model predictive control,” in Proceedings of the 2012 IEEE 51st IEEE Conference on Decision and Control (CDC), pp. 6819–6824, IEEE, 2012.10.1109/CDC.2012.6426138Search in Google Scholar
13. G. Costantini, R. Rostami and D. Görges, “Decomposition methods for distributed quadratic programming with application to distributed model predictive control,” in Proceedings of the 2018 56th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pp. 943–950, 2018.10.1109/ALLERTON.2018.8636067Search in Google Scholar
14. G. Costantini, R. Rostami and D. Görges, “Fast separable terminal cost synthesis for distributed MPC,” in Proceedings of 18th European Control Conference (ECC), pp. 313–318, IEEE, 2019.10.23919/ECC.2019.8795859Search in Google Scholar
15. T. H. Summers and J. Lygeros, “Distributed model predictive consensus via the alternating direction method of multipliers,” in Proceedings of the 2012 50th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pp. 79–84, 2012.10.1109/Allerton.2012.6483202Search in Google Scholar
16. S. Boyd, N. Parikh, E. Chu, B. Peleato and J. Eckstein, “Distributed optimization and statistical learning via the alternating direction method of multipliers,” Foundations and Trends® in Machine learning, vol. 3, no. 1, pp. 1–122, 2011.10.1561/9781601984616Search in Google Scholar
17. E. Ghadimi, A. Teixeira, I. Shames and M. Johansson, “Optimal parameter selection for the alternating direction method of multipliers (ADMM): quadratic problems,” IEEE Transactions on Automatic Control, vol. 60, no. 3, pp. 644–658, 2014.10.1109/TAC.2014.2354892Search in Google Scholar
18. J. Nocedal and S. Wright, Numerical Optimization. Springer Science & Business Media, second ed., 2006.Search in Google Scholar
19. S. Boyd, S. P. Boyd and L. Vandenberghe, Convex Optimization. Cambridge University Press, 2004.10.1017/CBO9780511804441Search in Google Scholar
20. E. Poupard and W. P. Heath, “Hamiltonian decomposition for model predictive control,” IFAC-PapersOnLine, vol. 51, no. 3, pp. 193–198, 2018.10.1016/j.ifacol.2018.06.052Search in Google Scholar
21. G. Costantini, R. Rostami and D. Görges, “Online trajectory planning and collision avoidance for a group of robots using distributed model predictive control,” in Advances in Service and Industrial Robotics. RAAD 2019. Advances in Intelligent Systems and Computing (K. Berns and D. Görges, eds.), vol. 980, (Cham), pp. 240–249, Springer International Publishing, 2020.10.1007/978-3-030-19648-6_28Search in Google Scholar
© 2021 Walter de Gruyter GmbH, Berlin/Boston