Fusion de données redondantes avec une technique ensembliste atteignant la consistance globale

30/09/2017
Publication e-STA e-STA 2005-1
OAI : oai:www.see.asso.fr:545:2005-1:20023
DOI :

Résumé

Fusion de données redondantes avec une technique ensembliste atteignant la consistance globale

Métriques

11
5
274.74 Ko
 application/pdf
bitcache://c852d9ba9b1d2b81ef1bcee86a52352c4b374001

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:2005-1/20023</identifier><creators><creator><creatorName>Amadou Gning</creatorName></creator><creator><creatorName>Philippe Bonnifait</creatorName></creator></creators><titles>
            <title>Fusion de données redondantes avec une technique ensembliste atteignant la consistance globale</title></titles>
        <publisher>SEE</publisher>
        <publicationYear>2017</publicationYear>
        <resourceType resourceTypeGeneral="Text">Text</resourceType><dates>
	    <date dateType="Created">Sat 30 Sep 2017</date>
	    <date dateType="Updated">Sat 30 Sep 2017</date>
            <date dateType="Submitted">Fri 20 Apr 2018</date>
	</dates>
        <alternateIdentifiers>
	    <alternateIdentifier alternateIdentifierType="bitstream">c852d9ba9b1d2b81ef1bcee86a52352c4b374001</alternateIdentifier>
	</alternateIdentifiers>
        <formats>
	    <format>application/pdf</format>
	</formats>
	<version>34039</version>
        <descriptions>
            <description descriptionType="Abstract"></description>
        </descriptions>
    </resource>
.

Résumé — Cet article propose de traiter un problème de fusion de données ensembliste à l'aide d’outils de satisfaction de contraintes sur les intervalles réels. En effet, dans le cas où il existe une forte redondance des données, on cherche à étudier les performances d'une telle approche compte tenu de son fort potentiel à être implémentée sur un calculateur temps-réel. La contribution de ce travail est essentiellement méthodologique dans la mesure où nous proposons une méthode originale pour atteindre la consistance globale en un nombre calculable a priori d'opérations arithmétiques. D'un point de vue applicatif, nous nous intéressons ici à l'estimation de l'état cinématique d'une automobile à partir des mesures des quatre capteurs ABS et de l'angle au volant. Mots clés—estimation ensembliste, fusion de données garantie, propagation de contraintes sur les réels. I. INTRODUCTION La fusion de données est un problème d'estimation avec plus de données que d'inconnues dans lequel on cherche à tirer profit de toutes les informations disponibles. Dans un problème de fusion de données, il est fondamental de gérer l'imprécision et l'incertitude. L'imprécision d'une grandeur est définie comme l'écart entre cette grandeur et sa valeur vraie alors que la certitude d'une proposition traduit la confiance que l'on a dans le fait que cette proposition soit vraie. Plus l'incertitude d'une proposition est grande et plus les chances que cette proposition soit vraie sont faibles. Dans cet article, on ne considère que les imprécisions des données. Lorsque celles-ci sont modélisées sous forme d'intervalles, la propagation de contraintes sur les intervalles réels permet de résoudre à elle seule des problèmes de fusion de données redondantes [4, 5, 7, 8]. En d'autres termes, en cas de forte redondance, cette technique permet d'obtenir des pavés assez réduits et donc peu pessimistes. Dans ce travail, on cherche à appliquer un concept théorique nouveau, susceptible de résoudre un problème souvent rencontré lorsqu’on résout un problème de satisfaction de contraintes. En effet, les algorithmes de propagation de contraintes aboutissent souvent à des consistances locales sauf dans certains cas, comme celui où le graphe de représentation des contraintes reliant les variables est sous forme d’un arbre [2, 5]. Dans le cas où des cycles interviennent, les méthodes reposent souvent sur un algorithme de Waltz [3], dans lequel l’amélioration consiste à utiliser des heuristiques tendant à organiser le choix de l’ordre de contraction des variables. Si on veut améliorer la consistance locale qui découle de ces algorithmes et donc tendre vers la consistance globale, les solutions existantes se basent en général sur un découpage des pavés. Malheureusement, ces approches ont en commun la mauvaise propriété d’avoir un temps de calcul inconnu a priori, ce qui complique leur implémentation temps réel. Nous définissons dans cet article la notion de domaine de consistance. Un tel domaine présente des propriétés intéressantes, notamment, celle de conduire à la consistance globale en un nombre fini et connu d'opérations. Nous avons appliquée cette technique au problème de fusion de données non linéaire des mesures des quatre capteurs ABS et de l’angle au volant dans le but d'obtenir une estimation garantie de l'état cinématique d'une automobile en déplacement. Le graphe correspondant à ce problème présente des cycles dus à la forte redondance des données [2, 5]. L'article est organisé comme suit. D'abord, le problème de fusion de données sera présenté ; il s'agit d'estimer de façon garantie l'état cinématique 2D d'une automobile en déplacement à partir de mesures redondantes. Ensuite, la notion de domaine de consistance sera définie. Grâce à plusieurs propriétés démontrées, on verra comment l'utiliser pour atteindre la consistance globale d’un problème académique présentant un cycle. Enfin, nous appliquerons cette technique à la résolution de notre problème et nous présenterons les résultats d'une telle approche sur des données réelles obtenues avec le véhicule expérimental du laboratoire. II. LE PROBLEME CONSIDERE Considérons un modèle simple d'Ackerman [3] établi sous hypothèse de roulement sans glissement. ψ R x M ψ ρ I L ψ ψ L D D R D L ro u e a v a n t v irtu e lle e Figure 1 : modèle d'Ackerman d'un véhicule. On note δs et δθ respectivement la distance parcourue par le point M et la variation de cap entre deux instants d’échantillonnage. De simples considérations géométriques utilisant le centre instantané de rotation « I » permettent d'établir les relations suivantes [10] : AMADOU GNING ET PHILIPPE BONNIFAIT HEUDIASYC UMR UTC/CNRS 6599. 60205 COMPIEGNE CEDEX. Fusion de données redondantes avec une technique ensembliste atteignant la consistance globale tan(ψ) = L. δθ δs δRL = δs − e.δθ δRR = δs + e.δθ δFL.cos(ψL ) = δs − e.δθ δFR.cos(ψR ) = δs + e.δθ ⎧ ⎨ ⎪ ⎪ ⎩ ⎪ ⎪ (1) où δRL, δRR, δFL, δFR, sont respectivement les distances parcourues par les roues arrières droite et gauche, et les roues avants droite et gauche. ψR et ψL sont les orientations des roues droite et gauche, et ψ l'angle d'une roue virtuelle centrale (cf. figure 1). L’objectif que l'on se fixe est de trouver une méthode ensembliste utilisant l’analyse par intervalle et capable de fournir une estimation garantie de δs et δθ. Cette méthode doit de plus être compatible avec une implémentation en temps réel, c'est-à-dire que le nombre d'opérations doit être borné et connu à chaque pas de temps. Le système redondant (1) entraîne des cycles dans le graphe des contraintes. Dans ce cas, les méthodes de propagation de contraintes de type "Waltz" [3, 6] ne permettent pas de connaître a priori le temps de calcul car elles se basent sur une boucle de type "répéter tant que ça contracte". De plus, ces approches ne permettent d'atteindre qu'une consistance locale. Pour résoudre ces deux problèmes, nous proposons une nouvelle approche basée sur la notion de domaine de consistance présentée dans la suite. III. DOMAINES DE CONSISTANCE A. Consistances locale et globale Etant donné un pavé [x] ∈ IRn , résoudre le CSP H = (x∈[x] | F(x)=0) signifie rechercher dans ce pavé l’ensemble des solutions du système de contraintes F(x)=0. On note S l’ensemble des solutions dans [x] des contraintes f : S ={x∈[x] | F(x)=0} Contracter H signifie remplacer le pavé [x] par un sous-pavé [x]’ ⊂ [x] qui conserve toutes les solutions S, i.e S ⊂ [x]’. Un pavé [xi] est dit localement consistant avec H s'il vérifie toutes les contraintes prises séparément. Un pavé [xi] est dit globalement consistant avec H s'il vérifie toutes les contraintes en même temps. B. Domaine de consistance associé à un sous-vecteur Soient I = (1, …, n) et J = (j1, …, jm) un sous-ensemble de I de cardinal m. Considérons un vecteur noté x ∈ IRn . On note xJ un sous- vecteur de x associé à J. Ce sous-vecteur est de dimension m et s'écrit : xJ = (x(j1), …, x(jm))T De même, soit [x] un pavé dans IRn . Le sous-pavé de [x] associé à J, noté [xJ] ∈ IRm , s'écrit [xJ] = ([x(j1)], …, [x(jn)])T On note K=I\J le complémentaire de J dans I. Considérons d'abord le cas simple décrit par la figure 2 où H est un CSP à 2 variables (x, y) et constitué de 2 contraintes (une bande et une ellipse, ici). Pour la valeur de x0 choisie, l’ensemble DF(x0) des y tels que (x0, y) soit globalement consistant avec H est représenté sur la figure 2. Soit xJ un sous-vecteur de x associé à J. On appelle domaine de consistance associé à xJ, l’ensemble DF(xJ) inclus dans l’ensemble des sous-vecteurs de IRn associés à K. x0 DF(x0) Figure 2 : domaine de consistance associé à la valeur x0. DF(xJ) est vide ou bien vérifie les conditions suivantes : 1. tout vecteur globalement consistant ayant xJ comme sous-vecteur a ses composantes complémentaires à xJ incluses dans le domaine de consistance, i.e. ∀ z ∈ IRn tel que zJ = xJ et tel que z vérifie toutes les contraintes F, alors zK ∈ DF(xJ) 2. tout vecteur constitué des sous-vecteurs zK ∈ DF(xJ) et xJ est globalement consistant, i.e. ∀ zK ∈ DF(xJ), le produit cartésien zK × xJ dans IRn (dans le bon ordre) vérifie toutes les contraintes F. Pour un sous-vecteur donné xJ, DF(xJ) représente donc le plus grand ensemble de sous-vecteurs tels que leurs produits cartésiens avec xJ donne un vecteur dans IRn globalement consistant avec H. C. Domaine de consistance associé à un ensemble de sous-vecteurs Considérons maintenant le cas décrit par la figure 3 où cette fois-ci, on cherche à caractériser pour un intervalle [x] donné, l’ensemble des y pour lesquels ∃ x ∈ [x] tel que (x, y) soit globalement consistant avec H. Cet ensemble, noté DF([x]), est appelé domaine de consistance associé à l’intervalle [x]. [x] DF([x]) x Figure 3 : domaine de consistance d'un intervalle. Dans le cas général, pour un ensemble de sous-vecteurs associés à J donné AJ non vide, DF([xJ]) représente le plus grand ensemble de sous-vecteurs vérifiant : ∀ zK ∈ DF(AJ), ∃ xJ ∈ AJ tel que le produit cartésien avec xJ donne un vecteur dans [x] globalement consistant. DF(AJ) (inclus dans l’ensemble des sous vecteurs dans [x] associés à K) est vide ou bien vérifie : 1. si z est globalement consistant et si ses composantes selon J sont incluses dans AJ alors celles de z selon K appartiennent au domaine de consistance, i.e. ∀ z∈ IRn tel que zJ ∈ AJ et tel que z vérifie toutes les contraintes F, alors zK ∈ DF(AJ) 2. pour tout sous-vecteur dans DF(AJ) on peut trouver un sous-vecteur dans AJ tel que leur produit cartésien soit globalement consistant, i.e ∀ zK ∈ DF(AJ), ∃ zJ ∈ [AJ] tel que le produit cartésien de zK et zJ dans IRn vérifie toutes les contraintes F. Remarque : si AJ est vide, DF(AJ) est vide. D. Propriétés Un certain nombre de propriétés intéressantes, dont les démonstrations sont en annexe, sont citées ci dessous. Elles nous ont permis d’aboutir à des résultats intéressants, permettant d’évaluer les domaines de consistances. 1. Dans le cas particulier de deux variables x et y reliées par une contrainte x = f(y), on a Df([y])=f([y]). 2. Soient [z] et [y] des sous-intervalles dans H associés à J tels que [y] ⊂ [z] alors DF([y]) ⊂ DF([z]) 3. le domaine de consistance associé à un sous-pavé est l’union des domaines de consistance de tous les sous- vecteurs de ce sous-pavé, i.e. ∀ le sous-pavé [xJ] de [x], DF([xJ]) = [ ] U J J x x ∈ DF(xJ). 4. Soit [z] un sous-pavé associé à J et soient [zJ,1], …, [zJ,p] p sous-pavés associés à J constituant un recouvrement de [z], i.e. [z] = U p i≤ ≤ 1 [zJ,i]. Alors DF([z]) = U p i≤ ≤ 1 DF([zJ,i]). 5. Si un système de contraintes G(x)=0 est une sous-partie du système F(x)=0, alors pour [xJ] sous-pavé de [x], on a DF([xJ]) ⊂ DG([xJ]). 6. Supposons que le système F(x)= 0 soit équivalent à un système qui s’écrive G(x)=0, alors pour [xJ] sous-pavé de [x], on a DF([xJ]) = DG([xJ]) E. Théorèmes Soient [x] un pavé de IRn , (fi)i=1…p des fonctions réelles et F=(f1, …,fp). Soit I={1…n} et le CSP H = (F(x)= | x∈[x]). 1) Théorème 1 : calcul du domaine globalement consistant à l’aide des domaines de consistance associés au complémentaire de chaque composante Pour tout j ∈ I, on a : Πj(S) = [xj]∩ DF( { } × − ∈ j I i [xi]) où Πj(S) est la projection de la solution S selon la jème composante. En répétant n fois cette opération pour toutes les composantes, on obtient un pavé globalement consistant. 2) Théorème 2 Soit [xJ] le sous-pavé de [x] associé à J. On note [ − 1 J x ] et [ + 1 J x ] les composantes de [xJ] qui apparaissent respectivement une fois au plus et deux fois au moins dans le graphe des contraintes. On a pour tout + 1 J x dans [ + 1 J x ] DF([ − 1 J x ]× + 1 J x ) = p ... 1 i= I D i f ([ − 1 J x ]× + 1 J x ) 3) Théorème 3 Pour j ∈ 1…n, soit le CSP noté HI-{j}, dans l’espace IRn-1 , correspondant aux variables réduites aux xi ≠ xj et aux contraintes les reliant i.e. HI-{j} = (g(y)=0, y∈ { } × − ∈ j I i [xi]) où g est le sous-ensemble des contraintes F indépendantes de la variable xj. Notons SI-{j} l’ensemble solution du CSP HI-{j} . On a le résultat : DF( { } × − ∈ j I i [xi]) = DF(SI-{j}) (2) Corollaire1 Posons f{j} l’ensemble des contraintes reliant la variable xj aux autres variables dans H,. On a la relation suivante découlant du résultat précédent : DF( { } × − ∈ j I i [xi]) = D { } j f (SI-{j}). (3) Corollaire2 Supposons de plus que l’ensemble de contraintes f{j} relie xj uniquement aux q variables d’indices notés j1,…, jq (q≤n), on a alors : DF( { } × − ∈ j I i [xi]) = D { } j f (Π j1 … j p ,(SI-{j}) (4) où Π j1 … j p est la projection sur l’espace des (x j1 ×…× x j p ). IV. EXEMPLE : RESOLUTION D’UN CSP CONTENANT UN CYCLE Considérons un CSP H = {F(a, b, x, y) = 0 | (a×b×x×y)∈[a1, a2]×[b1, b2]×[x1, x2]×[y1, y2]} où F est constitué des 2 contraintes linéaires y+x =a et y –x =b Le graphe de ce CSP contient un cycle (fig.4) et est bien connu pour mettre en défaut l’algorithme de Waltz [6]. Figure 4 : domaine de consistance d'un intervalle. Pour résoudre ce CSP en utilisant la méthode de consistance globale, considérons d’abord la variable y. A. Calcul de la composante [y] globalement consistante In te rv a lle g lo b a le m e n t c o n s is ta n t a v e c x 0 x 0 y x Figure 5 : contraintes de l’exemple. Appliquons le théorème 1 pour déterminer [y] globalement consistant avec H. On a : Π3(S) = [y] ∩ DF([a]×[b]×[x]) 1) Etape 1 : bornes du domaine associé à un scalaire x0 La variable x étant la seule à apparaître plus d’une fois dans les équations, d'après le théorème 2, pour un x0 ∈ [x], le domaine de consistance associé à [a]×[b]×x0, DF([a]×[b]×x0) peut être calculé grâce à une intersection des domaines obtenus en prenant les contraintes séparément : y b x a DF([a]×[b]×x0)=([a]–x0)∩([b]+x0)=([a1,a2]–x0)∩([b1, b2]+x0) = ([a1–x, a2 –x0]) ∩ ([b1+x0, b2+x0]) = [Sup(a1–x0, b1+x0), Inf(a2 –x0, b2+x0)] (5) (1) 2) Etape 2 : évolution des bornes en fonction de x0 On cherche à caractériser le domaine lorsque x0 parcourt [x] notamment en étudiant les bornes de l’intervalle (5). Faisons une étude de la fonction suivante ∆(x) = (a–x)–(x+b) = a–b– 2x. Notons x ab = 2 b a − . ∆ est décroissante et s’annule pour x ab . Le tableau qui suit détermine les maxima et minima de a– x et b+x selon x. [x ab , + ∞[ ]-∞, x ab ] <0 >0 ∆(x) b+x a–x Sup{a–x, b+x} a–x b+x Inf{a–x, b+x} En remplaçant dans ce tableau le couple (a,b) par chaque couple (a1,b1) et (a2,b2), on obtient 3 secteurs (P1, P2, P3) qui recouvrent IR et pour lesquels les bornes de DF([a]×[b]×x) sont connues. P3=[x 2 2b a , +∞[ P2=[x 1 1b a ,x 2 2b a ] P1=]-∞,x 1 1b a ] Si x 1 1b a x 2 2b a [b1+x, a2–x] [a1–x, a2–x] [a1–x, b2+x] DF([a]×[b]×x) 3) Etape 3 : élimination des x pour lesquels l’intervalle DF([a]×[b]×x) est impropre Il est à noter que le domaine de consistance peut être impropre (ce qui signifie « vide » physiquement) si sa borne supérieure devient inférieure à sa borne inférieure. Par exemple, pour x dans P1, DF([a]×[b]×x) = [a1–x, b2+x], ce domaine est impropre si a1–x>b2+x ⇔ si x< 2 2 1 b a − soit x< x b a 2 1 . On note P1,s (s pour solution), l’ensemble des P1 pour lesquels [a1–x, b2+x] est non vide. On a P1,s = P1∩[x b a 2 1 , + ∞[ On fait de même pour P3 pour supprimer les intervalles impropres. On introduit ainsi : P3,s = P3∩]–∞, x 1 2b a ]. Pour P2, on remarque que les intervalles sont toujours propres (pour tout x, b1+x