Calculs d’enveloppes pour des systèmes linéaires discrets avec des entrées bornées à variations bornées

23/09/2017
Publication e-STA e-STA 2007-3
OAI : oai:www.see.asso.fr:545:2007-3:19889
DOI :

Résumé

Calculs d’enveloppes pour des systèmes linéaires discrets avec des entrées bornées à variations bornées

Métriques

23
11
197.7 Ko
 application/pdf
bitcache://615309ff37e4e4ee551dd79d3876e26a200c9e3c

Licence

Creative Commons Aucune (Tous droits réservés)
<resource  xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
                xmlns="http://datacite.org/schema/kernel-4"
                xsi:schemaLocation="http://datacite.org/schema/kernel-4 http://schema.datacite.org/meta/kernel-4/metadata.xsd">
        <identifier identifierType="DOI">10.23723/545:2007-3/19889</identifier><creators><creator><creatorName>Abdelhalim Lalami</creatorName></creator><creator><creatorName>Christophe Combastel</creatorName></creator></creators><titles>
            <title>Calculs d’enveloppes pour des systèmes linéaires discrets avec des entrées bornées à variations bornées</title></titles>
        <publisher>SEE</publisher>
        <publicationYear>2017</publicationYear>
        <resourceType resourceTypeGeneral="Text">Text</resourceType><dates>
	    <date dateType="Created">Sat 23 Sep 2017</date>
	    <date dateType="Updated">Sat 23 Sep 2017</date>
            <date dateType="Submitted">Mon 17 Dec 2018</date>
	</dates>
        <alternateIdentifiers>
	    <alternateIdentifier alternateIdentifierType="bitstream">615309ff37e4e4ee551dd79d3876e26a200c9e3c</alternateIdentifier>
	</alternateIdentifiers>
        <formats>
	    <format>application/pdf</format>
	</formats>
	<version>33803</version>
        <descriptions>
            <description descriptionType="Abstract"></description>
        </descriptions>
    </resource>
.

Résumé — Cet article porte sur le calcul de l'ensemble atteignable (par les états ou les sorties) d'un système dynamique linéaire discret avec des entrées bornées à variations bornées. Les relations de dépendance entre variables incertaines apparaissent comme un point clé lors de la conception d’algorithmes ensemblistes et justifient la représentation des domaines à l’aide de zonotopes dans le cas des systèmes linéaires. Cela permet non seulement de limiter l’effet d’enveloppement, mais aussi d’étendre la formulation du problème de calcul d’enveloppes induites par des entrées bornées au cas où ces mêmes entrées sont également à variations bornées (ou pentes bornées). Des simulations illustrent l’intérêt de l’approche pour limiter le conservatisme des ensembles calculés. Mots clés — Ensembles atteignables, Calcul ensembliste, Zonotopes, Erreurs bornées, Analyse par intervalles. I. INTRODUCTION La prise en compte des incertitudes dans la modélisation des systèmes dynamiques représente une étude importante pour la validité du modèle défini. Ces incertitudes peuvent être classées en deux catégories : stochastiques ou déterministes. La modélisation stochastique des incertitudes est souvent bien adaptée pour représenter des bruits (bruit de mesure par exemple). Cependant, les densités de probabilité (lois gaussiennes et autres) sont souvent supposées connues. Si ces hypothèses ont du sens pour modéliser certaines sources de bruit, elles ne sont pas pour autant toujours bien appropriées pour représenter des perturbations pour lesquelles la connaissance de l’ingénieur se limite à des bornes (intervalles), sans aucune information sur les lois de distribution statistiques. Dans ce cas, une modélisation déterministe des incertitudes peut être intéressante mais pose le problème du calcul efficace de la propagation des incertitudes dans le système dynamique étudié. Dans ce but, des approches ensemblistes telles que celles basées sur l’arithmétique des intervalles [5], les ellipsoïdes [3], [8], ou les zonotopes [6],[7],[1] ont été développées. Les algorithmes qui en découlent permettent, par exemple, de calculer des bornes sur les sorties (ou les états) de systèmes dynamiques. Le calcul d’enveloppes sur les états peut se faire sans recalage par les mesures (étape de prédiction seule). Cela peut se révéler utile pour la vérification des systèmes dynamiques hybrides où le calcul des ensembles atteignables est très important [4], ou bien pour le diagnostic de défauts où le choix de seuils adaptés est crucial pour éviter les fausses alarmes [2], [10]. L’étape de prédiction peut être éventuellement complétée par une étape de correction par la mesure afin de calculer le domaine des états possibles. La synthèse de tels observateurs ensemblistes (voir, par exemple [1] et [11]) ne sera pas étudiée dans cet article qui se focalise sur l’amélioration de la seule étape de prédiction. Cependant, les approches ensemblistes sont souvent considérées comme conservatives et/ou nécessitant une charge de calcul importante. Lors du calcul de bornes sur les états (ou les sorties) d’un système dynamique, le conservatisme est souvent induit par l’« effet d’enveloppement ». L’effet d’enveloppement se manifeste par la croissance (potentiellement instable) des domaines calculés due à l’incertitude cumulée résultant des approximations extérieures effectuées à chaque pas lors du calcul des trajectoires possibles d’un système dynamique. Une manière de combattre l’effet d’enveloppement consiste à éviter autant que possible les approximations sur les ensembles (autrement dit, conserver le plus d’information possible sur les relations de dépendances entre les incertitudes). Dans le cas des systèmes linéaires, les zonotopes représentent une classe particulière de polytopes procurant un compromis intéressant entre un faible conservatisme et un temps de calcul raisonnable (la plupart des calculs se ramènent à des opérations matricielles usuelles). Une deuxième raison pouvant conduire un calcul ensembliste à fournir des domaines de taille plus importante que prévue est liée à la formulation même du problème. Considérons deux cas : premièrement, supposer que l’entrée d’un système est bornée ne spécifie aucune limite sur la vitesse des variations de cette entrée à l’intérieur de ses bornes, alors même que de nombreuses grandeurs physiques ne peuvent pas varier de façon arbitrairement rapide. Deuxièmement, borner uniquement la pente d’une incertitude ne modélise pas le fait que la plupart des incertitudes appartiennent à des domaines bornés. Afin de surmonter ces difficultés, cet article propose un algorithme ensembliste bornant l’état (ou la sortie) d’un système dynamique linéaire discret sous l’hypothèse d’entrées bornées ayant également une pente bornée. La recherche d’un compromis entre conservatisme et temps de calcul a également guidé la conception de l’algorithme proposé. Ce travail contribue donc à améliorer l’étape de prédiction conduisant au ABDELHALIM LALAMI1 , CHRISTOPHE COMBASTEL1 1 EQUIPE COMMANDE DES SYSTEMES ‘ECS’ Ecole Nationale Supérieure de l’Electronique et de ses Applications 6 av. du Ponceau, 95014 CERGY PONTOISE CEDEX, FRANCE Tél. : 01 30 73 66 66 lalami@ensea.fr, combastel@ensea.fr Calculs d’enveloppes pour des systèmes linéaires discrets avec des entrées bornées à variations bornées e-STA copyright © 2007 by see Volume 4 (2007), N°3 pp 1-6 calcul d’enveloppes sur les états (ou les sorties), lorsque la pente des entrées est bornée. Le papier est organisé comme suit : la section II est tout d'abord consacrée à l'analyse par intervalles et aux liens entre le problème de dépendance et l'effet d’enveloppement. Après une présentation de l’intérêt de l'utilisation des zonotopes, des définitions et des propriétés de ces derniers sont présentées dans la section III, ainsi qu’un algorithme de calcul de l’ensemble atteignable d'un système linéaire à entrée bornée. Ensuite, plusieurs manières de formuler la prise en compte de variations bornées des entrées incertaines (bornées) seront données dans la section IV. La section V montre comment le modèle du système peut être réécrit afin de modéliser les relations de dépendance induites par une entrée bornée à variations bornées. Il est alors possible d’appliquer l'algorithme présenté dans la section III. L'intérêt de traiter les entrées bornées avec variations bornées est finalement illustré dans la section VI. II. ANALYSE PAR INTERVALLE ET PROBLEME DE DEPENDANCE A. Arithmétique par intervalles Le nom d’une variable x entre crochets, [x], représente un domaine de valeurs possibles pour x : x ∈ [x]. Un intervalle (scalaire) [x] = [xm; xM] est un sous-ensemble fermé, borné et connexe de où xm et xM sont deux nombres réels tels que xm≤x≤xM. est l'ensemble de tous les intervalles réels de . Si • représente l’un des opérateurs +, −, ×, ÷ sur les nombres réels x et y, alors l’opérateur correspondant sur les intervalles [x] et [y] est : [x] • [y] = {x • y | x ∈ [x], y ∈ [y]} (1) Par exemple, les opérateurs somme et multiplication peuvent être définis dans le cas des intervalles réels par : [x] + [y] = [xm+ym; xM+yM] et [x] × [y] = [min(xmym, xmyM, xMym, xMyM); max(xmym, xmyM, xMym, xMyM)]. B. Le problème de dépendance Un intervalle vectoriel de n peut être défini par une boîte (alignée) multidimensionnelle (hyper-rectangle). n est l'ensemble de toutes les boîtes de n . Une manière simple (mais conservative) de calculer la boîte englobant l'image d’une boîte par une fonction f est basée sur l’application directe de l’arithmétique des intervalles. Elle consiste à remplacer chaque variable d'entrée par l'intervalle auquel elle appartient et à remplacer chaque opérateur réel par l’opérateur intervalle correspondant dans l'algorithme utilisé pour calculer l'image de f. Ce faisant, on suppose implicitement que chaque occurrence de la même variable incertaine (bornée par un intervalle) est indépendante, conduisant ainsi à une approximation conservatrice de l’ensemble image. Ceci est connu sous le nom de « problème de dépendance ». Par exemple : soit f la fonction : y = x2 . Un algorithme pour évaluer f est {f}=x×x. L'image de [x]=[-1;+1] par f est f([x]) = [0;+1] tandis que {f}([x])=[x]×[x]=[-1;+1]. f([x]) ⊂ {f}([x]) est certes garanti mais l'approximation est très pessimiste. Afin de limiter le conservatisme dans le calcul de l'image d'une boîte, une approche consiste à conserver autant d’information que possible sur les dépendances entre les variables incertaines. Dans le même temps, la quantité de calcul doit rester raisonnable. C. L’ effet d’enveloppement Durant le calcul des bornes sur les états d'un système dynamique, la perte de certaines relations de dépendance entre les variables incertaines lors du passage d’un pas de calcul au suivant conduit à ce que l’on appelle l’effet d’enveloppement. Une illustration très courante de l'effet d’enveloppement est la suivante : on considère le système linéaire autonome à temps discret (2). xk+1 = R.xk, x0 =       2 1 s s ∈ [-1;+1]2       − = )4/cos()4/sin( )4/sin()4/cos( ππ ππ R (2) R est une matrice de rotation et l’état initial est supposé appartenir à [-1,1]2 . s1 et s2 sont deux variables incertaines scalaires utilisées pour caractériser l'ensemble des états initiaux. Une manière simple de calculer des domaines auxquels appartiennent les états xk consiste à appliquer l’arithmétique des intervalles. Il en résulte (Fig. 1) que chaque élément de xk appartient à l'intervalle [- 2 k ; + 2 k ], ce qui peut être réécrit sous la forme : ( ) ( )         +−∈                    ∈ + + + + 2 22 12 22 12 ]1;1[,. 20 02 k k k k k k k s s s s x (3) s2k+1 s2k+2 0 time k s2k+3 s2k+4 0 time k+1 R Fig. 1. Illustration de l'effet d’enveloppement. En plus de l'augmentation de la taille des domaines, il est important de remarquer que les variables incertaines modélisant les domaines (ici, des boîtes alignées) ne sont pas les mêmes à des instants différents. Dans l’équation (3), les deux variables incertaines s2k+1 et s2k+2 servent à décrire le domaine des états xk atteignables à l’instant k (remarque : avec k=0, ces notations sont bien cohérentes avec l’utilisation de s1 et de s2 pour caractériser l’ensemble des états initiaux). Une conséquence immédiate de (3) est que les bornes divergent ( 2 >1) alors que le domaine solution (4) est de taille bornée. Il correspond en effet à une simple rotation du carré initial.         +−∈            ∈ 2 2 1 2 1 ]1;1[,. s s s s Rx k k (4) En comparant (3) et (4), il est important de noter que la solution exacte (4) à chaque instant k s’exprime en fonction des mêmes variables incertaines (s1 et s2) que celles modélisant l’ensemble des valeurs possibles des états initiaux. Au contraire, la solution approximative basée sur les boîtes alignées (3) s’exprime en fonction de variables incertaines qui sont différentes d’une itération à l’autre. Il en résulte que la e-STA copyright © 2007 by see Volume 4 (2007), N°3 pp 1-6 dépendance de la trajectoire réelle par rapport à l'état initial (pour lequel seules des bornes sont connues) est perdue d'une itération à l'autre. De plus, l’approximation par une boîte du domaine ayant subi la rotation introduit une majoration supplémentaire à chaque itération, ce qui conduit à la croissance instable de la taille des domaines. On peut également noter que, même pour un système stable, la taille du domaine calculé peut diverger si l'incertitude supplémentaire induite par la perte de certaines relations de dépendance a une influence plus importante que la contraction produite par la matrice d’état dans certaines directions de l'espace d’état. Cependant, l’utilisation de boîtes alignées pour représenter les domaines n'est pas la seule solution. L'équation (4) montre que xk est toujours borné par un domaine défini comme l’image d'un hypercube unitaire (carré unitaire dans (4)) par une application linéaire (Rk dans (4)). Une telle application linéaire peut être facilement calculée par récurrence et elle définit implicitement la forme exacte du domaine solution. Comme cela sera détaillé dans la prochaine partie, ces constatations motivent l'utilisation de zonotopes pour caractériser les domaines. III. ENSEMBLE ATTEIGNABLE AVEC DES ENTREES BORNEES : UN ALGORITHME BASE SUR LES ZONOTOPES Le but de cette partie est de rappeler quelques définitions et propriétés des zonotopes ainsi qu’un algorithme assez simple et efficace pour calculer l'ensemble atteignable d'un système linéaire discret avec des entrées bornées (sans contrainte sur les variations des entrées dans cette partie). A. Zonotopes : définition et propriétés 1) Définition. Soit R une matrice réelle de taille n×p. Le zonotope (centré sur l’origine) Z(R) ⊂ n est un polytope particulier défini comme l’image d’un hypercube unitaire de dimension p, [-1;+1]p , par l'application linéaire R (5). Par conséquent, un zonotope est un domaine qui contient l’information sur les dépendances linéaires entre les p variables incertaines correspondant aux éléments du vecteur s. Z(R) = { x = R.s, s∈[-1;+1]p } (5) 2) Somme de deux zonotopes. La somme de Minkowski de deux ensembles, [x] et [y], est l'ensemble défini par [x] + [y] = {x+y / x ∈ [x], y ∈ [y]}. La somme (de Minkowski) de deux zonotopes est un zonotope qui peut être calculé par une concaténation matricielle (6). Un corollaire important est que tout zonotope Z(R), R∈ n×p , peut être défini par la somme de Minkowski de p segments de droite. Plus précisément, le ième segment est ri[-1;+1] (autrement dit, l’ensemble des points {ris, s∈[-1;+1]}), où ri ∈ n est le vecteur correspondant à la ième colonne de la matrice R, i=1…p. Ce vecteur ri caractérise donc la direction de la droite support du ième segment. Z(R1) + Z(R2) = Z([R1 R2]) (6) 3) Image linéaire. L'image d'un zonotope par une application linéaire L est un zonotope qui peut être calculé par un produit matriciel : L.Z(R) = Z(L.R) (7) 4) La plus petite boîte alignée Box(Z(R)) englobant un zonotope Z(R) peut être calculée à partir de la norme un de chaque vecteur ligne de R (8). rs(R)∈ n×n est une matrice diagonale : Box(Z(R)) = Z(rs(R)) ∑= = p j ijii RRrs 1 )( , i=1…n (8) Box(Z(R)) Z(R) Fig. 2. Plus petite boîte alignée englobant un zonotope. B. Calcul de l'ensemble atteignable d'un système linéaire à temps discret avec des entrées bornées : Considérons un système linéaire discret avec des entrées bornées tel que l'état initial appartienne à un zonotope donné : xk+1 = A.xk + B.uk + E.vk yk = C.xk + D.uk + F.wk x0 ∈ c0 + Z(R0), vk ∈[-1;+1]q , wk ∈[-1;+1]m (9) L’ensemble des états initiaux x0 possibles est l’ensemble c0 + Z(R0) = { x0 = c0+R0.s, s∈[-1;+1]p }. En utilisant les propriétés des zonotopes, on peut montrer que l’état xk appartient à un zonotope qui peut être calculé récursivement comme indiqué par (10) : ∀k≥0, xk+1 ∈ [xk+1] = ck+1 + Z(Rk+1), où : ck+1 = A.ck + B.uk Rk+1 = [A.Rk E] (10) Remarque : Etant donné un ensemble [xk] contenant xk, un zonotope bornant la sortie yk est [yk] = (C.ck+D.uk) + Z([C.Rk F]). D’après la propriété 4) (plus petite boîte contenant un zonotope), une boîte englobant yk est donc (C.ck+D.uk) + Box(Z([C.Rk F])). La représentation des domaines par des zonotopes réduit donc le calcul de l’ensemble des états atteignables à l’instant k, [xk], à des calculs matriciels très simples. De plus, le domaine résultant obtenu n’est sujet à aucune approximation et l’extension à des matrices variant dans le temps (Ak, Bk, Ck, Dk, Ek, Fk) est immédiate. Cependant, le développement de la récurrence Rk+1 = [A.Rk E] montre la nécessité d’une étape de réduction : comme A.Rk a la même dimension que Rk, il s’en suit que Rk+1 a ncol(E) colonnes de plus que le nombre des colonnes de Rk où ncol(.) désigne le nombre de colonnes d’une matrice. Par conséquent, le nombre de segments générateurs du zonotope [xk] augmente à chaque itération si une étape de réduction (Rk+1=Red(Rk+1)) n'est pas ajoutée à la récurrence (10) afin de contrôler la complexité des domaines. Le but de l'étape de réduction est de limiter la complexité des zonotopes en fixant le nombre maximum de segments générateurs. Soit Z(R) un zonotope centré de n engendré par p segments : R∈ n×p . L'opérateur de réduction Red(.) associe à la matrice R la matrice Red(R) telle que l'inclusion Z(R) ⊆ Z(Red(R)) soit satisfaite et Red(R) a au plus nd colonnes. Le paramètre d règle le compromis entre une complexité limitée (d petit) et une précision suffisante pour limiter l'effet d'enveloppement (d grand). Une implantation d’un tel opérateur est décrite dans [1] et rappelée brièvement ci-après : e-STA copyright © 2007 by see Volume 4 (2007), N°3 pp 1-6 R = [r1 … ri … rp], ||ri|| ≥ ||ri+1|| (11) Si p≤nd Alors Red(R)=R Sinon Red(R) = [r1 … rnd-n rs([rnd-n+1 … rp])] (12) Les segments générant Z(R) (i.e. les colonnes de R) sont tout d’abord triés par norme euclidienne décroissante (11). La somme de Minkowski des segments de plus faible longueur est alors bornée par une boîte (12). Cela est illustré par une conséquence de (12) lorsque p>nd : Z(Red(R)) = Z([r1 … rnd-n]) + Box(Z([rnd-n+1 … rp])) (13) VI. PRISE EN COMPTE D’ENTREES BORNEES A VARIATIONS BORNEES : FORMULATION DU PROBLEME A. Comparaison de différentes formulations du problème Même lorsque l'ensemble atteignable est calculé exactement (sans étape de réduction), l'ensemble solution peut paraître dans certains cas très grand par rapport aux connaissances empiriques de l'ingénieur. Cela peut donc amener à revoir la formulation même du problème. Même si l’hypothèse d’entrées bornées est souvent proche de la connaissance disponible sur les entrées incertaines (perturbations), une telle formulation du problème ne définit aucune limite sur les variations des entrées incertaines à l’intérieur des bornes spécifiées. Cela peut avoir une forte influence sur les ensembles calculés, notamment si le système est sensible aux moyennes et/ou hautes fréquences. Le but de ce travail est donc de traiter le problème consistant à borner les états en réponse à des entrées non seulement à valeurs bornées, mais aussi à variations bornées (bornes sur la pente maximale admissible). En temps continu, la formulation du problème se ramène à une simple extension d’état (pour simplifier, les entrées connues n’apparaissent pas et une seule entrée incertaine est considérée) : soit le système non linéaire à temps continu dx/dt = f(x(t),v(t)) où v(t)∈[-1;+1] (∀t) est une entrée bornée, l'extension de l'état à [x(t); v(t)] avec dv/dt = Gσ(t) et ∀t, σ(t)∈[-1;+1] modélise une entrée bornée à variations bornées. Cependant, le calcul de bornes conduit dans ce cas à des algorithmes relativement complexes [9]. Si le champ de vecteur f est linéaire, la formulation du problème en temps continu devient : ]1;1[)(, ]1;1[)(, ),(. 0 )( )( . 00)( )( +−∈∀ +−∈∀       +            =      tvt tt t Gtv txEA tv tx σ σ & & Il est important de remarquer que, du fait de l’extension d’état, les bornes sur v(t) deviennent des bornes sur une partie de l’état étendu ; ainsi, v(t)∈[-1;+1] peut être vue comme une mesure incertaine supplémentaire. Une discrétisation avec un bloqueur d’ordre zéro introduit l’hypothèse supplémentaire que σ est constant sur chaque période d’échantillonnage et conduit à : k k k k k v x v x σ. * * . 10 ** 1 1       +            =      + + , ∀k, σk ∈ [-1;+1] (14) [ ] k k k w v x ).1(.100 −+      = , ∀k, wk ∈ [-1;+1] (15) Calculer l'ensemble des états possibles à partir de (14) et (15) ne requiert pas seulement une étape de prédiction basée sur (14) (et implantée avec l'algorithme décrit dans la partie III), mais aussi une étape de correction pour calculer l’intersection entre l'ensemble prédit et la bande –1≤vk≤+1. La contrainte associée à cette bande peut être intégrée au modèle au travers de l’équation de mesure (15). Il s’agit là d’une mesure « artificielle » du fait qu’elle ne correspond pas physiquement à la présence d’un capteur. Même si des solutions existent, le calcul d’une telle intersection n'est pas très simple et peut induire un certain conservatisme. L'originalité de ce travail consiste à modéliser les relations de dépendance induites par la satisfaction simultanée de contraintes du type bornes sur les entrées et du type bornes sur les variations de ces mêmes entrées, de sorte que l'algorithme de la partie III puisse être appliqué directement. B. Formulation du problème Pour simplifier l’étude, on considère un système linéaire à temps discret avec une seule entrée bornée à variation bornée : kkk vExAx ..1 +=+ , ∀k, vk ∈ [-M;+M] x0 ∈ Z(R0), ∀k, vk+1 - vk ∈ [-g;+g] (16) Cette formulation du problème peut être étendue à des matrices variant dans le temps, ainsi qu’à des systèmes multi entrées (en utilisant le principe de superposition). M>0 est supposé être un multiple de g>0 (cela sera justifié par la suite) ce qui n'est pas très restrictif lorsque g est petit par rapport à M. De plus, le choix de la période d’échantillonnage peut influencer g et pas M, procurant ainsi un moyen supplémentaire pour satisfaire cette hypothèse. Le problème consiste alors à calculer aussi efficacement que possible l'ensemble des états atteignables. V. REECRITURE DU MODELE POUR PRENDRE EN COMPTE LES RELATIONS DE DEPENDANCE. Le point de départ de la solution proposée est basé sur des considérations géométriques. A chaque instant k, la relation entre vk+1 et vk est un zonotope dans l'espace (vk, vk+1) : g g g g vk vk+1 -M -M +M +M Fig. 3. Relation entre deux entrées consécutives Le zonotope de la Fig. 3 est généré par une matrice 2×3.                 − − =      + k k k k k s s s hhM hhM v v ,3 ,2 ,1 1 . 0 0 , 2/ ]1;1[, gh s ki = +−∈ (17) Cependant, lorsque k est remplacé par k+1 dans (17), on remarque que la dépendance entre vk et vk+2 est perdue car si,k+1 est a priori indépendant de si,k, i=1…3. Pour réduire ce conservatisme, toutes les relations de dépendance doivent être modélisées. Les bornes sur vk et ses variations décrites par (16) conduisent à (18) : ∀k, ∀m, vk+m ∈ [-M;+M] ∩ (vk + [-mg;+mg]) (18) e-STA copyright © 2007 by see Volume 4 (2007), N°3 pp 1-6 (18) montre que les bornes de vk+m peuvent dépendre de vk pour 0≤m<(2M/g). La valeur maximale de m correspond au cas vk=-M ou vk=+M qui requiert le temps le plus long pour que vk+m devienne indépendant de vk. On pose : n = 2M/g = M/h. La relation entre les vk+i, 0≤i≤n, peut être décrite par un zonotope de dimension plus élevée :                                 =                 + kn k nk k s s hh hh hh hh v v ,2 ,1 . 00 000 000 00 M LL L L LL M (19) Remarque 1 : La projection de (19) sur le plan (vk,vk+1) correspond à (17) : il suffit de regrouper les (n-1) segments [h;h] dans les deux premières lignes de (19) pour obtenir (17). Remarque 2 : La structure de la matrice dans (19) montre l’indépendance entre vk et vk+n : leurs expressions ne partagent en effet aucune variable incertaine si,k, i=1…2n. Remarque 3 : En appliquant la propriété 4) (plus petite boîte englobant un zonotope) à (19), on a: [vk;…;vk+n] ∈ [-M;+M]n+1 . Une formulation récursive de (19) est donnée par (20) et (21) : ∀k, vk = h.(s1,k + … + sn,k), si,k ∈ [-1;+1] (20) si,k+1 = si+1,k, i=1…n (21) Comme M=nh et comme toutes les variables si,k ∈ [-1;+1] sont indépendantes, (20) implique que vk ∈ [-M;+M]. De plus, on peut vérifier que (20) et (21) impliquent (18) (en calculant vk+m – vk à partir de (20) et en simplifiant le résultat avec (21)). L’intérêt de la formulation récursive donnée par (20) et (21) est qu’elle peut être utilisée pour obtenir une représentation d’état prenant en compte explicitement les relations de dépendance. En substituant vk par (20) et en utilisant (21) pour étendre le modèle d’état (16), le problème peut être reformulé comme le calcul de l’ensemble des états atteignables par (22) : kn kn kn k k kn kn k k s s s s xEhEhEhA s s s x ,1 , ,1 ,1 1, 1,1 1,1 1 . 1 0 0 0 . 00 1 00 0010 + − + +− + +                 +                                 =                 MM LL OM OOM L M               ∈      nn I R Z s x 0 00 0,...1 0 , ∀k, sn+1,k ∈ [-1;+1] (22) (22) montre que le calcul de l’ensemble des états atteignables d’un système linéaire avec entrée bornée à variation bornée se ramène à celui d’un système linéaire à entrée bornée seulement, et ce, par une extension d’état basée sur des variables incertaines modélisant les relations de dépendance d’une itération à l’autre et par une modification de l’entrée incertaine de sorte que cette dernière ne représente plus que l’incertitude supplémentaire introduite dans l’évolution du système à l’instant k. On peut aussi remarquer que la matrice d'identité In utilisée pour définir le zonotope qui englobe l’ensemble des états initiaux dans (22) signifie que si,0 ∈ [-1;+1] pour i=1…n. La formulation du problème (22) rend possible l’application directe de l’algorithme présenté dans la partie III. Cependant, une légère modification de l’étape de réduction a été introduite dans l’implantation de l’algorithme : elle consiste à exclure les (n+1) dernières colonnes de la matrice Rk+1 lors de l’étape de réduction, afin d’éviter que les relations de dépendance décrites par (21) soient modifiées par cette étape de réduction. Par conséquent, lorsque l’algorithme de la partie III est appliqué à (22) (cas d’une entrée bornée à variation bornée), l’étape de réduction qui suit (10) (Rk+1=Red(Rk+1) normalement) est remplacée par : Rk+1 = [Sk+1 Tk+1] Rk+1 = [Red(Sk+1) Tk+1] (23) où Tk+1 représente la matrice définie par les (n+1) dernières colonnes de Rk+1. La prochaine partie est consacrée à une étude en simulation illustrant l'intérêt de l’algorithme obtenu. VI. APPLICATION L'algorithme proposé a été appliqué à un modèle linéaire résultant de la discrétisation (avec un bloqueur d’ordre zéro et Ts=0.05 comme période d’échantillonnage) d'un filtre passe- bande d’ordre deux, Fc(p), avec ω=10 et z=0.7 : 12 )( 2 2 ++ = ωω p z p p pFc xk+1 = A.xk + E.vk yk = C.xk (24)       − = 02 24829.03205.1 A ,       = 0 2 E [ ]86226.07245.1 −=C (25) Dans les deux simulations détaillées ci-après, l’état initial x0 est supposé exactement nul (x0 ∈ Z(R0) où R0 est une matrice nulle) afin de montrer l'influence propre à l’entrée incertaine. 1er cas : Entrée bornée (M=1 : ∀k, vk ∈ [-M;+M]) sans limite sur ses variations (g=∞ : pas de contrainte sur vk+1-vk). L'algorithme décrit dans la partie III.B peut être appliqué directement pour calculer l’intervalle [yk] bornant yk. Le rayon de [yk] (qui est centré sur zéro) est tracé sur la Fig. 4. Le zoom montre que l'utilisation de l'opérateur de réduction (nd=30, tracé avec une ligne continue) induit un très faible conservatisme par rapport à la solution exacte (tracé avec une ligne discontinue). 0 0.5 1 1.5 2 2.5 3 0 2 4 6 8 10 2.2 2.4 2.6 2.8 9.52 9.54 9.56 9.58 kTs Rayon([yk]) Fig. 4. Rayon (demi-largeur) de l’intervalle [yk] dans le cas d’une entrée bornée (vk ∈ [-1;+1]) sans contrainte sur les variations de cette entrée. e-STA copyright © 2007 by see Volume 4 (2007), N°3 pp 1-6 Remarque : compte-tenu de la formulation du problème (16), toute valeur de g satisfaisant g>2M conduit à des résultats identiques à ceux de la Fig. 4. En effet, ∀k, vk ∈ [-M;+M] est alors toujours plus contraignant que ∀k, vk+1 - vk ∈ [-g;+g], ce qui rend la contrainte de variations bornées sur l’entrée inactive pour g>2M. 2ème cas : Entrée bornée (M=1 : ∀k, vk ∈ [-M;+M]) avec variations bornées : sr ∈ [-1;+1] désigne la pente maximale admissible (« slew-rate »). Par conséquent, g = sr*Ts = 0.05 et ∀k, vk+1 - vk ∈ [-g;+g]. 0 0.5 1 1.5 2 2.5 3 0 1 2 3 4 5 kTs Rayon([yk]) Fig. 5. Rayon (demi-largeur) de l’intervalle [yk] avec une entrée bornée (vk ∈ [-1;+1]) à variations bornées (vk+1 - vk ∈ [-0.05;+0.05]). La fig. 5 montre l’évolution temporelle du rayon de [yk]. Le calcul est basé sur l’application de l’algorithme de la partie III.B au modèle (22) qui prend en compte les relations de dépendance supplémentaires induites par la contrainte de variations bornées de l’entrée incertaine. A nouveau, l’utilisation de l’opérateur de réduction (nd=84) comme indiqué dans la partie V n’introduit pas un conservatisme significatif par rapport à la solution exacte. En comparant Fig. 4 et Fig. 5, il apparaît clairement que la contrainte limitant les variations de l’entrée peut avoir un effet considérable sur les domaines calculés. Dans le 1er cas, vk peut être égal à -1 à un instant et égal à +1 à l’échantillon suivant. Il en résulte que vk est susceptible d’exciter une très large gamme de fréquences ce qui n’est plus le cas lorsque la pente de vk est bornée par des valeurs relativement faibles. Les méthodes ensemblistes garantissant la propriété d’inclusion dans le pire des cas, il en résulte que si le système est sensible aux moyennes ou hautes fréquences, les intervalles obtenus sont considérablement plus larges lorsque la borne sur les variations n’est pas prise en compte. VII. CONCLUSION Les relations de dépendance entre variables incertaines apparaissent comme l’un des points clé lors de la conception d’algorithmes ensemblistes. Ainsi, conserver autant d’information que possible sur les relations de dépendance sans induire un temps de calcul trop élevé permet de lutter contre l’effet d’enveloppement. Une modélisation dynamique des relations de dépendance constitue également un moyen supplémentaire pour enrichir la formulation du problème. Cela a été illustré dans cet article par la conception et la validation d’un algorithme calculant l’ensemble des états atteignables par un système linéaire discret à entrée bornée en absolu et en relatif (variations bornées). VIII. REFERENCES [1] C. Combastel, “A state bounding observer based on zonotopes,” European Control Conference, Cambridge, UK, 2003. [2] C. Combastel and Q. Zhang, “Robust fault diagnosis based on adaptive estimation and set-membership computations,” IFAC Safeprocess’2006, Beijing, China, 2006. [3] C. Durieu, E. Walter, and B. Polyak, “Multi-Input, multi-output ellipsoidal state bounding,” Journal of optimisation theory and applications, vol. 111, no. 2, pp. 273-303, 2001. [4] A. Girard, “Reachability of uncertain linear systems using zonotopes,” in Hybrid Systems: Computation and Control, ser. LNCS. Springer, vol. 3414, pp. 291–305, 2005. [5] L. Jaulin, M. Kieffer, O. Didrit, and E. Walter, Applied interval analysis, with examples in parameter and state estimation, robust control and robotics. Springer, 2001. [6] W. Kühn, “Rigorously computed orbits of dynamical systems without the wrapping effect,” Computing, vol. 61, pp. 47-67, 1998. [7] W. Kühn, “Towards an optimal control of the wrapping effect,” SCAN’98, IMACS/GAMM International symp. on scientific computing, computer arithmetic and validated numerics, Hungary. [8] S. Lesecq, A. Barraud, “Off-line diagnosis using output error membership set estimation : application to induction motor,” IFAC Safeprocess’2000, Vol. 2, pp. 1163-1167, Budapest, Hungary, 2000. [9] T. Raïssi, N. Ramdani, and Y. Candau, “Set membership state and parameter estimation for systems described by nonlinear differential equations,” Automatica, vol. 40, no. 10, pp. 1771-1777, 2004. [10] A. Stancu, V. Puig, P. Cugueró and J. Quevedo, “Benchmarking on approaches to interval observation applied to robust fault detection”. European Control Conference, Cambridge, UK, 2003. [11] T. Alamo, J. M. Bravo, E. F. Camacho, “Guaranteed state estimation by zonotopes,” (Brief paper), Automatica, Vol. 41, no. 6, pp. 1035-1043, June, 2005. e-STA copyright © 2007 by see Volume 4 (2007), N°3 pp 1-6