{'fraction_non_alphanumeric': 0.03435215695186153, 'fraction_numerical': 0.0062492898534257475, 'mean_word_length': 4.643086129514853, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 5, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Region-of-convergence estimation for learning-based adaptive controllers

Recent learning-based extensions to popular adaptive control procedures offer improved convergence, but at the cost of increased complexity. This complexity makes it difficult to analytically compute level sets that bound the system response. These level sets can be combined with the a priori known Lyapunov function for such systems to provide barrier certificates, verifying the safety of the system to maximum allowable error limits. This paper presents a complementary automated procedure for computing invariant level sets offline using simulation data. These level sets encompass combinations of safe initial conditions and parameters that will not cause the adaptive system's response to exceed constraints. First, conditions for the complete set of safe initial states and parameters, known as the region-of-convergence, are established. These conditions, coupled with the known Lyapunov functions describing the adaptation, are used to form an optimization procedure to construct verifiable level sets for the system response. These levels sets thus provide barrier certificates for safety and conservatively estimate the complete regionof-convergence. Lastly, the procedure is demonstrated on an adaptive control system.


I. INTRODUCTION
Adaptive control procedures combine parameter estimation with control to achieve a desire level of performance while maintaining robustness. In particular, popular model reference adaptive control (MRAC) methods have been extensively studied in order to guarantee the stability of the adaptation and the ability of the uncertain system to track the desired reference model [1]- [3]. As a result, the stability and convergence is defined using well-known Lyapunov functions than can be used to prove Uniform Ultimate Boundedness of the system and determine level sets that bound the system response [3].
Recent approaches [4]- [6] have improved performance and robustness of the baseline MRAC methods, but at the cost of increased complexity. This complexity presents a challenge towards the calculation of level sets that describe the system response. For instance, concurrent learning MRAC (CL-MRAC) adds a history stack of saved data points to improve convergence of the adaptation and decrease transient errors in the response, but this history stack complicates analysis of the system. Analytical bounds on the CL-MRAC response have been shown [7], but these bounds are difficult to calculate in practice as they explicitly depend on the particular points saved in the history stack. Since CL-MRAC periodically updates the history stack, the bounds will have to be recomputed, making it difficult to provide more general certificates. Until a bounding set can be determined, these adaptive systems cannot be theoretically verified as safe.
In contrast, simulations of adaptive systems are an extremely useful tool to gain insight on the behavior of the adaptive system. Model checking procedures [8], [9] already utilize large batches of simulation traces to generate statistical guarantees on complex, stochastic, nonlinear systems. When dealing with deterministic systems, these guarantees can be tightened even further. In particular, recent work in simulation-guided region-of-attraction [10], [11] and Lyapunov function [12], [13] analysis procedures provide theoretically guaranteed bounds generated using simulation traces. These approaches intelligently sample the state space to find falsifying simulation traces and construct a linear program that describes a Lyapunov function and its maximum invariant level set that avoids such traces. The crux of these methods is that if the Lyapunov function and its corresponding maximum invariant set meets certain conditions, then they create a barrier certificate that verifies the stability of the complex nonlinear system. In short, if the system starts within the region-of-attraction identified by the procedure, then the system response will always remain bounded and eventually converge towards the equilibrium point. This provides a powerful method for automatically and provably verifying the stability of a system of interest.
In this paper, a similar simulation-based methodology is used to analyze the response of learning-based adaptive controllers. For a given deterministic adaptive control system, the system's state and adaptation trajectory is completely characterized by the initial state conditions and parameters. When constraints are placed on the allowable limits of the system response, the initial states and parameters determine whether the system response will exceed those constraints. If a certain combination of initial states and parameters do not lead to a violation of these constraints, then the combination is labeled as "safe". The complete set of safe combinations is defined as the region-of-convergence.
Simulations of the adaptive system at various combinations can be employed to estimate this region with an invariant level set and create barrier certificates. The simulations help compute an absolute lower bound on the failed trajectories. Paired with the fact that the known Lyapunov function for such systems is bounded, this information forms a maximum invariant level set on safe trajectories. The com-bination of the Lyapunov function and maximum invariant set provides a barrier certificate such that any trajectories started within some initial region will never exceed the constraints.
The paper is organized as follows. First, a background on recent learning-based model reference adaptive controllers is given. In particular, the concurrent learning MRAC algorithm is used as a case study for these approaches. This background is then used to motivate and define the region-of-convergence problem for these adaptive systems. Once the region-ofconvergence has been defined, the next section describes the simulation-based procedure to estimate this set using simulation traces. The procedure uses an optimization problem to maximize an invariant set within the region-of-convergence, which also provides a barrier certificate verifying the safety. The last section demonstrates the procedure on an adaptive control system.

II. MODEL REFERENCE ADAPTIVE CONTROL
Consider the following uncertain dynamical systeṁ where x(t) ∈ R n is the state vector and u(t) ∈ R m is the corresponding control input vector. Assume x(t) is available for measurement and the pair of matrices A ∈ R n×n and B ∈ R n×m are both known and controllable. This pair (A, B) defines the nominal system dynamics; however, uncertainties ∆(x) ∈ R m are also present in the actual dynamics. These uncertainties ∆(x) are assumed to have a known structure parameterized by an unknown constant weighting matrix W * ∈ R kn×m and a known regressor vector φ(x) ∈ R kn where φ(x) can be either a linear or nonlinear basis vector without loss of generality. Let regressor φ(x) be Lipschitz continuous to ensure the existence and uniqueness of the simulation trace [1]. While the exact values of the parameters in the system are unknown, the set of all possible parameters W * feas ∈ R k is known, that is all possible W * ∈ W * feas with k = k n × m. Additionally, the initial state x(0) may be uncertain, but is also assumed to fall within some known feasible region X init ∈ R n .
The adaptive controller forces the system to track a known, stable reference system with desirable characteristics. In this paper, the underlying reference model is assumed to be linear and the resulting reference model dynamics are given bẏ where x m (t) ∈ R n is the reference state and r(t) ∈ R mr , m r ≤ m is the external reference command, assumed to be piecewise continuous and bounded. The state tracking error between the reference state trajectory and the actual state trajectory is given by e(t) = x m (t) − x(t). It is assumed that all x m (0) start at the same nominal initial condition x nom and any uncertainty on x(0) can be treated as disturbances to the known x nom .
The control system then attempts to minimize the state tracking error e(t) using control inputs u(t). The control input is the combination of three components: and an adaptive control input u ad .
In the absence of uncertainties, the feedforward u rm and feedback u pd terms would force the nominal system to track the reference trajectory. Now, the adaptive control input u ad attempts to suppress the uncertainty ∆(x) by estimating the parameterization of ∆(x) and updating u ad accordingly. The adaptive inputs follow the same known structure of ∆(x): with estimated parameters W in place of actual W * . The resulting estimation error is W = W − W * . Usually, the initial estimates can be set to zero, W (0) = 0, as any known quantities are assumed to be included in the nominal system (A, B).

A. Concurrent Learning Adaptive Control
Many possible techniques exist for adapting the parameter estimates [1]- [6], but MRAC-based procedures all update their estimates based upon the reference model tracking error e(t). For the remainder of the paper, the concurrent learning MRAC (CL-MRAC) procedure will be used as the adaptive process, but other techniques can also be employed. The concurrent learning adaptive law is given bẏ where learning rates Γ and Γ c are positive scalars. The symmetric positive definite matrix P is determined from the Lyapunov equation A T m P + P A m = −Q with Q = Q T > 0. The innovation of the concurrent learning adaptive law is the history stack, which stores a fixed, finite number p of measurements of the state vector and estimation error alongside the instantaneous tracking error. Central to this process are measurements oḟ x to obtain ∆(x). The derivativeẋ can be either measured directly or estimated using a fixed point smoother [4].
An important aspect of this CL-MRAC procedure is the singular value maximizing (SVM) algorithm that periodically replaces the least-informative data points (φ(x i ), i ) in the history stack with more-informative ones as they are encountered. This ensures the matrix S(x, t) = MRAC procedures use a known Lyapunov function to prove the stability of the system. This Lyapunov function V is differentiable, positive definite, and radially unbounded and describes both the stability of the reference model tracking error and parameter estimation error with V (0) = 0.
For the CL-MRAC procedure, the derivative of this Lyapunov function is a strictly negative definite function that asymptotically converges to the solution e = 0, W = 0.
This Lyapunov function and its derivative was shown in [4] to prove the stability and convergence of the CL-MRAC controller. Similar proofs for other adaptive procedures establish the Lyapunov stability of the adaptation and convergence toward the stable reference model, thus also establishing stability of the adaptive system.

III. REGION-OF-CONVERGENCE OF CONSTRAINED ADAPTIVE SYSTEMS
The Lyapunov function in (8) is common to most MRACbased adaptive procedures. If V (e, W ) > 0 andV (e, W ) ≤ 0 for all (e, W ) = 0, this function establishes the Lyapunov stability and convergence of the controlled system towards the desired reference trajectory. Additionally, this also indicates that in the absence of restrictions on u(t), any value for W * and x(0) will not destabilize the adaptation. Because the Lyapunov function (8) is radially unbounded, the adaptive system is globally stable.
While the ultimate stability of the adaptation is invariant to the particular values of x(0) and W * , the transient response of e(t) and W (t) during the adaptation must also be considered. Many systems place additional constraints on the system response, such as maximum allowable thresholds on the tracking error e(t). Stability alone does not guarantee these performance constraints will be met. For instance, consider Figure 1, which depicts a sample trajectory taken from the CL-MRAC controlled system in Section V-A. The adaptation is known to be stable, but the transient tracking error e(t) response exceeds the allowable threshold. The error dynamics are dependent upon the particular x(0), W * values used; therefore, it is desirable to identify whether a set of initial conditions x(0) and parameters W * will cause the adaptive system to exceed any performance thresholds.
The set of all possible combinations of initial conditions x(0) and parameters W * is the feasible search region R feas ∈ R n+k , where R feas := X init ∪ W * feas . Since different combinations of x(0) and W * will either cause the system to exceed the constraints or not, the feasible region R feas can be broken up into two independent subsets. In order to define these subsets, first define the space outside these constraint thresholds, called the failure region R fail .  Fig. 1. State space diagram of the response of a CL-MRAC system. Even though the system is stable [4], the actual state exceeds the allowable error.

Definition 1
The failure region R fail ∈ R n is the set of infeasible tracking errors e fail ∈ R n outside the allowable bounds.

Definition 2
The region-of-convergence R 0 ∈ R n+k is the set of W * ∈ W * 0 and x(0) ∈ X 0 such that the solution to (1), trajectory Φ(t : x 0 , w 0 ), never enters the region R fail . The trajectory Φ(t : This region-of-convergence is generally unknown ahead of time, so the task is to estimate this region. Due to the nonlinear nature of the adaptive system, the shape of this region in R n+k space can be complex and even non-convex, as will be seen in Section V-A. The second subset of R feas is the region-of-failure, R F . Just like R 0 , R F considers initial conditions x(0) and W * rather than the space of all e(t) like R fail .

Definition 3
The region-of-failure R F ∈ R n+k is the set of W * ∈ W * 0 and x(0) ∈ X 0 such that the trajectory Φ(t : x 0 , w 0 ) enters the region R fail , again where W * 0 ⊆ W * feas and X 0 ⊆ X init . Note that the intersection R F ∩ R 0 = ∅.
Previous work has provided some analytical tools for estimating the ROC. More specifically, extensions to the respective Lyapunov convergence proofs can be used to calculate upper bounds on the state tracking error ||e(t)|| for each MRAC method under consideration [3], [7], as well as other approaches such as L1 adaptive control [14]. These upper bounds will then determine whether the system will exceed any of the indicated constraints. However, with more complex procedures, these analytical bounds on e(t) become increasingly difficult and unwieldy to calculate offline, thus complicating a priori safety verification.
For instance, consider the following bound on tracking error for a CL-MRAC system. This bound is taken from the proof for Corollary 2 in [7]. It states that the tracking error e(t) is bounded by an exponential function where k 1 and k 2 are functions of known constants P , Γ, and Γ c . The difficulty in computing the analytical bounds arises from the fact that function k 3 depends explicitly on the saved values of φ(x i ) and i stored in the history stack from the adaptive law in (6) and is periodically updated with new information. As mentioned in Section II-A, these values are gradually replaced with more-informative ones as the system evolves, changing the value of k 3 . Since k 3 is not constant and evolves as the system executes, it is extremely difficult to compute the analytical bounds for e(t) offline and ensure the system is safe before execution. In comparison, it is rather straightforward to generate large numbers of simulations of the adaptive systems of interest and these simulations give insight into the sensitivity of the performance to X init and W * feas . While simulation traces of the system at various samples of X init and W * feas can provide statistical bounds on the system response, they generally lack the guarantees of the difficult, but verifiable, analytically determined bounds. Simulation-guided verification methods provide a bridge between the two. Simulation traces can be used to construct verifiable invariant level sets to estimate the region-of-convergence and form barrier certificates.

IV. ESTIMATION OF THE REGION-OF-CONVERGENCE
Large numbers of simulations are used to estimate the region-of-convergence of learning-based MRAC systems. The following procedure selectively samples R feas and performs simulations at these values to find the smallest boundary between R 0 and R F . The simulation traces are then used to construct barrier certificates to ensure a system will never enter R fail if the system is initialized within set R init .
This approach is an extension of recent work in simulation-guided region-of-attraction estimation, which addresses a closely related problem. These procedures [10], [11] attempt to find which system trajectories converge to the origin in asymptotically stable, but not globally attractive, nonlinear systems. Not surprisingly, these approaches can be readily adapted to address the region-of-convergence estimation problem. In particular, the robust estimation procedure [10], [11] provides a good groundwork for a region-ofconvergence estimation procedure. The ROC procedure will utilize many of the same functions. A much more detailed analysis and discussion of these functions can be found in [15].
While the region-of-attraction (ROA) procedures and region-of-convergence (ROC) procedure are very similar, they do address different problems. Unlike ROA procedures, the ROC procedure already starts with a known Lyapunov function. The procedure does not need to search for a suitable Lyapunov function to characterize the system as it is provided by the respective adaptive control method under consideration. For MRAC systems, this will look like (8). Additionally, the ROC method must enforce stricter conditions (boundedness) in place of attraction to the origin. These differences require a slightly different approach for region-of-convergence estimation. The following subsections describe the ROC estimation procedure.

A. Invariant Subsets of the Region-Of-Convergence
The estimation of the region-of-convergence relies upon invariant sublevel sets of R 0 to form the basis of an optimization procedure. These invariant sublevel sets describe a set of (e, W ) for which the system trajectory will fall below a set threshold and ensure the system remains out of R fail . For MRAC systems, sublevel sets can be written in terms of the Lyapunov function as follows.
Definition 4 For η > 0 and Lyapunov function V : R n+k → R from (8), the η-sublevel set of V is: Sublevel sets of R feas can then be used to define a set of initial values x(0) and W * , R init , such that the Lyapunov function V of the corresponding response falls below some bound β. If all trajectories that enter R fail have V (e, W ) > β, then the initial set R init is a subset of R 0 and provides a barrier certificate B(e, W ) to verify the safety of the system.

Definition 5
Given an initial set R init ⊂ R feas and a failure region R fail ⊂ R feas , a function B: R feas → R is a barrier certificate if: (14) such that B(e, W ) = 0.
With this definition, the following Lemma provides a description of barrier certificates for the system response in terms of sublevel sets of the Lyapunov function.
Proof: A proof for Lemma 1 is omitted here for space, but can be found online in an extended version of this paper at http://tinyurl.com/jk4fzfz.

Remark 1
If two additional weak assumptions are met, then the η-sublevel set can be increased slightly from the result in Lemma 1. This is further discussed and proven in the extended paper.

B. Computation of Barrier Certificates
The barrier certificate verifies the safety of the system as long as the system is initialized within the initial set R init . It identifies a region-of-convergence of the system; however, as an estimate of the full ROC, R init may be conservative. It is therefore advantageous to not only identify a barrier certificate of the system, but also attempt to maximize the region to include as much of R 0 as possible.
The barrier certificate computation process is broken into two steps: generate samples and compute bounds. These two steps naturally extend from the earlier region-of-attraction work. As such, the following overview focuses on the particular modifications required for the ROC. The details of the SimLFG and CWOpt algorithms discussed next can be found with full descriptions in the earlier works [10], [15].
This first step involves selectively sampling x(0) and W * in the R feas space, looking for points on either side of the R 0 boundary. This algorithm uses a search parameter β sim to define a ball ∈ R feas and randomly selects points in that region to run simulations. If the simulations return failures or converged trajectories, β sim will shrink or expand accordingly. Once the procedure has simulated N conv converged trajectories, it terminates.
After the procedure terminates, the C and D datasets of trajectories that lead to success or failure can be used to determine a candidate level set and barrier certificate. At a minimum, the failed trajectories in D provide a strict upper bound on the allowable size of the η-sublevel set, since V (e, W ) ≥ β U B for all (x(0), W * ) ∈ D, and therefore η < β U B .
Next, the invariant sublevel set for the Lyapunov function can be computed using the following optimization problem. γ > 0 (20) where Σ[e, W ] refers to a positive semidefinite function R n+k → R. Notice that sinceV < 0 for CL-MRAC systems, the resulting level set Ω V,γ * l can also be directly used to form a barrier certificate as in Lemma 1.
The s 2 , s 3 functions can be determined according to the procedure described in [15]. In practice, these functions are usually -scaled versions of the Lyapunov function, V , for some small real or another quadratic function of the system dynamics.
The resulting γ * l yields a suitable lower bound for the ηsublevel set used to form a barrier certificate, so that γ * l ≤ η < β U B . Therefore, by setting η = γ * l , the process returns a theoretically verified, albeit conservative, estimate R init of the full region-of-convergence R 0 . A second algorithm from [15], CWOpt, can also be used to attempt to maximize γ * l even further is available, but was not used here. Note, it is also possible to use the β U B upper bound to generate barrier certificates using counter-example based methods from [12], [13], but requires additional toolboxes and software.

C. Discussion
In practice, this procedure will result in a conservative estimate of the region-of-convergence. Even though the estimate is conservative, it is still valuable as a certified bound. Additionally, the process generates a number of samples of x(0) and W * in R 0 that did not fall within the level set. A parallel research effort has focused on using all the converged trajectories to compute a tighter estimate of the region-of-convergence. However, this approach replaces the strong theoretical guarantees with statistical bounds. The region-of-convergence estimation procedure within this paper is intended as a complementary approach.

V. EXAMPLES
The following example demonstrates the region-ofconvergence estimation process for concurrent learning MRAC system [4] described in Section II. For these types of systems, the form of the Lyapunov function V (e, W ) is already known from (8). Additional examples are included online in an extended form of the paper at http://tinyurl.com/jk4fzfz. Those examples also cover a more complex nonlinear wingrock model [4], but were omitted here due to space. maximum upper bound β U B . The convergence (or lack of it) of the trajectories changes the search parameter β sim used to generate subsequent samples. This ends up clustering the data points near the boundary of R 0 at a ball with its radius set to the current β U B . The inadvertent clustering is apparent in Figure 2 by the large density of data points clumped together near 4 ≤ ||W * || ≤ 8. The emergent clustering also explains why the successful region down near 0 ≤ W * 1 ≤ 5 and W * 2 < −9 is not explored further: the procedure limited its β sim to search around β U B = 1.767. After 3000 successful pairs were simulated, the procedure returned the size of the η-sublevel set as γ * l = η = 1.414. Note that this discrepancy between β U B and η results from the conservativeness necessary in computing a certifiable bound. However, previous analytical methods [7] can only provide verified estimate η analytic = 1.015.
For comparison, Figure 3 displays the actual region-ofconvergence for the system. The invariant set Ω V,η calculated by the estimation procedure is also overlaid on top of the full R 0 . This figure highlights a number of important considerations. First, the region-of-convergence may be highly nonconvex as the boundary of R 0 for W * < 0 values is oddly shaped and jagged. Additionally, this figure also highlights the aforementioned conservativeness of ROC estimation procedures. The invariant set Ω V,η is not able to capture values on the outskirts of R 0 due to the limitations of the process. While a tighter estimate of the ROC is desirable, the verified barrier certificate is still extremely useful as a proven safe set and larger than previous analytical methods.

VI. CONCLUSION
This paper presents a method for computing invariant sets to produce verifiable estimates of the region-of-convergence of learning-based adaptive controllers. These level sets can subsequently be used to create barrier certificates for safety. This procedure provides an automated offline tool to supplement existing analytical methods that can become increasingly unwieldy with the complexity of learning-based adaptive controllers. This work extends recent work in regionof-attraction analysis, a similar but separate problem for nonlinear systems without global attraction to the origin. The paper presents results for a CL-MRAC example problem to demonstrate the ability of the procedure to find verifiable estimates of the region-of-convergence. While these estimates may be conservative, they do provide theoretical guarantees of safety with their associated barrier certificates. Ultimately, the procedure is intended as a step in the process to address the larger problem of formally verifying adaptive systems.