Model Predictive Control with Reach-avoid Analysis

1 Introduction

Control synthesis is a fundamental problem which automatically constructs a control strategy that induces a system to exhibit a desired behavior. Due to the ability of handling control and state constraints and yielding high performance control systems [Camacho and Alba, 2013], control design methods based on MPC have gained great popularity and found wide acceptance in industrial applications, ranging from autonomous driving [Verschueren et al., 2014; Kabzan et al., 2019] to large scale interconnected power systems [Ernst et al., 2008; Mohamed et al., 2011].

In MPC design methods one issue is to guarantee feasibility of the successive optimization problems [Scokaert and Rawlings, 1999]. Because MPC is 'greedy' in its nature, i.e., it only searches for the optimal strategy within a finite horizon, an MPC controller may steer the state to a region starting from where the violation of hard state constraints cannot be avoided. Although this feasibility issue could be solved by using a sufficiently long prediction horizon, we may not be able to afford the computation overhead due to the limited computational resources. Consequently, several solutions towards the feasibility issue are proposed [Zheng and Morari, 1995; Zeng et al., 2021; Ma et al., 2021]. Besides the feasibility issue of satisfying all hard state constraints [Zheng and Morari, 1995; Zeng et al., 2021; Ma et al., 2021], a system is also desired to achieve certain performance objective in an optimal sense. In existing literature, stability performance of approaching an equilibrium within the MPC framework is extensively studied. One common solution of achieving stability is adding Lyapunov functions as terminal costs and/or corresponding invariant sets as terminal sets [Michalska and Mayne, 1993; Limon et al., 2005; Lim´on et al., 2006; Mhaskar et al., 2006; de la Pe˜na and Christofides, 2008; Wu et al., 2019; Grandia et al., 2020]. This has motivated significant research work on applications of this control design to nonlinear processes [Yao and Shekhar, 2021]. However, in many real applications stability performance is demanding. For example, a spacecraft rendezvous may require the chaser vehicle to be at a certain position relative to the target, moving towards it with a certain velocity. All of these quantities are specified with some tolerance, forming a target region in the state space. When the chaser enters that region a physical connection would be made and the maneuver is complete. However, since the target velocity is non-zero, the region is not invariant and stability cannot be achieved. Regarding this practical issue, the formulation in this paper replaces the notion of stability with reachability: given a target set, the system will achieve the reachability objective of reaching the target set in finite time successfully. To the best of our knowledge, the learning model predictive control (LMPC) proposed in [Rosolia and Borrelli, 2017], which utilizes the historical data to improve suboptimal controllers iteratively, is the only method within the MPC framework which can solve this problem. However, it leads to mixed-integer nonlinear programming problems which are fundamentally challenging to solve.

∗Corresponding author

In this work, we consider control tasks where the goal is to steer the system from a starting configuration to a target set in finite time, while satisfying state and input constraints. The control task is formalized as a reach-avoid optimization problem. For solving the optimization problem, we propose a novel learning based MPC algorithm which fuses iterative learning control (ILC) [Arimoto et al., 1984] and reachavoid analysis in [Zhao et al., 2022]. The proposed algorithm utilizes MPC to iteratively improve upon a suboptimal controller. Based on a suboptimal controller obtained in the previous iteration, the reach-avoid analysis is to compute a set of initial states such that the closed-loop system can reach the target set without a violation of the state and input constraints. In our algorithm, the reach-avoid analysis not only provides terminal constraints which ensure feasibility of the MPC, but also expands the viability space of the system and thus facilitates exploring better trajectories with lower costs. Finally, several examples demonstrate the benefits of our algorithm over state-of-the-art ones.

The closest work to the present one is [Rosolia and Borrelli, 2017]. Due to the use of a set of discrete states visited by previous (sub-)optimized trajectories, computationally expensive mixed-integer nonlinear programming problems have to be addressed online in the proposed LMPC, limiting its application in practice. Our method is inspired by [Rosolia and Borrelli, 2017]. However, it incorporates the recently developed reach-avoid analysis technique and expands discrete states into a continuous (reach-avoid) set, which not only facilitates exploring better trajectories but also leads to a novel MPC formulation which involves solving more computationally tractable nonlinear programming problems online. Besides, this work is also close to the ones on model-based safe reinforcement learning, such as [Thomas et al., 2021; Luo and Ma, 2021; Wen and Topcu, 2018]. However, these studies prioritize enforcing the safety objective rather than achieving a joint objective of safety and reachability.

This paper is structured as follows. In Section 2 the reachavoid problem of interest is introduced. Then, we detail our algorithm for solving the reach-avoid problem in Section 3, and evaluate it on several examples in Section 4. Finally, we conclude this paper in Section 5.

2 Preliminaries

In this section we introduce the reach-avoid optimization problem of interest. Throughout this paper, Rn and N denote the set of n-dimensional real vectors and non-negative integers, respectively. R[·] denotes the ring of polynomials in variables given by the argument. ∑[x] represents the set of sum-of-squares polynomials over variable x, i.e., ∑[x] = {p ∈ R[x] | p = ∑ki=1 q2 i , qi ∈ R[x], i = 1, 2, . . . , k}.

2.1 Problem Statement

Consider a discrete-time dynamical system

where f(·) : Rn ×Rm → Rn is the system dynamics, x(·) : N → Rn is the state and u(·) : N → U ⊆ Rm is the control.

Definition 1. A control policy is a sequence of control inputs π = {u(i)}i∈N, where u(i) : N → U. Furthermore, we define Π as the set of all control policies.

Given a safe set X = {x ∈ Rn | w(x) ≤ 0} and a target set T = {x ∈ Rn | g(x) ≤ 0} with T ⊆ X, a control policy

π ∈ Π is safe with respect to a state x0, if the control policy π will drive system (1) starting from x(0) = x0 to reach the target set T in finite time while staying inside the safe set X before the first target hitting time. The associated cost of reaching the target set T safely is defined below.

Definition 2. Given a state x(0) = x0 ∈ X \ T , and a safe policy π = {u(i)}i∈N ∈ Π, the cost with respect to the state x0 and the policy π is defined below:

where x(k + 1) = f(x(k), u(k)), L = min{i ∈ N | x(i) ∈ T }, and h(·, ·) is continuous and satisfies

In this paper, we would like to synthesize a safe control policy π ∈ Π with respect to a specified initial state x0 such that system (1) will enter the target set T with the minimal cost in finite time while staying inside the safe set X before the first target hitting time.

Problem 1. We attempt to solve the following reach-avoid optimization problem:

where T is the first time of hitting the target set T .

Due to uncertainties on the target hitting time, it is challenging to solve optimization (4) directly. However, the computational complexity can be reduced when searching for a feasible sub-optimal solution. In this paper we will adopt a learning strategy to solving (4), which iteratively improves upon already known suboptimal policies as the LMPC algorithm in [Rosolia and Borrelli, 2017]. Consequently, an initial feasible policy is needed, as formulated in Assumption 1.

Assumption 1. Assume an initial policy π0 = {u0 (i)}i∈N, which can drive system (1) starting from x0 to the target set T in finite time safely, is available. The corresponding trajectory of system (1) can be obtained and is denoted by {x0 (i)}0≤i≤L0 , where,

Remark 1. The availability of a feasible control policy is not restrictive in practice for a number of applications. For instance, with race cars one can always run a path at very low speed to obtain a control policy.

2.2 Guidance-barrier Functions

In this subsection we introduce guidance-barrier functions. They not only provide terminal constraints in our MPC method escorting system (1) to the target set T safely, but also generate a set which curves out a viability space for system (1) to reach the target set T safely.

Definition 3. Given the safe set X, target set T and a factor λ ∈ (1, ∞), a bounded function v(x) : Y → R is a guidancebarrier function of system (1) with the feedback controller ˆu(·) : X →U, if it satisfies the following constraints:

where Y = {y | y = f(x, u), u ∈ U, x ∈ X} ∪ X , and M is a user-defined positive number.

When f(x, ˆu(x)) is polynomial over x, and X is semialgebraic set, i.e., f(x, ˆu(x)),w(x) ∈ R[x], a set Y of the form {x | w0(x) ≤ 0} with w0(x) ∈ R[x] can be obtained using program (3) in [Zhao et al., 2022].

Remark 2. It is worth remarking here that if (5) holds, for system (1) with ˆu(·) : X → U, the induced trajectory starting from x0 will hit the target set T within a bounded amount of time being less than or equal to logλ M v(x0) (It can obtained according to λT v(x0) ≤ v(x(T)) ≤ M, where T is the first hitting time of T .).

A reach-avoid set R = {x ∈ X | v(x) > 0} can be computed via solving constraint (5), which is a set of states such that there exists a control policy π ∈ Π driving system (1) to enter the target set T in finite time while staying inside the safe set X before the first target hitting time.

Theorem 1. Given the safe set X, target set T and a factor λ ∈ (1,∞), if v(x) : Y → R is a guidance-barrier function of system (1) with the feedback controller ˆu(·) : X → U, then R = {x ∈ X | v(x) > 0} is a reach-avoid set.

Theorem 1 can be assured by Corollary 1 in [Zhao et al., 2022]. Due to space limitations, we omitted the proof herein.

Remark 3. One of admissible control policies π ∈ Π such that system (1) satisfies the reach-avoid specification can be constructed by the feedback controller ˆu(·) : X → U: when system (1) is in state x(i) ∈ R, the corresponding control action is u(i) = ˆu(x(i)). We denote such a control policy by πˆu in the rest of this paper.

3 Reach-avoidModel Predictive Control

In this section we elucidate our learning-based algorithm for solving optimization (4) in Problem 1, which is built upon a so-called reach-avoid model predictive control (RAMPC). The proposed RAMPC is constructed based on a guidancebarrier function.

Our RAMPC algorithm is iterative and at each iteration it mainly consists of three steps. The first step is to synthesize a feedback controller by interpolating the suboptimal state-control pair obtained in the previous iteration. Then, a guidance-barrier function satisfying (5) with the synthesized feedback controller is computed. Finally, based on the computed guidance-barrier function a MPC controller, together with its resulting state trajectory, is generated online. The framework of the algorithm is summarized in Alg. 1.

For solving (5) in Alg. 1, when f(x, ˆu(x)) is polynomial over x, and Y, X and T are semi-algebraic sets, i.e., Algorithm 1 The framework for solving optimization (4).

Require: system (1); initial state x0; safe set X; target set T ; control input set U; feasible state-control trajectory {(x0 (i), u0 (i))}L0-1 i=0 , of which the cost is J 0 (x0) = ∑L0-1 i=0 h(x0 (i), u0 (i)); factor λ and bound M in (5); maximum iteration number K; prediction horizon N in RAMPC; termination threshold ξ > 0.

Ensure: Return J ∗ (x0).

• for j = 0 : K do 1 apply interpolation techniques to compute a feedback controller ˆuj (·) : X → U based on the j-th state-control trajectory {(xj (i), uj (i))}Lj -1 i=0 ; 2 compute vj (x) via solving (5) with ˆu(x) = ˆuj (x); 3 solve RAMPC optimization, which is constructed with vj (x), to obtain a state-control pair {(xj+1 (i), uj+1 (i))}Lj+1-1 i=0 and the cost J j+1 (x0): if J j+1 (x0) - J j (x0) ≥ -ξ then Return J ∗ (x0) = J j+1 (x0); end if end for

f(x, ˆu(x)),w0(x),w(x), g(x) ∈ R[x], the problem of solving constraint (5) can be transformed into a semi-definite programming problem (6),



(6)

Otherwise, sample-based approaches in the context of randomized algorithms [Tempo et al., 2013] for robust convex optimization can be employed to solve constraint (5). The basis of these approaches is the Almost Lyapunov condition [Liu et al., 2020], which allow the Lyapunov conditions to be violated in restricted subsets of the space while still ensuring stability properties. Although results from these approaches lack rigorous guarantees, nice empirical performances demonstrated the practicality of these approaches in existing literature (e.g., [Chang and Gao, 2021]). We will revisit it in our future work.

Remark 4. In Alg. 1, the computations in the first two steps, i.e., synthesizing feedback controllers and solving (5), can be carried out offline. Online computations occur only in the third step, which generate MPC controllers.

In the following subsection we will introduce the RAMPC optimization in Alg. 1.

3.1 Reach-avoidModel Predictive Control

This subsection introduces the RAMPC optimization in Alg. 1, which involves solving the MPC optimization problem online :

where the superscript j is the iteration index, xjk|t is the state predicted k time steps ahead, computed at time t, initialized at xj0|t = xjt with xj0 = x0, and similarly for ujk|t , and Qj (xjN|t ) = ∑L-1 i=0 h(xji+N|t , ˆuj-1 (xji+N|t )) is the cost with respect to the state xjN|t and the control policy πˆuj-1 .

In (7), the terminal constraint

guarantees that the terminal state xjN|t lies in the reach-avoid set Rj-1 = {x ∈ X | vj-1 (x) > 0}, which carves out a larger continuous viability space (visualized as the cyan region in Fig. 1) for system (1) to be capable of achieving the reach-avoid objective. This is different from the LMCP method in [Rosolia and Borrelli, 2017], which restricts terminal states within previously explored discrete states (visualized as pink points in Fig. 1) and thus leads to computationally demanding mixed-integer nonlinear optimization. As to the practical computations of the cost Qj (·, πˆuj-1 ) : Rj-1 → R, we will give a detailed introduction in Subsection 3.2.

Let

be the optimal solution to (7) at time t and J RAMPC,j t→t+N (xjt ) the corresponding optimal cost. Then, at time t of the iteration j, the first element uj (t) = u∗,j 0|t of u∗,j 0:N|t is applied to the system (1) and thus the state of system (1) turns into

where xj (t) = x∗,j 0|t , which will be the used to update the initial state in (7) for subsequent computations. Once there exist t ∈ N and l ≤ N s.t. xjl|t ∈ T , we terminate computations in this iteration: from the state x∗,j 0|t on, we will apply the control actions {u∗,j i|t }l-1 i=0 successively to system (1).

Let πj = {uj (t)}0≤t≤Lj -1 be the control policy applied to system (1) by solving optimization (7). The resulting state-control pair {xj (i), uj (i)}0≤i≤Lj -1, where xj (Lj ) ∈ T , is obtained. We can conclude that the performance of πj is no worse than that of πj-1 , i.e., J j-1 (x0) = ∑Lj-1-1 i=0 h(xj-1 (i), uj-1 (i)) ≥ ∑Lj -1 i=0 h(xj (i), uj (i)) = J j (x0). This conclusion can be justified by Theorem 3.

Under Assumption 2, we in Theorem 2 show that the RAMPC (7) is feasible and system (1) with controllers computed by solving (7) satisfies the reach-avoid property, and in Theorem 3 show that the j-th iteration cost J j (x0) is nonincreasing as j increases in RAMPC (7). Their proofs can be found in the appendix of the extended version [Ren et al., 2023].

Assumption 2. At each iteration 0 ≤ j ≤ K the computed reach-avoid set Rj = {x ∈ X | vj (x) > 0} via solving (5) is non-empty. In addition, we assume that it includes the state trajectory {xj (i)}Lj -1 i=0 1 .

Theorem 2. For each iteration j ≤ K, the RAMPC (7) is feasible for 1 ≤ t ≤ Lj - 1; also, system (1) with controllers obtained by solving RAMPC (7) can reach the target set T within the time interval [0, logλ Mv0 ] while satisfying all of state and input constraints.

Theorem 3. Consider system (1) with controllers obtained by solving (7). Then, the iteration cost J j (x0) is non-increasing with the iteration index j.

3.2 Estimating Terminal Costs via Scenario Optimization

In practice, the exact terminal cost Qj (·, πˆuj-1) : Rj-1 → R is challenging, even impossible to obtain. In this subsection, we present a linear programming method based on the scenario optimization [Calafiore and Campi, 2006] to compute an approximation of the terminal cost Qj (·, πˆuj-1 ) : Rj-1 → R in the probably approximately correct (PAC) sense.

Let {xi}N ′ i=1 be the independent samples extracted from Rj-1 = {x ∈ X | vj-1 (x) > 0} according to the uniform distribution P, and Qj (xi, πˆuj-1) be the corresponding cost of the roll-out from xi with the controller πˆuj-1. Such cost can be simply computed by summing up the cost along the closed-loop realized trajectory until the target set T is reached. Finally, using the set of sample states and correspding costs {(xi,Qj (xi, πˆuj-1))}N ′ i=1 , we approximate the terminal cost Qj (·, πˆuj-1) : Rj-1 → R using the scenario optimization [Calafiore and Campi, 2006].

A linearly parameterized model template Qja (c1, . . . , cl, x), k ≥ 1 is utilized, which is a linear function in unknown parameters c = (c1, . . . , cl) but can be nonlinear over x. Then we construct the following linear program over c based on the family of given datum

1 This assumption can be realized by interpolating the feedback controller ˆuj (·) : X → U s.t. ˆuj (xj (i)) = uj (i), i = 0, . . . , Lj - 1. This requirement mainly serves for our theoretical analysis since it can guarantee that our algorithm can iteratively improve the policy (Theorem 3). However, in practical this requirement is not indispensable regarding efficient computations.

where Uc ≥ 0 is a pre-specified upper bound for ci, i = 1, . . . , l.

Denote the optimal solution to (11) by (c∗ , δ∗ ). The discrepancy between Qja (c∗ , x) and Qj (x, πˆuj-1) is formally characterized by two parameters: the error probability ϵ ∈ (0, 1) and confidence level β ∈ (0, 1).

Theorem 4. Let (c∗ , δ∗ ) be an optimal solution to (11), ϵ ∈ (0, 1), β ∈ (0, 1) and

Then we have that with at least 1 - β confidence,

Thus, we relax optimization (4) into the following form:

where Qj-1 a (c∗ , xN|t) is the approximate terminal cost at the state xN|t, which is obtained via solving (11).

Proposition 1. With at least 1 - β confidence,

holds with the probability larger than or equal to 1 - ϵ, i.e.,

Relying on (12), we summarize our RAMPC algorithm for solving optimization (4) in Algorithm 2.

4 Examples

In this section we evaluate our RAMPC algorithm, i.e., Alg. 2, and make comparisons with the LMPC algorithm in [Rosolia and Borrelli, 2017] on several examples. All the experiments were run on MATLAB 2022b with CPU 12th Gen Intel(R) Core(TM) i9-12900K and RAM 64 GB. Constraint (5) is solved by encoding it into sum-of-squares constraints which is treated by the semi-definite programming solver MOSEK; the nonlinear programming (7) and the mixedinteger nonlinear programming in the LMPC algorithm in

Algorithm 2 The RAMPC algorithm for solving (4).

Require: system (1) with an initial state x0, a safe set X, a target set T a control input set U and a feasible statecontrol trajectory {(x0 (i), u0 (i))}L0-1 i=0 , of which the corresponding cost is J 0 (x0) = ∑L0-1 i=0 h(x0 (i), u0 (i)); factor λ and bound M in (5); iteration number K, prediction horizon N and termination threshold ξ > 0; probability error ϵ and confidence level δ in PAC approximations.

Ensure: Return J ∗ (x0).

for all j = 0 : K do

• 1 apply interpolation techniques to compute ˆuj (·) : X → U for the j-th state-control trajectory {(xji , uji )}L1-1 i=0 ;
• 2 obtain Rj = {x ∈ X | vj (x) > 0} via solving (5) with ˆu(x) = ˆuj (x);
• 3 compute the PAC terminal cost Qja (·) : Rj → R via solving optimization (11);
• 4 SolvingMPCoptimization (12) with vj to obtain a statecontrol pair {(xj+1 (i), uj+1 (i))}Lj+1-1 i=0 and the cost J j+1 (x0):

end if end for

[Rosolia and Borrelli, 2017] are solved using YALMIP [Lofberg, 2004]. In addition, we take ˆuj (·) as a linear function to interpolate the j-th state-control trajectory {(xji , uji )}Lj -1 i=0 at each iteration j ≥ 1. The configuration parameters in Alg. 2 for all examples are shown in Table 1.

Example 1. Consider the drone system from [Rosolia and Borrelli, 2017],

where xt = (pt, vt)⊤, pt and vt are respectively the position and velocity of the drone at time t, ut is the control input and dt is the control interval which is equal to 0.1.

We assume X = {(p, v)⊤ | p2 82 + v2 82 -1 ≤ 0}, initial state x0 = (4, -6)⊤, target set T = {(p, v)⊤ | p2 +v2 -0.52 ≤ 0} and control input set U = {u | -0.5 ≤ u ≤ 0.5}. The set Y = {(p, v)⊤ | p2 82 + v2 82 -2 ≤ 0} in constraint (5) is obtained by solving a semi-define program as in [Zhao et al., 2022]. The cost in optimization (4) is h (x, u) = ∥x∥22 + ∥u∥22 . For simplicity of presentation herein, we do not present the initial state-control trajectory which is a long sequence. The initial state-control trajectory is induced by the feedback controller ˆu0 (p, v) = -0.04p - 0.1v. For scenario optimization (11), we use a template of the polynomial form Qja (c, p, v) = c1 + c2p+c3v+c4pv+c5p2 +c6v2 and N ′ = 207 sampled points which can be computed via Theorem 4.

We compare our RAMPC algorithm with the LMPC one in [Rosolia and Borrelli, 2017] with the same prediction horizon and termination conditions (i.e., N and ξ). Since this system is linear, instead of using a set of explored discrete states, the terminal constraint in the LMPC algorithm can be constructed by its convex hull, thus resulting in non-linear programs instead of mixed-integer nonlinear programs as mentioned in [Rosolia and Borrelli, 2017]. The performances of trajectories (shown in Figure 2) generated by both are compared. The iteration costs and computation times at each iteration of RAMPC and LMPC are presented in Table 2. It is observed that the iteration costs in our algorithm drop more quickly than those in the LMPC one. Also, our RAMPC algorithm is more efficient than the LMPC one. RAMPC terminates after 2 iterations with the computation time of 6.3304s, but LMPC converges more slowly and has to take 5 iterations with the computation time of 8.2259s.

Example 2. Consider the Euler version with the time step ∆t = 0.05 of the controlled reversed-time Van der Pol oscillator in [Drazin and Drazin, 1992]:

initial state x0 = (1.2, 1)⊤, target set T = {(x1, x2)⊤ | x21+x22-0.22 ≤ 0} and input set U = {u | -0.5 ≤ u ≤ 0.5}.

In (5), the set Y = {(x1, x2)⊤ | ( x1 2 )2 + ( x2 2 )2 - 2 ≤ 0} is computed by solving a semi-define program in [Zhao et al., 2022]. In addition, the cost h(x, u) = ∥x∥22 + ∥u∥22 , where x = (x1, x2)⊤, is adopted. The initial trajectory is induced by the controller ˆu0 (x) ≡ 0. For scenario optimization (11), we use a template of the polynomial form Qja (c, x) = c1 + c2x1 + c3x2 + c4x1x2 + c5x21 + c6x22 and N ′ = 428 samples which can be computed via Theorem 4. LMPC uses the same prediction horizon and termination conditions (i.e., N and ξ).

Some trajectories generated by our RAMPC algorithm and the LMPC algorithm are visualized in Figure 3. Our RAMPC algorithm terminates after the third iteration, but the LMPC one does not terminate after eight iterations. Figure 3 shows that the initial trajectory and the trajectory generated by the first iteration in the LMPC algorithm are too close to be indistinguishable within the first few time steps, which on the other hand further reflects that the controller generated in the first iteration of the LMPC algorithm may not improve the performance induced by the initial control policy. Besides, it is observed that the eighth trajectory from the LMPC algorithm looks not stable and has strong oscillations, which are not expected in practice. In contrast, the trajectory generated by our algorithm is smoother.

Table 3 summarizes the iteration costs and the computation times at each iteration of our RAMPC algorithm and the LMPC one. The iteration cost induced by the initial trajectory is 64.3087, after three iterations our RAMPC algorithm reduces the cost to 29.2824 with the computation time of 31.2841s. In contrast, the LMPC algorithm needs more than 8 iterations with the computation time of almost more than 3 hours to achieve the same cost. This striking contrast definitely demonstrates that our RAMPC algorithm can solve optimization (4) more efficiently for some cases.

Example 3. Consider the Euler version with the time step ∆t = 0.1 of the controlled 3D Van der Pol oscillator from

[Korda et al., 2014]:

with the safe set X = {(x1, x2, x3)⊤ | x21 + x22 + x23 - 0.52 ≤ 0}, initial state x0 = (0.2, 0.4, 0.1)⊤, target set T = {(x1, x2, x3)⊤ | x21 + x22 + x23 - 0.12 ≤ 0} and input set U = {u | -2 ≤ u ≤ 2}.

The set Y = {(x1, x2, x3)⊤ | x21 + x22 + x23 - 0.5 ≤ 0} is utilized in (5) by solving a semi-define program, as described in [Zhao et al., 2022]. We use the cost function h(x, u) = ∥x∥22 + ∥u∥22 in this example, where x = (x1, x2, x3)⊤. The initial trajectory is generated by the controller ˆu0 (x) ≡ 0. The template of the polynomial form Qja (c, x) = c1 +c2x1 + c3x2+c4x3+c5x1x2+c6x1x3+c7x2x3+c8x21+c9x22+c10x23 and sample number N ′ = 267 computed through Theorem 4 are adopted for scenario optimization (11). The prediction horizon N and termination condition ξ are same for LMPC.

In this example, LMPC is unable to achieve the desired task of reducing the iteration cost and generating a suitable controller. In contrast, our RAMPC algorithm demonstrates good performance and can generate an effective controller. Table 4 summarizes the iteration costs and computation times at each iteration of our RAMPC algorithm. The initial trajectory and ones generated in the first and last iterations of our RAMPC algorithm are visualized in Figure 4.

Discussions on configuration parameters. Here we give a brief discussion on the configuration parameters:

λ,M,K, ξ,N, δ, ϵ based on the experiments (some are presented in the appendix of the extended version [Ren et al., 2023]). The less conservative the computed reach-avoid set in each iteration is, the smaller the iteration cost is. Therefore, λ is recommended to be as close to one as possible, but it cannot be one. For details, please refer to [Zhao et al., 2022]; the upper bound M can be any positive number since if v(x) satisfies constraint (5) with M = M ′ , then v(x) M′ also satisfies constraint (5) with M = 1; K and ξ, especially ξ, affect the number of iterations and thus the quality of controllers. Generally, a larger K and/or smaller ξ will improve the control performance, but the computational burden increases; the approximation error for terminal costs is formally characterized in the PAC sense using ϵ and δ. These two parameters and the size of parameters c determine the minimal number of samples for approximating terminal costs according to Theorem 4. Smaller ϵ and δ will lead to more accurate approximations of terminal costs in the PAC sense. However, regarding the overfitting issue and the computational burden of solving (11), too small ϵ and δ are not desired in practice; the prediction horizon N controls how far into the future the MPC predicts the system response. Like other MPC schemes, a longer horizon generally increases the control performance, but requires an increasingly powerful computing platform (due to solving (7) online), excluding certain control applications. In practice, an appropriate choice strongly depends on computational resources and real-time requirements. In addition, it is worth remarking here that the costs obtained by RAMPC are not sensitive to N for some cases. For details, please refer to experimental results in the appendix of the extended version [Ren et al., 2023].

5 Conclusion

In this paper we proposed a novel RAMPC algorithm for solving a reach-avoid optimization problem. The RAMPC algorithm is built upon MPC and reach-avoid analysis. Rather than solving computationally intractable mixed-integer nonlinear optimization online, it addresses computationally more tractable nonlinear optimization. Moreover, due to the incorporation of reach-avoid analysis, which expands the viability space, the RAMPC algorithm can provide better controllers with a smaller number of iterations. Several numerical examples demonstrated the advantages of our RAMPC algorithm.

Acknowledgments

This research was supported by the NSFC under grant No. 61836005, CAS Project for Young Scientists in Basic Research under grant No. YSBR-040, NSFC under grant No. 52272329, and CAS Pioneer Hundred Talents Program.