Computationally efficient stochastic MPC: A probabilistic scaling approach

Computationally efficient stochastic MPC: a probabilistic scaling approach Martina Mammarella1, Teodoro Alamo2, Fabrizio Dabbene1, and Matthias Lorenzen3 Abstract— In recent years, the increasing interest in Stochastic model predictive control (SMPC) schemes has highlighted the limitation arising from their inherent computational demand, which has restricted their applicability to slow-dynamics and high-performing systems. To reduce the computational burden, in this paper we extend the probabilistic scaling approach to obtain low-complexity inner approximation of chance-constrained sets. This approach provides probabilistic guarantees at a lower computational cost than other schemes for which the sample complexity depends on the design space dimension. To design candidate simple approximating sets, which approximate the shape of the probabilistic set, we introduce two possibilities: i) fixed-complexity polytopes, and ii) `p-norm based sets. Once the candidate approximating set is obtained, it is scaled around its center so to enforce the expected probabilistic guarantees. The resulting scaled set is then exploited to enforce constraints in the classical SMPC framework. The computational gain obtained with the proposed approach with respect to the scenario one is demonstrated via simulations, where the objective is the control of a fixed-wing UAV performing a monitoring mission over a sloped vineyard. I. INTRODUCTION In recent years, the performance degradation of model predictive control (MPC) schemes in the presence of uncertainty has driven the interest towards stochastic MPC, to overcome the inherent conservativeness of robust approaches. A probabilistic description of the disturbance or uncertainty allows to optimize the average performance or appropriate risk measures. Furthermore, allowing a (small) probability of constraint violation, by introducing so-called chance constraints, seems more appropriate in some applications. As highlighted in [1], current SMPC methods can be divided in two main groups, depending on the approach followed to solve the chance-constrained optimization problem: (i) analytic approximation methods; and (ii) randomized [2] and scenario-based methods. For the analytic approximation methods, the probabilistic properties of the uncertainty are exploited to reformulate the chance constraints in a deterministic form. For the second class of methods, the craved ∗This work was funded by the Italian Institute of Technology (IIT) and the Italian Ministry of Education, University and Research (MIUR) within the 2017 Projects of National Interest (PRIN 2017 N. 2017S559BB). Corresponding author: [email protected].it (Dabbene F.) 1Institute of Electronics, Computer and Telecommunication Engineering, National Research Council of Italy, Turin, Italy, [email protected], [email protected] 2Departamento de Ingenier´ ıa de Sistemas y Automtica, Universidad de Sevilla, Escuela Superior de Ingenieros, Camino de los Descubrimientos s/n, 41092 Sevilla, Spain, [email protected] [email protected] control performance and constraint satisfaction are guaranteed properly generating a sufficient number of uncertainty realizations and on the solution of a suitable constrained optimization problem, as proposed in [3], [4]. The main advantage of this class of stochastic MPC algorithms is given by the inherent flexibility to be applied to (almost) every class of systems, including any type of uncertainty and both state and input constraints, as long as the optimization problem is convex. On the other hand, they share two main drawback: i) slowness, which has limited their application to problems involving slow dynamics and where the sample time is measured in tens of seconds or minutes; and ii) a significant computational burden required for real-time implementation, narrowing the application domains to those involving low-computation assets. Some examples are [5] for water networks, [6] for river flood control, [7] for chemical processes, and [8] for energy plants. An efficient solution to the aforementioned disadvantages was proposed in [9] where the SMPC controllers design is based on an offline sampling approach and only a predefined number of necessary samples are kept for online implementation. In this approach, the sample complexity is linearly dependent to the design space dimension and the sampling procedure allows to obtain offline an inner approximation of the chance-constrained set. This approach has been extended to a more generic setup in [10] and experimentally validated for the control of a spacecraft during rendezvous maneuvers. Beside the efficacy of the approach, the results highlighted the need to further reduce the computational load and the slowness of the proposed approach to comply with faster dynamics and low-cost, low-performance hardware. Among challenging applications, the control of unmanned aerial vehicles (UAVs) during assorted scenarios, have been triggering the attention of MPC community. These platforms are typically characterized by fast dynamics and equipped with computationally-limited autopilots. In the last decade, different receding horizon techniques have been proposed, see e.g. [11], [12], [13], [14], including a stochastic approach by [15]. In this case, preliminary analysis have confirmed the effectiveness of the proposed offline sampling-based SMPC (OS-SMPC) strategy but the results highlighted also the need to further reduce the dimension of the optimization problem to comply with hardware requirements. The main contribution of this paper is to propose a new methodology that combines the probabilistic-scaling approach proposed in [16], which allows to obtain a lowcomplexity inner approximation of the chance constrained set, with the SMPC approach of [9], [10]. In [16], authors arXiv:2005.10572v1 [eess.SY] 21 May 2020 show how to scale a given set of manageable complexity around its center to obtain, with a user-defined probability, a region that is included in the chance constrained set. In this paper, we extend the aforementioned approach showing how it is possible to reduce the sample complexity via probabilistic scaling exploiting so-called simple approximating sets (SAS). The starting point consists in obtaining a first simple approximation of the “shape” of the probabilistic set. To design a candidate SAS, we propose two possibilities. The first one is based on the definition of an approximating set by drawing a fixed number of samples. On the other hand, the second case envisions the use of `p-norm based sets, first proposed in [17]. In particular, we consider as SAS a `1-norm cross-polytope and a `∞-norm hyper-cube. Solving a standard optimization problem, it is possible to obtain the center and the shape of the SAS, which will be later scaled to obtain the expected probabilistic guarantees following the approach described in [16]. Then, the scaled SAS is used in the classical SMPC algorithm to enforce constraints. To validate the proposed approach, an agriculture scenario has been selected, because of the increasing interest of using drones in the agriculture 4.0 framework, as explained in [18], due to their great potential to support and address some of the most pressing dares in farming. And real-time quality data and crop monitoring are two of those challenges. In particular, UAVs could represent a favorable alternative to conventional farming machines, whenever clear advantages with respect to traditional methods, in terms of higher efficiency in operations, reduced environmental impact or enhanced human health and safety are sought. For this paper, the control objective envisions the proposed approach applied to a fixed-wing UAV performing a monitoring mission over a sloped vineyard, following a pre-defined snake path. The performance of the proposed approach in terms of tracking capabilities and computational load has been compared with those obtained exploiting the “classical” OS-SMPC scheme proposed in [15]. 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]. Positive (semi)definite matrices Aare denoted A0 (A0) and kxk2 A . =xTAx. For vectors, x0(x0) is intended component-wise. Pradenotes the probabilistic distribution of a random variable a. Sequence of scalars/vectors are denoted with bold lower-case letters, i.e. v. II. OFFLINE SAMPLING-BASED STOCHASTIC MPC In this section, we first recall the Stochastic MPC Framework proposed in [9], [10]. A. Problem setup We consider the case of a discrete-time system subject to generic uncertainty wk∈Rnw xk+1 =A(wk)xk+B(wk)uk+aw(wk),(1) with state xk∈Rn, control input uk∈Rm, and the vector valued function aw(wk)represent the additive disturbance affecting the systems states. The system matrices A(wk)and B(wk), of appropriate dimensions, are (possibly nonlinear) functions of the uncertainty wkat step k. The disturbances (wk)k∈N≥0are modeled as realizations of the stochastic process (Wk)k∈N≥0, on which take the following assumptions. Assumption 1 (Random Disturbances): The disturbances Wk, for k∈N≥0, are independent and identically distributed (i.i.d.), zero-mean random variables with support W⊆ Rnw. Moreover, let G={(A(wk), B(wk), aw(wk)}wk∈W, a polytopic outer approximation with Ncvertexes ¯ G. = co Aj, Bj, aj wj∈NNc 1⊇Gexists and is known. We can notice that the system can be augmented by a filter to model a specific stochastic processes of interest. The assumption of independent random variables in necessary to perform the offline computations discussed next while the need of a known outer bound is required to establish a safe operating region (see [9] for details). We remark that the system’s representation in (1) is very general, and encompasses e.g. those in [9], [10], [19]. Given the model (1) and a realization of the state xkat time k, state predictions lsteps ahead are random variables, as well and are denoted xl|k, to differentiate it from the realization xl+k. Similarly ul|kdenotes predicted inputs that are computed based on the realization of the state xk. The system is subject to pstate and input chance constraints of the form1 Prw[Hx]T jxl|k+ [Hu]T jul|k≤1|xk≥1−εj, l∈N>0, j ∈Np 1,(2) with εj∈(0,1), and Hx∈Rp×n,Hu∈Rp×m, where [H]T j denotes the j-th row of matrix H. The probability Prwis measured with respect to the sequence w={wi}i>k. Hence, equation (2) states that the probability of violating the linear constraint [Hx]T jx+ [Hu]T ju≤1for any future realization of the disturbance should not be larger than εj. The objective is to derive an asymptotically stabilizing control law for the system (1) such that, in closed loop, the constraints (2) are satisfied. B. Stochastic Model Predictive Control To solve the constrained control problem, a stochastic MPC algorithm is considered. The approach is based on repeatedly solving a stochastic optimal control problem over a finite, moving horizon, but implementing only the first control action. Defined the control sequence as uk= (u0|k, u1|k, ..., uT−1|k), the prototype optimal control problem that is to be solved at each sampling time is given minimizing the cost function JT(xk,uk) = E(T−1 X l=0 x> l|kQxl|k+u> l|kRul|k+x> T|kPxT|k|xk)(3) 1The case where one wants to impose hard input constraints can be also be formulated in a similar framework, see e.g. [9]. with Q0,R0, and appropriately chosen P0, subject to the system dynamics (1) and constraints (2). The online solution of the stochastic MPC problem remains a challenging task but several special cases, which can be evaluated exactly, as well as methods to approximate the general solution have been proposed in the literature. The approach followed in this work was first proposed in [9], [10], where an offline sampling scheme was introduced. Therein, with a prestabilizing input parametrization ul|k=Kxl|k+vl|k,(4) with suitably chosen control gain K∈Rn×mand free optimization variables vl|k∈Rm, equation (1) is solved explicitly for the predicted states x1|k, . . . , xT|kand predicted inputs u0|k, . . . , uT−1|k. In this case, the expected value of the finite-horizon cost (3) can be evaluated offline, leading to a quadratic cost function of the form JT(xk,vk)=[xT kvT k1T n]˜ S  xk vk 1n (5) in the deterministic variables vk= (v0|k, v1|k, ..., vT−1|k) and xk. The reader can refer to [10, Appendix A] for a detailed derivation of the cost matrix ˜ S. Focusing now on the constraint definition, we can notice that by introducing the uncertainty sequence wk= {wl}l=k,...,k+T−1, we can rewrite the j-th chance constraint defined by equation (2) as Xj ε=xk vk∈Rn+mT | PrwkfT j(wk)xk vk≤1≥1−ε,(6) with fjbeing a function of the sequence of random variables wk. Again, the reader is referred to [10] for details on the derivation of fj. The results in [9] show that, by exploiting results from statistical learning theory (cf. [20], [21]), we can construct an inner approximation Xjof the constraint set Xj ε by extracting NLT i.i.d. samples w(i) kof wkand taking the intersection of the sampled constraints, i.e. Xj LT =xk vk∈Rn+mT | fT j(w(i) k)xk vk≤1, i = 1, . . . , NLT ,(7) In particular, it has been shown in [9], that for given probabilistic levels δ∈(0,1) and εj∈(0,0.14), choosing the sample complexity Nj LT ≥˜ N(n+mT, εj, δ) . =4.1 εln 21.64 δ+ 4.39(n+mT) log28e εj,(8) guarantees that with probability at least δthe sample approximation Xj LT is included in the original chance constraint Xj ε, i.e. Pr nXj LT ⊆Xj εo≥1−δ, j = 1, .., p. (9) Hence, exploiting these results, we obtain that the stochastic MPC problem can be well approximated by the following linearly constrained quadratic program min vk JT(xkvk)(10) s.t. (xk,vk)∈Xj LT , j = 1, .., p (11) While the result reduces the original stochastic optimization program to an efficiently solvable quadratic program, the ensuing number of constraints, equal to NLT = T X i=1 Nj LT , may still be too large. For instance, even for a moderately sized MPC problem with n= 5 states, m= 2 inputs and horizon of T= 10, and for a reasonable choice of probabilistic εj= 0.05,δ= 10−6, we get Nj LT = 20,604. For this reason, in [9] a post-processing analysis of the constraint set was proposed for removing redundant constraints. While it is indeed true that all the cumbersome computations may be performed offline, it is still the case that in applications with stringent requirements on the solution time the final number of inequalities may easily become unbearable. This observation motivates the approach presented in the next section, which builds upon the results presented in [16], showing how the probabilistic scaling approach leads to approximations of “controllable size,” that can be directly used in applications. III. COMPLEXITY REDUCTION VIA PROBABILISTIC SCALING In this section, we consider the very general problem of finding a decision variable vector ξ, restricted to a set Ξ⊆ Rnξ, subject puncertain linear inequalities. Formally, we consider uncertain inequalities of the form F(q)ξ≤g(q)(12) where F(q)∈Rp×nξand g(q)∈Rnpare continuous function of the uncertainty vector q∈Rnq. The uncertainty vector qis assumed to be of random nature, with given probability distribution Prqand (possibly unbounded) support Q. Hence, to each sample of qcorresponds a different set of linear inequalities. We aim at finding an approximation of the ε-chance-constraint set, defined as Xε . =nξ∈Ξ|Prq{F(q)ξ≤g(q)} ≥ 1−εo(13) that represents the region of the design space Ξfor which this probabilistic constraint is satisfied. Note that this captures exactly the SMPC setup discussed in the previous section. Indeed, the chance-constrained set in (6) is a special instance of (13), with ξ= [xT kvT k]Tand q=wk. The characterization of the chance constrained set has several application in robust and stochastic control. A classical approach is to find inner convex approximation of the probabilistic set Xε, obtained for instance by means of applications of Chebyshev-like inequalities, see e.g. [22] and Fig. 1. Example of chance-constraint set for ε= 0.05, for 2D scalar linear constraints of the form f(q)Tξ≤1, with f(q) = q1·q2∈R2,q1∈R uniformly distributed in the interval [0.5,1.5] and q2∈R2Gaussian with variance Σ. The set was obtained by evaluating the empirical probability via random sampling. [23]. A recent approach, which is the one applied in the previous section to the SMPC problem, is instead based on the derivation of probabilistic approximations of the chance constraints set Xεthrough sampling of the uncertainty. That is, we aim at constructing a set Xwhich is contained in Xε with high probability. Denote Fj(q)and gjthe j-th row of F(q)and j-th component of qrespectively. Consider the binary functions hj(ξ, q). =0if Fj(q)ξ≤gj(q) 1otherwise , j = 1, . . . , p. Now, if we define h(ξ, q). = p Y j=1 hj(ξ, q). we have that his an (1, p)-boolean function since it can be expressed as a function of pboolean functions, each of them involving a polynomial of degree 1. See e.g. [21, Definition 7] for a precise definition of this sort of boolean functions. Suppose that we draw Ni.i.d. samples q(i),i= 1, . . . , N. Then, we can consider the (empirical) region XNdefined as XN . ={ξ∈Rnξ:h(ξ, q(i)) = 0, i = 1, . . . , N }. It has been proved in [21, Theorem 8], that if ∈(0,0.14) and Nis chosen such that2 N≥4.1 ln 21.64 δ+ 4.39nξlog28ep  then XN⊆Xεwith a probability no smaller than 1−δ. We notice that XNis a convex set, which is a desirable property in an optimization framework. However, the number of required samples Nmight be prohibitive for a real-time application. To tackle this issue, in this paper we exploit an appealing alternative approach proposed in [16], and we specialize it to the problem at hand. This work proposes a probabilistic scaling approach to obtain, with given confidence, an inner approximation of the chance constrained 2Note the difference under the log2with respect to (8). set Xεavoiding the computational burden due to the sample complexity raising in other strategies. The main idea behind this approach consist in first obtaining a simple initial approximation of the “shape” of the probabilistic set Xεby exploiting simple approximating sets of the form xc⊕S. This set is not required to have any guarantees of probabilistic nature. Instead, to derive such probabilistic guaranteed set, a scaling procedure is devised. In particular, an optimal scaling factor γis derived so that the set scaled around its center xc S(γ). =xc⊕γS.(14) is guaranteed to be an inner approximation of Xεwith the desired confidence level δ. A. Simple Approximating Sets The idea at the basis of the proposed approach is to define Simple Approximating Sets (SAS), which represent specifically defined sets with a low – and pre-defined – number of constraints. First, we note that the most straightforward way to design a candidate SAS is to draw a fixed number NSof uncertainty samples, and to construct a sampled approximation as follows: 1. Sampled-poly SS= NS \ i=1 Xi(15) where Xi . =nξ∈Ξ|F(q(i))≤g(q(i)), i = 1, . . . , NSo(16) Clearly, if NS<< NLT , the probabilistic properties of SS before scaling will be very bad. However, at this point we do not care, since the probabilistic scaling proposed in Section III-B will take care of this. A second way to construct a SAS considered in this paper exploits a class of `p-norm based sets introduced in [17] as follows A(xc, P). ={ξ∈Rnξ|ξ=xc+Pz, z ∈ Bp},(17) where Bp⊂Rnξis the unit ball in the pnorm, xcis the center and P=PT0is the so-called shape matrix. In particular, we note that for p= 1,∞these sets take the form of polytopes with fixed number of facets/vertices. Hence, we introduce the following two SAS: 2. `1-poly S1={ξ∈Rnξ|ξ=xc+Pz, kzk1≤1},(18) defined starting from a cross-polytope, also known as diamond, of order nξwith 2nξvertices and 2nξfacets. 3. `∞-poly S∞={ξ∈Rnξ|ξ=xc+Pz, kzk∞≤1},(19) defined starting from a hyper-cube of dimension nξwith 2nξvertices and 2nξfacets. Hence, the problem becomes designing the center and shape parameters (xc, P)of the set S1(resp. S∞) so that they represent in the best possible way the set Xε. To this end, we start from a sampled design polytope D= ND \ i=1 Xi, with a fixed number of samples ND, and construct the largest set S1(resp. S∞) contained in D. It is easily observed that to obtain the largest `1-poly inscribed in D, we need to solve the following convex optimization problem max xc,C tr(P)(20) s.t. P0, fT iPz[j]≤gi−fT ixc i= 1, . . . , ND, z[j]∈ V1,(21) where V1={z[1], . . . , z[2nξ]}are the vertices of the unit cross-polytope while the vertices of the optimal `1-poly can then be obtained as ξ[j]=xc+Pz[j], j = 1,...,2nξ.(22) It should be remarked that, from these vertices, one could then recover the corresponding 2nξlinear inequalities, each one defining a facet of the rotated diamond. However, this procedure, besides being computationally extremely demanding (going from a vertex-description to a linear inequality description of a polytope is known to be NP hard, [24]), would lead to an exponential number of linear inequalities, thus rendering the whole approach not viable. Instead, we exploit the following equivalent formulation of (17), see e.g. [17] for details S1={ξ∈Rnξ| kMx −ck1≤1}(23) where M. =P−1and c. =P−1xc. From a computational viewpoint, this second approach results to be more appealing. Indeed, using a slack variable ζ, it is possible to obtain the following system of 3nξ+ 1 linear inequalities        mT iξ−ci≤ζi, i = 1, . . . , nξ −mT iξ+ci≤ζi, i = 1, . . . , nξ ζi≥0, i = 1, . . . , nξ Pnξ iζi≤1, The same convex optimization problem of (20) could be solved to define the center and the shape of the largest `∞- poly inscribed in D. However, this would involve an exponential number of vertices 2nξ. To avoid this, an approach based on Farkas lemma can be adopted, exploiting again a formulation in terms of linear inequalities. The details are not reported here due to space limitations. In this second case, obtained the center xcand the rotation matrix P, the corresponding H-poly has only 2nξhyper-planes, each one representing a different linear inequality. Once the initial SAS, SSand the `1and `∞-polys, i.e. S1 and S∞respectively, has been evaluated in terms of linear inequalities, the probabilistic scaling approach can be applied to determine the corresponding scaling factor γ. The scaling procedure is described in details in the paper [16]. For the sake of completeness, in the next subsection we recall its basic ideas and illustrate its application to the SAS case. B. SAS probabilistic scaling Given a candidate SAS set, the following simple algorithm can be used to guarantee with prescribed probability 1−δ that the scaled set S(γ)is a good inner approximation of Xε. Algorithm 1 Probabilistic SAS Scaling 1: Given probability levels εand δ, let Nγ≥7.67 εln 1 δand r=εNγ 2. 2: Draw Nγsamples of the uncertainty q(1), . . . , q(Nγ) 3: for i= 1 to Nγdo 4: Solve the optimization problem γi . = arg max γ(24) s.t. S(γ)⊆Xi 5: end for 6: Return the r-th smallest value of γi. A few comments are at hand regarding the algorithm above. In step 4, for each uncertainty sample q(i)one has to solve a convex optimization problem, which amounts at finding the largest value of γsuch that S(γ)is contained in the set Xidefined in (16). Then, in step 6, one has to reorder the set {γ1, γ2, . . . , γNγ}so that the first element is the smallest one, the second element is the second smallest one, and so on and so fort, and then return the r-th element of the reordered sequence. The following Lemma applies to Algorithm 1. Lemma 1: Given a candidate SAS set in the form S(γ) = xc⊕γS, assume that xc∈Xε. Then, Algorithm 1 guarantees that S(γ)⊆Xε with probability at least 1−δ. Proof to Lemma 1 is reported in Appendix. C. Illustrating Example To better illustrate the proposed approach, and to highlight its main features, we first consider a simple threedimensional examples (nξ= 3), with scalar uncertain linear inequalities of the form f(q)Tξ≤1 with f(q) = q1q2, with q1∈Runiformly distributed in the interval [0.5,1.5] and q2∈R3zero-mean Gaussian distribution. Note that, for nξ= 3, the `1and `∞-polys have Fig. 2. Visualization of the probabilistic scaling procedure for the 2D chance-constraint set considered in Figure III-B. The initial set (in red) was obtained by constructing the largest S1-poly enclosed in the set S. 10 and 6facets, respectively, irrespective to the number of design samples NDused to preliminary obtain the generic polyhedron D. However, as we will see, the number of constraints NDemployed to design the initial SAS plays a significant role in the final outcome of the procedure. To show this, we performed two different tests, where the number of design samples was set to ND= 100 and ND= 1,000. The results are shown in Figures 3 and 4 respectively, for both the `1(left) and `∞(right) cases. Algorithm 1 was applied in all cases with ε= 0.05 and δ= 10−6, leading to Nγ= 2,063 and r= 103. For allowing a better comparison, the same set of samples where considered for the evaluation of the scaling factor in all examples. These samples lead to Nγrandom hyper-planes which define a polyhedron represented (in black) in the figures. (a) γ1= 0.7183 (b) γ∞= 0.6527 Fig. 3. Scaled `1-poly (a) and `∞-poly (b) obtained starting from ND= 100. It can be observed that when NDis small, the ensuing initial `1- (resp. `∞-) poly is large, and Algorithm 1 returns a scaling factor γwhich is less than one (Fig. 3). Hence, the probabilistic scaling produces a ”deflation” of the original set so to guarantee the probabilistic constraints. Vice-versa, for large ND(Fig. 4), the scaling produces an inflation, returning a value of γlarger than one. Finally, we compared the `1- / `∞- polys with the naive approach based on sampled polytope SS. Notice that, to allow a fair comparison, we should select a number of hyperplanes comparable with the number of linear inequalities defining S1and S∞. In Fig. 5(a), we represent the initial (a) γ1= 1.1509 (b) γ∞= 1.1890 Fig. 4. Scaled `1-poly (a) and `∞-poly (b) obtained starting from ND= 1,000. and final polytopes. Then, we also generated two additional sampled-polys with NS= 100 and NS= 1,000, i.e. equal to the number of hyper-planes used to generate the design polyhedrons Dfor the previous case. These are depicted in (a) NS= 10,γS= 0.1754 (b) NS= 100,γS= 0.6918 (c) NS= 1000,γS= 0.9459 Fig. 5. Scaled sampled-polys obtained starting from NS= 10 (a), NS= 100 (b) and NS= 1,000 (c) and for Nγ= 2,063. Figs. 5(b)-5(c) while the volumes of the different SASs are reported in Table I. IV. UAV CONTROL OVER A SLOPED VINEYARD The selected application involves a fixed-wing UAV performing a monitoring mission over a Dolcetto vineyard at Carpeneto, Alessandria, Italy (44◦40055.600N,8◦37028.100E). The Mission Planner of ArduPilot open source autopilot has TABLE I VOLUME OF THE DIFFERENT SASS CONSIDERED IN EXAMPLE 1. SNSNDV S10 10 −0.0091 S100 100 −0.0403 S1000 1000 −0.0526 S1−100 0.0176 S1−1000 0.0258 S∞−100 0.0131 S∞−1000 0.0175 been used to identify a grid pattern with a peculiar path orientation with respect to the grapevine rows, as shown in Fig. 6. The main objective is to provide proper control Fig. 6. Carpeneto vineyard, Piedmont, Italy (credit: Google). capabilities to a fixed-wing UAV to guarantee a fixed relative altitude with respect to the terrain of 150 m while following the desired optimal path defined by the guidance algorithm (described in detail in [25]), maintaining a constant airspeed, i.e. Vref = 12 m/s. The controllability of the aircraft shall be guaranteed despite the presence of external disturbance due to a fixed-direction wind turbulence, which intensity can randomly vary among ±1m/s. For validation purpose, the longitudinal control of the UAV has been provided exploiting both OS-SMPC and the new PS-SMPC approach. In this case study, we have that the state variable are the longitudinal component of the total airspeed in body axes u, the angle of attack α, the pitch angle θ, the pitch rate q, and the altitude h. On the other hand, the control variables are represented by the throttle command ∆Tand the elevator deflection δe. Hence, we have n= 5 and m= 2 while the prediction horizon Thas been set equal to 15. Consequently, setting ε= 0.05,δ= 10−6, we get NLT = 20,604 and Nγ= 2,063. On the other hand, the sample complexity selected for generating the `1-poly has been set equal to ND= 100 obtaining (n+mT )·ND= 3,500 hyper-planes but only 3(n+mT) + 1 = 107 linear constraints implemented online. The preliminary results are represented in Fig. 7 as 3D trajectories and in Fig. 8 as controlled states with respect to reference signals. We can notice that both MPC schemes provide acceptable tracking capabilities, despite larger (but (a) OS-SMPC (b) PS-SMPC Fig. 7. UAV controlled trajectories obtained running OS-SMPC (a) and PS-SMPC (b) five times each. Fig. 8. Zoom-in on the behavior of controlled state variables, i.e. airspeed u, altitude hand roll angle φ, obtained exploiting OS-SMPC (blue lines) and PS-SMPC (red lines) with respect to corresponding reference signals (black lines), i.e. uref ,href and φref . still acceptable) oscillations can be observed in 7(b) when the scaled set is exploited. More interesting results are reported in Tab. II in terms of maximum and average values of the computational time required to solve online the finite-horizon optimal control problem, evaluated for 5different run each. The results show a significant reduction (about 100 times lower) of the computational load when a lower complexity constraint set is employed. This makes the stochastic MPC approach not only effective from a performance viewpoint but also presumably compliant with the computational constraint coming from autopilot hardware. V. CONCLUSIONS In this paper, we proposed a novel approach which exploits a probabilistic scaling technique recently proposed by some of the authors to derive a novel Stochastic MPC scheme. The TABLE II MAXIMUM AND AVERAGE COMPUTATIONAL COST REQUIRED BY OS-SMPC AND PS-SMPC APPROACHES FOR ONLINE SOLVING THE OPTIMIZATION PROBLEM DURING EACH RUN. n. tcMAXOS tcAV GOS tcMAXP S tcAV GP S 12.0959 0.4178 0.0966 0.0087 20.5394 0.3291 0.0215 0.0088 35.1215 0.4546 0.1065 0.0045 42.1497 0.5434 0.2628 0.0086 52.9411 0.5626 0.7221 0.0190 introduced framework exhibits a lower computational complexity, while sharing the appealing probabilistic guarantees of off-line sampling. APPENDIX The proof of to Lemma 1 follows from Proposition 1 in [16], which guarantees that, for given r≥0,Pr{S(γ)⊆Xε} is guaranteed if the scaling is performed on a number of samples such that N≥1 ε r−1 + ln 1 δ+r2(r−1) ln 1 δ!.(25) Since r=dεN 2e, we have that r−1≤εN 2. Thus, inequality (25) is satisfied if N≥1 ε εN 2+ ln 1 δ+rεN ln 1 δ! =N 2+1 εln 1 δ+rN1 εln 1 δ. Letting3∇. =√Nand α. =q1 εln 1 δ, the above inequality rewrites ∇2−2α∇−2α2≥0, which has unique positive solution ∇ ≥ (1+√3)α, which rewrites as N≥(1+√3)2 εln 1 δ. The formula in Algorithm 1 follows by observing that (1 + √3)2<7.67. REFERENCES [1] M. Farina, L. Giulioni, and R. Scattolini, “Stochastic linear model predictive control with chance constraints–a review,” Journal of Process Control, vol. 44, pp. 53–67, 2016. [2] R. Tempo, G. Calafiore, and F. Dabbene, Randomized algorithms for analysis and control of uncertain systems: with applications. Springer Science & Business Media, 2012. [3] G. C. Calafiore and M. C. Campi, “The scenario approach to robust control design,” IEEE Transactions on Automatic Control, vol. 51, no. 5, pp. 742–753, 2006. [4] G. Schildbach, L. Fagiano, C. Frei, and M. Morari, “The scenario approach for stochastic model predictive control with bounds on closed-loop constraint violations,” Automatica, vol. 50, no. 12, pp. 3009–3018, 2014. [5] J. M. Grosso, P. Velarde, C. Ocampo-Martinez, J. M. Maestre, and V. Puig, “Stochastic model predictive control approaches applied to drinking water networks,” Optimal Control Applications and Methods, vol. 38, no. 4, pp. 541–558, 2017. [6] H. A. Nasir, A. Car` e, and E. Weyer, “A randomised approach to flood control using value-at-risk,” in 2015 54th IEEE Conference on Decision and Control (CDC). IEEE, 2015, pp. 3939–3944. 3Note that both quantities under square root are positive. [7] D. Van Hessem and O. Bosgra, “Stochastic closed-loop model predictive control of continuous nonlinear chemical processes,” Journal of Process Control, vol. 16, no. 3, pp. 225–241, 2006. [8] R. M. Vignali, F. Borghesan, L. Piroddi, M. Strelec, and M. Prandini, “Energy management of a building cooling system with thermal storage: An approximate dynamic programming solution,” IEEE Transactions on Automation Science and Engineering, vol. 14, no. 2, pp. 619–633, 2017. [9] M. Lorenzen, F. Dabbene, R. Tempo, and F. Allg¨ ower, “Stochastic MPC with offline uncertainty sampling,” Automatica, vol. 81, no. 1, pp. 176–183, 2017. [10] M. Mammarella, M. Lorenzen, E. Capello, H. Park, F. Dabbene, G. Guglieri, M. Romano, and F. Allg¨ ower, “An offline-sampling SMPC framework with application to autonomous space maneuvers,” IEEE Transactions on Control Systems Technology, pp. 1–15, 2018. [11] M. Kamel, T. Stastny, K. Alexis, and R. Siegwart, “Model predictive control for trajectory tracking of unmanned aerial vehicles using robot operating system,” in Robot Operating System (ROS). Springer, 2017, pp. 3–39. [12] K. Alexis, C. Papachristos, R. Siegwart, and A. Tzes, “Robust model predictive flight control of unmanned rotorcrafts,” Journal of Intelligent & Robotic Systems, vol. 81, no. 3-4, pp. 443–469, 2016. [13] T. J. Stastny, A. Dash, and R. Siegwart, “Nonlinear mpc for fixed-wing UAV trajectory tracking: Implementation and flight experiments,” in AIAA Guidance, Navigation, and Control Conference, 2017, p. 1512. [14] N. Michel, S. Bertrand, G. Valmorbida, S. Olaru, and D. Dumur, “Design and parameter tuning of a robust model predictive controller for UAVs,” in 2017 20th IFAC World Congress, 2017. [15] M. Mammarella, E. Capello, F. Dabbene, and G. Guglieri, “Samplebased SMPC for tracking control of fixed-wing UAV,” IEEE Control Systems Letters, vol. 2, no. 4, pp. 611–616, 2018. [16] T. Alamo, V. Mirasierra, F. Dabbene, and M. Lorenzen, “Safe approximations of chance constrained sets by probabilistic scaling,” in 2019 18th European Control Conference (ECC). IEEE, 2019, pp. 1380–1385. [17] F. Dabbene, C. Lagoa, and P. Shcherbakov, “On the complexity of randomized approximations of nonconvex sets,” in 2010 IEEE International Symposium on Computer-Aided Control System Design. IEEE, 2010, pp. 1564–1569. [18] G. Sylvester, G. Rambaldi, D. Guerin, A. Wisniewski, N. Khan, J. Veale, and M. Xiao, “E-agriculture in action-drones for agriculture. food and agriculture organization of the united nations and international telecommunication union,” Bangkok: Food and Agriculture Organization of the United Nations and International Telecommunication Union. Retrieved July, vol. 19, 2018. [19] M. Lorenzen, F. Dabbene, R. Tempo, and F. Allg¨ ower, “Constrainttightening and stability in stochastic model predictive control,” IEEE Transactions on Automatic Control, vol. 62, no. 7, pp. 3165–3177, 2017. [20] M. Vidyasagar, Learning and Generalisation: with Applications to Neural Networks. Springer Science & Business Media, 2013. [21] T. Alamo, R. Tempo, and E. F. Camacho, “Randomized strategies for probabilistic solutions of uncertain feasibility and optimization problems,” IEEE Transactions on Automatic Control, vol. 54, no. 11, pp. 2545–2559, 2009. [22] S. Yan, P. Goulart, and M. Cannon, “Stochastic model predictive control with discounted probabilistic constraints,” in 2018 European Control Conference (ECC). IEEE, 2018, pp. 1003–1008. [23] L. Hewing and M. N. Zeilinger, “Stochastic model predictive control for linear systems using probabilistic reachable sets,” in 2018 IEEE Conference on Decision and Control (CDC), 2018, pp. 5182–5188. [24] V. Kaibel and M. E. Pfetsch, “Some algorithmic problems in polytope theory,” in Algebra, geometry and software systems. Springer, 2003, pp. 23–47. [25] M. Mammarella, G. Ristorto, E. Capello, N. Bloise, G. Guglieri, and F. Dabbene, “Waypoint tracking via tube-based robust model predictive control for crop monitoring with fixed-wing UAVs,” in 2019 IEEE International Workshop on Metrology for Agriculture and Forestry (MetroAgriFor). IEEE, 2019, pp. 19–24.