FR 3054886 A1 20180209 FR 1601189 A 20160802 1 SYSTEME ET PROCEDE GLOBAL DE GEOLOCALISATION A PARTIR DE MESURES DE DISTANCES ET DE POSITIONS D'ANCRES IMPRECISES L'invention concerne un procédé global et un système permettant la géolocalisation d'un (ou plusieurs) objet(s) à partir de mesures de distances, obtenues par une fonction de mesure de distances inter-noeuds connue sous le terme anglo-saxon « ranging », et de positions d'ancres imprécises. Le procédé permet ainsi de déterminer la position d'un objet sur une carte, sur un plan, dans un repère donné à l'aide de ses coordonnées géographiques, latitude/longitude ou d'autres coordonnées. La détermination de la position d'un objet dont on connaît les distances à d'autres objets de positions connues est un sujet classique dans le domaine de la localisation. En général, on utilise des stations de détection dont la position est parfaitement connue ou « ancres ». Dans ce cas, l'incertitude du résultat de la position réside principalement dans la précision des mesures de distances appelées plus loin « ranging ». Une autre approche possible consiste à déterminer le positionnement relatif des noeuds d'un réseau de stations, sur la seule base d'informations de distances relatives entre tout ou partie de ces noeuds. La connaissance précise d'un nombre limité d'informations a priori de positions sur certains noeuds permet alors de déterminer la position absolue de l'ensemble des noeuds du réseau. Cependant, plusieurs obstacles doivent être surmontés, notamment les suivants: - L'ensemble des mesures de distances entre les noeuds n'est pas forcément accessible, du fait de la portée des modules de ranging, - Les mesures de distances sont nécessairement entachées d'erreurs rendant la résolution géométrique potentiellement surdéterminée, - Les informations nécessaires au positionnement absolu peuvent être distribuées sur les coordonnées de plusieurs noeuds, 3054886 2 - Enfin, les informations nécessaires au positionnement absolu peuvent également être entachées d'erreurs, potentiellement plus importantes que celles associées au ranging. Ce dernier point est particulièrement important en pratique, 5 notamment en navigation collaborative. En effet, l'information de positionnement absolu de certains noeuds est souvent obtenue par des récepteurs du système de positionnement par satellite connu sous l'abréviation GNSS commerciaux (Global Navigation Satellite System), dont l'erreur de positionnement peut, dans des conditions de réception difficiles, 10 largement excéder les erreurs de mesures de distance (ranging) entre noeuds. Ignorer cette situation peut alors conduire à des erreurs de positionnement des noeuds libres, voire à rejeter des mesures de ranging valides, mais incompatibles des distances calculées à partir des positions absolues supposées sans erreurs. 15 L'un des problèmes techniques posé est de trouver une solution efficace de calcul des positions de noeuds, afin qu'une métrique des écarts entre les mesures de ranging et les distances entre noeuds de la solution soit minimale et en prenant en compte l'incertitude associée aux erreurs de ranging et aux erreurs de positionnement absolu. 20 L'art antérieur décrit principalement deux approches pour traiter ce problème. Une première approche consiste à reconstruire une géométrie relative des noeuds d'un réseau à partir d'informations de ranging et, éventuellement, d'informations angulaires entre noeuds, par exemple par 25 goniométrie au sein d'un noeud. Ces méthodes sont généralement regroupées sous le terme de « localisation sans ancre » ou en anglo-saxon « Anchor Free Localization ». Dans cette approche, qui utilise uniquement les mesures de ranging, toutes les positions des noeuds sont libres, a priori, et les méthodes cherchent à ajuster celles-ci de telle sorte que l'erreur quadratique moyenne entre les distances calculées entre noeuds et les mesures de ranging soit minimale. De très nombreux algorithmes ont été 3054886 3 proposés, du simple algorithme de type ressort de masse ou « mass-spring » à des techniques d'optimisation plus complexes, par exemple, la résolution des moindres carrés par Newton-Raphson, le filtrage particulaire, etc. L'essentiel des variantes de cette approche s'attache à éviter la convergence 5 vers un minimum local sans toutefois le garantir. Une deuxième approche vise à reconstruire la position absolue des noeuds du réseau à partir d'informations de ranging moyennant la connaissance a priori de la position de certains d'entre eux, appelés « ancres ». Il s'agit également de minimiser l'écart quadratique moyen entre 10 la distance entre les positions des noeuds et les mesures de ranging, certaines positions étant a priori fixes et connues. Le problème est alors un problème de minimisation d'une fonction des coordonnées de noeuds libres, par exemple via un algorithme de type plus forte pente ou en anglo-saxon « steepest descent ». L'article « Anchor-Based Three-Dimensional 15 Localization Using Range Measurements », Wang, Yue et al, illustre cette approche qui ne garantit cependant pas l'atteinte d'un optimum global. Des travaux plus théoriques proposent des méthodes d'optimisation globale. Une troisième approche utilise des sources ou ancres externes de positions inconnues. Le problème est connu sous le terme « autocalibration » 20 où l'on cherche à localiser conjointement des sources et les capteurs qui les détectent. Des différences de temps d'arrivée ou TDOA sont utilisées, ce qui donne une information moins riche qu'une mesure directe de ranging, assimilable à un temps d'arrivée ou TOA (abrégé anglo-saxon de « Time Of Arrivai ») et n'exploite pas d'informations a priori sur les positions des 25 sources. L'article « Calibration-Free TDOA Self-Localization », Wendeberg Johannes et al, in Journal of Location Based Services, May 2013, illustre une mise en oeuvre possible de cette approche au travers de plusieurs algorithmes classiques (de type mass-spring, gradient descent, Gauss Newton...) ou plus spécifiques (algorithme de « Cone alignment »), ces 30 algorithmes étant connus de l'homme du métier. L'un des inconvénients de l'art antérieur est qu'il suppose : 3054886 4 - Soit que toutes les positions des capteurs sont libres, ne délivrant qu'une géométrie de l'ensemble des noeuds potentiellement précise, mais des coordonnées relatives des noeuds entre eux, - Soit que la détermination de la position absolue des noeuds repose 5 sur la connaissance externe de la position de certains d'entre eux dont l'exactitude est supposée parfaite. A priori, l'art antérieur ne traite pas de l'intégration conjointe de l'incertitude sur la position des ancres et de la possible remise en cause de ces positions. La figure 1 illustre les problèmes non résolus par l'art antérieur. 10 Dans cet exemple, les coordonnées des ancres associées aux noeuds M1 et M2 sont supposées être accessibles de façon idéale, c'est-à-dire sans erreur, par exemple grâce à des relevés topographiques, alors que les coordonnées de l'ancre M3 sont en pratique entachées d'une erreur d3, par exemple mesurée par un système GNSS, positionnant l'ancre M3 au point M'3. Une 15 autre hypothèse de cette illustration est que la précision de ranging est parfaite, en pratique l'erreur est très inférieure à d3. Les mesures de ranging sont représentées par une flèche sur la figure 1. Les techniques de l'art antérieur estiment incorrectement la position du noeud libre en M'4, la position réelle du noeud libre M4 en distribuant les erreurs de ranging 20 associées à ce noeud, ce qui aboutit à un minimum d'erreur quadratique moyenne résiduelle important. En outre, la position du noeud M3 n'est pas remise en cause, et reste erronée. Le procédé selon l'invention présente une méthode d'estimation des positions des noeuds basée sur une minimisation globale d'un critère, 25 constitué de l'écart quadratique pondéré entre toutes les mesures de distances entre noeuds du réseau et les mesures d'ancrages disponibles à un instant donné, et un modèle de mesures théoriques associées. Le procédé va utiliser un vecteur de mesures hétérogène comprenant à la fois les mesures de ranging entre noeuds (mesures de distances inter-noeuds) et 30 les coordonnées des ancres dont on dispose d'une connaissance imprécise. On introduit donc les coordonnées des ancres comme des mesures 3054886 5 supplémentaires de covariance connue, s'ajoutant aux mesures de ranging entre noeuds dans le vecteur d'observations (également appelé « vecteur de mesures »). Les coordonnées des noeuds associés sont parallèlement introduites dans le vecteur d'état à estimer, de sorte qu'elles peuvent être 5 remises en cause par l'algorithme de minimisation. Le procédé consiste alors en une estimation conjointe des coordonnées des noeuds constituant le vecteur d'état par recherche du minimum du critère quadratique global qui tient compte de l'ensemble des observations disponibles (mesures de ranging et mesures d'ancrage) et de leurs incertitudes respectives (matrice 10 de covariance sur les mesures de ranging et sur les coordonnées des ancres). L'invention concerne un procédé pour déterminer la position d'un ou plusieurs objets Mi susceptibles de se déplacer dans un réseau, un ou plusieurs objets étant dotés d'une capacité de mesure de distance aux autres 15 objets du réseau, caractérisé en ce qu'il comporte au moins les étapes suivantes : - disposer de coordonnées de points Ai et de l'incertitude sur ces coordonnées décrivant des informations sur la position de tout ou partie des objets à localiser, objets dits ancrés, 20 - mesurer au moins une distance inter-objets entre au moins un ou plusieurs couples d'objets Mi, Mj, avec une valeur d'incertitude associée à chaque mesure et exécuter les étapes suivantes : - Calculer un vecteur initial X représentatif des positions estimées pour les noeuds dont on cherche la position, 25 - Calculer un critère c(x) en utilisant un vecteur de mesures observées Mes contenant l'ensemble des mesures de distance inter-objets disponibles pour les objets de position à estimer et des coordonnées d'objets dits ancrés, une matrice de covariance représentant la variation statistique sur le vecteur de mesures et le vecteur de mesures théoriques Mes(x) correspondant au 30 vecteur de mesures observées Mes , 3054886 6 - Minimiser ce critère c(x) et déterminer les coordonnées de la position d'un ou desdits objets correspondant à ce minimum, X=Arg Min[C(X)]. Selon une variante de réalisation, le procédé utilise un critère C(x) défini de la manière suivante : 5 C(X)=LIVles- Mes(X)1E-1[Mes- Mes(X)1 où : - T désigne la transposée, X est le vecteur d'état contenant les coordonnées des objets dont on cherche à estimer la position correspondant à tout ou partie des 10 positions P(t)= {M (t)};,' Mes = 1?` A est le vecteur de mesures observées contenant l'ensemble des observations disponibles à l'instant t considéré ; il est composé : o D'un vecteur R contenant les mesures de ranging r1 15 disponibles à cet instant t, o D'un vecteur A contenant les mesures d'ancrage - Mes (X) disponibles à cet instant ; D(X)` XA le vecteur modèle des mesures, qui contient les A mesures théoriques associées aux mesures observées Mes ; il est 20 composé de deux vecteurs D(X) et XA OÙ : o les composantes de D(X) correspondent aux distances inter- noeuds, entre deux noeuds d(MoMj), o xA comprend tout ou partie des composantes du vecteur d'état X. 3054886 7 - E vR v est la matrice de covariance comportant la matrice AR EAR 1A .1 de covariance BR contenant les incertitudes sur les mesures de ranging et la matrice de covariance EA contenant les incertitudes sur les mesures d'ancrages, ainsi que la matrice rectangulaire BAR 5 contenant les covariances croisées entre ces deux types de mesures. Pour définir la matrice de covariance EA, on tient compte, par exemple, des incertitudes d sur chaque coordonnée des ancres et leur corrélation éventuelle ; pour définir la matrice de covariance ER on tient 10 compte des incertitudes sur chaque mesure de ranging et leur corrélation éventuelle ; pour définir la matrice BAR, on tient compte des corrélations éventuelles entre les erreurs sur les mesures de ranging et les erreurs sur les coordonnées des objets ancrés. L'invention concerne aussi un dispositif permettant de déterminer 15 la position d'un ou plusieurs objets Mi susceptibles de se déplacer dans un réseau, un ou plusieurs objets étant dotés d'un dispositif de mesures de distance inter-noeuds, les noeuds communiquant entre eux grâce à un moyen de communication, caractérisé en ce qu'il comporte au moins un processeur adapté à exécuter les étapes du procédé selon l'invention et un dispositif de 20 mesure de la position des noeuds. Selon une variante de réalisation, le réseau est un réseau de communication et les noeuds comportent un module de communication par radiofréquence. D'autres caractéristiques et avantages de la présente invention 25 apparaîtront mieux à la lecture de la description qui suit, d'exemples de réalisation, annexée des figures qui représentent : - Figure 1, une illustration des problèmes de l'art antérieur, - Figure 2, un schéma d'un réseau de communication, 3054886 8 - Figure 3, un organigramme avec les étapes principales du procédé selon l'invention, - Figure 4, un exemple d'implémentation du procédé selon l'invention, et 5 - Figure 5, un exemple de résultat après la mise en oeuvre du procédé selon l'invention. Afin de mieux faire comprendre le procédé selon l'invention, l'exemple qui suit est donné dans le cas d'un système de communication 1 comprenant plusieurs noeuds M. Chaque noeud Mi comporte, par exemple, 10 un moyen de communication 10, un processeur 12 adapté à exécuter les étapes du procédé selon l'invention et une batterie 13 ou dispositif d'alimentation. Les noeuds Mi communiquent entre eux, par exemple, par une liaison radiofréquence, sans fil, ou d'autres moyens connus de l'homme du métier. 15 Le système comporte aussi un dispositif pour déterminer la position absolue de tout ou partie des noeuds. Ainsi, tout ou partie des noeuds peuvent par exemple être équipés d'un récepteur 11 qui, couplé avec un dispositif satellitaire 20, permet au noeud équipé du récepteur 11 de se géo-localiser. Ce dispositif peut être un système de géolocalisation GPS 20 (Global Positioning System), un système GNSS (Global Navigation Satellite System), un moyen de topographie. Sur la figure 2, le noeud M2 est équipé d'un récepteur 11, alors que le noeud M3 ne l'est pas. Il comporte aussi un dispositif de mesures de distance ou dispositif de ranging 21 colocalisé par exemple sur un noeud Mi ou sur 25 chacun des noeuds du système. Par exemple, le dispositif de mesures de distance peut se présenter sous la forme d'une carte électronique portée par le noeud. Selon une autre variante de réalisation, ce pourrait être une fonctionnalité du système de communication au niveau du noeud mesurant le temps mis par l'onde radio pour transiter entre les noeuds. 30 Soit un ensemble de N noeuds Mi de positions : 3054886 9 xi yi en trois dimensions (3D) et OM, = 0Mi = X. en deux dimensions (2D), les yi coordonnées sont, par exemple, choisies dans un repère cartésien, O étant le point origine choisi dans ce repère. La distance entre deux noeuds M, , Mi , ) est définie 5 par Cl(Mo J)=- . L'ensemble des positions des N noeuds Mi à un instant donné t, Pi(t)={ ,(t)},,c,..Ni est appelé « géométrie courante ». ri, est une mesure de distance (ranging) obtenue entre le noeud Mi et le noeud Mi par un dispositif de mesure dédié (module de ranging situé par exemple au niveau du noeud) et connue avec une incertitude , 10 correspondant à un écart type sur la mesure. On appellera « ancre » ou « mesure d'ancrage »4, une information de position absolue sur la kième coordonnée du noeud M, , obtenue avec une incertitude csAki , correspondant à l'écart type sur cette coordonnée. Cette information peut être obtenue par des moyens divers tels que des relevés 15 topographiques ou des récepteurs GNSS. L'information sur la position d'une ancre varie en fonction de l'instant de mesure. C'est une fonction délivrée par exemple en temps réel par un dispositif GPS. Par souci de simplification d'écriture, le temps n'est pas indiqué. Un noeud disposant d'une mesure de positionnement absolue est dit « noeud ancré ». 20 Toutes les coordonnées d'une ancre peuvent être connues a priori, ou en partie seulement, par exemple, lorsque la position du noeud est déterminée par examen d'une carte : si le noeud est situé sur une route, on peut savoir que le noeud est à une latitude donnée sans en connaître la longitude. 3054886 10 Le procédé permettant d'estimer la position de noeuds, par exemple, dans un système de communication met en oeuvre une étape au cours de laquelle on va chercher à minimiser un critère global représentatif de l'ensemble des mesures de ranging disponibles entre noeuds ainsi que les 5 coordonnées des ancres, informations de position absolue sur la kième coordonnée du noeud Mi obtenue avec une incertitude 6âi . On va effectuer une estimation conjointe des coordonnées des noeuds constituant le vecteur d'état par la recherche du minimum du critère quadratique global qui tient compte de l'ensemble des observations 10 disponibles, mesures de ranging et mesures d'ancrage, et de leurs incertitudes respectives traduites par une matrice de covariance sur les mesures de ranging et sur les coordonnées des ancres. Avant de détailler un exemple d'implémentation, la forme du critère global C(X) à minimiser est donnée. C(X) s'écrit sous la forme 15 générale : C(X) ---=[114es- Mes(X)1 E-' [Mes- Mes(X)1 où : - T désigne la transposée X est le vecteur d'état contenant les coordonnées des noeuds dont 20 on cherche à estimer la position, correspondant à tout ou partie des positions P(t)= ( st ),=0 N-1. Les coordonnées des noeuds pour lesquelles on dispose d'une ancre imprécise sont introduites dans le vecteur inconnu X à estimer, afin de rendre modifiables les coordonnées dans la recherche de la solution, (R 25 Mes = est le vecteur de mesures observées contenant ~A1 l'ensemble des observations ou mesures disponibles à l'instant t considéré; dans le cas général, il est composé de deux vecteurs R et A, où : 3054886 11 o Le vecteur R contient les mesures de ranging ru disponibles à cet instant t, 5 o Le vecteur A contient les mesures d'ancrage disponibles à cet instant t ; ces données sont des coordonnées de certains noeuds dits « ancrés », coordonnées accessibles par la mesure, obtenues par exemple par un capteur GNSS par objet; Mes (X) = r D()est le vecteur modèle des mesures, qui contient XA les mesures théoriques associées aux mesures observées Mes et 10 accessibles par le calcul ; il est donc composé de deux vecteurs : o D(X) est le vecteur des distances théoriques correspondant à R, calculé à partir du vecteur X et, si nécessaire, de connaissances a priori supposées parfaites; les composantes de D(X) correspondent aux distances inter-noeuds, entre 15 deux noeuds, d(Mi,Mj), o XA est le vecteur contenant les coordonnées théoriques des noeuds pour lesquels on dispose de mesures d'ancrages ; xA comprend tout ou partie des composantes du vecteur d'état X; 20 - E est la matrice de covariance globale sur toutes les mesures. Elle comporte donc : o La matrice de covariance ER sur les mesures de ranging qui permet de quantifier l'incertitude sur chaque mesure de ranging ainsi que la corrélation statistique éventuelle des 25 mesures de ranging entre elles. La précision de la mesure de ranging n'est pas forcément identique pour toutes les mesures (usage possible de technologies différentes selon 3054886 12 les noeuds), et toute information disponible sur ces précisions est explicitement exploitée, o La matrice de covariance EA sur les mesures d'ancrages. Les termes diagonaux de cette matrice sont égaux aux carrés 5 des incertitudes o-Ak, mais il est aussi possible de tenir compte de corrélations entre les erreurs sur les différentes coordonnées : la matrice EA n'est pas nécessairement diagonale, o Une matrice EAR comprenant les termes croisés résultant 10 d'une éventuelle corrélation entre les erreurs sur les mesures de ranging et sur les coordonnées des ancres. En cas de non corrélation, ces termes croisés sont nuls (EAR=0). La matrice de covariance s'écrit donc sous la forme générale suivante : (" y , sachant que les termes de E AR peuvent être nuls, et T = R AR EAR ) 15 désigne la transposée. Un exemple détaillé d'implémentation des étapes du procédé selon l'invention est donné ci-après et illustré à la figure 3. Au préalable, on se dote d'un vecteur d'état, d'un vecteur de mesures et de sa matrice de covariance. 20 - Vecteur d'état X . le vecteur X contient les coordonnées des noeuds que le procédé va chercher à estimer. Dans le cas le plus général, le vecteur X contient donc les coordonnées des N noeuds du réseau associés aux positions P(t)={m,(t)},=, En 3D, le vecteur X a 3N composantes et s'écrit \T 25 X= (x0,y0,zo,xi,m,zi,...,xN_ijN_i,zN_1) , En 2D, le vecteur X a 2N composantes et s'écrit X = (xo,y0,x1,y1,-,xN_1,YN-1) 3054886 13 En pratique, il peut y avoir des cas particuliers où l'on ne cherche pas à localiser certains noeuds ou à estimer certaines coordonnées. Dans ce cas, le vecteur X peut ne contenir qu'une partie des coordonnées des N noeuds. Cependant, si l'on souhaite que le procédé puisse modifier, dans 5 sa recherche de solutions, les positions des noeuds pour lesquelles on dispose d'informations imprécises (« ancres »), les coordonnées de ces noeuds doivent être introduites dans le vecteur d'état X à estimer. Pour la mise en oeuvre du procédé : A On détermine le vecteur des mesures Mes , 301, comprenant lui-même 10 deux vecteurs : o Le vecteur R contenant les mesures de ranging r11 disponibles à l'instant considéré: à noter que le vecteur R peut être surdimensionné en considérant le nombre maximal de mesures de ranging pouvant être disponibles à un instant donné, soit 15 typiquement N(N-1) mesures où N est le nombre maximal de noeuds (et en comptant les mesures bidirectionnelles i-j et j-i, i et j sont les indices de deux noeuds). En fonction des mesures disponibles, on remplira ou non les indices correspondants, o Le vecteur A contenant les mesures d'ancrage 4, c'est-à-dire les 20 coordonnées des noeuds pour lesquels on dispose d'informations a priori, d'incertitude connue (« noeuds ancrés »); On construit, 302, la matrice de covariance sur les mesures E, à partir : o De la matrice de covariance ER sur les mesures de ranging ; les termes diagonaux de ER sont donnés par les valeurs d'incertitudes 25 0-2' ; si les mesures de ranging sont décorrélées entre elles, la matrice ER sera une matrice purement diagonale, o De la matrice de covariance EA sur les mesures d'ancrages. Les termes diagonaux de cette matrice sont égaux à o-2, , on peut tenir compte de la corrélation éventuelle entre les erreurs sur les 3054886 14 différentes coordonnées : la matrice EA n'est pas nécessairement diagonale, o Une matrice EAR comprenant les termes croisés résultant d'une éventuelle corrélation entre les erreurs sur les mesures de ranging et 5 les erreurs sur les coordonnées des ancres. En cas de non corrélation, ces termes croisés sont nuls (EAR=0), avec : E ER v - AR T\ \1AR EA ) - On minimise, 303, le critère C(X), 10 C(X) = Mes(X)1T E-1[11jies- Mes(X)1, en calculant ( D(X)\ X A - On détermine, 304, les coordonnées des objets à la Mes(X) fin de l'étape de vecteur modèle des mesures défini précédemment, et minimisation, en prenant le vecteur X solution de la minimisation du critère, X=Arg Min[C(X)], le vecteur X contenant les coordonnées des 15 objets. Sous l'hypothèse d'erreurs de mesures gaussiennes additives centrées, de matrice de covariance connue I, l'estimateur minimisant le critère c(x) n'est autre que l'estimateur du maximum de vraisemblance de X, car minimiser c(x) revient à maximiser la vraisemblance A 20 probabilité Mes X I . Il est de plus réputé robuste, même en présence de mesures déviant de ce modèle d'erreurs gaussiennes. Du fait de la non linéarité de Mes(X), la minimisation de c(x) n'est pas immédiate et les algorithmes efficaces minimisant c(x) sont des algorithmes itératifs connus de l'homme du métier. 3054886 15 De nombreux algorithmes de minimisation de critère quadratique existent et peuvent être utilisés pour estimer les positions à partir des mesures de ranging et des mesures d'ancrage (par exemple, algorithme du gradient, algorithme de Newton-Raphson,...). 5 Une variante de réalisation utilise les algorithmes de Gauss- Newton, qui sont réputés présenter un bon compromis entre coût de calcul, efficacité et robustesse. Ils utilisent un développement limité du critère à l'ordre deux, en négligeant toutefois l'un des deux termes du hessien du critère. L'équation d'itération s'écrit sous la forme générale suivante : X k±i -Xk a(k)H k 1 Jk 10 où : - AT, est le vecteur des coordonnées des noeuds estimées à l'itération k, (ables T( - `"' E-1 Mes- Mes(X est le gradient du critère c(x), ax - X = Xk calculé en Xk, X = Xk est le premier terme du hessien du (aMeST aMeS - Hk= 2 ax, ax 15 critère c(x) , calculé en Xk, ( -8X ) est la matrice jacobienne sur le vecteur de mesures théoriques mes (x) , comprenant le vecteur de mesures théoriques de distance D(X) et le vecteur x, contenant les coordonnées des noeuds « ancrés » (et comprenant tout ou partie du vecteur d'état X), 20 - a(k) est un pas d'optimisation, constant ou variable (Gt=1 pour l'algorithme de Gauss-Newton classique mais de nombreuses variantes utilisent des pas adaptatifs visant à accélérer la convergence, ou bien à éviter de rester bloqué dans un minimum local). 3054886 16 Ainsi, l'équation d'itération du procédé pour déterminer le vecteur des coordonnées des noeuds à l'itération k+1 à partir de l'itération k s'exprime par: Xk+i= Xk+ a(k)[(amaxes\T Ilamaxes) / aMeS)7' i[Mes- Mes(X)] ax . - -1 , 5 La nouvelle estimation Xk+1 résulte de l'application d'une « force de rappel » [, sur le vecteur d'écart Mes- Mes(X) entre mesures observées et mesures théoriques qu'il s'agisse de ranging ou d'ancrage. Dans le cas particulier d'un critère quadratique : - Une matrice (non carrée et non diagonale dans le cas général) est 10 appliquée au vecteur I Mes-Mes(X) I , autrement dit, la minimisation se fait globalement et non pas noeud par noeud, ou mesure par mesure. Cette matrice n'est ni constante, ni « libre » (au coefficient alpha près), mais résulte d'un calcul précis impliquant la matrice jacobienne du vecteur de mesures théoriques mes (x). 15 En pratique, on peut noter que les mesures de ranging et les mesures de coordonnées d'ancrage sont a priori issues de systèmes de mesures indépendants de sorte que ces mesures respectives sont le plus souvent décorrélées. Dans ce cas particulier, la matrice de covariance est diagonale par blocs et s'écrit E = o ; le critère c(x) est alors 0 E A i 20 constitué de la somme de deux critères : l'un, noté CR, sur les seules mesures de ranging et l'autre, CA, sur les seules mesures d'ancrage, avec : C(X) = CR + CA +[R D(x)] T E R1[R r(x)]-kk X A TEA ik xi- Selon une variante de réalisation, l'estimation du vecteur X minimisant le critère C(X), (303 figure 3) dans sa forme générale, s'obtient de 25 manière itérative en appliquant les étapes illustrées à la figure 4: 3054886 17 Etape d'initialisation, 401 : on dispose en entrée d'un vecteur initial X. contenant des positions estimées des noeuds qui peut être obtenu de plusieurs façons: a. En utilisant les positions estimées résultantes d'une application 5 précédente du procédé, b. En utilisant le résultat d'un algorithme sous-optimal de pré-positionnement, par exemple le procédé décrit dans la demande de brevet du demandeur déposée le même jour et intitulée « procédé et système de géo localisation par calcul direct d'éléments de 10 déplacement » ou bien un algorithme direct sous-optimal sur les mesures de ranging de pseudo-linéarisation PSL, c. De façon déterministe, par exemple, en exploitant des éléments connus sur les coordonnées de certains noeuds. Typiquement, si des données d'ancrage sont disponibles pour un noeud donné, les 15 coordonnées du vecteur X sont initialisées par les données d'ancrage, d. De façon aléatoire (tirage au sort) ; pour les noeuds pour lesquels on ne dispose pas de mesures d'ancrage, on peut réaliser un tirage aléatoire dans une zone ou selon une géométrie pré-définie ; pour 20 les noeuds pour lesquels on dispose de données d'ancrage, il est possible d'utiliser un tirage aléatoire centré sur l'ancre et de covariance égale à la covariance sur l'ancre. Cette technique permet d'initialiser le procédé autrement que sur un zéro du critère CA lié aux ancres, et ainsi d'éviter de rester bloqué sur des minima locaux. 25 Il est aussi possible de panacher ces approches : par exemple, utiliser les coordonnées d'ancrage pour initialiser les noeuds pour lesquels on dispose de ces coordonnées, et utiliser pour les autres noeuds un algorithme de type PSL exploitant les mesures de ranging (localisation classique sur mesures de TOA). 30 Etape 402 - on va calculer le vecteur X contenant les coordonnées des points pour une itération k+1 à partir du vecteur obtenu à l'itération 3054886 18 précédente k et d'un vecteur de rappel pondéré calculé de sorte à faire décroître le critère : 5 Calcul de xk+, à partir de xk : = X k ±a(k)3Xk aMes r 81) en xk des o Calcul de la matrice jacobienne r par dérivation - la sous-matrice ax ax 3XA est obtenue ,ax ,ax, mesures de distances théoriques disponibles : ainsi le terme ÔIP I,m de ,ax, distance inter-objets par rapport à la mième composante du vecteur d'état à estimer, 1 0 - La sous-matrice /agi relative aux mesures d'ancrages ne comporte que des 0 et des 1. o Calcul du vecteur A x k de « rappel » à appliquer en minimisant : A 8X ) ( a8 es AX k AMes k T E_t( aMeS )AX k - AMes ki avec AMk = Mes- Mes(Xk). Il s'agit là d'un problème de moindres carrés linéaires pondérés, dont la solution explicite a été donnée plus haut : - -1 1 5 [( a/1:évs 511:-A7)T _1T E AMesk " Selon une variante de réalisation, le problème est résolu en utilisant une décomposition en valeurs singulières (SVD), dont le détail est bien connu de l'homme de l'art. La résolution par décomposition en SVD présente l'avantage d'être plus stable numériquement et de traiter le cas est obtenu en dérivant la Hème mesure de 20 d'une matrice r ail/lesT ( 011/les E-1 singulière, ce qui peut arriver lorsque , ax , pax, 3054886 19 les mesures de ranging disponibles ou les données d'ancrage ne sont pas suffisamment nombreuses. Dans ce cas, l'algorithme s'adaptera en fixant automatiquement certaines variables du vecteur d'état. o Calcul du pas a (k) : ce pas peut être : 5 ^ Fixé une fois pour toutes, ce qui est la solution la moins coûteuse (a=1 dans l'algorithme de Gauss-Newton original), ^ Ajusté à chaque itération, afin de converger au plus vite : plusieurs méthodes publiées de détermination du pas sont possibles comme, par exemple, la méthode de Brent, la 10 méthode de Levenberg-Marquardt, etc. Des méthodes semi- empiriques consistant à partir d'une valeur fixe puis, à diviser par un coefficient P jusqu'à décroissance du critère (ou atteinte d'une valeur minimum), constituent généralement un bon compromis entre coût de calcul et rapidité de 15 convergence. o Actualisation du vecteur estimé : Xk+1 = Xk ±a(k)&ek ; Etape 403 - Arrêt du processus itératif qui se poursuit jusqu'à satisfaction de conditions prédéfinies, typiquement : ^ Critère c(x) non décroissant d'une itération à la suivante, i.e. 20 C(Xk+i)i C(Xk ) ^ Décroissance relative du critère c(x) inférieure à un seuil prédéfini, i.e., c()(,)) seuil * C (X k) ^ Nombre maximal d'itérations atteint, ^ Positions estimées n'évoluant plus suffisamment d'une 25 itération à la suivante (IAXI REVENDICATIONS1 - Procédé pour déterminer la position d'un ou plusieurs objets Mi susceptibles de se déplacer dans un réseau, un ou plusieurs objets étant 5 dotés d'une capacité de mesure de distance aux autres objets du réseau, caractérisé en ce qu'il comporte au moins les étapes suivantes : - disposer de coordonnées de points Ai et de l'incertitude sur ces coordonnées décrivant des informations sur la position de tout ou partie des objets à localiser, objets dits ancrés, 10 - mesurer au moins une distance inter-objets entre au moins un ou plusieurs couples d'objets Mi, Mj, avec une valeur d'incertitude associée à chaque mesure et exécuter les étapes suivantes : - Calculer un vecteur initial X représentatif des positions estimées pour les noeuds dont on cherche la position, 15 - Calculer un critère c(x) en utilisant un vecteur de mesures observées Mes (301) contenant l'ensemble des mesures de distance inter-objets disponibles pour les objets de position à estimer et des coordonnées d'objets dits ancrés, une matrice de covariance représentant la variation statistique sur le vecteur de mesures (302) et le vecteur de mesures théoriques 20 Mes(X) correspondant au vecteur de mesures observées Mes , - Minimiser ce critère c(x) (303) et déterminer les coordonnées de la position d'un ou desdits objets correspondant à ce minimum, (304) X=Arg Min[C(X)]. 25 2 - Procédé selon la revendication 1 caractérisé en ce que l'on utilise un critère c(x) défini de la manière suivante : T C(X) =[11/2es- Mes(X)1 E-'Mes- Mes(X)1 où : 3054886 25 - T désigne la transposée, X est le vecteur d'état contenant les coordonnées des objets dont on cherche à estimer la position correspondant à tout ou partie des positions P(t)= {m-,(t)},_, , R\ - Mes = (301) est le vecteur de mesures observées contenant A l'ensemble des observations disponibles à l'instant t considéré ; il est composé : o D'un vecteur R contenant les mesures de ranging r1 disponibles à cet instant t, 10 o D'un vecteur A contenant les mesures d'ancrage disponibles à cet instant, r D (X)\ XA j mesures théoriques associées aux mesures observées Mes ; il est composé de deux vecteurs D(X) et XA où : 15 o les composantes de D(X) correspondent aux distances inter- noeuds, entre deux noeuds o XA comprend tout ou partie des composantes du vecteur d'état X, - Mes (X) -= le vecteur modèle des mesures, qui contient les - E_ ( v L'R AR (302) est la matrice de covariance comportant la EAR A ) 20 matrice de covariance ER contenant les incertitudes sur les mesures de ranging et la matrice de covariance EA contenant les incertitudes sur les mesures d'ancrages, ainsi que la matrice rectangulaire EAR contenant les covariances croisées entre ces deux types de mesures. 25 3054886 26 3 - Procédé selon la revendication 2 caractérisé en ce que pour définir la matrice de covariance EA on tient compte des incertitudes o sur chaque coordonnée des ancres et leur corrélation éventuelle, pour définir la matrice de covariance ER on tient compte des incertitudes sur chaque mesure de 5 ranging et leur corrélation éventuelle et pour définir la matrice EAR on tient compte des corrélations éventuelles entre les erreurs sur les mesures de ranging et les erreurs sur les coordonnées des objets ancrés. 4 - Procédé selon l'une des revendications précédentes caractérisé en ce que l'on initialise le vecteur d'état X en utilisant au moins une des méthodes suivantes : o de façon arbitraire déterministe, o de manière aléatoire, par tirage au sort des valeurs des coordonnées des noeuds, o en utilisant les positions estimées résultantes d'une application précédente du procédé, o en utilisant la solution de méthodes de résolution sous-optimale telles que la pseudo-linéarisation PSL, ou autre algorithme peu coûteux, o en exploitant des éléments connus sur les coordonnées de certains noeuds, comme les coordonnées d'ancrage pour les objets « ancrés ». 5 - Procédé selon l'une des revendications précédentes caractérisé en ce 25 que l'on obtient des informations de position des ancres par des relevés topographiques ou par un système GNSS en temps réel. 6 - Procédé selon l'une des revendications précédentes caractérisé en ce que l'on minimise le critère C(X) par mise en oeuvre d'un algorithme de 30 Gauss-Newton. 3054886 27 7 - Procédé selon l'une des revendications précédentes caractérisé en ce que le vecteur X(k+1) pour une itération k+1 est obtenu à partir du vecteur X(k) obtenu à l'itération précédente k en exécutant une méthode de moindres carrés linéaires utilisant une décomposition en valeurs singulières. 5 8 - Procédé selon l'une des revendications précédentes caractérisé en ce que la condition d'arrêt du procédé utilise un des critères suivants : - Critère c(x) non décroissant d'une itération à la suivante, - Décroissance relative du critère c(x) inférieure à un seuil prédéfini, 10 - Nombre maximal d'itérations atteint, - Positions estimées n'évoluant plus suffisamment d'un instant à l'autre 9 - Procédé selon l'une des revendications précédentes caractérisé en ce 15 qu'un objet est désigné comme maître et en ce que ledit objet est adapté à exécuter les étapes du procédé selon l'une des revendications 1 à 8 et à centraliser les résultats. 10 - Procédé selon l'une des revendications 1 à 8 caractérisé en ce que 20 chaque objet du réseau est adapté à exécuter les étapes du procédé selon l'une des revendications 1 à 8. 11 - Procédé selon l'une des revendications précédentes caractérisé en ce que l'objet dont la position est recherchée est un noeud dans un système de 25 communication. 12 - Dispositif permettant de déterminer la position d'un ou plusieurs objets Mi susceptibles de se déplacer dans un réseau, un ou plusieurs objets étant dotés d'un dispositif de mesures de distance inter-noeuds (21), les noeuds 30 communiquant entre eux grâce à un moyen de communication (10), 3054886 28 caractérisé en ce qu'il comporte au moins un processeur (12) adapté à exécuter les étapes du procédé selon l'une des revendications 1 à 11, un dispositif de mesure (11, 20) de la position des noeuds. 5 13 - Dispositif selon la revendication 12 caractérisé en ce que les noeuds comportent un module de communication par radiofréquence et le réseau est un système de communication (1). 10