A E Polyakov
email: andrey.polyakov@inria.fr

Time-Suboptimal Feedback Design via Linear Matrix Inequalities

published or not. The documents may come

Time-suboptimal feedback design via linear matrix inequalities

INTRODUCTION

In control practice it is often a challenge to design a controller which guarantees the minimal transient time. This problem is know as the time-optimal control problem; it typically arises in robotics, space applications, control of submarine and surface mobile systems. In spite of the long-standing and prolific history of the optimal control theory formulated as early as in 1950s and 1960s in the works by A.A. Fel'dbaum [START_REF] Feldbaum | Optimal Processes in Systems of Automatic Control[END_REF], L.S. Pontryagin at al. [START_REF] Pontryagin | The Mathematical Theory of Optimal Processes[END_REF], R. Bellman [START_REF] Bellman | Dynamic Programming[END_REF], optimal control problems are still in the focus of active research [START_REF] Lasserre | Nonlinear Optimal Control: Numerical Approximations via Moments and LMI-Relaxations[END_REF][START_REF] Chernousko | Control of Nonlinear Dynamical Systems: Methods and Applications[END_REF][START_REF] Dinuzzo | Higher Order Sliding Mode Controllers with Optimal Reaching[END_REF][START_REF] Boltyanski | The Robust Maximum Principle: Theory and Applications[END_REF].

The so-called bang-bang control is a classical discontinuous solution of the time-optimal control problem, which is based on the profound Fel'dbaum's n interval theorem [START_REF] Feldbaum | Optimal Processes in Systems of Automatic Control[END_REF]. Traditionally, the corresponding control law is implemented as open-loop control (i.e., without feedback), except for low-dimensional cases which admit time-optimal control design by using sliding modes; e.g., see [START_REF] Chernousko | Control of Nonlinear Dynamical Systems: Methods and Applications[END_REF][START_REF] Dinuzzo | Higher Order Sliding Mode Controllers with Optimal Reaching[END_REF]. In practice, however, not only time-optimality of a control algorithm is of interest, but also other performance indices which are associated with the robustness and accuracy of the algorithm, its energy characteristics, etc. These indices are often conflicting, so that control design problems are sometimes reformulated in terms of quite hard multi-objective optimization. Finally, discontinuous time-optimal control laws are often impossible to implement because of physical peculiarities of the system [START_REF] Bernstein | Optimal Nonlinear, but Continuous, Feedback Control of Systems with Saturating Actuators[END_REF][START_REF] Glizer | Robust Controllability of Linear Systems[END_REF]. In this respect, suboptimal controllers [START_REF] Bertsekas | Dynamic Programming and Suboptimal Control: A Survey from ADP to MPC[END_REF][START_REF] Bohl | Linear Feedback vs. Time Optimal Control[END_REF] are of great practical importance. They are usually being designed under additional constraints on the class of admissible feedbacks (for instance, those leading to robust control laws) and other, not always constructive practice-driven requirements.

In this paper we consider the time-optimal control problem for a simplest plant represented by a chain of integrators, which is governed by a linear dynamic state feedback. In spite of the linear formulation of the problem, control design will be performed with the use of methods which are more popular in the nonlinear control theory. In particular, the nonlinear implicit control law proposed in this paper provides the closed-loop system with the so-called property of weighted homogeneity with negative exponent [START_REF] Zubov | On Systems of Homogenous Differential Equations with Generalized Homogenous Righthand Sides[END_REF][START_REF] Rosier | Homogenous Lyapunov Function for Homogenous Coninuous Vector Field[END_REF][START_REF] Bhat | Geometric Homogeneity with Applications to Finite-time Stability[END_REF][START_REF] Bernuau | On Homogeneity and Its Application in Sliding Mode Control[END_REF]. It is this property that guarantees robustness and finite-time stability, the latter being the ability for an asymptotically stable system to attain its equilibrium in finite time. On top of that, the ideas of weighted homogeneity are fundamental to the implicit Lyapunov function method [START_REF] Adamy | Soft Variable-Structure Controls: A Survey[END_REF][START_REF] Polyakov | Finite-time and Fixed-time Stabilization: Implicit Lyapunov Function Approach[END_REF], which is applied in this paper to suboptimal control design. To analyse stability of a system, this method suggests use of a Lyapunov function which is specified implicitly, e.g., in the form of an algebraic equation. Generally speaking, neither the stability analysis, nor the evaluation of the rate of convergence do require finding a solution of such an equation, since with the classical implicit function theorem [START_REF] Courant | Introduction to Calculus and Analysis[END_REF], the corresponding conditions of the Lyapunov theorem can be checked by analyzing only the properties of this algebraic equation and the right-hand sides of the system. In the Russian-language control literature, similar ideas were proposed by V.I. Korobov [START_REF] Korobov | Metod funktsii upravlyaemosti (Controllability Function Method)[END_REF] in the construction of the "controllability function," which is essentially a finite-time Lyapunov function of the closed-loop system.

The salient feature of combining the implicit Lyapunov function method with the theory of homogeneous system is that the algorithm for tuning the parameters of essentially nonlinear feedbacks [START_REF] Polyakov | Finite-time and Fixed-time Stabilization: Implicit Lyapunov Function Approach[END_REF] can be formalized in terms of linear matrix inequalities (LMIs) [START_REF] Boyd | Linear Matrix Inequalities in System and Control Theory[END_REF][START_REF] Polyak | Upravlenie lineinymi sistemami pri vneshnikh vozmushcheniyakh: tekhnika lineinykh matrichnykh neravenstv (Control of Linear Systems Subject to Exogenous Disturbances: The Linear Matrix Inequalitiy Technique)[END_REF]. At present, LMIs are considered as the most efficient computational approach to linear control system design [START_REF] Boyd | Linear Matrix Inequalities in System and Control Theory[END_REF]; it allows for a considerable simplification of H 2 /H ∞ -robust control design procedures [START_REF] Polyak | Upravlenie lineinymi sistemami pri vneshnikh vozmushcheniyakh: tekhnika lineinykh matrichnykh neravenstv (Control of Linear Systems Subject to Exogenous Disturbances: The Linear Matrix Inequalitiy Technique)[END_REF]. Many other problems in control theory [START_REF] Boyd | Linear Matrix Inequalities in System and Control Theory[END_REF] can be reduced to solving semidefinite programs (SDPs), i.e., to the optimization of a (usually linear) cost subject to LMI constraints. In a number of works conducted by B.T. Polyak in the recent years, this approach was applied to the design of robust control for optimal rejection of exogenous disturbances in linear systems [START_REF] Polyak | Upravlenie lineinymi sistemami pri vneshnikh vozmushcheniyakh: tekhnika lineinykh matrichnykh neravenstv (Control of Linear Systems Subject to Exogenous Disturbances: The Linear Matrix Inequalitiy Technique)[END_REF]. An extension of these ideas to nonlinear control plants can be found in [START_REF] Poznyak | Attractive Ellipsoids in Robust Control[END_REF]. In this paper, the nonlinear time-suboptimal design problem also reduces to solving a semidefinite program.

Notation. In the paper, the following notation will be used:

R + = {x ∈ R : x > 0}, R -= {x ∈ R : x < 0}, where R is the field of real numbers; diag{λ i } n
i=1 is the diagonal matrix with the entries λ i on the main diagonal; the continuous function σ : R + → R + belongs to the class K if it is monotonically increasing and σ(s) → 0 + as s → 0 + ; if this function is not bounded as s → +∞, we say that it belongs to the class K ∞ ; a continuous function β : R + × R + → R + belongs to the class KL if β(•, t) ∈ K ∞ for any fixed t ∈ R + , and β(s, •) is monotonically decreasing for any fixed s ∈ R + ; for a matrix P ∈ R n×n with real spectrum, its minmal and maximal eigenvalues are denoted by λ min (P ) and λ max (P ), respectively; for a symmetric matrix P ∈ R n×n , the inequality P > 0 (P ≥ 0, P < 0, P ≤ 0) is understood as positive definiteness (respectively, positive semidefiniteness, negative definiteness, negative semidefiniteness); C k is the space of functions having derivatives up to order k inclusive; L is the space of Lebesgue integrable functions; L ∞ is the space of measurable, almost everywhere bounded functions.

STATEMENT OF THE PROBLEM

In this paper we analyze a single-input control plant represented by a chain of n integrators:

ẋ(t) = Ax(t) + bu(t), t ∈ [0, T ], x(0) = x 0 ∈ R n , (1)
where T ∈ R + is a finite time instant, x ∈ R n is the state vecror, u ∈ R is the control input, and

A = ( 0 I n-1 0 0 ) , b = (0, ..., 0, 1) ⊤ ∈ R n .
The importance of this model is stipulated by numerous mechanical and electromechanical applications, see [START_REF] Chernousko | Control of Nonlinear Dynamical Systems: Methods and Applications[END_REF][START_REF] Utkin | Sliding Mode Control in Electro-Mechanical Systems[END_REF][START_REF] Biagiotti | Time-Optimal Regulation of a Chain of Integrators with Saturated Input and Internal Variables: An Application to Trajectory Planning[END_REF]. Let us consider the time optimal control problem in the classical formulation:

T → min (2)
subject to the constraints

u(•) ∈ U = {u(•) ∈ L (0,T ) : |u(t)| ≤ u 0 , t ∈ [0, T ]}, x(•) ∈ C [0,T ] : { ẋ(t) = Ax(t) + bu(t), t ∈ (0, T ), x(0) = x 0 , x(T ) = 0, (3)
where x 0 ∈ R n and u 0 ∈ R + are given. By the Feldbaum theorem [START_REF] Feldbaum | Optimal Processes in Systems of Automatic Control[END_REF], the optimal solution is provided by the so-called "bang-bang" control, which is a piece-wise constant function u opt (t) ∈ {-u 0 , u 0 }, t ∈ (0, T ), with n -1 discontinuities. In this paper we will be interested in solving problem (2), (3), subject to certain additional constraints. First, admissible input signals are assumed to be smooth, u(•) ∈ C ∞ (0,T ) . This restriction is natural in many problems encountered in practice, [START_REF] Wang | Control of a Chain of Integrators Subject to Actuator Saturation and Disturbances[END_REF][START_REF]Control of Uncertain Systems with Bounded Inputs[END_REF]. This condition is often adopted in order to guarantee that the control law be implementable [START_REF] Shinar | Capture Zone of Linear Strategies in Interception Problems with Variable Structure Dynamics[END_REF]. Linear control laws can be designed close to optimal ones [START_REF] Bohl | Linear Feedback vs. Time Optimal Control[END_REF]; hence, we additionally limit ourselves to the class of smooth, linear dynamical state controllers:

u(•) = w ⊤ (•)x(•) ∈ U , w = (w 1 , w 2 , ..., w n ) ⊤ , w i (•) ∈ C ∞ (0,T ) . (4)
"Rubustification" of optimal controllers is equally important, [START_REF] Chernousko | Control of Nonlinear Dynamical Systems: Methods and Applications[END_REF][START_REF] Dinuzzo | Higher Order Sliding Mode Controllers with Optimal Reaching[END_REF][START_REF] Boltyanski | The Robust Maximum Principle: Theory and Applications[END_REF]. This requirement unavoidably leads to feedback control algorithms. In this paper we are interested in nonlinear continuous robust state feedback control laws (u(t) = u f (x(t)), t > 0, u f : R n → R) such that they globally stabilize system (1) at the origin for all t > 0 and, moreover, provide feasible solutions to the optimization problem (2)-( 4). It is this class of feedback laws over which we will be searching for a suboptimal solution of the time-optimal control problem (2)-( 4) with given x 0 ∈ R n .

Yet another limitation (strictly speaking, not an intrinsic one) in the problem analyzed in this paper is the necessity of using the apparatus of linear matrix inequalities. Actually, this requirement may be thought of as the most important one, since control practice is always targeted at finding simplest and most efficient design solutions. Moreover, with this technique, the infinite-dimensional optimization problem (2)-(4) will be reduced to a finite-dimensional problem.

Finally, note that the time optimal control problem with terminal state x(T ) = x 1 := (ξ, 0, ..., 0) ⊤ ∈ R n , ξ ̸ = 0 can be easily reduced to problem (2)-(4) by change of variables x = xx 1 .

AUXILIARY CONCEPTS AND RESULTS

Finite-Time Stability

Control design problems under constraints (3) are usually referred to as finite-time control design. Problems of such type are traditionally considered over finite time horizon, while the issues of stability and robustness are kept aside, since the solution is usually turns out to be a certain openloop (feedforward) control law. Instead, in this paper we are interested in finite-time regulators, which specify a stabilizing feedback control and, on top of asymptotic stability of the closed loop system, guarantee attainment of the equilibrium in finite time [START_REF] Roxin | On Finite Stability in Control Systems[END_REF][START_REF] Bhat | Finite-time Stability of Continuous Autonomous Systems[END_REF][START_REF] Orlov | Finite Time Stability and Robust Control Synthesis of Uncertain Switched Systems[END_REF][START_REF] Polyakov | Method of Lyapunov Functions for Systems with Higher-order Sliding Modes[END_REF][START_REF] Polyakov | Stability Notions and Lyapunov Functions for Sliding Mode Control Systems[END_REF].

Let us consider a Cauchy problem for the ordinary differential equation

ẋ(t) = f (t, x(t)), t ∈ R, x(t 0 ) = x 0 , (5)
where t 0 is a number, x ∈ R n is the state vector, f : R × R n → R n is a nonlinear, continuous vector-valued function, which is locally Lipschitz in x everywhere except for the origin. Let the origin be an equilibrium point of system (5), i.e., f (t, 0) = 0.

Definition 1. The zero solution of system ( 5) is said to be finite-time stable if it is Lyapunov stable and there exists a function T : R × R n → R + such that lim t→t 0 +T (t 0 ,x 0 )

x(t, t 0 , x 0 ) = 0 for all x 0 ∈ V ⊆ R n , where x(t, t 0 , x 0 ) is the solution of the Cauchy problem (5), and V is a neighborhood of the origin, which, generally speaking, depends on t 0 .

The definition of stability formulated above almost coincides with the definition of asymptotic stability, with the only difference that the limit is considered as t tends to a certain finite number. Importantly, the requirement of the Lyapunov stability in Definition 1 obviously ensures x(t, t 0 , x 0 ) = 0 for all t ≥ t 0 + T (t 0 , x 0 ). In other words, any finite-time stable system is asymptotically stable.

The function T in Definition 1 is referred to as settling-time function of system [START_REF] Chernousko | Control of Nonlinear Dynamical Systems: Methods and Applications[END_REF]. If the set V coincides with R n , the zero solution of system (5) becomes finite-time stable in the large, or globally finite-time stable.

Following the ideas of the stability theory, a natural definition of the uniform finite-time stability can be formulated. It is important to note that uniformity is to be considered with respect to both time and the space R n , since inherent to the finite-time stability is the dependence of the settlingtime function on both the initial time instant and the initial state. In particular, if the function of ("uniform") settling time T (•) = sup t 0 ∈R T (t 0 , •) is locally bounded in a certain t 0 -independent neighborhood V of the origin, the finite-time stable system is said to be uniformly finite-time stable [START_REF] Orlov | Finite Time Stability and Robust Control Synthesis of Uncertain Switched Systems[END_REF][START_REF] Polyakov | Stability Notions and Lyapunov Functions for Sliding Mode Control Systems[END_REF]. As of today, the most comprehensive survey of the results in finite-time stability can be found in [START_REF] Polyakov | Stability Notions and Lyapunov Functions for Sliding Mode Control Systems[END_REF].

A simple example of a uniformly finite-time stable system is given by a scalar control plant embraced by the negative relay state feedback: ẋ(t) = -sign[x(t)], x(t 0 ) = x 0 ∈ R. In this case, the settling-time function has the form T (x 0 ) = |x 0 |.

Weighted Homogenous Systems

Homogeneity is a property of an object (say, a vector field) to retain its characteristics under certain stretcing/shrinkage. This property turns out to be extremely useful in many areas such as analysis of nonlinear ordinary differential equations [START_REF] Zubov | On Systems of Homogenous Differential Equations with Generalized Homogenous Righthand Sides[END_REF][START_REF] Zubov | Methods of A.M. Lyapunov and Their Applications[END_REF][START_REF] Hahn | Stability of Motion[END_REF][START_REF] Hermes | Nilpotent Approximations of Control Systems and Distributions[END_REF] and finite-time stability [START_REF] Bhat | Geometric Homogeneity with Applications to Finite-time Stability[END_REF][START_REF] Orlov | Finite Time Stability and Robust Control Synthesis of Uncertain Switched Systems[END_REF][START_REF] Levant | Homogeneity Approach to High-order Sliding Mode Design[END_REF], robustness of nonlinear control systems [START_REF] Ryan | Universal Stabilization of a Class of Nonlinear Systems with Homogeneous Vector Fields[END_REF][START_REF] Hong | H ∞ Control, Stabilization, and Input-output Stability of Nonlinear Systems with Homogeneous Properties[END_REF][START_REF] Bernuau | Verification of ISS, iISS and IOSS Properties Applying Weighted Homogeneity[END_REF], etc.

Let us consider a positive vector of weights r = (r 1 , . . . , r n

) ⊤ ∈ R n + and a so-called dilation matrix D r (λ) = diag{λ r i } n i=1 , λ ∈ R + . Clearly, for x = (x 1 , ..., x n ) ⊤ ∈ R n we have D r (λ)x = (λ r 1 x 1 , . . . , λ r i x i , . . . , λ rn x n ) ⊤ ∈ R n . Definition 2 ([12]). A function g : R n → R (respectively, a vector field f : R n → R n ) is referred to as r-homogeneous with degree m ∈ R, if the equality g(D r (λ)x) = λ m g(x) (respectively, f (D r (λ)x) = λ m D r (λ)f (x)) holds for any λ ∈ R + and any x ∈ R n .
Functions that fall under Definition 2 will be also referred to as weighted homogeneous. Homogeneous and weighted homogeneous system are often encountered in control theory. First of all note that linear systems are obviously homogeneous of degree zero with D r (λ) = λI n . Design of nonlinear algorithms for control and state identification which are based on the homogeneity property is discussed in [START_REF] Bhat | Geometric Homogeneity with Applications to Finite-time Stability[END_REF][START_REF] Polyakov | Finite-time and Fixed-time Stabilization: Implicit Lyapunov Function Approach[END_REF][START_REF] Orlov | Finite Time Stability and Robust Control Synthesis of Uncertain Switched Systems[END_REF][START_REF] Levant | Homogeneity Approach to High-order Sliding Mode Design[END_REF].

Following Definition 2, homogeneity can be detected by checking just the right-hand sides of ordinary differential equations. By knowing the degree of homogeneity, finite-time stability of the system can be established via the theorem below.

Theorem 1 ([40], Theorem 5.8 and Property 5.4). If the vector field f : R n → R n is defined in R n , continuous, and r-homogeneous with negative degree m ∈ R -, then the asymptotically stable zero solution of the system ẋ(t) = f (x(t)), t ∈ R, is globally finite-time stable. This result remains valid for homogeneous differential inclusions and generalized evolutionary equations in Banach spaces, [START_REF] Bernuau | On Homogeneity and Its Application in Sliding Mode Control[END_REF][START_REF] Orlov | Finite Time Stability and Robust Control Synthesis of Uncertain Switched Systems[END_REF][START_REF] Levant | Homogeneity Approach to High-order Sliding Mode Design[END_REF].

It is important to note that, on top of detecting finite-time stability, the homogeneity method facilitates qualitative analysis of robustness.

By robustness of a control system we usually mean its stability (in one or another sense) against exogenous disturbances and inaccuracies in the parameters of the model. In this paper, robustness is considered in the sense of input-to-state stability [START_REF] Sontag | Smooth Stabilization Implies Coprime Factorization[END_REF][START_REF] Dashkovskiy | Input to State Stability and Allied system Properties Autom[END_REF]. Consider a disturbed system

ẋ(t) = f (x(t), d(t)), t > 0, x(0) = x 0 ∈ R n , (6)
where

x(t) ∈ R n is the state vector, d(t) = (d 1 (t), ..., d p (t)) ⊤ ∈ R p , d i (•) ∈ L ∞
is the vector of exogenous disturbances, and f : R n × R p → R n is a (generally speaking discontinuous [START_REF] Bernuau | On Homogeneity and Its Application in Sliding Mode Control[END_REF]) vector field.

Definition 3 ([41]

). System ( 6) is referred to as input-to-state stable (ISS), if, for all x 0 ∈ R n and all d ∈ L ∞ , the ineuality ∥x(t,

x 0 )∥ ≤ β(∥x 0 ∥, t) + γ ( ess sup τ ∈[0,t) ||d(τ )|| )
is valid for all t ∈ R + over any solution x(t, x 0 ) of the Cauchy problem [START_REF] Dinuzzo | Higher Order Sliding Mode Controllers with Optimal Reaching[END_REF], where β ∈ KL and γ ∈ K.

A weaker notion of robustness is introduced as follows.

Definition 4 ([41]

). System ( 6) is said to be integral input-to-state stable (iISS), if for all

x 0 ∈ R n and all d ∈ L ∞ the inequality α(∥x(t, x 0 )∥) ≤ β(∥x 0 ∥, t) + t ∫ 0 γ(∥d(τ )∥)
dτ holds for all t ≥ 0 over any solution x(t, x 0 ) of system (6) for some α ∈ K ∞ , β ∈ KL, and γ ∈ K.

The theorem below establishes a link between robust stability and homogeneity.

Theorem 2 ([39]

). Let the following conditions be satisfied: 1) the zero solution of the disturbance-free (d = 0) system (6) is asymptotically stable; 2) the disturbance-free vector field f (•, 0) : R n → R n is r-homogeneous with degree m ≥min 1≤i≤n r i ;

3) there exists r = (r 1 , . . . , rp )

⊤ ∈ R p , ri ≥ 0, such that f (D r (λ)x, D r(λ)d) = λ m D r (λ)f (x, d) for all x ∈ R n , d ∈ R p , and λ ∈ R + .
Then system (6) is input-to-state stable if rmin > 0, and it is integral input-to-state stable if rmin = 0 and m ≤ 0, where it is denoted rmin = min 1≤j≤p rj .

From these results it is seen that robust and finite-time stability of homogeneous systems can be expressed in terms of a simple function of the degree of homogeneity and the vector of weights. These properties can be easily checked via elementary algebraic manipulations.

Implicit Lyapunov Functions

The implicit Lyapunov function method assumes an implicit specification of a function, for instance, in the form of an algebraic equation Q(V, x) = 0. The theorem below is an extension of the known result in [START_REF] Adamy | Soft Variable-Structure Controls: A Survey[END_REF] to the analysis of finite-time stability.

Theorem 3 ([17]). Assume there exists a continuous function

Q : R + × R n → R (V, x) ? → Q(V, x)
with the following properties: C1) Q is continuously differentiable for all V ∈ R + and all x ∈ R n \{0}; C2) for every x ∈ R n \{0} there exists

V ∈ R + such that Q(V, x) = 0; C3) lim x→0 (V,x)∈Ω V = 0 + , lim V →0 + (V,x)∈Ω ∥x∥ = 0, lim ∥x∥→∞ (V,x)∈Ω V = +∞, where Ω = { (V, x) ∈ R n+1 : Q(V, x) = 0 } ; C4) the inequality -∞ < ∂Q(V,x)
∂V < 0 holds for all V ∈ R + and all x ∈ R n \{0};

C5) for all t ∈ R + and all (V, x) ∈ Ω the following inequality holds:

∂Q(V,x) ∂x f (t, x) ≤ cV 1-µ ∂Q(V,x)
∂V , where c > 0 and 0 < µ ≤ 1 are some numbers.

Then the zero solution of system (5) is globally finite-time stable and the following estimate is valid for the settling-time function:

T (x 0 ) ≤ V µ 0 cµ , where V 0 ∈ R + : Q(V 0 , x 0 ) = 0.
Conditions C1 -C4 of Theorem 3 guarantee the uniqueness, positive-definiteness, smoothness (outside the origin), and radial unboundedness of the solution of Q(V, x) = 0 with respect to V . By the classical implicit function theorem (e.g., see [START_REF] Courant | Introduction to Calculus and Analysis[END_REF]), the partial derivative of the function V : R n → R can be computed via the formula ∂V ∂x = -

[ ∂Q ∂V
] -1 ∂Q ∂x . Hence, the condition ∂Q(V,x) ∂x f (t, x) < 0 ensures the negative definiteness of the total derivative of V , and condition C5 guarantees the finite-time stability of system (5) due to the inequality V (x(t)) ≤ -cV 1-µ (x(t)).

Introduce now the explicit Lyapunov function as

Q(V, x) := x ⊤ D r (V -1 )P D r (V -1 )x -1, (7)
where D r (λ) is the dilation matrix of the form D r (λ) = diag{λ r i } n i=1 , r = (r 1 , ..., r n ) ⊤ ∈ R n + , and P ∈ R n×n is a symmetric positive definite matrix.

This function can be thought of as a counterpart of a quadratic Lyapunov function for rhomogeneous functions. Indeed, for any fixed V = const, the set {x ∈ R n : Q(V, x) = 0} is the surface of an ellipsoid in R n . For r = (0, 5, ..., 0, 5) ⊤ , the equation Q(V, x) = 0 possesses the unique solution V = x ⊤ P x.

Corollary 1. Let a vector field f : R n → R n be r-homogeneous of degree m, with the weight vector r = (r 1 , r 2 , ..., r n ) ⊤ ∈ R n + . If there exists a matrix P ∈ R n×n which satisfies the inequalities diag(r)P + P diag(r) > 0, P > 0, (8)

z ⊤ P f (z) + f ⊤ (z)P z < 0 for z ∈ R n : z ⊤ P z = 1, (9)
then the zero solution of system ẋ(t) = f (x(t)), t > 0, is asymptotically stable, and the function Q defined by ( 7) is an implicit Lyapunov function for the system. Moreover, for m < 0 the system is finite-time stable.

Proof. I. The function Q(V, x) defined by Ineq. [START_REF] Boltyanski | The Robust Maximum Principle: Theory and Applications[END_REF] satisfies Conditions C1 -C4 of Theorem 3. Indeed, it is continuously differentiable for all V ∈ R + and all x ∈ R n . Since P > 0, the chain of inequalities

λ min (P )∥x∥ 2 max{V 1+(n-1)µ ,V } ≤ Q(V, x) + 1 ≤ λmax(P )∥x∥ 2 min{V 1+(n-1)µ ,V } guarantees that for any x ∈ R n \{0} there exist V -∈ R + and V + ∈ R + such that Q(V -, x) < 0 < Q(V + , x), while the continuity of the function Q implies the existence of V ∈ R + such that Q(V, x) = 0.
Moreover, for Q(V, x) = 0, the same chain of inequalities ensures min{V 1+(n-1)µ ,V } λ max (P ) ≤ ∥x∥ 2 ≤ max{V 1+(n-1)µ ,V } λ min (P )

; hence, Condition C3 of Theorem 3 is also fulfilled.

Since ∂Q ∂V = -V -1 x ⊤ D µ (V -1 )(diag(r)P + P diag(r))D µ (V -1 )x, Ineq. (8) implies ∂Q ∂V < 0 for all V ∈ R + and all x ∈ R n \{0}.

By the implicit function theorem, there exists a unique positive definite, smooth (outside the origin), and radially unbounded solution V : R n → R of the equation Q(V, x) = 0, which can be continued to the origin as V (0) = 0 and Q(V (x), x) = 0 for x ∈ R n \{0}.

II. Let us compute the total derivative of the function V along the trajectories of the system:

V (x) = - [ ∂Q ∂V ] -1 ∂Q ∂x f (x) = - [ ∂Q ∂V ] -1 (z ⊤ P D r (V -1 )f (x) + f (x) ⊤ D r (V -1 )P z),
where x ∈ R n \{0} z = D r (V -1 )x. The vector field f is homogeneous, i.e., λ -m D -1 r (λ)f (D r (λ)x) = f (x) for all λ ∈ R + and all x ∈ R n , where m ∈ R is the degree of homogeneity. We then have

V (x) = - [ ∂Q ∂V ] -1 V -m (z ⊤ P y + y ⊤ P z) = V 1-m z ⊤ P f (z)+f (z) ⊤ P z z ⊤ (diag(r)P +P diag(r))z .
Since Q(V, x) = 0, relations z ⊤ P z = 1 and (9) imply V (x) < 0 for x ̸ = 0.

CONTROL DESIGN

Design of Homogenous Finite-Time Controllers

Design of finite-time controllers will be accomplished by using the concept of r-homogeneity of the closed-loop system. In that case, for some r ∈ R n + and µ ∈ R + , the equality AD r (λ)x + bu(D r (λ)x) = λ -µ D r (λ)(Ax+bu(x)) is to be satisfied for all λ ∈ R + and x ∈ R n . Hence, keeping in mind the structure of the matrix A and vector b, we obtain explicit bounds on the the components of the weight vector r ∈ R n + : r i = r i+1 + µ, i = 1, 2, ..., n -1, and on the degree of homogeneity of the control function: u(D r (λ)x) = λ rn-µ u(x).

By taking r n = 1, we obtain r = (1 + (n -1)µ, 1 + (n -2)µ, ..., 1) ⊤ ∈ R n + , where µ ∈ (0, 1]. The theorem below is a simple extension of the results in [START_REF] Korobov | A General Approach to Synthesis Problem[END_REF] and [START_REF] Polyakov | Finite-time and Fixed-time Stabilization: Implicit Lyapunov Function Approach[END_REF].

Theorem 4. Assume that X ∈ R n×n and y ∈ R 1×n satisfy the linear matrix inequalities

{ AX + XA ⊤ + by + y ⊤ b ⊤ + diag(r)X + Xdiag(r) = 0, Xdiag(r) + diag(r)X > 0, X > 0, (10)
for some fixed µ ∈ (0, 1].

Then system (1) embraced by the feedback

u(V, x) = V 1-µ kD r (V -1 )x ( 11
)
with k = yX -1 , V ∈ R + and Q(V, x) = 0, where Q(V, x
) is of the form (7) with P = X -1 , is globally uniformly finite-time stable with the settling-time function

T 0 (x 0 ) = V µ 0 µ , ( 12
)
where

V 0 ∈ R + : Q(V 0 , x 0 ) = 0.
Proof. The fulfillment of conditions C1 -C4 of Theorem 3 for the implicit function Q specified by [START_REF] Boltyanski | The Robust Maximum Principle: Theory and Applications[END_REF] was established in the proof of Corollary 1. It now remains to check the satisfaction of Condition C5. Since

∂Q ∂x (Ax + bu(x)) = 2x ⊤ D r (V -1 )P D r (V -1 )(Ax + bu(x)), equalities D r (V -1 )AD -1 r (V -1 ) = V -µ A and D r (V -1 )bu(x) = V -µ bkD r (V -1 )x imply the relations ∂Q ∂x (Ax + bu(x)) = V -µ x ⊤ D r (V -1 ) ( P (A + bk) + (A + bk) ⊤ P ) D µ (V -1 )x and V (x) = - [ ∂Q ∂V ] -1 ∂Q ∂x (Ax + bu) = x ⊤ Dr(V -1 )(P (A+bk)+(A+bk) ⊤ P )Dr(V -1 )x x ⊤ Dr(V -1 )(diag(r)P +P diag(r))Dr(V -1 )x V 1-µ = -V 1-µ (x).
The last equality guarantees the finite-time stability of the closed-loop system (1), [START_REF] Bohl | Linear Feedback vs. Time Optimal Control[END_REF], and representation [START_REF] Zubov | On Systems of Homogenous Differential Equations with Generalized Homogenous Righthand Sides[END_REF] of the settling-time function.

The control law [START_REF] Bohl | Linear Feedback vs. Time Optimal Control[END_REF] represents an implicitly defined nonlinear controller whose properties are formulated in the corollary below.

Corollary 2. The implicitly defined nonlinear state feedback controller ũ(x) = u(V (x), x) with V : R n → R such that Q(V (x), x) = 0 for all x ∈ R n \{0}, has the following properties:

1) continuity in R n for µ ∈ (0, 1); 2) discontinuity only at the origin and global boundedness in R n for µ = 1;

3) r-homogeneity with degree 1µ for µ ∈ [0, 1], i.e., ũ(D r (λ)x) = λ 1-µ ũ(x) for all x ∈ R n and λ ∈ R + .

Proof. 1. The function V : R n → R explicitly specified by the equation Q(V, x) = 0 is continuously differentiable for all x ∈ R n \{0}. Moreover, V (x) → 0 as ∥x∥ → 0. Hence, the only possible point of discontinuity of the function ũ is the origin. For Q(V (x), x) = 0 we obtain

ũ2 (x) = V 2-2µ (x)x ⊤ T D r (V -1 (x))k ⊤ kD r (V -1 (x))x ≤ ≤ V 2-2µ (x)λ max (k ⊤ k)x ⊤ D r (V -1 (x))D r (V -1 (x))x ≤ ≤ V 2-2µ (x)λ max (kk ⊤ )x ⊤ D r (V -1 (x))P D r (V -1 (x))x λ min (P ) = V 2-2µ (x) λ max (k ⊤ k) λ min (P ) .
Obviously, we have ũ2 (x) → 0 as ∥x∥ → 0 and µ ∈ (0, 1), i.e., ũ is a continuous function.

2. For µ = 1 we have ũ2 (x) ≤ λmax(k ⊤ k) λ min (P ) for all x ∈ R n . To prove the discontinuity of the control input in this situation, it suffices to consider x = (0, ..., 0, x n ) ⊤ ∈ R n . In this case we have

V (x) = √ b ⊤ P b|x n | and u(x) = kb √ b ⊤ P b sign[x n ]. 3. From Q(V, D r (λ)x)=Q(λ -1 V, x) we obtain V (D r (λ)x)=λV (x) and ũ(D r (λ)x)=λ 1-µ ũ(x) by the equality V 1-µ (D r (λ)x)kD r (V -1 (D r (λ)x))D r (λ)x=λ 1-µ V 1-µ (x)kD r (λ -1 V -1 (x))D r (λ)x.
Note that the r-homogeneity property of the controller ũ clearly implies the r-homogeneity of the closed-loop system. Theorem 2 ensures the robustness of the system against various disturbances, e.g., such as measurement noises. Indeed, if ẋ = f (x) is weighted homogeneous, then ẋ = f (x + d) satisfies Theorem 2.

One of the attractive properties of the finite-time control design scheme described above is its simplicity in tuning the parameters on the basis of linear matrix inequalities; these can be solved by using various available software, e.g., Matlab.

Proposition 1. Inequalities [START_REF] Bertsekas | Dynamic Programming and Suboptimal Control: A Survey from ADP to MPC[END_REF] are feasible for all µ > 0.

Proof. Consider the following component-wise representation of the matrix X and vector y:

X =        x 1 1 x 1 2 ... x 1 n-1 x 1 n x 1 2 x 2 2 ... x 2 n-1 x 2 n-1 ... ... ... ... ... x 1 n-1 x 2 n-1 ... x n-1 n-1 x n-1 n x 1 n x 1 n-1 ... x n-1 n x n n        , x i j ∈ R, i, j = 1, 2, ..., n; y = ( y 1 y 2 ... y n-1 y n ) , y i ∈ R, i = 1, 2, ..., n.
The algebraic equation in system [START_REF] Bertsekas | Dynamic Programming and Suboptimal Control: A Survey from ADP to MPC[END_REF] can be written down in the following form:

2x i i+1 + 2[1 + µ(n -i)]x i i = 0, i = 1, 2, ..., n -1, (13)
x i+1 j + x i j+1 + [2 + µ(2n -i -j)]x i j = 0, j > i = 1, 2, ..., n -1, (14)
x i+1 n + [2 + µ(n -i)]x i n + y i = 0, i = 1, 2, ..., n -1, (15)
2x n n + 2y n = 0. ( 16
)
Let X (i 1 :i 2 ; j 1 :j 2 ) denote the block of the matrix X composed of the entries x ij satisfying i = i 1 , i 1 + 1, ..., i 2 and j = j 1 , j 1 + 1, ..., j 2 for i 1 ≤ i 2 and j 1 ≤ j 2 .

Denote next

H i = diag{1 + µ(n -1), 1 + µ(n -2), ..., 1 + µ(n -i)} and Z = Xdiag(r) + diag(r)X. Let Z (i 1 :i 2 ; j 1 :j 2 )
be the block of the matrix Z composed similarly to the block X (i 1 :i 2 ; j 1 :j 2 ) . Clearly, we have

Z (1:1; 1:1) = 2[1 + µ(k -1)]X (1:1; 1:1) , Z (1:i; 1:
i) = ( Z (1:i-1; 1:i-1) X (1:i-1; i:i) H i X ⊤ (1:i-1; i:i) H i 2[1 + µ(k -i)]x i i ) .
Let us construct a solution of ( 13)-( 16) such that the conditions X > 0 and Z > 0 be satisfied. To this end, we use the method of mathematical induction.

Basis. Let x 1 1 = α 1 , where α 1 > 0 is an arbitrary positive number. From Eq. ( 13) we obtain x 1 2 = -α 1 [1 + µ(n -1)]x 1 1 . Noting that x 1 1 = X (1:1; 1:1) > 0 and Z (1:1; 1:1) > 0, and taking x 2 2 = α 2 , we can guarantee X (1:2; 1:2) > 0 and Z (1:2; 1:2) > 0 for sufficiently large α 2 > 0.

Inductive step. Assume that for some k < n, the matrices X (1: k; 1: k) > 0 and Z (1: k; 1: k) > 0 are composed in such a way that x ii = α i ∈ R + . From Eq. ( 13) we then have x k k+1 = -α k[1+µ(n-k)], and using Eq. ( 14) we find

x i k+1 = -(x i+1 k + [2 + µ(2n -i -k)]x i k), i = 1, 2..., k -1.
Noting that X (1: k; 1: k) > 0 and Z (1: k; 1: k) > 0, take x k+1 k+1 = α k+1 to obtain X (1: k+1; 1: k+1) > 0 and Z (1: k+1; 1: k+1) > 0 for sufficiently large α k+1 > 0.

With the algorithm proposed above, a matrix X > 0 can be computed such that Z > 0 and Eqs. ( 13), ( 14) are satisfied. By specifying y k = x n n and

y i = -(x i+1 k + [2 + µ(n -i)]x i k ), i = 1, 2, ..., n -1,
at the final step ( k = n), we arrive at X > 0 and Y satisfying equalities ( 13)-( 16) and the inequality Xdiag(r) + diag(r)X > 0.

The control law [START_REF] Bohl | Linear Feedback vs. Time Optimal Control[END_REF] proposed above admits a simple implementation provided that the initial condition x(0) = x 0 ∈ R n is known. Indeed, if a function Q satisfies the conditions of Theorem 3, then the equation Q(V 0 , x 0 ) = 0 possesses a unique positive solution V 0 ∈ R + for an arbitrarily specified x 0 ∈ R n . This solution can be found numerically, for example, by using the simplest dichotomy. On the other hand, for the closed-loop system (1), [START_REF] Bohl | Linear Feedback vs. Time Optimal Control[END_REF], the function V considered is valid for all x ∈ R n \{0} V ∈ R + . On the one hand we have [START_REF] Polyakov | Finite-time and Fixed-time Stabilization: Implicit Lyapunov Function Approach[END_REF]) and T (x 0 ) ≤ T . On the other hand, the equality Q(V, x) = 0 ensures

u 2 (t) = V 2-2µ (t)x ⊤ (t)D µ (V -1 (t))k ⊤ kD µ (V -1 (t))x(t) ≤ ≤ V 2-2µ 0 x ⊤ (t)D µ (V -1 (t))k ⊤ kD µ (V -1 (t))x(t) ≤ (µT ) 2-2µ µ x ⊤ D µ (V -1 (t))k ⊤ kD µ (V -1 (t))x, since V (x(t)) ≤ V 0 for t ∈ [0, T (x 0 )] (see
u 2 0 x ⊤ D µ (V -1 )P D µ (V -1 )x = u 2 0 . Therefore, u 2 (V (t), x(t)) ≤ u 2 0 for t ∈ [0, T (x 0 )].
With the corollary above, a finite-time controller with a pre-specified upper bound on the magnitude of the control input can be designed. For µ = 1, Ineq. [START_REF] Korobov | Metod funktsii upravlyaemosti (Controllability Function Method)[END_REF] no longer depends on T , so that the control input is globally bounded.

To summarize, the following finite-dimensional optimization scheme can be exploited to design a suboptimal finite-time regulator:

T → min X∈R n ,y∈R 1×n ,µ∈(0,1]
subject to [START_REF] Bertsekas | Dynamic Programming and Suboptimal Control: A Survey from ADP to MPC[END_REF], ( 18), [START_REF] Korobov | Metod funktsii upravlyaemosti (Controllability Function Method)[END_REF]. [START_REF] Boyd | Linear Matrix Inequalities in System and Control Theory[END_REF] Note that in the scalar case n = 1, the controller design procedure proposed above leads to the optimal solution of problem ( 2)-(3). Indeed, with µ = 1 and n = 1, we have

V (x) = √ P |x|, P ∈ R 1×1 , x ∈ R 1 , and u opt (x) = -u 0 sign[x].
For any fixed numbers µ ∈ (0, 1] and T ∈ R + , the matrix inequalities ( 10), ( 18), ( 19) become linear and can be easily solved using standard software.

To solve this problem for a fixed µ, an approach in [START_REF] Tuan | Advanced Global Optimization Algorithms for Parameterized LMIs[END_REF] can be used, and the minimization with respect to the parameter µ can be accomplished via use of any known methods of scalar gradient-free optimization (for example, with the fminsearch routine in Matlab).

The gap between the proposed suboptimal solution and the optimal one can hardly be evaluated analytically in the general case. By [START_REF] Zubov | On Systems of Homogenous Differential Equations with Generalized Homogenous Righthand Sides[END_REF], the settling time depends on the Lyapunov function, which is specified implicitly and does not admit a closed-form representation in the majority of the problems.

ROBUST REALIZATION OF SUBOPTIMAL FINITE-TIME CONTROLLERS

As it was noted, the value of the Lyapunov function along the trajectory of the disturbance-free closed-loop system can be easily computed via the formula

V (t) = (V µ 0 -µt) 1/µ , t ∈ [0, V µ 0 /µ],
where V 0 ∈ R + : Q(V 0 , x 0 ) = 0, and a suboptimal linear dynamic regulator can be specified by [START_REF] Bohl | Linear Feedback vs. Time Optimal Control[END_REF] for V = V (t). However in practice, the original system (1) is subject to parametric uncertainties and exogenous disturbances; this often leads to considerable degradation of the performance of optimally designed control systems. Below we formulate two corollaries to Theorem 4 which will serve as the basis for the development of a practical realization scheme for finite-time regulators. These regulators will be designed in the form of a linear feedback with coefficients that change at discrete time instants.

Corollary 5. Let the finite-time regulator u(V, x) be designed according to Theorem 4; then the control u 0 (x) = u(V 0 , x) represents a stabilizing linear static regulator for system (1) for any fixed

V 0 ∈ R + .
Hence, the function Ṽi (x(t)) exponentially decays along the trajectory of the closed-loop system (1) on the time segment [t i , t i+1 ); i.e., Ṽ (x(t i+1 )) ≤ e

-α V i (t i+1 -t i ) Ṽ (x(t i )). Therefore we have Q(V (t i ), x(t)) = x ⊤1 (t)D r (V -1 (x(t i )))P D r (V -1 (x(t i )))x(t) -1 = Ṽi (x(t)) -1 < < Ṽi (x(t i )) -1 = Q(V i (x(t i )), x(t i )) = 0 = Q(V (x(t)), x(t)) for all t ∈ (t i , t i+1 ].
For any given x ∈ R n \{0}, the function Q(V, x) is monotonically decreasing for all V ∈ R + (see Property C4 in Theorem 3). Hence, the inequality

Q(V (x(t i )), x(t)) < Q(V (x(t)), x(t)) ∀t ∈ (t i , t i+1 ] implies V (x(t)) < V (x(t i
)) for all t ∈ (t i , t i+1 ], i.e., the sequence {V (x(t i ))} ∞ i=1 is monotonically decreasing. Moreover, the inequality V (x(t)) ≤ V (x(0)) holds for all t > 0, i.e., the sero solution of the closed-loop system is Lyapunov stable.

Since the function V (x) is positive definite, the monotonically decreasing sequence {V (x(t i ))} ∞ i=1 tends to a limit. Let us show it is equal to zero. Assuming converse, lim i→∞ V (x(t

i )) = V * > 0, we obtain ∀ε > 0 ∃N = N (ε) : |V (x(t i )) -V * | < ε ∀ i ≥ N.
Since the control input u(V, x) is a continuous function for all x ∈ R n and all V ∈ R + , we have

|u(V (x(t i )), x)-u(V * , x)| = |V 1-µ (x(t i ))kD r (V -1 (x(t i )))x-(V * ) 1-µ kD r (V -1 * )x| ≤ γ(ε)∥x∥ ∀i ≥ N,
where γ(•) ∈ K. This means that for t > t N , the closed-loop function can be written in the form ẋ

= Ax + b(k * x + δ(t)x), where k * = k(V * ) 1-µ kD r (V -1
* ) and ∥δ∥ ≤ γ(ε). Corollary 5 guarantees that the matrix A + bk * is Hurwitz; then for a sufficiently small ε > 0 the zero solution of this system is asymptotically stable. In turn, this means that lim i→∞ V (x(t i )) = 0. The Lyapunov stability shown above implies asymptotic stability of the zero solution of the closed-loop system (1), [START_REF] Polyak | Upravlenie lineinymi sistemami pri vneshnikh vozmushcheniyakh: tekhnika lineinykh matrichnykh neravenstv (Control of Linear Systems Subject to Exogenous Disturbances: The Linear Matrix Inequalitiy Technique)[END_REF].

II. If lim i→∞ t i = t * , then for all t > t * we have u(x) = u(V (t * ), x), and Corollary 5 ensures the desired asymptotic stability.

Corollary 6 guarantees that the discrete-time piecewise-linear realization of the finite-time regulator retains the stability of the closed-loop system independently of the sampling interval.

For a fixed x i = x(t i ), i = 1, 2, ..., the solution of the scalar equation Q(V, x i ) = 0 can be found numerically; hence, in practice, the regulator thus obtained can be implemented with the use of a digital computing device (microcontroller) which changes the coefficients of the regulator at discrete time instants based on the current measurements. Recall that, by Property C4 in Theorem 3, we have ∂Q ∂V < 0 for all x ∈ R n \{0} and all V ∈ R + ; i.e., the equation Q(V, x i ) = 0 always has a unique solution with respect to V ∈ R + . This solution can be found by dichotomy or by the Newton method as

V [k+1] = V [k] -Q(V [k] , x i ) [ ∂Q(V [k] ,x i ) ∂V ] -1 , k = 1, 2, ..., where V [k] ∈ R + is the scalar variable, x i ∈ R n is a fixed vector, and V [k] → V as k → ∞.
To avoid infinitely large values of the coefficients of the regulator, the quantity V is to be bounded from below by a certain parameter V min ∈ R + .

A NUMERICAL EXAMPLE

Let us consider system (1) for n = 2 under the constraint |u| ≤ 1. Discontinuous time-optimal regulator is known [START_REF] Chernousko | Control of Nonlinear Dynamical Systems: Methods and Applications[END_REF] to have the following form:

u opt (x 1 , x 2 ) = -sign ( x 2 + √ 2|x 1 |sign[x 1 ]
) .

The stabilizing finite-time regulator [START_REF] Bohl | Linear Feedback vs. Time Optimal Control[END_REF] obtained by solving the finite-dimensional optimization problem [START_REF] Boyd | Linear Matrix Inequalities in System and Control Theory[END_REF] for µ = 1 and x 0 = (1, 0), has the following parameters: Numerical simulation of the closed-loop model was performed by the explicit Euler method with fixed step, and the computational implementation of the finite-time regulator was performed by dichotomy.

The results of numerical experiments for the sampling interval h = 0.001 and V min = 0.001 are depicted in Fig. 1. As expected, the optimal discontinuous regulator demonstrates a better transient time; however the comparison of the algorithms for a bigger sampling time testifies to a higher robustness of the suboptimal finite-time regulator. Figure 2 depicts the results of simulations for h = 0.05 and V min = 0.05. Such a drawback of discontinuous time-optimal regulators is well know as the so-called chattering effect [START_REF] Utkin | Sliding Mode Control in Electro-Mechanical Systems[END_REF]. Chattering emerges in time-optimal systems exploiting sliding mode control [START_REF] Dinuzzo | Higher Order Sliding Mode Controllers with Optimal Reaching[END_REF]. The sampling time h ≥ 0.05 is natural in many control applications, for instance, such as mobile robots. Indeed, in autonomous mobile systems, the computational resource is largely used for image processing, positioning, calculation of the trajectories of motion, etc., and it is only a small portion of it which is spent for producing control inputs.

CONCLUSION

In this paper we proposed a robust finite-time control design algorithm for plants described by chains of integrators; the implicit Lyapunov function method was adopted as the principal tool. The computational procedure for the minimization of the transient time in the closed-loop system was formulated as a semidefinite program. An algorithm for practical realization of the implicit finite-time regulator was also developed. The main drawback of the proposed control scheme is that it can be implemented only with the use of digital devices. However, keeping in mind the current level of electronics, this drawback does not seem to be crucial for the successful practical use of the proposed finite-time controllers. The main advantage of the approach, which is confirmed by numerical simulations, is a much higher degree of robustness as compared to time-optimal solutions implemented in the form of static state feedback.

  (-5.2511 -3.0000).

Fig. 1 .

 1 Fig. 1. Simulation results for h = 0.001. 1: Optimal discontinuous regulator; 2: Suboptimal finite-time regulator.

Fig. 2 .

 2 Fig. 2. Simulation results for h = 0.05. 1: Optimal discontinuous regulator; 2: Suboptimal finite-time regulator.

POLYAKOV as function of time can be found as the solution of the Cauchy problem V (t) = -V 1-µ (t), t > 0, V (0) = V 0 (see proof of Theorem 4), hence, it admits the following closed-form representation:

Clearly, the linear dynamic feedback u(•) = w ⊤ (•)x(•) obtained in such a way (here, w(•) = V 1-µ (•)kD µ (V -1 (•))), satisfies constraints (3), [START_REF] Lasserre | Nonlinear Optimal Control: Numerical Approximations via Moments and LMI-Relaxations[END_REF].

In the sections to follow we propose an alternative scheme of implementation of the proposed control algorithm; it is motivated by robustness considerations.

Suboptimal Finite-Time Controllers

In order to solve the time-optimal control problem in the class of finite-time regulators, one has to minimize the quantity T = V µ 0 /µ subject to the constraint u(•) ∈ U , where the control u is defined by [START_REF] Bohl | Linear Feedback vs. Time Optimal Control[END_REF].

Corollary 3. Assume that the set of LMIs (10) together with

where X ∈ R n×n and y ∈ R 1×n , is feasible for some µ ∈ (0, 1], x 0 ∈ R n \{0}, and T ∈ R + .

Then the settling-time function of the closed-loop system (1), [START_REF] Bohl | Linear Feedback vs. Time Optimal Control[END_REF] satisfies the inequality T 0 (x 0 ) ≤ T , where x 0 ∈ R n is given. [START_REF] Courant | Introduction to Calculus and Analysis[END_REF] guarantees the fulfillment of the following relation:

and by Theorem 4 we obtain

The minimization of the parameter T ∈ R + subject to constraints [START_REF] Bertsekas | Dynamic Programming and Suboptimal Control: A Survey from ADP to MPC[END_REF], [START_REF] Courant | Introduction to Calculus and Analysis[END_REF], yields the minimal settling time of the closed-loop system (1), [START_REF] Bohl | Linear Feedback vs. Time Optimal Control[END_REF] with initial condition x(0) = x 0 . Without any constraints on the magnitude of the control input, the settling time T 0 (x 0 ) can be made arbitrarily small. Indeed, let the pair (y 0 , X 0 ) satisfy the matrix inequalities [START_REF] Bertsekas | Dynamic Programming and Suboptimal Control: A Survey from ADP to MPC[END_REF]; then y = αy 0 , X = αX 0 satisfy the same inequalities for any α ∈ R + . Since X 0 > 0, for any T > 0 and any x 0 ∈ R n \{0} there exists α ∈ R + such that inequality (18) is satisfied.

Corollary 4. Assume that the matrix inequalities (10), [START_REF] Courant | Introduction to Calculus and Analysis[END_REF]

are feasible for some µ ∈ (0, 1], T ∈ R + , x 0 ∈ R n , and u 0 ∈ R + , where X ∈ R n×n and y ∈ R 1×n . Then the magnitude of the control input in the closed-loop system (1), ( 11) is bounded from above: |u(V (x(t)), x(t))| ≤ u 0 for all t ∈ [0, T 0 (x 0 )].

Proof. Using the Schur complement, Ineq. ( 19) writes (µT ) 2-2µ µ u 2 0 y ⊤ y ≤ X. Taking X = P -1 and y = kP -1 into account, we obtain (µT )

2-2µ

µ k ⊤ k ≤ u 2 0 P , so that the inequality (µT )

Proof. Rewrite the matrix inequality AX + XA + by + y ⊤ b ⊤ + diag(r)P + P diag(r) = 0 with X = P -1 and k = yX -1 in the form P A + A ⊤ P + P bk + k ⊤ b ⊤ P + diag(r)P + P diag(r) = 0.

We then have

or, equivalently,

where P 0 > 0 and

). Since diag(r)P + P diag(r) > 0, we have diag(r)P 0 + P 0 diag(r) > 0, which means that u 0 (x) = u(V 0 , x) = k 0 x is a stabilizing linear static controller for system (1), and Ṽ (x) = x ⊤ P 0 x is the corresponding Lyapunov function for the closed-loop system.

. . , be an arbitrary strictly increasing sequence of time instants and let the function u(V, x) be defined according to Theorem 4.

Then the zero solution of system (1) with the piecewise-linear control

where V i > 0 : Q(V i , x(t i )) = 0, is asymptotically stable.

Proof. I. We first consider the case lim i→∞ t i = +∞. Let V (•) be a positive definite and radially unbounded Lyapunov function specified implicitly by the equation Q(V, x) = 0. We prove that the sequence {V (x(t i ))} ∞ i=1 is monotonically decreasing and tends to zero. Clearly, this property ensures the convergence of the trajectory of the closed-loop system to the origin. Let us consider the segment t ∈ [t i , t i+1 ) and the quadratic function Ṽi (x) = x ⊤ P i x, where Corollary 5), where k i = V 1-µ (x(t i ))kD r (V -1 (x(t i ))). We thus obtain d Ṽi (x(t)) dt = x ⊤ (t)(P i A +

Similarly to the proof of Corollary 5 we have

(diag(r)P i + diag(r)P i ) = 0.

Since diag(r)P i + diag(r)P i > 0, there exists a number α ∈ R + such that diag(r)P i + diag(r)P i ≥ αP i . Then d Ṽi (x(t)) dt ≤ -α V (x(t i )) Ṽi (x(t)) for t ∈ [t i , t i+1 ).


Amine El Kouhen
email: elkouhen@encs.concordia.ca

Abdelouahed Gherbi
email: abdelouahed.gherbi@etsmtl.ca

Cédric Dumoulin
email: cedric.dumoulin@univ-lille1.fr

Ferhat Khendek
email: khendek@encs.concordia.ca

On the Semantic Transparency of Visual Notations: Experiments with UML

Keywords: Visual Languages, UML, Semantic Transparency, Crowdsourcing

Graphical notations designed by committees in the context of standardization bodies, like Object Management Group (OMG), are widely used in the industry and academia. Naive users of these notations have limited background on visualization, documentation and specification of workflows, data or software systems. Several studies have pointed out the fact that these notations do not convey any particular semantics and their understanding is not perceptually immediate. As reported in these studies, this lack of semantic transparency increases the cognitive load to differentiate between concepts, slows down the learning and comprehension of the language constructs. This paper reports on a set of experiments that confirm the lack of semantic transparency of the Unified Modeling Language (UML) as designed by OMG and compares this standard to alternative solutions where naive users are involved in the design of the notations to speed-up the learning of these languages to new users.

Introduction

Over the past three decades, visual languages have been gaining in popularity. Several of these languages, such as the Unified Modeling Language (UML) have been designed by standardization bodies involving different contributors, such as language experts, tool vendors, (expert) users, etc. As reported in [START_REF] Moody | Evaluating the visual syntax of uml: An analysis of the cognitive effectiveness of the uml family of diagrams[END_REF] these languages, we refer to as committee-designed languages, have been developed in a bottom-up approach by reusing existing notations and through consensus among the experts. As in [START_REF] Moody | Evaluating the visual syntax of uml: An analysis of the cognitive effectiveness of the uml family of diagrams[END_REF][START_REF] Morris | Uml: An evaluation of the visual syntax of the language[END_REF] we believe that this is not the best approach, especially when the target audience includes naive users.

Several observations on visual languages have been made over time. The current development process strongly emphasizes the domain conceptualization (i.e. building the abstract syntaxes) and often relegates the visual notations (concrete syntaxes) and their semantic transparency as secondary products (byproducts). However, the visual notation is the first contact of the users with the modeling language and its semantic transparency plays a crucial role in its acceptance. The current development process is criticized by research in diagrammatic reasoning, which shows that the form of representations has an equal, if not greater, influence on cognitive effectiveness as their content [START_REF] Larkin | Why a diagram is (sometimes) worth ten thousand words[END_REF][START_REF] Siau | Informational and computational equivalence in comparing information modelling methods[END_REF]. A major incentive for using visual notations is the widely-held belief that they convey information more effectively than text, especially to novices [START_REF] Britton | The untrained eye: How languages for software specification support understanding in untrained users[END_REF]. Committee-designed visual notations can sometimes be very distant from semantic concepts they represent. As reported in [START_REF] Moody | Evaluating the visual syntax of uml: An analysis of the cognitive effectiveness of the uml family of diagrams[END_REF][START_REF] Genon | Analysing the cognitive effectiveness of the bpmn 2.0 visual notation[END_REF][START_REF] Moody | An evaluation of i* visual syntax[END_REF] this lack of semantic transparency increases the cognitive load to differentiate between concepts and slows down both the recognition and the learning of the language constructs. In [START_REF] Dobing | How uml is used[END_REF], the authors suggest that the difficulty of understanding many of UML notations "supports the argument that the UML may be too complex". The authors in [START_REF] Moody | Evaluating the visual syntax of uml: An analysis of the cognitive effectiveness of the uml family of diagrams[END_REF][START_REF] Genon | Analysing the cognitive effectiveness of the bpmn 2.0 visual notation[END_REF][START_REF] Moody | An evaluation of i* visual syntax[END_REF] evaluated the visual syntax of several committee-designed languages using a set of evidencebased principles for designing cognitively effective visual notations. The analysis reveals some serious flaws in the notation in terms of cognitive effectiveness of these languages, which is defined as the speed, ease and accuracy with which a representation can be processed by the human mind [START_REF] Larkin | Why a diagram is (sometimes) worth ten thousand words[END_REF].

In this paper, we ask a rather simple question: to design notations that are understandable by new users, why not involve them in the notation development process? If involving end-users in the development of software systems (e.g. participatory design [START_REF] Muller | Participatory design[END_REF], user-centred design) is working well, why this should not also be the case for graphical notations? The purpose is not to make modeling languages understable without learning, but to speed-up the learning and comprehension of the language constructs and reducing misinterpretations due to the notations complexity.

For this purpose we conduct a set of experiments on UML involving endusers. Some of these experiments have been proposed and applied to another language in [START_REF] Caire | Visual notation design 2.0: Towards user comprehensible requirements engineering notations[END_REF]. The main difference is our comparison between the outcome of these experiments and the standard UML notations. We have also used as input for this comparison a set of notations created by experts in cognitive sciences according to the Physics of Notations theory, which was not the case in [START_REF] Caire | Visual notation design 2.0: Towards user comprehensible requirements engineering notations[END_REF]. On the other hand, [START_REF] Caire | Visual notation design 2.0: Towards user comprehensible requirements engineering notations[END_REF] has used the recognition experiment which was not necessary in our process.

Because of space limitations, we selected only a set of visual elements of UML. We believe this set represents a good sample of UML diagrams widely used and easily understandable without deep technical background. For instance, class, statechart and use-case diagrams are the most widely used UML diagrams by non-experts users [START_REF] Reggio | Who knows/uses what of the uml: A personal opinion survey[END_REF] and are included in this study. The other diagrams, which are created and used only by system designer experts in their domains and without direct impact to other stakeholders are out of the scope of this study.

The goal of this paper is not to redefine the visual syntax of UML but to show the importance of involving end-users in the design of visual notations. We show the importance of involving end-users actively in the notations design process as co-designers rather than as passive consumers. The broader goal of this paper is to raise awareness about the importance of the semantic transparency in the acceptance of a modeling language, which has historically received little attention.

Background and Related Research

One of the main advantages behind the use of modeling languages is their ability to provide to their target users a set of concrete artifacts (visual notations) that can directly express related domain abstractions (concepts) in a concise, complete and unambiguous way [START_REF] Guizzardi | Ontology-based evaluation and design of domain-specific visual modeling languages[END_REF]. According to [START_REF] Moody | Evaluating the visual syntax of uml: An analysis of the cognitive effectiveness of the uml family of diagrams[END_REF], visual representations have greater effect on understanding and performance than their content.

Existing approaches for designing visual notations consist of proposing symbols and voting on them (i.e. expert consensus). For example, in UML diagrams, symbols are conventional shapes on which iconic markers are added. However, symbol shapes seem not to convey any particular semantics: there is no explicit rationale to represent a Class as a rectangle, an action as a rounded rectangle and a use case as an ellipse. The differentiation of UML notations is not perceptually immediate, it is purely conventional. According to [START_REF] Petre | Why looking isn't always seeing: Readership skills and graphical programming[END_REF], to have an unambiguous modeling language its symbols should provide cues to their meaning. Semantically direct representations reduce cognitive load: their meaning can be perceived directly or easily. This kind of representations speeds-up concepts recognition, especially for novices [START_REF] Britton | The untrained eye: How languages for software specification support understanding in untrained users[END_REF][START_REF] Masri | Using iconic graphics in entity-relationship diagrams[END_REF]. According to [START_REF] Caire | Visual notation design 2.0: Towards user comprehensible requirements engineering notations[END_REF], current visual notation design practice is characterised by: -An unselfconscious design approach [START_REF] Alexander | Notes on the synthesis of form[END_REF]: there are no explicit principles for designing visual notations [START_REF] Moody | The "physics" of notations: Toward a scientific basis for constructing visual notations in software engineering[END_REF]. -Lack of design rationale [START_REF] Lee | Design rationale systems: understanding the issues[END_REF]: symbols are chosen without any evidence-based decisions or rational justification [START_REF] Hitchman | The details of conceptual modelling notations are important[END_REF]. -Small forms variations: similar geometrical shapes are used for different purposes [START_REF] Novick | The importance of both diagrammatic conventions and domainspecific knowledge for diagram literacy in science[END_REF]. Without selfconscious design principles, the range of symbols is limited by the imagination of the design team [START_REF] Moody | The "physics" of notations: Toward a scientific basis for constructing visual notations in software engineering[END_REF]. -Lack of involvement of the target audience: notations design decisions are made exclusively by experts, without the involvement of the target audience. For this reason, we propose our experimental process, which uses endusers (target audience) suggestions as inputs into the language design process made by experts.

Physics of Notations

On the whole, the most complete and referenced work on the assessment of visual notations is probably the Physics of Notations theory [START_REF] Moody | The "physics" of notations: Toward a scientific basis for constructing visual notations in software engineering[END_REF] of Moody, which is exclusively devoted to the design, evaluation, comparison and improvement of visual notations. In this work, Moody establishes a set of nine principles defined from theory and empirical evidence and obtained from different disciplines such as: cognitive and perceptual psychology, graphic design, communication theory, cartography, etc. Each of the principles of the Physics of Notations contains: design strategies, which may contribute towards improving visual notations regarding this principle; a different evaluation procedure or metric that can be used to compare different notations, and examples of notations that satisfy or violate the principle. These nine principles are:

1. Visual Expressiveness: use the full capacities of visual variables. The seminal work in the graphical communication field is Jacques Bertin's Semiology of Graphics [START_REF] Jacques | Semiology of graphics : diagrams, networks, maps[END_REF]. Bertin identified eight elementary visual variables, which can be used to graphically encode information. These are categorized into planar variables (the two spatial dimensions x, y) and retinal variables (features of the retinal image).

The set of visual variables define a vocabulary for graphical communication: a set of atomic building blocks that can be used to construct any graphical representation. Different visual variables are suitable for encoding different types of information (Fig. 1). The choice of visual variables has a major impact on cognitive effectiveness as it affects both speed and accuracy of interpretation [START_REF] Cleveland | Graphical perception: Theory, experimentation, and application to the development of graphical methods[END_REF][START_REF] Lohse | A cognitive model for understanding graphical perception[END_REF][START_REF] Winn | An account of how readers search for information in diagrams[END_REF]. 2. Semiotic Clarity: According to [START_REF] Goodman | Languages of Art: an approach to a theory of symbols[END_REF], there must be a one-to-one correspondence between elements of the language and graphical symbols.

The Semiotic Clarity's principle, maximises expressiveness by eliminating the deficit when a domain concept is not represented by any representation and reduces ambiguity by eliminating symbol overload (multiple domain concepts are represented by one representation).

UML visual notation violates the semiotic clarity principle. Many of the diagrams that need to be understandable by everyone (e.g. Structural diagrams) contain high levels of symbol redundancy and symbol overload. For example, of the 33 symbols commonly used on class diagram there are 5 synographs (15%), 20 homographs (61%) and 2 symbol excesses (6%). This assessment was confirmed when we proposed in [START_REF] Kouhen | Spécification d'un métamodèle pour l'adaptation des outils UML[END_REF] a framework to specify and reuse visual languages. It turned out that we can reuse up to 71% of UML notations, which represents a high level of redundancy in this language and thus ambiguity. Symbols are called homographs if they have zero visual distance (i.e. they have identical values for all visual variables) but represent different semantic constructs. Thus, in UML the majority of graphical conventions used to mean different things. For example, in Class Diagrams, the same graphical symbol can be used to represent objects, classes, interface and attributes. Different types of relationships can also be represented using the same graphical convention e.g. package merges, package imports and dependencies are all represented using dashed arrows. These notations are differentiated only by textual stereotypes. However, text relies on sequential cognitive processes, which is an inefficient way to differentiate symbols. 3. Principle of Perceptual Discriminability: different symbols should be distinguishable from each other. Discriminability is a mental process that consists of symbols segregation [START_REF] Winn | An account of how readers search for information in diagrams[END_REF][START_REF] Palmer | Rethinking perceptual organization: The role of uniform connectedness[END_REF] from the background. Then symbols discrimination from each other. This differentiation relies on variations of visual variables between symbols [START_REF] Genon | Analysing the cognitive effectiveness of the bpmn 2.0 visual notation[END_REF]:

-Shape plays the main role in this process since it represents the first concern on which we classify objects in the real world [START_REF] Biederman | Recognition-by-components: A theory of human image understanding[END_REF]. In UML, the notations differ on only a single visual variable (shape) and the values chosen are very close together: all shapes are either rectangles or rectangle variants. Given that experimental studies show that rectangles and diamonds are often confused by naive users in Entity/Relation diagrams [START_REF] Nordbotten | The effect of graphic style on data model interpretation[END_REF]. -Some of the symbols have zero visual distance (homographs) and are differentiated by labels or typographical characteristics. It is the case of most of UML links, which have identical shapes but differentiated only by textual stereotypes (Fig. 3). However, according to [START_REF] Moody | Evaluating the visual syntax of uml: An analysis of the cognitive effectiveness of the uml family of diagrams[END_REF]: text is an inefficient way to differentiate between symbols as it relies on slower cognitive processes. -Colour is the most performant and cognitively expressive visual variable. The human visual system can quickly and accurately distinguish between them [START_REF] Winn | An account of how readers search for information in diagrams[END_REF]. However, colours are prohibited in UML: The use of colours is up to tools vendors. 4. Principle of Semantic Transparency: using visual representations whose appearances suggest their meaning. We will focus on this principle when we propose our experimental process. We believe that involving target audience into design process may improve this criterion. Indeed, these principles have already been used in several works to evaluate and improve other visual committee-designed languages such as i* [START_REF] Moody | An evaluation of i* visual syntax[END_REF], Business Process Modeling Notation (BPMN) [START_REF] Genon | Analysing the cognitive effectiveness of the bpmn 2.0 visual notation[END_REF] and UML [START_REF] Moody | Evaluating the visual syntax of uml: An analysis of the cognitive effectiveness of the uml family of diagrams[END_REF]. In the next section, we reuse the alternative notation proposed by [START_REF] Moody | Evaluating the visual syntax of uml: An analysis of the cognitive effectiveness of the uml family of diagrams[END_REF], which is based on these nine principles.

Experiments on UML Semantic Transparency

This section summarizes a set of related experiments applied to UML Visual Syntax. The experiments and the workflow are shown in Fig. 4. A similar experimental process have been proposed and applied to another language in [START_REF] Caire | Visual notation design 2.0: Towards user comprehensible requirements engineering notations[END_REF]. In this paper, we reused the Experiments 1, 2, 3 and 4 from [START_REF] Caire | Visual notation design 2.0: Towards user comprehensible requirements engineering notations[END_REF]. As mentioned earlier, the main difference is our comparison between the outcome of these experiments and the standard UML notations. We also used as input for this comparison, a set of notations created by experts in cognitive sciences according to the Physics of Notations theory which is not the case in [START_REF] Caire | Visual notation design 2.0: Towards user comprehensible requirements engineering notations[END_REF]. In [START_REF] Caire | Visual notation design 2.0: Towards user comprehensible requirements engineering notations[END_REF], authors have used the recognition experiment, which is not the case in our process. As mentioned in the introduction, we limit these experiments to a few elements of UML visual syntax. The purpose is not to redefine the visual syntax of UML but to show the importance of involving end-users into the design decisions made generally by experts. This experimental workflow combines quantitative and qualitative research methods: Experiments 1, 2, 3 primarily use qualitative methods, while study 4 uses quantitative methods. The used data is primarily in the form of pictures (drawings). The quantitative studies measure the interpretation/recognition accuracy in combination with psychometric scales (for rating the cognitive difficulty of tasks). More detailed data on participants artifacts, samples, results as well as the coded data set and the statistical scripts are available in [START_REF] Kouhen | Semantic transparency experiment artifacts[END_REF].

Symbolization experiment

In this experiment, "naive" participants imagined and drew symbols for UML concepts, a task normally reserved for experts. There were 64 participants in this experiment, all have background in Object-Oriented concepts. They had no previous knowledge of modeling languages in general or UML in particular: this was a requirement for participation in the study (inclusion criterion), to ensure participants were truly naive. UML regular users would not have been suitable participants, due to their technical orientation and knowledge (i.e. the curse of knowledge [START_REF] Heath | Made to Stick: Why Some Ideas Take Hold and Others Come Unstuck[END_REF]).

Each participant was provided with a two-page questionnaire that consists of a table of constructs (we chose twelve concepts, which are frequently used in software engineering : Class, Interface, Enumeration, Instance Specification, Component, Signal, Model, Package, Dependency, Merge, Import and Substitution), their definitions, and an empty cell in which participants were instructed to draw the construct.

Participants were asked to draw the constructs in the order in which they appeared. They were instructed to produce drawings that they felt most expressive (conveyed better the meaning of the construct). They were instructed to draw as simple as possible and that the quality of drawings wasn't important: the most important thing was to represent clearly and unambiguously the meaning of the construct. The participants produced a total of 749 drawings with a response rate of 97.5% for a set of twelve UML concepts, which was a high response rate given the known difficulty in "concretizing" [START_REF] Jones | Stereotypy in pictograms of abstract concepts[END_REF] UML abstract concepts. Instance Specification (6.25%), Interface (4.68%), Class (3.13%) and Model (3.13%) received the highest number of non-responses, which is more likely to be the case for such abstract concepts. Enumeration, Signal and Package receiving less than 1% (only 1 non-response out of 64).

Stereotyping analysis

In this step, we analysed the results of Experiment 1 and identified the most common symbols produced for each UML concept. These defined the stereotype symbol sets.

The analysis was conducted by three volunteers. It was done by looking at similarity of drawings. The drawings produced in Experiment 1 were used as input for this experiment. Three copies were made of the drawings to conduct this task independently.

We used the judges' ranking method [START_REF] Jones | Stereotypy in pictograms of abstract concepts[END_REF], is an approach for reaching convergence on a set of categories. In the first step, each judge categorized the drawings produced for each concept by sorting them into categories based on their similarity (pattern-matching), following the approach described in [START_REF] William | Population stereotypy in code design[END_REF].

Then, they compared their choices (categories) for each concept and agreed on a common set of categories. Finally, they selected for each concept, a set that consists of a drawing from each category (the stereotypical category), resulting in a stereotypical set for each concept (twelve in total).

Prototyping experiment

For each evaluated concept, the participants studied the stereotypical sets selected in Experiment 2 and identified the "best" representation. These defined the prototype symbol set. 2. Degree of prototypy 40 naive users participated in this experiment, all undergraduate students in computer science from multiple cultural backgrounds (different universities in Canada, France, Morocco, Algeria, Indonesia and Jordan). We used a different sample population from Experiment 1 but drawn from the same underlying population. It would not have been accurate to use the same participants as in Experiment 1, as their judgements may have been biased by their own drawings.

We conducted this experiment using a form, which consists of a table showing the name and the definition of each concept with the candidate drawings (representatives from each category identified in the stereotyping study). Participants were asked to select the most expressive drawing for each concept (regardless on the aestetic the drawing). The order of the concepts and the position of the drawings were randomized in the forms to avoid sequence effects.

The output of this experiment was a set of 12 prototypical drawings (one for each evaluated UML concept).

Table 2 shows the Degree of prototypy i.e. percentage of participants who rated the prototype drawing as the best. For all concepts, there was a high level of consensus among judgements of prototyping (43.67% in average). The highest score was for Enumeration, which achieved more than 72% agreement, and lowest for Class and Model, which achieved less than 30% agreement.

Semantic Transparency experiment

For this experiment, naive users were asked to infer the meaning of symbols from their appearance alone. The symbols were from one of 3 symbol sets, two designed by experts (the standard UML notation and the notation designed following Physics of Notations principles as explained in [START_REF] Moody | Evaluating the visual syntax of uml: An analysis of the cognitive effectiveness of the uml family of diagrams[END_REF]) and those designed by naive end-users (the prototype symbols set from Experiments 3).

There were 120 participants, all undergraduate students in computer sciences from several universities. As in studies 1 and 3, the participants had no prior knowledge of software modeling languages or UML, so were truly naive.

There were three experimental groups (composed by 40 participants for each of them), corresponding to different levels of input:

1. Standard UML notations: official symbols from UML specification (unselfconscious design). 2. UML notations designed according Physics of Notations theory (selfconscious design) called PoN in table 3. The details of this notation are available in [START_REF] Moody | Evaluating the visual syntax of uml: An analysis of the cognitive effectiveness of the uml family of diagrams[END_REF]. 3. Prototype notations of UML: the best symbols produced by naive users as judged by other naive users.

We conducted this experiment using a multiple-choices questionnaire. One symbol was displayed at the top of each page (representing the stimulus [START_REF] Moody | An evaluation of i* visual syntax[END_REF]) and the complete set of UML constructs and definitions displayed in a table below (representing the possible responses). Participants were asked to choose the construct they thought most likely corresponds to the symbol. In each page, there was one correct response and 11 incorrect responses (distractors).The order in which the stimuli (symbols) were presented (i.e. order of pages) and the order in which the responses (concepts) were listed were randomized to avoid sequence effects. Participants were instructed to work alone and not share their answers with each other. They were asked to answer each question in order and told to choose one and only one concept for each symbol presented. They were told that they could choose the same concept in response to multiple symbols.

Identify best of breed symbols

Based on the results of steps 4, we identified the most cognitively effective symbols for each UML construct across all symbol sets.

To measure graphical symbols comprehensibility, we used the hit rates (i.e. percentage of correct responses). The ISO standard for testing graphical symbols [START_REF]Graphical symbols -Test methods -Methods for testing comprehensibility (ISO 9186-1)[END_REF] defines 67% as the hit rate required for acceptance of public information and safety symbols [START_REF]Metamodel for development methodologies[END_REF]. Only 9 out of 12 symbols across the 3 symbols sets met the ISO required limit for comprehensibility.

Table 3 shows the best symbols across all symbol sets in terms of hit rates. The best of breed symbol set includes 12 symbols from the prototype symbol set and none from the standard UML and PoN symbol sets. The mean hit rate is 71.5%, which exceeds the ISO threshold for comprehensibility of symbols. For space limitation, we choose to show only symbols, which have met a low level of non-response in Experiment 1, a high degree of prototypy in Experiment 2 and exceed the threshold of 67% in Experiment 3. The differences between groups are visually confirmed by the box and whisker plot in Fig. 5. The boxes show confidence intervals for each group mean, while the whiskers show minimum and maximum values. The line through the middle of each box represents the median. Fig. 5 shows a comparison of semantic transparency results for unselfconscious and self-conscious notation design. We can observe that the prototype symbol set exceeds largely the ISO threshold for comprehensibility of symbols.

Standard

Using explicit design principles (selfconscious design) significantly improves semantic transparency (supported by our hypothesis), showing that conscious efforts to improve semantic transparency are likely to be successful. The average hit rate for the PoN symbol set was more than 1.5 times that of the standard UML notation, meaning that PoN symbols were more than 1.5 times as likely to be correctly interpreted without prior explanation. Moreover, the average hit rate for the Prototype symbol set was more than three times that of the standard UML notation and more than twice that of the PoN notation, meaning that Prototype symbols were by far more expressive and more often interpreted correctly. More detailed results as well as the coded data set and the statistical scripts are available in [START_REF] Kouhen | Semantic transparency experiment artifacts[END_REF].

In this experiment, our a priori hypothesis was confirmed. We find that symbols proposed and chosen by naive users are naturally based on good rules that can be found in theory and empirical approaches. We can thus observe that user-comprehensible notations (Prototype set) have absolutely a better cogni-tive expressiveness and semantic transparency than the other two symbol sets combined.

Threats to validity

The validity of our experiments are categorized into internal and external validity. The internal one refers to whether an experimental condition could be sufficient to support the claim of the experiment or not. External validity refers to the generalization of experiments outcomes [START_REF] Campbell | Experimental and Quasi-Experimental Designs for Research[END_REF].

1. Internal validity. the following factors may jeopardize internal validity :

-Selection of subjects : all participants in this study were randomly assigned to experimental groups to avoid the selection bias. As semantic transparency is culture-specific, we choose participants from differents cultural and ethnical background. -Instrumentation : the same measurements were used in all experimental groups to avoid the measurement bias. As we mentionned before, the experiments materials were presented randommely to avoid the sequence effect. -Statistical regression : the results may be different if we applied this study on another subset of UML notations. However, in this study we get 300% of improvement, which is the same as the study [START_REF] Caire | Visual notation design 2.0: Towards user comprehensible requirements engineering notations[END_REF] for another modeling language (i*).

External validity. the following factors may threaten external validity :

-To avoid the expertise bias, we used naive users in all experiments. We considered computer science students as adequate participants as they must know Object-Oriented concepts to draw them, but we considered only students with no previous knowledge of modeling languages in general or UML specifically to avoid the knowledge bias (the curse of knowledge [START_REF] Heath | Made to Stick: Why Some Ideas Take Hold and Others Come Unstuck[END_REF]). -We used different population samples in the last experiment. It would not have been accurate to use the same participants accross the experiments, as their judgements may have been biased by the drawings they produced. -Our study evaluated the comprehension of symbols as visual unit rather than complete diagrams, which can represents a threat to this study. Thus the results and their interpretation cannot be generalizable to complete diagrams. -We did not consider other principles such as the Principle of Cognitive Fit (ease of drawing of symbols) or the Principle of Graphical Economy (usage of the space), which are important in modeling languages design. For example, the signal symbol may be hard to use when the sender and the receiver are not close in the diagram. -In this study, we used hit rates (positive values) as measurments for the semantic transparency. However, Semantic transparency is not a binary state but a sliding scale (Fig. 6) defined from -1 to +1 : -1 for symbols whose appearance implies an incorrect meaning (semantically perverse) and +1 for symbols whose appearance implies the correct meaning (semantically transparent) [START_REF] Moody | The "physics" of notations: Toward a scientific basis for constructing visual notations in software engineering[END_REF]. Such kind of measurments need further investigations. Several works have evaluated the cognitive effectiveness of committee-designed languages, such as UML, BPMN, etc., using theory and empirical evidence from a wide range of fields. The conclusion is that radical improvement is required to improve their cognitive effectiveness. One solution is to involve target end-users as co-designers of these languages rather than as passive consumers as it has been so far. In this paper, we have conducted experiments, for a subset of UML, that have confirmed the importance of involving end-users. Symbols designed this way increased semantic transparency by almost 300% compared to the standard UML notation. Reducing misinterpretations by end users could therefore lead to significant cost savings: According to [START_REF] Endres | A Handbook of Soft. and Sys. Engineering: Empirical Observations, Laws and Theories[END_REF][START_REF] Martin | Information Engineering[END_REF], design errors are the source of more than half the errors and failure in software development projects [START_REF] Endres | A Handbook of Soft. and Sys. Engineering: Empirical Observations, Laws and Theories[END_REF][START_REF] Group | The chaos report[END_REF] and are the most costly errors of all, as their postimplementation correction costs 100 times more than correcting them during the design phase [START_REF] Boehm | Software Engineering Economics[END_REF].

Our experimental approach is an application of the crowd-sourcing for UML visual syntax design. This approach also called peer production or collective intelligence [START_REF] Doan | Crowdsourcing systems on the world-wide web[END_REF] enlists a multitude of humans to help solve a problem. One of the advantages of this approach is that it enlarges/expands the range of notations ideas (i.e. beyond the imagination of the language design team), rather than relying exclusively on experts to design notations, one could follow this approach and take into the ideas of the target audience.

Fig. 1 .

 1 Fig. 1. Visual variables[START_REF] Jacques | Semiology of graphics : diagrams, networks, maps[END_REF]

Fig. 2 .

 2 Fig. 2. Zero visual distance between UML notations (homographs)

Fig. 3 .

 3 Fig. 3. Symbol overload: UML homographs

Fig. 4 .Workflow 1 . 3 . 4 .

 4134 Fig. 4. Experiments Workflow

Fig. 5 .

 5 Fig. 5. Differences in hit rate between experimental groups

Fig. 6 .

 6 Fig. 6. The semantic transparency and the semantic perversity

  5. Principle of Dual Coding: enhance diagrams with textual information. 6. Principle of Complexity Management: suggest some mechanisms when dealing with notations complexity. 7. Principle of Cognitive Integration: suggest explicit mechanisms to support the integration of information from different diagrams. 8. Principle of Graphic Economy. 9. Principle of Cognitive Fit.

Table 1 .

 1 Response rates for symbolization task

	UML Construct Non-Responses Reponse Rate
	Class	2	96.87%
	Interface	3	95.3%
	Instance Spec.	4	93.75%
	Enumeration	0	100%
	Component	1	98.44%
	Signal	0	100%
	Model	2	96.87%
	Package	1	98.44%
	Dependency	2	96.87%
	Merge	1	98.44%
	Import	1	98.44%
	Substitution	2	96.87%
	Average	1.58	97.5%

Table 3 .

 3 "Best of Breed " symbols

	UML Concepts	Experiment 3 : Semantic Transparency Best of breed symbol Standard PoN Notations Prototype
	Enumeration	30%	45%	77.5%
	Component	22.5%	30%	70%
	Signal	5%	35%	87.5%
	Package	22.5%	20%	87.5%
	Dependency	12.5%	20%	75%
	Merge	27.5%	37.5%	72.5%
	Import	32.5%	42.5%	77.5%
	Group size	40	40	40
	Hit Rate Mean	22%	33%	71.5%

Acknowledgements

This work was supported by the internationalization fund of ETS Montreal and the Natural Sciences and Engineering Research Council of Canada (NSERC).