Complexity Reduction of Explicit Model Predictive Control via Combining Separator Function and Binary Search Trees

Jamal Arezoo; Karim Salahshoor

doi:doi:10.11648/j.ajcst.20180101.13

| Peer-Reviewed

Complexity Reduction of Explicit Model Predictive Control via Combining Separator Function and Binary Search Trees

Jamal Arezoo, Karim Salahshoor

Published in American Journal of Computer Science and Technology (Volume 1, Issue 1)

Received: 21 November 2017 Accepted: 29 November 2017 Published: 24 December 2017

Views: Downloads:

Download PDF

Share This Article

Twitter
Linked In
Facebook

Abstract

The explicit Model Predictive Control (MPC) has emerged as a powerful technique to solve the optimization problem offline for embedded applications where computations is performed online. Despite practical obstacles in implementation of explicit model predictive control (MPC), the main drawbacks of MPC, namely the need to solve a mathematical program on line to compute the control action are removed. This paper addresses complexity of explicit model predictive control (MPC) in terms of online evaluation and memory requirement. Complexity reduction approaches for explicit MPC has recently been emerged as techniques to enhance applicability of MPC. Individual deployment of the approaches has not had enough effect on complexity reduction. In this paper, merging the approaches based on complexity reduction is addressed. The binary search tree and complexity reduction via separation are efficient methods which can be confined to small problems, but merging them can result in significant effect and expansion of its applicability. The simulation tests show proposed approach significantly outperforms previous methods.

Published in	American Journal of Computer Science and Technology (Volume 1, Issue 1)
DOI	10.11648/j.ajcst.20180101.13
Page(s)	19-23
Creative Commons	This is an Open Access article, distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution and reproduction in any medium or format, provided the original work is properly cited.
Copyright	Copyright © The Author(s), 2024. Published by Science Publishing Group

Keywords

Multi-Parametric Programming, Saturated Regions, Search Tree, Predictive Control

References

[1]	Oberdieck, R., Diangelakis, N. A. and Pistikopoulos, E. N. (2017). Explicit model predictive control: a connected-graph approach. Automatica, vol. 76, p. 103-12.
[2]	Cimini, G. and Bemporad, A. (2017). Exact Complexity Certification of Active-Set Methods for Quadratic Programming. IEEE Transactions on Automatic Control, Apr 24.
[3]	Kvasnica, M. (2016). Implicit vs. explicit MPC—Similarities, differences, and a path towards a unified method. In Control Conference (ECC) IEEE, 2016 European, p. 603-603.
[4]	Wen, C., Ma, X. and Ydstie, B. E., (2009). Analytical expression of explicit MPC solution via lattice piecewise-affine function. Automatica, vol. 45, no. 4, p. 910-917.
[5]	Di Cairano, S., Yanakiev, D., Bemporad, A., Kolmanovsky, I. V. and Hrovat, D. (2008). December. An MPC design flow for automotive control and applications to idle speed regulation. In Decision and Control, 2008. CDC 2008. 47th IEEE Conference on, p. 5686-5691.
[6]	Beccuti, A. G., Papafotiou, G., Frasca, R. and Morari, M. (2007). Explicit hybrid model predictive control of the dc-dcBoost converter. In Power Electronics Specialists Conference, 2007. PESC 2007. IEEE, p. 2503-2509.
[7]	Alessio, A. and Bemporad, A. (2009). A survey on explicit model predictive control. In Nonlinear model predictive control, Springer Berlin Heidelberg, p. 345-369.
[8]	Jones, C. N., Barić, M. and Morari, M. (2007). Multiparametric linear programming with applications to control. European Journal of Control, vol. 13, no. 2-3, p. 152-170.
[9]	Johansen, T. A. and Grancharova, A. (2003). Approximate explicit constrained linear model predictive control via orthogonal search tree. IEEE Transactions on Automatic Control, vol. 48, no. 5, p. 810-815.
[10]	Bemporad, A., Oliveri, A., Poggi, T. and Storace, M. (2011). Ultra-fast stabilizing model predictive control via canonical piecewise affine approximations. IEEE Transactions on Automatic Control, vol. 56, no. 12, p. 2883-2897.
[11]	Storace, M., Repetto, L. and Parodi, M. (2003). A method for the approximate synthesis of cellular non‐linear networks—Part 1: Circuit definition. International Journal of Circuit Theory and Applications, vol. 31, no. 3, p. 277-297.
[12]	Kvasnica, M. and Fikar, M. (2012). Clipping-based complexity reduction in explicit MPC. IEEE Transactions on Automatic Control, vol. 57, no. 7, p. 1878-1883.
[13]	Kvasnica, M., Hledík, J., Rauová, I. and Fikar, M. (2013). Complexity reduction of explicit model predictive control via separation. Automatica, vol. 49, no. 6, p. 1776-1781.
[14]	Tøndel, P., Johansen, T. A. and Bemporad, A. (2003). Evaluation of piecewise affine control via binary search tree. Automatica, vol. 39, no. 5, p. 945-950.
[15]	Gupta, A., Bhartiya, S. and Nataraj, P. S. V. (2011). A novel approach to multiparametric quadratic programming. Automatica, vol. 47, no. 9, p. 2112-2117.
[16]	Bemporad, A., Morari, M., Dua, V. and Pistikopoulos, E. N. (2002). The explicit linear quadratic regulator for constrained systems. Automatica, vol. 38, no. 1, p. 3-20.
[17]	Johansen, T. A., Jackson, W., Schreiber, R. and Tondel, P. (2007). Hardware synthesis of explicit model predictive controllers. IEEE Transactions on Control Systems Technology, vol. 15, no. 1, p. 191-197.
[18]	Mariéthoz, S., Mäder, U. and Morari, M. (2009). High-speed FPGA implementation of observers and explicit model predictive controllers. In IEEE IECON, Ind. Electronics Conf., Porto, Portugal, Nov 2009.
[19]	Bayat, F., Johansen, T. A. and Jalali, A. A. (2012). Flexible piecewise function evaluation methods based on truncated binary search trees and lattice representation in explicit MPC. IEEE Transactions on Control Systems Technology, vol. 20, no. 3, p. 632-640.
[20]	Herceg, M., Kvasnica, M., Jones, C. N. and Morari, M. (2013). Multi-parametric toolbox 3.0. In Control Conference (ECC), 2013 European, p. 502-510.

Cite This Article

Plain Text BibTeX RIS

APA Style

Jamal Arezoo, Karim Salahshoor. (2017). Complexity Reduction of Explicit Model Predictive Control via Combining Separator Function and Binary Search Trees. American Journal of Computer Science and Technology, 1(1), 19-23. https://doi.org/10.11648/j.ajcst.20180101.13

Copy | Download

ACS Style

Jamal Arezoo; Karim Salahshoor. Complexity Reduction of Explicit Model Predictive Control via Combining Separator Function and Binary Search Trees. Am. J. Comput. Sci. Technol. 2017, 1(1), 19-23. doi: 10.11648/j.ajcst.20180101.13

Copy | Download

AMA Style

Jamal Arezoo, Karim Salahshoor. Complexity Reduction of Explicit Model Predictive Control via Combining Separator Function and Binary Search Trees. Am J Comput Sci Technol. 2017;1(1):19-23. doi: 10.11648/j.ajcst.20180101.13

Copy | Download

@article{10.11648/j.ajcst.20180101.13,
  author = {Jamal Arezoo and Karim Salahshoor},
  title = {Complexity Reduction of Explicit Model Predictive Control via Combining Separator Function and Binary Search Trees},
  journal = {American Journal of Computer Science and Technology},
  volume = {1},
  number = {1},
  pages = {19-23},
  doi = {10.11648/j.ajcst.20180101.13},
  url = {https://doi.org/10.11648/j.ajcst.20180101.13},
  eprint = {https://article.sciencepublishinggroup.com/pdf/10.11648.j.ajcst.20180101.13},
  abstract = {The explicit Model Predictive Control (MPC) has emerged as a powerful technique to solve the optimization problem offline for embedded applications where computations is performed online. Despite practical obstacles in implementation of explicit model predictive control (MPC), the main drawbacks of MPC, namely the need to solve a mathematical program on line to compute the control action are removed. This paper addresses complexity of explicit model predictive control (MPC) in terms of online evaluation and memory requirement. Complexity reduction approaches for explicit MPC has recently been emerged as techniques to enhance applicability of MPC. Individual deployment of the approaches has not had enough effect on complexity reduction. In this paper, merging the approaches based on complexity reduction is addressed. The binary search tree and complexity reduction via separation are efficient methods which can be confined to small problems, but merging them can result in significant effect and expansion of its applicability. The simulation tests show proposed approach significantly outperforms previous methods.},
 year = {2017}
}

Copy | Download

TY  - JOUR
T1  - Complexity Reduction of Explicit Model Predictive Control via Combining Separator Function and Binary Search Trees
AU  - Jamal Arezoo
AU  - Karim Salahshoor
Y1  - 2017/12/24
PY  - 2017
N1  - https://doi.org/10.11648/j.ajcst.20180101.13
DO  - 10.11648/j.ajcst.20180101.13
T2  - American Journal of Computer Science and Technology
JF  - American Journal of Computer Science and Technology
JO  - American Journal of Computer Science and Technology
SP  - 19
EP  - 23
PB  - Science Publishing Group
SN  - 2640-012X
UR  - https://doi.org/10.11648/j.ajcst.20180101.13
AB  - The explicit Model Predictive Control (MPC) has emerged as a powerful technique to solve the optimization problem offline for embedded applications where computations is performed online. Despite practical obstacles in implementation of explicit model predictive control (MPC), the main drawbacks of MPC, namely the need to solve a mathematical program on line to compute the control action are removed. This paper addresses complexity of explicit model predictive control (MPC) in terms of online evaluation and memory requirement. Complexity reduction approaches for explicit MPC has recently been emerged as techniques to enhance applicability of MPC. Individual deployment of the approaches has not had enough effect on complexity reduction. In this paper, merging the approaches based on complexity reduction is addressed. The binary search tree and complexity reduction via separation are efficient methods which can be confined to small problems, but merging them can result in significant effect and expansion of its applicability. The simulation tests show proposed approach significantly outperforms previous methods.
VL  - 1
IS  - 1
ER  -

Copy | Download

Author Information

Jamal Arezoo

Department of Automation and Instrumentation, Petroleum University of Technology, Ahvaz, Iran
Karim Salahshoor

Department of Automation and Instrumentation, Petroleum University of Technology, Ahvaz, Iran

Download PDF

Sections

Plain Text BibTeX RIS

APA Style

Jamal Arezoo, Karim Salahshoor. (2017). Complexity Reduction of Explicit Model Predictive Control via Combining Separator Function and Binary Search Trees. American Journal of Computer Science and Technology, 1(1), 19-23. https://doi.org/10.11648/j.ajcst.20180101.13

Copy | Download

ACS Style

Jamal Arezoo; Karim Salahshoor. Complexity Reduction of Explicit Model Predictive Control via Combining Separator Function and Binary Search Trees. Am. J. Comput. Sci. Technol. 2017, 1(1), 19-23. doi: 10.11648/j.ajcst.20180101.13

Copy | Download

AMA Style

Jamal Arezoo, Karim Salahshoor. Complexity Reduction of Explicit Model Predictive Control via Combining Separator Function and Binary Search Trees. Am J Comput Sci Technol. 2017;1(1):19-23. doi: 10.11648/j.ajcst.20180101.13

Copy | Download

@article{10.11648/j.ajcst.20180101.13,
  author = {Jamal Arezoo and Karim Salahshoor},
  title = {Complexity Reduction of Explicit Model Predictive Control via Combining Separator Function and Binary Search Trees},
  journal = {American Journal of Computer Science and Technology},
  volume = {1},
  number = {1},
  pages = {19-23},
  doi = {10.11648/j.ajcst.20180101.13},
  url = {https://doi.org/10.11648/j.ajcst.20180101.13},
  eprint = {https://article.sciencepublishinggroup.com/pdf/10.11648.j.ajcst.20180101.13},
  abstract = {The explicit Model Predictive Control (MPC) has emerged as a powerful technique to solve the optimization problem offline for embedded applications where computations is performed online. Despite practical obstacles in implementation of explicit model predictive control (MPC), the main drawbacks of MPC, namely the need to solve a mathematical program on line to compute the control action are removed. This paper addresses complexity of explicit model predictive control (MPC) in terms of online evaluation and memory requirement. Complexity reduction approaches for explicit MPC has recently been emerged as techniques to enhance applicability of MPC. Individual deployment of the approaches has not had enough effect on complexity reduction. In this paper, merging the approaches based on complexity reduction is addressed. The binary search tree and complexity reduction via separation are efficient methods which can be confined to small problems, but merging them can result in significant effect and expansion of its applicability. The simulation tests show proposed approach significantly outperforms previous methods.},
 year = {2017}
}

Copy | Download

TY  - JOUR
T1  - Complexity Reduction of Explicit Model Predictive Control via Combining Separator Function and Binary Search Trees
AU  - Jamal Arezoo
AU  - Karim Salahshoor
Y1  - 2017/12/24
PY  - 2017
N1  - https://doi.org/10.11648/j.ajcst.20180101.13
DO  - 10.11648/j.ajcst.20180101.13
T2  - American Journal of Computer Science and Technology
JF  - American Journal of Computer Science and Technology
JO  - American Journal of Computer Science and Technology
SP  - 19
EP  - 23
PB  - Science Publishing Group
SN  - 2640-012X
UR  - https://doi.org/10.11648/j.ajcst.20180101.13
AB  - The explicit Model Predictive Control (MPC) has emerged as a powerful technique to solve the optimization problem offline for embedded applications where computations is performed online. Despite practical obstacles in implementation of explicit model predictive control (MPC), the main drawbacks of MPC, namely the need to solve a mathematical program on line to compute the control action are removed. This paper addresses complexity of explicit model predictive control (MPC) in terms of online evaluation and memory requirement. Complexity reduction approaches for explicit MPC has recently been emerged as techniques to enhance applicability of MPC. Individual deployment of the approaches has not had enough effect on complexity reduction. In this paper, merging the approaches based on complexity reduction is addressed. The binary search tree and complexity reduction via separation are efficient methods which can be confined to small problems, but merging them can result in significant effect and expansion of its applicability. The simulation tests show proposed approach significantly outperforms previous methods.
VL  - 1
IS  - 1
ER  -

Copy | Download