A probabilistic validation approach for penalty function design in stochastic model predictive control

IFAC PapersOnLine 53-2 (2020) 11271–11276 ScienceDirect ScienceDirect Available online at www.sciencedirect.com 2405-8963 Copyright © 2020 The Authors. This is an open access article under the CC BY-NC-ND license . Peer review under responsibility of International Federation of Automatic Control. 10.1016/j.ifacol.2020.12.362 10.1016/j.ifacol.2020.12.362 2405-8963 Copyright © 2020 The Authors. This is an open access article under the CC BY-NC-ND license ( http://creativecommons.org/licenses/by-nc-nd/4.0 ) A probabilistic validation approach for penalty function design in Stochastic Model Predictive Control Martina Mammarella ∗1Teodoro Alamo ∗∗ Sergio Lucia ∗∗∗ Fabrizio Dabbene ∗ ∗Institute of Electronics, Computer and Telecommunication Engineering, National Research Council of Italy, Turin, Italy (e-mail: [email protected], fabrizio.dabbene@ ieiit.cnr.it). ∗∗ Departamento de Ingenier´ıa de Sistemas y Autom´atica, Universidad de Sevilla, Escuela Superior de Ingenieros, Camino de los Descubrimientos s/n, 41092 Sevilla, Spain (e-mail: [email protected]) ∗∗∗ Einstein Center Digital Future, Technische Universit¨at Berlin, Germany (e-mail: [email protected]) Abstract: In this paper, we consider a stochastic Model Predictive Control able to account for effects of additive stochastic disturbance with unbounded support, and requiring no restrictive assumption on either independence nor Gaussianity. We revisit the rather classical approach based on penalty functions, with the aim of designing a control scheme that meets some given probabilistic specifications. The main difference with previous approaches is that we do not recur to the notion of probabilistic recursive feasibility, and hence we do not consider separately the unfeasible case. In particular, two probabilistic design problems are envisioned. The first randomization problem aims to design offline the constraint set tightening, following an approach inherited from tube-based MPC. For the second probabilistic scheme, a specific probabilistic validation approach is exploited for tuning the penalty parameter, to be selected offline among a finite-family of possible values. The simple algorithm here proposed allows designing a single controller, always guaranteeing feasibility of the online optimization problem. The proposed method is shown to be more computationally tractable than previous schemes. This is due to the fact that the sample complexity for both probabilistic design problems depends on the prediction horizon in a logarithmic way, unlike scenario-based approaches which exhibit linear dependence. The efficacy of the proposed approach is demonstrated with a numerical example. Keywords: Predictive control, randomized algorithms, sampling methods, stochastic systems, optimization. 1. INTRODUCTION Model predictive control (MPC) is a popular control strategy mainly for its ability to deal with multivariate systems and constraints in a systematic fashion. However, the presence of uncertainties can significantly degrade closed-loop performance, cause violation of constraints or even lead to instabilities. These shortcomings have been addressed by many research works, since the first formulation of robust MPC schemes (Campo and Morari, 1987) based on worst-case analysis. Indeed, traditional robust MPC schemes minimize the chosen cost function for the worstcase value of the uncertainties, which are assumed to be defined in a compact set, and enforce the constraints for all possible realizations of the uncertainties. On the other Fabrizio Dabbene aknowledges the Italian Institute of Technology and the Italian Ministero dell’Istruzione, dell’Universit`a e della Ricerca (PRIN 2017 N. 2017S559BB). Teodoro Alamo acknowledges MEyC Spain (contract DPI2016-76493-C3-1-R). 1corresponding author. hand, because the worst-case value of the uncertainties can have a very small probability of occurrence and any knowledge about their probability distribution is ignored, traditional robust MPC schemes can be very conservative. An alternative to mitigate such conservativeness is to formulate stochastic MPC problems (Mesbah, 2016), which explicitly consider probability distribution functions, including expectations or standard deviations in the cost functions as well as the use of constraints that should be fulfilled in probability, often called chance constraints. Stochastic MPC formulations face two important challenges: (i) the propagation of the stochastic uncertainty through the system dynamics; and (ii) the consideration of chance constraints and recursive feasibility. Unfortunately, exact formulations are intractable even in the linear case. Hence, previous works have been focused on different simplifying assumptions, such as conservative approximation of chance constraints based on the propagation of the variance through linear dynamics (Farina and Scattolini (2016), Hewing and Zeilinger (2018)) or via polynomial A probabilistic validation approach for penalty function design in Stochastic Model Predictive Control Martina Mammarella ∗1Teodoro Alamo ∗∗ Sergio Lucia ∗∗∗ Fabrizio Dabbene ∗ ∗Institute of Electronics, Computer and Telecommunication Engineering, National Research Council of Italy, Turin, Italy (e-mail: [email protected], fabrizio.dabbene@ ieiit.cnr.it). ∗∗ Departamento de Ingenier´ıa de Sistemas y Autom´atica, Universidad de Sevilla, Escuela Superior de Ingenieros, Camino de los Descubrimientos s/n, 41092 Sevilla, Spain (e-mail: [email protected]) ∗∗∗ Einstein Center Digital Future, Technische Universit¨at Berlin, Germany (e-mail: [email protected]) Abstract: In this paper, we consider a stochastic Model Predictive Control able to account for effects of additive stochastic disturbance with unbounded support, and requiring no restrictive assumption on either independence nor Gaussianity. We revisit the rather classical approach based on penalty functions, with the aim of designing a control scheme that meets some given probabilistic specifications. The main difference with previous approaches is that we do not recur to the notion of probabilistic recursive feasibility, and hence we do not consider separately the unfeasible case. In particular, two probabilistic design problems are envisioned. The first randomization problem aims to design offline the constraint set tightening, following an approach inherited from tube-based MPC. For the second probabilistic scheme, a specific probabilistic validation approach is exploited for tuning the penalty parameter, to be selected offline among a finite-family of possible values. The simple algorithm here proposed allows designing a single controller, always guaranteeing feasibility of the online optimization problem. The proposed method is shown to be more computationally tractable than previous schemes. This is due to the fact that the sample complexity for both probabilistic design problems depends on the prediction horizon in a logarithmic way, unlike scenario-based approaches which exhibit linear dependence. The efficacy of the proposed approach is demonstrated with a numerical example. Keywords: Predictive control, randomized algorithms, sampling methods, stochastic systems, optimization. 1. INTRODUCTION Model predictive control (MPC) is a popular control strategy mainly for its ability to deal with multivariate systems and constraints in a systematic fashion. However, the presence of uncertainties can significantly degrade closed-loop performance, cause violation of constraints or even lead to instabilities. These shortcomings have been addressed by many research works, since the first formulation of robust MPC schemes (Campo and Morari, 1987) based on worst-case analysis. Indeed, traditional robust MPC schemes minimize the chosen cost function for the worstcase value of the uncertainties, which are assumed to be defined in a compact set, and enforce the constraints for all possible realizations of the uncertainties. On the other Fabrizio Dabbene aknowledges the Italian Institute of Technology and the Italian Ministero dell’Istruzione, dell’Universit`a e della Ricerca (PRIN 2017 N. 2017S559BB). Teodoro Alamo acknowledges MEyC Spain (contract DPI2016-76493-C3-1-R). 1corresponding author. hand, because the worst-case value of the uncertainties can have a very small probability of occurrence and any knowledge about their probability distribution is ignored, traditional robust MPC schemes can be very conservative. An alternative to mitigate such conservativeness is to formulate stochastic MPC problems (Mesbah, 2016), which explicitly consider probability distribution functions, including expectations or standard deviations in the cost functions as well as the use of constraints that should be fulfilled in probability, often called chance constraints. Stochastic MPC formulations face two important challenges: (i) the propagation of the stochastic uncertainty through the system dynamics; and (ii) the consideration of chance constraints and recursive feasibility. Unfortunately, exact formulations are intractable even in the linear case. Hence, previous works have been focused on different simplifying assumptions, such as conservative approximation of chance constraints based on the propagation of the variance through linear dynamics (Farina and Scattolini (2016), Hewing and Zeilinger (2018)) or via polynomial A probabilistic validation approach for penalty function design in Stochastic Model Predictive Control Martina Mammarella ∗1Teodoro Alamo ∗∗ Sergio Lucia ∗∗∗ Fabrizio Dabbene ∗ ∗Institute of Electronics, Computer and Telecommunication Engineering, National Research Council of Italy, Turin, Italy (e-mail: [email protected], fabrizio.dabbene@ ieiit.cnr.it). ∗∗ Departamento de Ingenier´ıa de Sistemas y Autom´atica, Universidad de Sevilla, Escuela Superior de Ingenieros, Camino de los Descubrimientos s/n, 41092 Sevilla, Spain (e-mail: [email protected]) ∗∗∗ Einstein Center Digital Future, Technische Universit¨at Berlin, Germany (e-mail: [email protected]) Abstract: In this paper, we consider a stochastic Model Predictive Control able to account for effects of additive stochastic disturbance with unbounded support, and requiring no restrictive assumption on either independence nor Gaussianity. We revisit the rather classical approach based on penalty functions, with the aim of designing a control scheme that meets some given probabilistic specifications. The main difference with previous approaches is that we do not recur to the notion of probabilistic recursive feasibility, and hence we do not consider separately the unfeasible case. In particular, two probabilistic design problems are envisioned. The first randomization problem aims to design offline the constraint set tightening, following an approach inherited from tube-based MPC. For the second probabilistic scheme, a specific probabilistic validation approach is exploited for tuning the penalty parameter, to be selected offline among a finite-family of possible values. The simple algorithm here proposed allows designing a single controller, always guaranteeing feasibility of the online optimization problem. The proposed method is shown to be more computationally tractable than previous schemes. This is due to the fact that the sample complexity for both probabilistic design problems depends on the prediction horizon in a logarithmic way, unlike scenario-based approaches which exhibit linear dependence. The efficacy of the proposed approach is demonstrated with a numerical example. Keywords: Predictive control, randomized algorithms, sampling methods, stochastic systems, optimization. 1. INTRODUCTION Model predictive control (MPC) is a popular control strategy mainly for its ability to deal with multivariate systems and constraints in a systematic fashion. However, the presence of uncertainties can significantly degrade closed-loop performance, cause violation of constraints or even lead to instabilities. These shortcomings have been addressed by many research works, since the first formulation of robust MPC schemes (Campo and Morari, 1987) based on worst-case analysis. Indeed, traditional robust MPC schemes minimize the chosen cost function for the worstcase value of the uncertainties, which are assumed to be defined in a compact set, and enforce the constraints for all possible realizations of the uncertainties. On the other Fabrizio Dabbene aknowledges the Italian Institute of Technology and the Italian Ministero dell’Istruzione, dell’Universit`a e della Ricerca (PRIN 2017 N. 2017S559BB). Teodoro Alamo acknowledges MEyC Spain (contract DPI2016-76493-C3-1-R). 1corresponding author. hand, because the worst-case value of the uncertainties can have a very small probability of occurrence and any knowledge about their probability distribution is ignored, traditional robust MPC schemes can be very conservative. An alternative to mitigate such conservativeness is to formulate stochastic MPC problems (Mesbah, 2016), which explicitly consider probability distribution functions, including expectations or standard deviations in the cost functions as well as the use of constraints that should be fulfilled in probability, often called chance constraints. Stochastic MPC formulations face two important challenges: (i) the propagation of the stochastic uncertainty through the system dynamics; and (ii) the consideration of chance constraints and recursive feasibility. Unfortunately, exact formulations are intractable even in the linear case. Hence, previous works have been focused on different simplifying assumptions, such as conservative approximation of chance constraints based on the propagation of the variance through linear dynamics (Farina and Scattolini (2016), Hewing and Zeilinger (2018)) or via polynomial A probabilistic validation approach for penalty function design in Stochastic Model Predictive Control Martina Mammarella ∗1Teodoro Alamo ∗∗ Sergio Lucia ∗∗∗ Fabrizio Dabbene ∗ ∗Institute of Electronics, Computer and Telecommunication Engineering, National Research Council of Italy, Turin, Italy (e-mail: [email protected], fabrizio.dabbene@ ieiit.cnr.it). ∗∗ Departamento de Ingenier´ıa de Sistemas y Autom´atica, Universidad de Sevilla, Escuela Superior de Ingenieros, Camino de los Descubrimientos s/n, 41092 Sevilla, Spain (e-mail: [email protected]) ∗∗∗ Einstein Center Digital Future, Technische Universit¨at Berlin, Germany (e-mail: [email protected]) Abstract: In this paper, we consider a stochastic Model Predictive Control able to account for effects of additive stochastic disturbance with unbounded support, and requiring no restrictive assumption on either independence nor Gaussianity. We revisit the rather classical approach based on penalty functions, with the aim of designing a control scheme that meets some given probabilistic specifications. The main difference with previous approaches is that we do not recur to the notion of probabilistic recursive feasibility, and hence we do not consider separately the unfeasible case. In particular, two probabilistic design problems are envisioned. The first randomization problem aims to design offline the constraint set tightening, following an approach inherited from tube-based MPC. For the second probabilistic scheme, a specific probabilistic validation approach is exploited for tuning the penalty parameter, to be selected offline among a finite-family of possible values. The simple algorithm here proposed allows designing a single controller, always guaranteeing feasibility of the online optimization problem. The proposed method is shown to be more computationally tractable than previous schemes. This is due to the fact that the sample complexity for both probabilistic design problems depends on the prediction horizon in a logarithmic way, unlike scenario-based approaches which exhibit linear dependence. The efficacy of the proposed approach is demonstrated with a numerical example. Keywords: Predictive control, randomized algorithms, sampling methods, stochastic systems, optimization. 1. INTRODUCTION Model predictive control (MPC) is a popular control strategy mainly for its ability to deal with multivariate systems and constraints in a systematic fashion. However, the presence of uncertainties can significantly degrade closed-loop performance, cause violation of constraints or even lead to instabilities. These shortcomings have been addressed by many research works, since the first formulation of robust MPC schemes (Campo and Morari, 1987) based on worst-case analysis. Indeed, traditional robust MPC schemes minimize the chosen cost function for the worstcase value of the uncertainties, which are assumed to be defined in a compact set, and enforce the constraints for all possible realizations of the uncertainties. On the other Fabrizio Dabbene aknowledges the Italian Institute of Technology and the Italian Ministero dell’Istruzione, dell’Universit`a e della Ricerca (PRIN 2017 N. 2017S559BB). Teodoro Alamo acknowledges MEyC Spain (contract DPI2016-76493-C3-1-R). 1corresponding author. hand, because the worst-case value of the uncertainties can have a very small probability of occurrence and any knowledge about their probability distribution is ignored, traditional robust MPC schemes can be very conservative. An alternative to mitigate such conservativeness is to formulate stochastic MPC problems (Mesbah, 2016), which explicitly consider probability distribution functions, including expectations or standard deviations in the cost functions as well as the use of constraints that should be fulfilled in probability, often called chance constraints. Stochastic MPC formulations face two important challenges: (i) the propagation of the stochastic uncertainty through the system dynamics; and (ii) the consideration of chance constraints and recursive feasibility. Unfortunately, exact formulations are intractable even in the linear case. Hence, previous works have been focused on different simplifying assumptions, such as conservative approximation of chance constraints based on the propagation of the variance through linear dynamics (Farina and Scattolini (2016), Hewing and Zeilinger (2018)) or via polynomial A probabilistic validation approach for penalty function design in Stochastic Model Predictive Control Martina Mammarella ∗1Teodoro Alamo ∗∗ Sergio Lucia ∗∗∗ Fabrizio Dabbene ∗ ∗Institute of Electronics, Computer and Telecommunication Engineering, National Research Council of Italy, Turin, Italy (e-mail: [email protected], fabrizio.dabbene@ ieiit.cnr.it). ∗∗ Departamento de Ingenier´ıa de Sistemas y Autom´atica, Universidad de Sevilla, Escuela Superior de Ingenieros, Camino de los Descubrimientos s/n, 41092 Sevilla, Spain (e-mail: [email protected]) ∗∗∗ Einstein Center Digital Future, Technische Universit¨at Berlin, Germany (e-mail: [email protected]) Abstract: In this paper, we consider a stochastic Model Predictive Control able to account for effects of additive stochastic disturbance with unbounded support, and requiring no restrictive assumption on either independence nor Gaussianity. We revisit the rather classical approach based on penalty functions, with the aim of designing a control scheme that meets some given probabilistic specifications. The main difference with previous approaches is that we do not recur to the notion of probabilistic recursive feasibility, and hence we do not consider separately the unfeasible case. In particular, two probabilistic design problems are envisioned. The first randomization problem aims to design offline the constraint set tightening, following an approach inherited from tube-based MPC. For the second probabilistic scheme, a specific probabilistic validation approach is exploited for tuning the penalty parameter, to be selected offline among a finite-family of possible values. The simple algorithm here proposed allows designing a single controller, always guaranteeing feasibility of the online optimization problem. The proposed method is shown to be more computationally tractable than previous schemes. This is due to the fact that the sample complexity for both probabilistic design problems depends on the prediction horizon in a logarithmic way, unlike scenario-based approaches which exhibit linear dependence. The efficacy of the proposed approach is demonstrated with a numerical example. Keywords: Predictive control, randomized algorithms, sampling methods, stochastic systems, optimization. 1. INTRODUCTION Model predictive control (MPC) is a popular control strategy mainly for its ability to deal with multivariate systems and constraints in a systematic fashion. However, the presence of uncertainties can significantly degrade closed-loop performance, cause violation of constraints or even lead to instabilities. These shortcomings have been addressed by many research works, since the first formulation of robust MPC schemes (Campo and Morari, 1987) based on worst-case analysis. Indeed, traditional robust MPC schemes minimize the chosen cost function for the worstcase value of the uncertainties, which are assumed to be defined in a compact set, and enforce the constraints for all possible realizations of the uncertainties. On the other Fabrizio Dabbene aknowledges the Italian Institute of Technology and the Italian Ministero dell’Istruzione, dell’Universit`a e della Ricerca (PRIN 2017 N. 2017S559BB). Teodoro Alamo acknowledges MEyC Spain (contract DPI2016-76493-C3-1-R). 1corresponding author. hand, because the worst-case value of the uncertainties can have a very small probability of occurrence and any knowledge about their probability distribution is ignored, traditional robust MPC schemes can be very conservative. An alternative to mitigate such conservativeness is to formulate stochastic MPC problems (Mesbah, 2016), which explicitly consider probability distribution functions, including expectations or standard deviations in the cost functions as well as the use of constraints that should be fulfilled in probability, often called chance constraints. Stochastic MPC formulations face two important challenges: (i) the propagation of the stochastic uncertainty through the system dynamics; and (ii) the consideration of chance constraints and recursive feasibility. Unfortunately, exact formulations are intractable even in the linear case. Hence, previous works have been focused on different simplifying assumptions, such as conservative approximation of chance constraints based on the propagation of the variance through linear dynamics (Farina and Scattolini (2016), Hewing and Zeilinger (2018)) or via polynomial A probabilistic validation approach for penalty function design in Stochastic Model Predictive Control Martina Mammarella ∗1Teodoro Alamo ∗∗ Sergio Lucia ∗∗∗ Fabrizio Dabbene ∗ ∗Institute of Electronics, Computer and Telecommunication Engineering, National Research Council of Italy, Turin, Italy (e-mail: martina.mammarel[email protected], fabrizio.dabbene@ ieiit.cnr.it). ∗∗ Departamento de Ingenier´ıa de Sistemas y Autom´atica, Universidad de Sevilla, Escuela Superior de Ingenieros, Camino de los Descubrimientos s/n, 41092 Sevilla, Spain (e-mail: [email protected]) ∗∗∗ Einstein Center Digital Future, Technische Universit¨at Berlin, Germany (e-mail: [email protected]) Abstract: In this paper, we consider a stochastic Model Predictive Control able to account for effects of additive stochastic disturbance with unbounded support, and requiring no restrictive assumption on either independence nor Gaussianity. We revisit the rather classical approach based on penalty functions, with the aim of designing a control scheme that meets some given probabilistic specifications. The main difference with previous approaches is that we do not recur to the notion of probabilistic recursive feasibility, and hence we do not consider separately the unfeasible case. In particular, two probabilistic design problems are envisioned. The first randomization problem aims to design offline the constraint set tightening, following an approach inherited from tube-based MPC. For the second probabilistic scheme, a specific probabilistic validation approach is exploited for tuning the penalty parameter, to be selected offline among a finite-family of possible values. The simple algorithm here proposed allows designing a single controller, always guaranteeing feasibility of the online optimization problem. The proposed method is shown to be more computationally tractable than previous schemes. This is due to the fact that the sample complexity for both probabilistic design problems depends on the prediction horizon in a logarithmic way, unlike scenario-based approaches which exhibit linear dependence. The efficacy of the proposed approach is demonstrated with a numerical example. Keywords: Predictive control, randomized algorithms, sampling methods, stochastic systems, optimization. 1. INTRODUCTION Model predictive control (MPC) is a popular control strategy mainly for its ability to deal with multivariate systems and constraints in a systematic fashion. However, the presence of uncertainties can significantly degrade closed-loop performance, cause violation of constraints or even lead to instabilities. These shortcomings have been addressed by many research works, since the first formulation of robust MPC schemes (Campo and Morari, 1987) based on worst-case analysis. Indeed, traditional robust MPC schemes minimize the chosen cost function for the worstcase value of the uncertainties, which are assumed to be defined in a compact set, and enforce the constraints for all possible realizations of the uncertainties. On the other Fabrizio Dabbene aknowledges the Italian Institute of Technology and the Italian Ministero dell’Istruzione, dell’Universit`a e della Ricerca (PRIN 2017 N. 2017S559BB). Teodoro Alamo acknowledges MEyC Spain (contract DPI2016-76493-C3-1-R). 1corresponding author. hand, because the worst-case value of the uncertainties can have a very small probability of occurrence and any knowledge about their probability distribution is ignored, traditional robust MPC schemes can be very conservative. An alternative to mitigate such conservativeness is to formulate stochastic MPC problems (Mesbah, 2016), which explicitly consider probability distribution functions, including expectations or standard deviations in the cost functions as well as the use of constraints that should be fulfilled in probability, often called chance constraints. Stochastic MPC formulations face two important challenges: (i) the propagation of the stochastic uncertainty through the system dynamics; and (ii) the consideration of chance constraints and recursive feasibility. Unfortunately, exact formulations are intractable even in the linear case. Hence, previous works have been focused on different simplifying assumptions, such as conservative approximation of chance constraints based on the propagation of the variance through linear dynamics (Farina and Scattolini (2016), Hewing and Zeilinger (2018)) or via polynomial A probabilistic validation approach for penalty function design in Stochastic Model Predictive Control Martina Mammarella ∗1Teodoro Alamo ∗∗ Sergio Lucia ∗∗∗ Fabrizio Dabbene ∗ ∗Institute of Electronics, Computer and Telecommunication Engineering, National Research Council of Italy, Turin, Italy (e-mail: [email protected], fabrizio.dabbene@ ieiit.cnr.it). ∗∗ Departamento de Ingenier´ıa de Sistemas y Autom´atica, Universidad de Sevilla, Escuela Superior de Ingenieros, Camino de los Descubrimientos s/n, 41092 Sevilla, Spain (e-mail: [email protected]) ∗∗∗ Einstein Center Digital Future, Technische Universit¨at Berlin, Germany (e-mail: [email protected]) Abstract: In this paper, we consider a stochastic Model Predictive Control able to account for effects of additive stochastic disturbance with unbounded support, and requiring no restrictive assumption on either independence nor Gaussianity. We revisit the rather classical approach based on penalty functions, with the aim of designing a control scheme that meets some given probabilistic specifications. The main difference with previous approaches is that we do not recur to the notion of probabilistic recursive feasibility, and hence we do not consider separately the unfeasible case. In particular, two probabilistic design problems are envisioned. The first randomization problem aims to design offline the constraint set tightening, following an approach inherited from tube-based MPC. For the second probabilistic scheme, a specific probabilistic validation approach is exploited for tuning the penalty parameter, to be selected offline among a finite-family of possible values. The simple algorithm here proposed allows designing a single controller, always guaranteeing feasibility of the online optimization problem. The proposed method is shown to be more computationally tractable than previous schemes. This is due to the fact that the sample complexity for both probabilistic design problems depends on the prediction horizon in a logarithmic way, unlike scenario-based approaches which exhibit linear dependence. The efficacy of the proposed approach is demonstrated with a numerical example. Keywords: Predictive control, randomized algorithms, sampling methods, stochastic systems, optimization. 1. INTRODUCTION Model predictive control (MPC) is a popular control strategy mainly for its ability to deal with multivariate systems and constraints in a systematic fashion. However, the presence of uncertainties can significantly degrade closed-loop performance, cause violation of constraints or even lead to instabilities. These shortcomings have been addressed by many research works, since the first formulation of robust MPC schemes (Campo and Morari, 1987) based on worst-case analysis. Indeed, traditional robust MPC schemes minimize the chosen cost function for the worstcase value of the uncertainties, which are assumed to be defined in a compact set, and enforce the constraints for all possible realizations of the uncertainties. On the other Fabrizio Dabbene aknowledges the Italian Institute of Technology and the Italian Ministero dell’Istruzione, dell’Universit`a e della Ricerca (PRIN 2017 N. 2017S559BB). Teodoro Alamo acknowledges MEyC Spain (contract DPI2016-76493-C3-1-R). 1corresponding author. hand, because the worst-case value of the uncertainties can have a very small probability of occurrence and any knowledge about their probability distribution is ignored, traditional robust MPC schemes can be very conservative. An alternative to mitigate such conservativeness is to formulate stochastic MPC problems (Mesbah, 2016), which explicitly consider probability distribution functions, including expectations or standard deviations in the cost functions as well as the use of constraints that should be fulfilled in probability, often called chance constraints. Stochastic MPC formulations face two important challenges: (i) the propagation of the stochastic uncertainty through the system dynamics; and (ii) the consideration of chance constraints and recursive feasibility. Unfortunately, exact formulations are intractable even in the linear case. Hence, previous works have been focused on different simplifying assumptions, such as conservative approximation of chance constraints based on the propagation of the variance through linear dynamics (Farina and Scattolini (2016), Hewing and Zeilinger (2018)) or via polynomial A probabilistic validation approach for penalty function design in Stochastic Model Predictive Control Martina Mammarella ∗1Teodoro Alamo ∗∗ Sergio Lucia ∗∗∗ Fabrizio Dabbene ∗ ∗Institute of Electronics, Computer and Telecommunication Engineering, National Research Council of Italy, Turin, Italy (e-mail: [email protected], fabrizio.dabbene@ ieiit.cnr.it). ∗∗ Departamento de Ingenier´ıa de Sistemas y Autom´atica, Universidad de Sevilla, Escuela Superior de Ingenieros, Camino de los Descubrimientos s/n, 41092 Sevilla, Spain (e-mail: [email protected]) ∗∗∗ Einstein Center Digital Future, Technische Universit¨at Berlin, Germany (e-mail: [email protected]) Abstract: In this paper, we consider a stochastic Model Predictive Control able to account for effects of additive stochastic disturbance with unbounded support, and requiring no restrictive assumption on either independence nor Gaussianity. We revisit the rather classical approach based on penalty functions, with the aim of designing a control scheme that meets some given probabilistic specifications. The main difference with previous approaches is that we do not recur to the notion of probabilistic recursive feasibility, and hence we do not consider separately the unfeasible case. In particular, two probabilistic design problems are envisioned. The first randomization problem aims to design offline the constraint set tightening, following an approach inherited from tube-based MPC. For the second probabilistic scheme, a specific probabilistic validation approach is exploited for tuning the penalty parameter, to be selected offline among a finite-family of possible values. The simple algorithm here proposed allows designing a single controller, always guaranteeing feasibility of the online optimization problem. The proposed method is shown to be more computationally tractable than previous schemes. This is due to the fact that the sample complexity for both probabilistic design problems depends on the prediction horizon in a logarithmic way, unlike scenario-based approaches which exhibit linear dependence. The efficacy of the proposed approach is demonstrated with a numerical example. Keywords: Predictive control, randomized algorithms, sampling methods, stochastic systems, optimization. 1. INTRODUCTION Model predictive control (MPC) is a popular control strategy mainly for its ability to deal with multivariate systems and constraints in a systematic fashion. However, the presence of uncertainties can significantly degrade closed-loop performance, cause violation of constraints or even lead to instabilities. These shortcomings have been addressed by many research works, since the first formulation of robust MPC schemes (Campo and Morari, 1987) based on worst-case analysis. Indeed, traditional robust MPC schemes minimize the chosen cost function for the worstcase value of the uncertainties, which are assumed to be defined in a compact set, and enforce the constraints for all possible realizations of the uncertainties. On the other Fabrizio Dabbene aknowledges the Italian Institute of Technology and the Italian Ministero dell’Istruzione, dell’Universit`a e della Ricerca (PRIN 2017 N. 2017S559BB). Teodoro Alamo acknowledges MEyC Spain (contract DPI2016-76493-C3-1-R). 1corresponding author. hand, because the worst-case value of the uncertainties can have a very small probability of occurrence and any knowledge about their probability distribution is ignored, traditional robust MPC schemes can be very conservative. An alternative to mitigate such conservativeness is to formulate stochastic MPC problems (Mesbah, 2016), which explicitly consider probability distribution functions, including expectations or standard deviations in the cost functions as well as the use of constraints that should be fulfilled in probability, often called chance constraints. Stochastic MPC formulations face two important challenges: (i) the propagation of the stochastic uncertainty through the system dynamics; and (ii) the consideration of chance constraints and recursive feasibility. Unfortunately, exact formulations are intractable even in the linear case. Hence, previous works have been focused on different simplifying assumptions, such as conservative approximation of chance constraints based on the propagation of the variance through linear dynamics (Farina and Scattolini (2016), Hewing and Zeilinger (2018)) or via polynomial 11272 Martina Mammarella et al. / IFAC PapersOnLine 53-2 (2020) 11271–11276 chaos expansions (Mesbah, 2016). Other formulations use the scenario approach (Prandini et al. (2012), Calafiore and Fagiano (2013), (Schildbach et al., 2014), Margellos et al. (2014)), and also an offline scenario setting that leads to a reduced number of samples and lower computational load as shown in Lorenzen et al. (2017), Mammarella et al. (2018). Another problem to deal with in a stochastic MPC setting is related to guaranteeing recursive feasibility. To overcome this difficulty, the approach presented in Lorenzen et al. (2017) employs constraint tightening to guarantee robust constraint satisfaction for bounded uncertainty whereas Fleming and Cannon (2019) uses firststep chance constraint and applies robust constraints for the rest of the horizon. The main contribution of this work is the achievement of the desired closed-loop guarantees by means of probabilistic validation techniques (Tempo et al., 1997), (Alamo et al., 2015), which are used at two different levels. The first use of probabilistic validation is to compute offline a constraint tightening, following the stochastic tube-based MPC approach proposed in (Lorenzen et al., 2016), but using probabilistic validation setting instead of the scenario approach. Secondly, to guarantee recursive feasibility, we relax the constraints using a penalty function method Kerrigan and Maciejowski (2000) and, following ideas presented in Karg et al. (2019), we perform an offline probabilistic design of the penalty parameter, selected among a finite-family of values, so that the desired probabilistic guarantees of the closed-loop constraint satisfaction are fulfilled. The proposed approach leads to an MPC formulation that is always feasible and it can obtain a verifiable closedloop performance. An important merit of our method is that no assumptions on independence or Gaussianity of the stochastic variables are necessary. In addition, the obtained sample complexity does not depend on the design space as in the scenario approach (Calafiore and Fagiano, 2013), or on quantities difficult to compute in general such as the Vapnik–Chervonenkis (VC) dimension (Lorenzen et al., 2017). As a result, the sample complexity depends on the prediction horizon only in a logarithmic way, significantly reducing the number of samples to draw and consequently the computational load. The potential of the approach has been shown via a numerical example in Mammarella et al. (2020). The remainder of the paper is organized as follows. Section 2 describes the mathematical problem setup. Section 3 bounds the effect of the disturbances while Section 4 describes how to design a proper tightening of the constraints. Section 5 describes the penalty function method used to obtain always a feasible optimization problem and Section 6 discusses the choice of the penalty parameter. Main conclusions of the work are presented in Section 7. Notation: The set N>0denotes the positive integers, the set N≥0={0}∪N>0the non-negative integers, and Nb athe integers interval [a, b]. Similarly R>0(R≥0) for positive real numbers. We use xkfor the (measured) state at time kand x|kfor the state predicted steps ahead at time k. Positive (semi)definite matrices Aare denoted A0(A0) and x2 A . =xTAx. For vectors, x0(x0) is intended component-wise. Calligraphic upper-case letters, e.g. A, denote sets. PAdenotes the probabilistic distribution of a random variable a∈A. Sequence of scalars/vectors are denoted with bold lower-case letters, i.e. v. Given a vector α=[α1,...,α nα]T∈Rnα, then α+is a scalar defined as α+. = nα  i=1 max{0,α i}. 2. PROBLEM SETUP Let us consider the following linear time-invariant system affected by persistent, additive disturbance ζk∈Rnx xk+1 =Axk+Buk+ζk,∀k∈N≥0(1) where xk∈Rnxis the state variable at time k,uk∈Rnuis the control input, and Aand Bare matrices of appropriate dimensions. No assumption on neither independence nor Gaussianity are made on the stochastic disturbance ζk. Moreover, both state and input are constrained in compact sets Xand U, respectively, and the corresponding constraints can be defined in a compact form as Cxk+Dukh. (2) The control objective is to design a stabilizing receding horizon control, which guarantees constraint satisfaction in a probabilistic setting. We will consider the following quadratic stage cost L(xk,u k). =xk2 Q+uk2 R,(3) where Q∈Rnx×nx,Q0, R∈Rnu×nu,R0. To solve the control problem, a stochastic MPC algorithm is considered where, as typical of predictive schemes, the optimal control problem is solved repeatedly over a finite horizon N, but only the first control action of the optimal sequence is implemented (see Mayne et al. (2000) for a meticulous review on MPC). The proposed controller is designed by means of a two-step procedure: (i) Using a sampling method, we first bound the effect of disturbances in a probabilistic manner. This allows us to formulate a nominal model predictive controller that addresses the chance constraints issue (Section 3 and Section 4). (ii) To avoid infeasibility of the proposed MPC approach, we rewrite the controller using a penalty cost scheme. In particular, the penalty factor is adjusted using sampling in such a way that the resulting controller meets online the probabilistic specifications on the constraints satisfaction (Section 5 and Section 6). 3. PROBABILISTIC UPPER BOUNDS OF THE EFFECT OF DISTURBANCES As it is common in robust and stochastic MPC, let us consider the state of the system x|k, predicted steps ahead from time k, split into a deterministic, nominal part z|kand an error part e|kas x|k=z|k+e|k.(4) Then, a parametrized feedback policy of the form u|k=v|k+Kx|k,∀∈NN−1 0,(5) is considered where the feedback gain matrix Kis quadratically stabilizing for the system (1). Martina Mammarella et al. / IFAC PapersOnLine 53-2 (2020) 11271–11276 11273 chaos expansions (Mesbah, 2016). Other formulations use the scenario approach (Prandini et al. (2012), Calafiore and Fagiano (2013), (Schildbach et al., 2014), Margellos et al. (2014)), and also an offline scenario setting that leads to a reduced number of samples and lower computational load as shown in Lorenzen et al. (2017), Mammarella et al. (2018). Another problem to deal with in a stochastic MPC setting is related to guaranteeing recursive feasibility. To overcome this difficulty, the approach presented in Lorenzen et al. (2017) employs constraint tightening to guarantee robust constraint satisfaction for bounded uncertainty whereas Fleming and Cannon (2019) uses firststep chance constraint and applies robust constraints for the rest of the horizon. The main contribution of this work is the achievement of the desired closed-loop guarantees by means of probabilistic validation techniques (Tempo et al., 1997), (Alamo et al., 2015), which are used at two different levels. The first use of probabilistic validation is to compute offline a constraint tightening, following the stochastic tube-based MPC approach proposed in (Lorenzen et al., 2016), but using probabilistic validation setting instead of the scenario approach. Secondly, to guarantee recursive feasibility, we relax the constraints using a penalty function method Kerrigan and Maciejowski (2000) and, following ideas presented in Karg et al. (2019), we perform an offline probabilistic design of the penalty parameter, selected among a finite-family of values, so that the desired probabilistic guarantees of the closed-loop constraint satisfaction are fulfilled. The proposed approach leads to an MPC formulation that is always feasible and it can obtain a verifiable closedloop performance. An important merit of our method is that no assumptions on independence or Gaussianity of the stochastic variables are necessary. In addition, the obtained sample complexity does not depend on the design space as in the scenario approach (Calafiore and Fagiano, 2013), or on quantities difficult to compute in general such as the Vapnik–Chervonenkis (VC) dimension (Lorenzen et al., 2017). As a result, the sample complexity depends on the prediction horizon only in a logarithmic way, significantly reducing the number of samples to draw and consequently the computational load. The potential of the approach has been shown via a numerical example in Mammarella et al. (2020). The remainder of the paper is organized as follows. Section 2 describes the mathematical problem setup. Section 3 bounds the effect of the disturbances while Section 4 describes how to design a proper tightening of the constraints. Section 5 describes the penalty function method used to obtain always a feasible optimization problem and Section 6 discusses the choice of the penalty parameter. Main conclusions of the work are presented in Section 7. Notation: The set N>0denotes the positive integers, the set N≥0={0}∪N>0the non-negative integers, and Nb athe integers interval [a, b]. Similarly R>0(R≥0) for positive real numbers. We use xkfor the (measured) state at time kand x|kfor the state predicted steps ahead at time k. Positive (semi)definite matrices Aare denoted A0(A0) and x2 A . =xTAx. For vectors, x0(x0) is intended component-wise. Calligraphic upper-case letters, e.g. A, denote sets. PAdenotes the probabilistic distribution of a random variable a∈A. Sequence of scalars/vectors are denoted with bold lower-case letters, i.e. v. Given a vector α=[α1,...,α nα]T∈Rnα, then α+is a scalar defined as α+. = nα  i=1 max{0,α i}. 2. PROBLEM SETUP Let us consider the following linear time-invariant system affected by persistent, additive disturbance ζk∈Rnx xk+1 =Axk+Buk+ζk,∀k∈N≥0(1) where xk∈Rnxis the state variable at time k,uk∈Rnuis the control input, and Aand Bare matrices of appropriate dimensions. No assumption on neither independence nor Gaussianity are made on the stochastic disturbance ζk. Moreover, both state and input are constrained in compact sets Xand U, respectively, and the corresponding constraints can be defined in a compact form as Cxk+Dukh. (2) The control objective is to design a stabilizing receding horizon control, which guarantees constraint satisfaction in a probabilistic setting. We will consider the following quadratic stage cost L(xk,u k). =xk2 Q+uk2 R,(3) where Q∈Rnx×nx,Q0, R∈Rnu×nu,R0. To solve the control problem, a stochastic MPC algorithm is considered where, as typical of predictive schemes, the optimal control problem is solved repeatedly over a finite horizon N, but only the first control action of the optimal sequence is implemented (see Mayne et al. (2000) for a meticulous review on MPC). The proposed controller is designed by means of a two-step procedure: (i) Using a sampling method, we first bound the effect of disturbances in a probabilistic manner. This allows us to formulate a nominal model predictive controller that addresses the chance constraints issue (Section 3 and Section 4). (ii) To avoid infeasibility of the proposed MPC approach, we rewrite the controller using a penalty cost scheme. In particular, the penalty factor is adjusted using sampling in such a way that the resulting controller meets online the probabilistic specifications on the constraints satisfaction (Section 5 and Section 6). 3. PROBABILISTIC UPPER BOUNDS OF THE EFFECT OF DISTURBANCES As it is common in robust and stochastic MPC, let us consider the state of the system x|k, predicted steps ahead from time k, split into a deterministic, nominal part z|kand an error part e|kas x|k=z|k+e|k.(4) Then, a parametrized feedback policy of the form u|k=v|k+Kx|k,∀∈NN−1 0,(5) is considered where the feedback gain matrix Kis quadratically stabilizing for the system (1). Hence, considering the feedback policy (5), the system dynamics in (1) along the prediction horizon Ncan be rewritten in terms of nominal and error dynamics as z+1|k=AKz|k+Bv|k,z 0|k=xk,(6a) e+1|k=AKe|k+ζ|k,e 0|k=0,(6b) where ζ|k . =ζ+kand AK . =A+BK. Now, considering the state decomposition in (4) and the feedback policy (5), the constraint (2) can be rewritten as CKz|k+Dv|k+CKe|kh, ∀∈IN N−1 =0 (7) where CK . =(C+DK). In absence of disturbances, e|k= 0, for all ∈IN N−1 =0 and, consequently, the constraints given in (7) would be equivalent to CKz|k+Dv|kh, ∀∈IN N−1 0.(8) On the other hand, in the presence of random disturbances, one has to deal with the uncertain random vectors CKe|k, with ∈IN N−1 =0 that appear in (7). One possibility is to probabilistically upper bound those terms. This is precisely the objective of the remaining of this section. 3.1 Preliminaries: Probabilistic upper bound of a random variable We first present a generalization of the notion of the maximum of a collection of scalars, borrowed from the field of order statistics (Ahsanullah et al., 2013; Arnold et al., 1992). This will allow us to reduce the conservativeness that follows from the use of the standard notion of max function. See also Section 3 of Alamo et al. (2018). Definition 1. (Ordered Sequence). Given a sequence of S scalars v={v(1),v(2),...,v(S)}={v(i)}S i=1, we denote with v+={v(i) +}S i=1 the ordered sequence obtained by rearranging the elements of vin a nonincreasing order. That is v(1) +≥v(2) +≥...≥v(S−1) +≥v(S) +. Definition 2. (Generalized max function ·r). Given a sequence v={v(i)}S i=1 of Sscalars and the integer r∈[1,S], we define the generalized max function vras vr . =v(r) +. where {v(i) +}S i=1 is given in Definition 1. Clearly, applying Definition 1, we have v1=v(1) += max 1≤i≤Sv(i),vS=v(S) += min 1≤i≤Sv(i). Furthermore, v2denotes the second largest value in v, v3the third largest one, etc. We notice that the notation vrdoes not need to make explicit S, the number of components of v. The following property, which has been already proved in (Alamo et al., 2018, Property 3), states that the generalized notion of max function can be used to provide a probabilistic upper bound of a given random variable. Property 1. Consider a random scalar variable v∈Vwith probabilistic distribution PV. Suppose that v={v(i)}S i=1 is a sequence of Sindependent identically distributed (i.i.d.) scalars that have been drawn according to PV. Then, with probability no smaller than 1 −δ, PV{v>vr}≤, provided that r∈IN S 1and r−1  m=0 S mm(1 −)S−m≤δ. (9) Moreover, (9) is satisfied if S≥1 r−1 + ln 1 δ+2(r−1) ln 1 δ. Property 1 has been already used in the context of probabilistic scaling and validation (see Alamo et al. (2019) and Karg et al. (2019)). See also Tempo et al. (1997) for the particularization of the result to the case r= 1 and a single constraint. In the following section, we will generalize this result in such a way that it will allow us to address the probabilistic tightening of the control constraints in order to cope with the uncertain disturbances. 3.2 Sample-based probabilistic upper bounds of the effect of disturbances From the uncertain dynamics given in (6b), we have that the sequence {e|k}N−1 =0 is completely determined by the sequence ζ={ζ0|k,ζ 1|k,...,ζ N−1|k}={ζk,ζ k+1,...,ζ k+N−1}. We assume that ζis a stationary random vector with probability distribution PDi n IR nx×N. Since we assume that the probability distribution of ζ∈Dis independent of sample time kdue to the stationary nature of random sequence ζ, we have that the probability distribution of e|kis equal to the probability distribution of e|0. In order to make explicit the dependence of e|kon the uncertain disturbances, we denote by {e|k(ζ)}N−1 =0 the sequence of error dynamics (6b) corresponding to the sequence ζ. Now, we generalize the results of Property 1 to obtain sample-based probabilistic upper bounds for CK,j e|k(ζ),j∈Nnh 1,∈NN−1 0, where CK,j denotes the j-th row of matrix CK. Theorem 1. Given a discarding parameter rq, and the probabilistic levels q∈(0,1) and δq∈(0,1), suppose that Sqi.i.d. samples {ζ(1),...,ζ(Sq)}are drawn according to PD. Let us assume also that the vectors {q0,q 1,...,q N−1}∈ IR nh×N are computed using the following expression q,j ={CK,j e|0(ζ(i))}Sq i=1rq ,∀∈IN N−1 0,∀j∈IN nh 1, (10) where q,j is the j-th component of q∈IR nh. Then, with probability no smaller than 1 −δq, we have PD{CK,j e|k(ζ)>q ,j}≤q,∀∈IN N−1 0,∀j∈IN nh 1, provided that r∈NSq 1and rq−1  m=0 Sq mm q(1 −q)Sq−m≤δq nhN.(11) 11274 Martina Mammarella et al. / IFAC PapersOnLine 53-2 (2020) 11271–11276 In addition, (11) is satisfied if Sq≥1 qrq−1 + ln nhN δq +2(rq−1) ln nhN δq.(12) Proof to Theorem 1 can be found in Appendix A of Mammarella et al. (2020). 4. SAMPLE-BASED CONSTRAINT TIGHTENING The objective of this section is to present a model predictive controller with a constraint tightening based on the probabilistic upper bounds {q}N−1 =0 that can be obtained from Theorem 1. For a classical MPC scheme with semi-feedback structure u|k=Kx|k+v|k, the finite horizon cost J(xk,vk) to be minimized at time kis defined as J(xk,vk)= N−1  =0 (x|k2 Q+Kx|k+v|k2 R)+xN|k2 ˜ P, (13) where xk=[x0|k,...,x N|k]T,vk=[v0|k,...,v N−1|k]T, and ˜ Pis the solution of the discrete-time Riccati equation Q+KTRK +AT K˜ PAK=˜ P. (14) Then, a nominal finite horizon optimization problem Pnom(xk) can be defined as min xk,vk J(xk,vk) (15a) s.t. x0|k=xk,(15b) x+1|k=AKx|k+Bv|k∀∈NN−2 0,(15c) xN−1|k=AKxN−1|k+BvN−1|k,(15d) CKx|k+Dv|kh, ∀∈NN−1 0.(15e) We notice that constraint (15d) is a terminal constraint that forces xN−1to be an equilibrium point for the nominal system. This corresponds to a tracking MPC approach targeting the origin and enforcing an equilibrium point as terminal constraint. This approach has the effect of enlarging the domain of attraction of the origin (Limon et al. (2008)). In this work, we inherit the typical approach exploited in tube-based MPC schemes (see e.g. Mayne and Rawlings (2009)), where the control objective becomes controlling the nominal dynamics z|kin (6a) by solving the following optimization problem subject to a tightened version of the nominal constraints given in (8). Definition 3. (Finite Horizon Optimization Problem with Tightened Constraints) Given an initial condition z0|k∈ Rnx, with z0|k=xk, we formulate the optimization problem Pq(xk) with tightened constraints as min zk,vk J(zk,vk) (16a) s.t. z0|k=xk,(16b) z+1|k=AKz|k+Bv|k,∀∈NN−2 0,(16c) zN−1|k=AKzN−1|k+BvN−1|k,(16d) CKz|k+Dv|kh−q,∀∈NN−1 0,(16e) We denote with XNthe set of initial conditions xk for which problem Pq(xk) is feasible. For every xk∈ XNwe denote the minimizer of Pq(xk)by(z∗ k,v∗ k)= (z∗ 0|k,...,z∗ N|k,v∗ 0|k,...,v∗ N−1|k). It is important to highlight that, as in (13), a weighted terminal cost is included to ensure that the optimal cost J(zk,vk) is a Lyapunov function for the system, guaranteeing stability. By properly weighting the terminal cost, the domain of attraction of this controller can be enlarged. See e.g. Limon et al. (2006) and references therein. From (7) we have that the control constraints Cx|k+Du|kh, ∀∈IN N−1 0, can be rewritten as CKz|k+Du|kh−CKe|k.(17) Thus, the tightened constraints (16e) guarantee the satisfaction of (17) provided that Cke|kq. We conclude that CKz|k+Dv|kh−q Cke|kq⇒Cx|k+Du|kh. From here we infer that, for every feasible solution (zk,vk) of Pq(xk), PD{Cx|k+Du|kh}≥PD{CKe|kq}. Denoting Cj,Dj, and CK,j the j-th rows of matrices C, Dand CKrespectively, and hj,q,j the j-th components of hand qwe also obtain PD{Cjx|k+Dju|k≤hj}≥PD{CK,j e|k≤q,j}. Given δq∈(0,1) and q∈(0,1), Theorem 1 provides a way to obtain {q}N−1 =0 such that, with probability no smaller than 1 −δq, PD{CK,j e|k(ζ)>q ,j}≤q,∀∈IN N−1 0,∀j∈IN nh 1. Thus, we conclude that, given δq∈(0,1) and q∈(0,1), if {q}N−1 =0 are obtained according to Theorem 1 then, with probability no smaller than 1 −δq, PD{Cjx|k+Dju|k≤hj}≥1−q,∀∈IN N−1 0,∀j∈IN nh 1. We notice that the previous probabilistic bound does not refer to the closed-loop behaviour, but to the prediction scheme of the stochastic MPC formulation. In the following sections, we present how to design a soft constrained version of the controller proposed in (16) in order to obtain closed-loop probabilistic guarantees. 5. SOFT-CONSTRAINED CONTROLLER The feasibility region XNof problem Pq(·) is often a bounded region around the origin. Moreover, if the probability distribution of the disturbances has not a finite support, then the on-line recursive feasibility of Pq(·) can only be guaranteed in a probabilistic way (see, for example, Fleming and Cannon (2019)). In order to circumvent this problem, we propose a soft constrained formulation of the optimization problem that defines the stochastic MPC controller. The proposed scheme relies on the notion of penalty function (Kerrigan and Maciejowski (2000)). Given a penalty factor ρ>0, and an initial condition xk, we define the new optimization problem Pρ(xk) as min zk,vk J(zk,vk)+ρ N−1  =0 CKz|k+Dv|k−h+q+ (18a) s.t. (16b),(16c),(16d),(18b) u0|k=v0|k+Kx0|k∈U.(18c) Martina Mammarella et al. / IFAC PapersOnLine 53-2 (2020) 11271–11276 11275 In addition, (11) is satisfied if Sq≥1 qrq−1 + ln nhN δq +2(rq−1) ln nhN δq.(12) Proof to Theorem 1 can be found in Appendix A of Mammarella et al. (2020). 4. SAMPLE-BASED CONSTRAINT TIGHTENING The objective of this section is to present a model predictive controller with a constraint tightening based on the probabilistic upper bounds {q}N−1 =0 that can be obtained from Theorem 1. For a classical MPC scheme with semi-feedback structure u|k=Kx|k+v|k, the finite horizon cost J(xk,vk) to be minimized at time kis defined as J(xk,vk)= N−1  =0 (x|k2 Q+Kx|k+v|k2 R)+xN|k2 ˜ P, (13) where xk=[x0|k,...,x N|k]T,vk=[v0|k,...,v N−1|k]T, and ˜ Pis the solution of the discrete-time Riccati equation Q+KTRK +AT K˜ PAK=˜ P. (14) Then, a nominal finite horizon optimization problem Pnom(xk) can be defined as min xk,vk J(xk,vk) (15a) s.t. x0|k=xk,(15b) x+1|k=AKx|k+Bv|k∀∈NN−2 0,(15c) xN−1|k=AKxN−1|k+BvN−1|k,(15d) CKx|k+Dv|kh, ∀∈NN−1 0.(15e) We notice that constraint (15d) is a terminal constraint that forces xN−1to be an equilibrium point for the nominal system. This corresponds to a tracking MPC approach targeting the origin and enforcing an equilibrium point as terminal constraint. This approach has the effect of enlarging the domain of attraction of the origin (Limon et al. (2008)). In this work, we inherit the typical approach exploited in tube-based MPC schemes (see e.g. Mayne and Rawlings (2009)), where the control objective becomes controlling the nominal dynamics z|kin (6a) by solving the following optimization problem subject to a tightened version of the nominal constraints given in (8). Definition 3. (Finite Horizon Optimization Problem with Tightened Constraints) Given an initial condition z0|k∈ Rnx, with z0|k=xk, we formulate the optimization problem Pq(xk) with tightened constraints as min zk,vk J(zk,vk) (16a) s.t. z0|k=xk,(16b) z+1|k=AKz|k+Bv|k,∀∈NN−2 0,(16c) zN−1|k=AKzN−1|k+BvN−1|k,(16d) CKz|k+Dv|kh−q,∀∈NN−1 0,(16e) We denote with XNthe set of initial conditions xk for which problem Pq(xk) is feasible. For every xk∈ XNwe denote the minimizer of Pq(xk)by(z∗ k,v∗ k)= (z∗ 0|k,...,z∗ N|k,v∗ 0|k,...,v∗ N−1|k). It is important to highlight that, as in (13), a weighted terminal cost is included to ensure that the optimal cost J(zk,vk) is a Lyapunov function for the system, guaranteeing stability. By properly weighting the terminal cost, the domain of attraction of this controller can be enlarged. See e.g. Limon et al. (2006) and references therein. From (7) we have that the control constraints Cx|k+Du|kh, ∀∈IN N−1 0, can be rewritten as CKz|k+Du|kh−CKe|k.(17) Thus, the tightened constraints (16e) guarantee the satisfaction of (17) provided that Cke|kq. We conclude that CKz|k+Dv|kh−q Cke|kq⇒Cx|k+Du|kh. From here we infer that, for every feasible solution (zk,vk) of Pq(xk), PD{Cx|k+Du|kh}≥PD{CKe|kq}. Denoting Cj,Dj, and CK,j the j-th rows of matrices C, Dand CKrespectively, and hj,q,j the j-th components of hand qwe also obtain PD{Cjx|k+Dju|k≤hj}≥PD{CK,j e|k≤q,j}. Given δq∈(0,1) and q∈(0,1), Theorem 1 provides a way to obtain {q}N−1 =0 such that, with probability no smaller than 1 −δq, PD{CK,j e|k(ζ)>q ,j}≤q,∀∈IN N−1 0,∀j∈IN nh 1. Thus, we conclude that, given δq∈(0,1) and q∈(0,1), if {q}N−1 =0 are obtained according to Theorem 1 then, with probability no smaller than 1 −δq, PD{Cjx|k+Dju|k≤hj}≥1−q,∀∈IN N−1 0,∀j∈IN nh 1. We notice that the previous probabilistic bound does not refer to the closed-loop behaviour, but to the prediction scheme of the stochastic MPC formulation. In the following sections, we present how to design a soft constrained version of the controller proposed in (16) in order to obtain closed-loop probabilistic guarantees. 5. SOFT-CONSTRAINED CONTROLLER The feasibility region XNof problem Pq(·) is often a bounded region around the origin. Moreover, if the probability distribution of the disturbances has not a finite support, then the on-line recursive feasibility of Pq(·) can only be guaranteed in a probabilistic way (see, for example, Fleming and Cannon (2019)). In order to circumvent this problem, we propose a soft constrained formulation of the optimization problem that defines the stochastic MPC controller. The proposed scheme relies on the notion of penalty function (Kerrigan and Maciejowski (2000)). Given a penalty factor ρ>0, and an initial condition xk, we define the new optimization problem Pρ(xk) as min zk,vk J(zk,vk)+ρ N−1  =0 CKz|k+Dv|k−h+q+ (18a) s.t. (16b),(16c),(16d),(18b) u0|k=v0|k+Kx0|k∈U.(18c) To guarantee that the controller provides admissible control action, we have explicitly added a first step constraint on the input u0|kin (18c), defining the feasible first inputs of the finite horizon program. Under very general assumptions (controllability and N≥nx), problem Pρ(xk) is always feasible. Moreover, Pρ(xk) can be cast into the following equivalent optimization problem using a slack variable η min zk,vk,η J(zk,vk)+ρη1(19a) s.t. z0|k=xk,(19b) z+1|k=AKz|k+v|k,∀∈NN−2 0,(19c) zN−1|k=AzN−1|k+BvN−1|k,(19d) u0|k=v0|k+Kx0|k∈U,(19e) CKz|k+Dv|k−h+qη, ∀∈NN−1 0(19f) η0.(19g) Since the components of ηare restricted to be nonnegative, η1is equal to the sum of the components of η. This implies that optimization problem (19) amounts to the minimization of a semi-definite quadratic function subject to a set of linear equalities and inequalities. Thus, (19) is a semi-definite quadratic optimization problem, for which there exits many reliable solvers suited for fastembedded implementations, e.g. OSQP and CVXGEN. See Stellato et al. (2018), Mattingley and Boyd (2012) and references therein. 6. SAMPLED-BASED DESIGN OF THE PENALTY FACTOR ρ The objective of this section is to determine, by means of a sampled-based scheme, a value of the penalty factor ρable to provide some probabilistic guarantees with respect to the closed-loop satisfaction of (2) along a given simulation horizon M Cxk+Dukh, k =0,...,M. Givens ρ∈(0,∞) and the state vector xk, the control action ukcorresponding to the control scheme presented in Section 5 is uk=v∗ 0|k+Kxk, where v∗ 0|kis the first element of the optimal control sequence v∗ k, solution of (19). The resulting controller is defined as uk=κ(xk,ρ), where we make explicit the penalty factor ρ. Hence, the closed-loop system (1) becomes xk+1 =Axk+Bκ(xk,ρ)+ζk,∀k∈IN ≥0. In order to characterize the closed-loop behaviour of the system, we consider a simulation horizon Mconsiderably larger than the prediction horizon Nused in the definition of the controller κ(·,ρ). In particular, we assume that the horizon Mis large enough to guarantee that the state xM reaches a safe region around the reference steady state. Thus, the closed-loop trajectory {xk,u k}M k=0 is determined by (i) the penalty factor ρ; (ii) the initial condition at k= 0, i.e. x0; (iii) the uncertain realization of the disturbances dM={ζ0,...,ζ M−1}. Now, let us consider a probability distribution in XN, i.e. the feasibility region of optimization problem (16). Moreover, given the simulation horizon M, we define DM as the set of the possible values for dMand a probability distribution in it too. In order to simplify the notation, we define Was the set of possible values for w={x0,dM}={x0,ζ 0,...,ζ M−1}∈X N×D M=W. We assume that we are able to draw i.i.d. samples from W. Then, the closed-loop trajectory corresponding to controller κ(·,ρ) and uncertain realization wis denoted as {xk(w, ρ),u k(w, ρ)}M k=0. Given the uncertain realization wand ρ, we can determine if the corresponding closed-loop trajectory satisfies the control constraints by means of the computation of the following performance index g(w, ρ). = M  k=0 Cxk(w, ρ)+Duk(w, ρ)−h+. Hence, we have g(w, ρ)=0⇔Cxk(w, ρ)+Duk(w, ρ)h, ∀k∈IN M 0, and we can conclude that g(w, ρ) serves as an index to evaluate to which extent the control constraints have been satisfied along the closed-loop trajectory. Now, we consider that ρis allowed to take values from a set of finite cardinality Θρ={ρ1,ρ 2,...,ρ nC}, where nCis the cardinality of Θρ. The next theorem presents a sample-based scheme that, for any ρ∈Θρ, provides a probabilistic upper bound on g(w, ρ). Theorem 2. Let us suppose to draw Sρi.i.d. samples of w(i)from W=XN×D M, i.e. {w(1),...,w (Sρ)}, and that rρis a given discarding parameter. Moreover, given any ρ∈Θρ, we introduce the following notation γ(ρ)={g(w(i),ρ)}Sρ i=1rρ .(20) Then, with probability no smaller than 1 −δρ, we have PW{g(w, ρ)>γ(ρ)}≤ρ,∀ρ∈Θρ,(21) provided that rρ∈IN Sρ 1and rρ−1  m=0 Sρ mm ρ(1 −ρ)Sρ−m≤δρ nC .(22) In addition, (22) is satisfied if Sρ≥1 ρrρ−1 + ln nC δρ +2(rρ−1) ln nC δρ.(23) Proof to Theorem 2 follows similar developments to that of Theorem 1 and is omitted for brevity. We notice that the probabilistic guarantees given in (21) are valid for every value of ρin Θρ. The particular choice for the controller implementation depends on the specific control application. For example, one could choose the value of ρthat minimizes γ(ρ) in Θρ. Another possibility is to choose the smallest ρsatisfying a pre-specified constraint on γ(ρ). The numerical example in Mammarella et al. (2020) illustrates how to choose ρ. Indeed, in that paper we demonstrate the efficacy of the proposed approach by means of a simple numerical example where the effects of the penalty factor on the controller are shown, providing a method to the users to select the best value of the penalty factor according to the application needs. 11276 Martina Mammarella et al. / IFAC PapersOnLine 53-2 (2020) 11271–11276 7. CONCLUSIONS A stochastic model predictive controller able to account for the effects of additive stochastic disturbances is presented in this paper. No restrictive assumptions on the random nature of disturbances are required. We use a sampling method to bound offline the effect of disturbances in a probabilistic manner. A penalty based formulation, which avoids infeasibility of the optimization problem defining the model predictive controller, is proposed. The novel control scheme meets some given probabilistic closedloop specifications. The required sample complexity has a logarithmic dependence with respect to the prediction horizon. REFERENCES Ahsanullah, M., Nevzorov, V., and Shakil, M. (2013). An introduction to Order Statistics. Atlantis Press, Paris. Alamo, T., Manzano, J., and Camacho, E. (2018). Robust design through probabilistic maximization. In T. Basar (ed.), Uncertainty in Complex Networked Systems. In Honor of Roberto Tempo, 247–274. Birkh¨auser. Alamo, T., Tempo, R., Luque, A., and Ramirez, D. (2015). Randomized methods for design of uncertain systems: sample complexity and sequential algorithms. Automatica, 52, 160–172. Alamo, T., Mirasierra, V., Dabbene, F., and Lorenzen, M. (2019). Safe approximations of chance constrained sets by probabilistic scaling. In 2019 18th European Control Conference (ECC), 1380–1385. IEEE. Arnold, B., Balakrishnan, N., and Nagaraja, H. (1992). A First Course in Order Statistics. John Wiley and Sons, New York. Calafiore, G.C. and Fagiano, L. (2013). Stochastic model predictive control of LPV systems via scenario optimization. Automatica, 49(6), 1861–1866. Campo, P.J. and Morari, M. (1987). Robust model predictive control. In Proc. of the American Control Conference, 1021–1026. Farina, M. and Scattolini, R. (2016). Model predictive control of linear systems with multiplicative unbounded uncertainty and chance constraints. Automatica, 70, 258 – 265. Fleming, J. and Cannon, M. (2019). Stochastic MPC for additive and multiplicative uncertainty using sample approximations. IEEE Transactions on Automatic Control, 64(9), 3883–3888. doi:10.1109/TAC.2018.2887054. Hewing, L. and Zeilinger, M.N. (2018). Stochastic model predictive control for linear systems using probabilistic reachable sets. In 2018 IEEE Conference on Decision and Control (CDC), 5182–5188. Karg, B., Alamo, T., and Lucia, S. (2019). Probabilistic performance validation of deep learning-based robust NMPC controllers. arXiv preprint arXiv:1910.13906. Kerrigan, E.C. and Maciejowski, J.M. (2000). Soft constraints and exact penalty functions in model predictive control. In Proceedings of UKACC International Conference on Control. Limon, D., Alamo, T., Salas, F., and Camacho, E.F. (2006). On the stability of constrained MPC without terminal constraint. IEEE transactions on automatic control, 51(5), 832–836. Limon, D., Alvarado, I., Alamo, T., and Camacho, E.F. (2008). Mpc for tracking piecewise constant references for constrained linear systems. Automatica, 44(9), 2382– 2387. Lorenzen, M., Dabbene, F., Tempo, R., and Allg¨ower, F. (2017). Stochastic MPC with offline uncertainty sampling. Automatica, 81, 176–183. Lorenzen, M., Dabbene, F., Tempo, R., and Allg¨ower, F. (2016). Constraint-tightening and stability in stochastic model predictive control. IEEE Transactions on Automatic Control, 62(7), 3165–3177. Mammarella, M., Lorenzen, M., Capello, E., Park, H., Dabbene, F., Guglieri, G., Romano, M., and Allg¨ower, F. (2018). An offline-sampling SMPC framework with application to autonomous space maneuvers. IEEE Transactions on Control Systems Technology, 1–15. Mammarella, M., Alamo, T., Lucia, S., and Dabbene, F. (2020). A probabilistic validation approach for penalty function design in stochastic model predictive control. arXiv preprint arXiv:2003.07241v1. Margellos, K., Goulart, P., and Lygeros, J. (2014). On the road between robust optimization and the scenario approach for chance constrained optimization problems. IEEE Transactions on Automatic Control, 59(8), 2258– 2263. Mattingley, J. and Boyd, S. (2012). CVXGEN: A code generator for embedded convex optimization. Optimization and Engineering, 13(1), 1–27. Mayne, D.Q., Rawlings, J.B., Rao, C.V., and Scokaert, P.O. (2000). Constrained model predictive control: Stability and optimality. Automatica, 36(6), 789–814. Mayne, D. and Rawlings, J. (2009). Model Predictive Control: Theory and Design. Nob Hill Publishing. Mesbah, A. (2016). Stochastic model predictive control: An overview and perspectives for future research. IEEE Control Systems Magazine, 36(6), 30–44. Prandini, M., Garatti, S., and Lygeros, J. (2012). A randomized approach to stochastic model predictive control. In 2012 IEEE 51st IEEE Conference on Decision and Control (CDC), 7315–7320. Schildbach, G., Fagiano, L., Frei, C., and Morari, M. (2014). The scenario approach for stochastic model predictive control with bounds on closed-loop constraint violations. Automatica, 50(12), 3009–3018. Stellato, B., Banjac, G., Goulart, P., Bemporad, A., and Boyd, S. (2018). OSQP: An operator splitting solver for quadratic programs. In 2018 UKACC 12th International Conference on Control (CONTROL), 339–339. IEEE. Tempo, R., Bai, E., and Dabbene, F. (1997). Probabilistic robustness analysis: explicit bounds for the minimum number of samples. Systems & Control Letters, 30, 237– 242.