{'fraction_non_alphanumeric': 0.04675346998410038, 'fraction_numerical': 0.01435262773408964, 'mean_word_length': 3.986500964216842, 'pattern_counts': {'":': 1, '<': 0, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 15, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
A Safe Control Architecture Based on Robust Model Predictive Control for Autonomous Driving

This paper proposes a Robust Safe Control Architecture (RSCA) for safe-decision making. The system to be controlled is a vehicle in the presence of bounded disturbances. The RSCA consists of two parts: a Supervisor MPC and a Controller MPC. Both the Supervisor and the Controller are tube MPCs (TMPCs). The Supervisor MPC provides a safety certificate for an operating controller and a backup control input in every step. After an unsafe action by the operating controller is predicted, the Controller MPC takes over the system. In this paper, a method for the computation of a terminal set is proposed, which is robust against changes in road curvature and forces the vehicle to reach a safe reference. Moreover, two important proofs are provided in this paper. First, it is shown that the backup control input is safe to be applied to the system to lead the vehicle to a safe state. Next, the recursive feasibility of the RSCA is proven. By simulating some obstacle avoidance scenarios, the effectiveness of the proposed RSCA is confirmed.


I. INTRODUCTION
Advances in technology have brought more attention to autonomous vehicles. However, autonomous vehicles are among safety-critical systems, i.e., their failure can cause harm to human health, life, property, or the environment [1]. For this reason, despite rapid advancements in Artificial Intelligence (AI) and Machine Learning (ML), control methods based on AI and ML usually cannot directly be applied to autonomous vehicles. A possible solution is a Safe Control Architecture (SCA) that provides safety certificates for any control input, regardless of the operating controller which generates the control input, e.g. [2]- [4]. The operating controller refers to a potentially unsafe control algorithm that can be treated as a black box. It could be an AI or ML based, a trajectory tracking algorithm, or even a human driver.
There is a vast literature on approaches for the safe decision-making of autonomous vehicles, e.g. [5]- [10]. In [5], time-to-collision (TTC) is calculated and intervention happens if the car passes the TTC threshold. In [6], an adaptive controller is proposed based on time to lane crossing 1 Institute for Electrical Engineering in Medicine, University of to shift the authority between the driver and the controller. In [7], under uncertain conditions, the probability of collision between multiple vehicles is estimated to provide a situational assessment. The method in [8] is based on a set-based prediction of the behavior of all traffic participants. In [9], a safety filter is proposed based on solving an MPC problem to maintain the car within the road boundaries. In [10], safe decision-making is attained by enforcing safety constraints in an MPC problem.
A SCA for safe decision-making, using a supervisory controller that continuously provides a safety certificate for the control actions of the operating controller, is proposed in [2]. In [2] the supervisory controller consists of a Supervisor Model Predictive Control (MPC). The safety certificate is provided by predicting the system state one step ahead and based on the feasibility status of an optimization problem. However, the SCA only uses a linearized nominal model, not considering model uncertainties or disturbances that might act on the system. Hence, due to wind or a change in surface friction, wrong decisions by the SCA are possible. Therefore in this paper, we propose a robust SCA (RSCA) based on tube MPC (TMPC) that can provide a safety certificate for an arbitrary controller for safe decision-making even in the presence of disturbances. Furthermore, the proposed RSCA provides another TMPC which replaces the operating controller once it is considered unsafe.
Contributions: This paper makes four main contributions. First, an RSCA based on TMPC is proposed. The RSCA is based on tightening the state and input constraints in optimization problem such that the architecture can guarantee the safety of the system even when it is disturbed. Second, a method for computing a terminal set that is robust against the changes in the road curvature is proposed. Third, the recursive feasibility of the proposed RSCA is established. Finally, the validation of the proposed RSCA is shown in a case study on a safe obstacle avoidance scenario by a vehicle.
Content: Section II reviews the concept of the Supervisor MPC from [2]. Section III describes the model that represents the vehicle in this paper. Section IV explains the RSCA and the setup of the TMPCs. Section V presents the method for the computation of the terminal set and the theoretical safety guarantees. Section VI demonstrates the simulation setup and the results. Section VII presents the conclusion.
Notation: In this paper the symbols ⊕ and denote Minkowski sum and Pontryagin difference, respectively. The function diag(x) constructs a diagonal matrix from a vector x and 1 denotes a vector of ones of suitable dimension. II. CONCEPT OF SUPERVISOR MPC Consider the discrete-time nonlinear system where,x 0 ∈ R n , x k ∈ R n and u k ∈ R m are the initial condition, the state vector and the input vector at time step k, respectively. System (1) is subject to polytopic state constraints, x k ∈ X k , and polytopic input constraints, u k ∈ U. The control input generated by the operating controller, whose safety should be certified, is u o k ∈ R m . Definition II.1 ( [2]) An operating controller is an arbitrary control algorithm that generates the control inputs u o k ∈ R m to fulfill a control goal for system (1).
Definition II.2 ([2]) At any time step k, system (1) is in a safe state if there exists a feasible control sequence such that the input and state constraints are satisfied at all time steps in the future, i.e., ∃{u k , u k+1 , · · · } such that x k+j ∈ X k+j , u k+j ∈ U, ∀j = 0, 1, 2, · · · .

Definition II.3 ([2])
A safety event is when the application of u o k drives the system (1) from a safe state to an unsafe state.
Just the detection of a safety event is not enough, because some time for a reaction is required to intervene with u o k . Therefore, the concept of a detection event is introduced, which is the prediction of a safety event. In the SCA, using an MPC as the Supervisor to predict a safety event is suggested. "An MPC-based detection event is the fact that the following optimization problem is infeasible [2]": where, Q 0 ∈ R n×n and R 0 ∈ R m×m are tuning matrices. The initial condition is x 0|k ∈ R n , whose value in step k of the optimization problem isx k+1 = f (x k , u o k ), where x k ∈ R n is the system's current state. The prediction horizon is N and U = {ū 0|k , · · · ,ū N −1|k } is the decision variable. The state and input constraints are enforced in the optimization problem in (2d) and (2e), respectively.
The infeasibility of the optimization problem (2) means that if u o k is applied to the system (1) and the system goes tox k+1 , then there will be no feasible solution for the optimization problem (2) with respect to the state and input constraints in the next step. In this case, u o k is labeled as unsafe and should not be applied to the system (detection event). What happens after a detection event depends on the application. In our case, we assume that after the operating controller makes a mistake, the system is controlled by another MPC. III. VEHICLE MODEL In the remainder of this paper, it is assumed that the system is a car that is moving at a constant longitudinal speed and that we can measure the system states in every step. Then, the vehicle's lateral dynamics can be represented in terms of error with respect to the road as follows [11, p. 36 where, Here, e y (t) and e ψ (t) are the distance of the center of gravity (CoG) of the vehicle from the center-line of the road and the orientation error of the vehicle with respect to the road, respectively. The rate of change of the road curvature is shown withψ des (t) and it is calculated offline. The control input which should be calculated online is the front wheel steering angle, δ(t). Table I shows the list of vehicle parameters, with their values and units. Assuming all the signals to be piecewise constant, model (3) is discretized by using the exact discretization method [13], as follows: Model (4) in the presence of disturbances due to model mismatches and external physical disturbances is considered: where, d k ∈ D ⊂ R 4 is a bounded disturbance in polytopic form containing the origin. Furthermore, we assume that the upper and lower bounds onψ des k are known, i.e.,ψ des k ∈ Ψ, where Ψ is an interval. The discrete system states are e y k , ∆e y k , e ψ k and ∆e ψ k . To keep the car within the road, the road boundaries are enforced in the problem by imposing constraints on e y k , i.e., |e y k | ≤ R 2 − w 2 , where R is the road width and w is the car width. The presence of an obstacle is enforced in the optimization problem by changing the constraint on k . Moreover, the control input is bounded, i.e., |u k | ≤ δ. Therefore, both the state constraint X k and the input constraint U can be formulated in a polytopic form.

IV. ROBUST SAFE CONTROL ARCHITECTURE
In this paper, a TMPC is used as the robust Supervisor. However, the generated tubes for tightening the state and input constraints in the RSCA cannot be the same as the standard TMPCs, e.g., in [14]. The reason is that in those approaches, the TMPC is used as the controller of the system, and in every step, the current state of the system is available. Therefore, the error propagation in two steps should be considered in the computation of tubes.
At step k, by using the system model (4), the nominal state, denoted byx k+1 , is calculated as follows: Comparing (5) and (6), the true state of the system is: The flowchart of the proposed RSCA is shown in Fig. 1. Ifx k+1 / ∈ X k+1 D, it is already concluded that u o k is unsafe, as x k+1 ∈ X k+1 cannot be guaranteed. Ifx k+1 ∈ X k+1 D, still the safety of u o k is not approved because it has to be assured that the Supervisor MPC can provide a backup control input for the next step. The Supervisor MPC is as follows: where,x 0|k andŪ = {ū 0|k , · · · ,ū N −1|k } are the decision variables. Model (8b), represents the nominal vehicle model wherex i|k ∈ R 4 andū i|k ∈ R are the predicted state and input at step i + k + 1, andψ i|k is defined asψ i|k =ψ des i+k+1 . In the state constraint (8c),X i|k is defined as follows: The tuning matrices are Q 0 ∈ R 4×4 and R > 0 ∈ R. The terminal set X N ∈ R 4 is a robust positively invariant set for system (5). The set Z ∈ R 4 is a disturbance invariant set for system (5) but without considering Eψ des k . The computation of Z and X N is explained in the next section. The gain K in (8d) is chosen such that the matrix, is a stable matrix, where A and B are from (5).
As long as the optimization problem (8) is feasible, u o k is safe, i.e., u k = u o k . Also, the first element of the optimal control sequenceū * 0|k andx * 0|k are to be saved in every step to be used in the calculation of a backup control input if necessary. At the moment, when a detection event takes place, u o k is labeled as unsafe. Then, instead of u o k the following control input should be applied to the system (5): where, x k is the current state and K is from (10). After a safety event is predicted, the following TMPC is suggested as the Controller MPC at the next steps: where,Ũ = {ũ 0|k , · · · ,ũ N −2|k } andx 0|k are the decision variables. Model (12b), represents the nominal vehicle model wherex i|k ∈ R 4 andũ i|k ∈ R are the predicted state and input at step k + i, andψ i|k =ψ des i+k . In the state constraint (12c),X i|k is defined as follows: The horizon of the Controller MPC (12) is one step shorter than the Supervisor MPC (8) in order to maintain the recursive feasibility when switching from the Supervisor MPC to Controller MPC. The control input by solving the optimization problem (12) In order to ensure that the car can always safely overtake obstacles on the road, using the proposed RSCA, we should guarantee that the car can always go as close as possible to one of the road boundaries. Definition V.1 A safe reference is a reference trajectory parallel to one of the road boundaries that the car should be able to reach at the end of every MPC horizon.
In Fig. 2, the red dashed lines located at w 2 meters, where w is given in Table I, away from the road boundaries represent the safe references which are the last point where the car can go without violating the road boundaries. Enforcing the system to exactly reach the safe reference at the end of every MPC horizon can result in a small terminal set, if one can be found. Therefore, similar to [15], we suggest to relax the state constraint by introducing a constant term ,  Fig. 2: Safe references as illustrated in Fig. 2. Then, the safe references are placed at R 2 − w 2 − 2 . Therefore, two terminal sets can be calculated. One enforces the system to reach the area between the red and cyan dashed lines on the top road boundary. The other one enforces the car to get to the area between the red and cyan dashed lines in the bottom road boundary. Based on of size and the placement of the obstacle, it is decided from which side to overtake. Respectively, one of the terminal sets is used in the optimization problems (8) and (12). In the calculation of a terminal set at the upper road boundary, the state constraint on e y k is R Similarly, for the lower road boundary, it is − R 2 + w 2 ≤ e y k ≤ − R 2 + w 2 + . Then, the state constraints, X , for computing the terminal set can be formulated in polytopic form.
Before computing the terminal sets, the system coordinates should be transformed from the center-line of the road to the safe reference. If the system coordinates are going to be transformed to the top safe reference, a constant vector x sr is defined as x sr = R 2 − w 2 − 2 0 0 0 . If the system coordinates are going to be transformed to the bottom safe reference, x sr is defined as x sr = − R 2 + w 2 + 2 0 0 0 . Considering q k = x k − x sr , the state space model (5) is rewritten as follows: (14) where, q k ∈ R 4 is the shifted system vector. Althougḣ ψ des k changes over the road, we want X N to be used for all road curvaturesψ des k ∈ Ψ. Therefore, in the terminal sets computations, the term Eψ des k is also considered as an unknown part, of which only the upper and lower bounds are available. Then, by defining a new disturbance term as d k = Eψ des k + d k + (A − I)x sr , the state space model is reformulated as: The new disturbance set isD = D ⊕ EΨ ⊕ (A − I)x sr andd k ∈D. The state constraint for system (15) is q k ∈ Q, where Q = X x sr . By using the linear controller u k = Kq k with K from (10), the system (15) is transformed into: Definition V.2 ( [16]) The set Ω ∈ R n is said to be a robust positively invariant set of the system (16) if q k+1 ∈ Ω for all q k ∈ Ω and alld k ∈D.
There are many papers on the computation of Ω which can be used, e.g., [17], [18]. However, Ω cannot directly be used in the Supervisor and Controller MPC. Because it is designed for the transformed system. Therefore, it should be shifted back to the original coordinate system, i.e., X N = Ω ⊕ x sr . B. Proof of recursive feasibility At first we prove that at step k when a detection event happens, u backup k satisfies the input constraint and that by applying u backup k to the system (5), the system state in the next step will satisfy the state constraint. The proofs depend on the calculation of Z. To reduce the conservativeness of the TMPCs, it is desirable to have a smaller Z. Thus, in Proposition V.1, we show that sinceψ des k is known in every step, it can be neglected in the computation of Z. Proposition V.1 Consider system (5) and the nominal system (4). Next, the control input u k of the system (5) is taken as follows: with K the control gain from (10). Define Z as the disturbance invariant set for the system x k+1 = A K x k + d k which satisfies: If x k ∈x k ⊕ Z, then x k+1 ∈x k+1 ⊕ Z. Proof: By introducing e k x k −x k , we have that e k+1 = A K e k + d k . Then, since e k ∈ Z (i.e., x k ∈x k ⊕ Z) and A K Z ⊕ d k ⊆ Z as required in (18), we have that e k+1 ∈ Z which results in x k+1 ∈x k+1 ⊕ Z. In the Supervisor MPC problem (8), the initial condition is the predicted nominal state at the next step (6), not the actual system state (7). Therefore, to ensure that the backup control input (11) and its application to the system (5) are safe, just considering the disturbance of one step in the computation of Z is not enough, but the propagation of the disturbance in two steps should be considered. This brings us to the following corollary. Corollary V.1 (Safety of the vehicle at the moment of detection event) Define a set Z as used in (8) and (12) to satisfy the following condition: in which, A K is from (10). Then, the control input u backup k in (11) satisfies the input constraint. Furthermore, if u backup k is applied to the real system (5) at step k, then, the next state x k+1 is still within the state constraint set X k+1 regardless the value of the disturbance, d k .
Proof: This proof consists of two parts. The first part is on proving that u backup k ∈ U. From (7), having that x k = x k + d k−1 leads to: 0|k−1 ∈ Z holds. With (8d), it also holds thatū * 0|k−1 ∈ (U KZ) KD. Therefore: Next, it is shown that by applying u backup k to the system (5) the state constraint is satisfied in the next step k + 1: Because x k =x k + d k−1 from (7), equation (20) is 0|k−1 )) + Eψ des k + d k , which leads to: The nominal system (4), after applyingū * 0|k−1 is as follows: By applying Proposition V.1 to the two systems (21) and (22), i.e. considering w d k + A K d k−1 , and using the property of Z as in (19), we have: sincex k ∈x * 0|k−1 ⊕ Z as constrained in (8f). Note that, we havex * 1|k−1 ∈ X k+1 Z as required from (8c) which leads to x k+1 ∈ X k+1 Z ⊕ Z ⊆ X k+1 . Theorem V.1 (Recursive feasibility) The feasibility of the Supervisor MPC at step k − 1 guarantees the feasibility of the Controller MPC at step k + 1.
VI. SIMULATION RESULTS To showcase the applicability of the proposed approach, 120 different obstacle avoidance scenarios are simulated using MATLAB [19] and the results compared with the SCA in [2]. In the MPC setup, the sampling time t s is 0.1 seconds. The tuning parameters are Q = diag ( 1 1 1 1 ), R = 0.1, and N = 30.
In the simulations, the operating controller is a Pure Pursuit (PP) controller which is a path-tracking algorithm [20]. The PP controller tries to keep the car on the reference trajectory by minimizing the car's deviation from the reference trajectory. The look-ahead time is chosen as 0.5 seconds.
Model (5) Table I. For the calculation of Z, the approach in [21] is used. The calculation of X N is carried out in accordance with [18, p. 25], with = 0.5m for initializing x sr in (14).
The constraint on |e y k |, for the steps over the prediction horizon where there is no obstacle is enforced in the optimization problems as |e y k | ≤ R 2 − w 2 , where R 2 = 8m and w is given in Table I. Otherwise, the constraint is updated based on the size of the obstacle, e.g., for a scenario, where an obstacle with a width of obs width is located at the center of the road, the constraint is obs width The constraints on the rest of the states are |∆e y k | ≤ 10m/s, |e ψ k | ≤ π 2 rad and |∆e ψ k | ≤ π 3ts rad/s. The input is also bounded by |u k | ≤ 34π 180 rad. In Fig. 3, a safe obstacle avoidance scenario is illustrated. In this scenario, the centerline of the road is the reference trajectory, and the blue line indicates the car's movement. The obstacle is 50m away from where the car starts. The car moves at a speed of 12m/s. In this scenario, the PP controller drives the car right to the obstacle, and the Supervisor MPC should intervene when necessary. A detection event takes place in the Supervisor MPC at 11.3m before the obstacle. This point is shown with a red dotted line. Thereafter, the Controller MPC takes over the car, and the car safely overtakes the obstacle. The gray line in the Fig. 3 shows the optimal state sequence, generated by the Supervisor MPC at step k, over the entire prediction horizon. As evident in Fig. 3, the car ends up in a safe reference at the end of the horizon.
To evaluate the RSCA and compare it with the SCA, 120 obstacle avoidance scenario simulations are carried out. The obstacles widths are chosen randomly based on uniform distribution within the range 0.1 and 2.5m and for the length between 1 to 10m as well as the vehicle speed between 5 to 20m/s. Between these 120 scenarios, one third of them is carried out with a disturbance set of |d 1 k | ≤ 1·10 −2 , one third with |d 2 k | ≤ 1 · 10 −3 , and 40 scenarios with |d 3 k | ≤ 1 · 10 −4 . In the simulations, the disturbances are randomly generated based on the uniform distribution according to the assigned ranges. The initial conditions are selected such that the MPC at k = 0 is feasible.
The measure of success or failure in each scenario is the feasibility or infeasibility status of the Controller MPC after a detection event. In 31% of all scenarios, the SCA failed in performing a safe obstacle avoidance scenario, while the RSCA succeeded in all of them. The chance of failure of the SCA was higher in more complex scenarios, e.g., if the obstacle's dimension was larger. When comparing the intervention time of both control approaches, it is noticeable that in some scenarios the RSCA reacts before the SCA. In total in 13% of the scenarios, the RSCA intervened the operating controller one or two sampling times earlier than the SCA. Most of the scenarios with the earlier intervention by RSCA belonged to the scenarios with larger disturbance d 1 k . In total, 75% of the earlier interventions by the RSCA are related to the set d 1 k of larger disturbances, while 19% and only 6% is the share of d 2 k and d 3 k , respectively. The earlier intervention of the RSCA compared to the SCA implies that the robust Supervisor is more conservative than the standard MPC in the SCA. However, the relation of the size of the expected disturbance and the conservativeness of the RSCA could be exploited to adapt to the situation, e.g. by considering the current uncertainty in the system states. Furthermore, the more conservative controller is acceptable, since the RSCA was capable to perform a safe obstacle avoidance maneuver in all scenarios.
VII. CONCLUSIONS The implementation of autonomous driving in real world applications requires rigorous satisfaction of safety-critical constraints in an uncertain environment. Thus, an RSCA is proposed to include disturbances acting on the system while guaranteeing constraint satisfaction during obstacle avoidance maneuvers independent of the roads' curvature. The proposed RSCA utilized two TMPCs, one for predicting a potential safety event, and one for taking over from the unsafe operating controller after a detection event. The general benefits of RSCA compared with [2] were displayed in a case study of 120 different scenario simulations.