FR 3054887 A1 20180209 FR 1601190 A 20160802 PROCEDE ET SYSTEME DE GEOLOCALISATION PAR CALCUL DIRECT D'ELEMENTS DE DEPLACEMENT L'invention concerne un procédé et un système permettant la 5 géolocalisation d'un ou de plusieurs objets à 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, par calcul direct d'éléments de déplacement. Le procédé permet ainsi de déterminer la position d'un objet sur une carte, sur un plan, dans un repère 10 donné à l'aide de ses coordonnées géographiques, latitude/longitude ou 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 15 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 20 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, par exemple: 25 - 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 30 distribuées sur les coordonnées de plusieurs noeuds, 3054887 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 30 quadratique moyenne entre les distances calculées entre noeuds et les mesures de ranging soit minimale. De très nombreux algorithmes ont été 3054887 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 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 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 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 » 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 qui n'exploite pas d'informations a priori sur les positions des 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 : 3054887 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. 10 La figure 1 illustre les problèmes non résolus par l'art antérieur. 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 15 mesurée par un système GNSS, positionnant l'ancre M3 au point M'3. Une autre hypothèse de cette illustration est que la précision de ranging est parfaite, en pratique très inférieure à d3. Les mesures de ranging sont représentées par des flèches 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 20 noeud libre M4 en distribuant les erreurs de ranging 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 va notamment exploiter l'ensemble des incertitudes des mesures de ranging et des positions des ancres, ce qui 25 permet notamment de modifier la position des ancres, afin d'aboutir à une erreur quadratique minimale sur les mesures de ranging. Le résultat de la mise en oeuvre du procédé selon l'invention permettra l'obtention précise de la position d'un objet dans un espace donné. L'invention concerne un procédé pour déterminer la position d'un 30 ou plusieurs objets susceptibles de se déplacer dans un réseau, chaque objet étant doté d'une capacité de mesure de distance aux autres noeuds du 3054887 5 réseau, au moins une partie des coordonnées d'un objet étant connue, caractérisé en ce qu'il comporte au moins les étapes suivantes : - Générer un ensemble de points Ai ou ancres, les coordonnées des ancres et l'incertitude sur les coordonnées décrivant des informations 5 sur la position des objets et l'incertitude sur ces informations, - Générer un ensemble de points contenant les positions estimées des objets et définir une position initiale des points, - Définir un ensemble de mesures de distance entre au moins deux objets Mi, Mj, avec des incertitudes associées, et exécuter les étapes 10 suivantes : - Etape 1, pour chaque objet M' calculer un déplacement correspondant à la somme vectorielle des déplacements de mesure ou ranging sur l'ensemble de mesures de ranging disponibles vers l'objet M, et induits sur cet objet M, par la totalité des autres objets 15 disposant d'une mesure de ranging à partir dudit objet M, , - Etape 2, pour chaque objet Mi, possédant une coordonnée d'ancrage dans une ancre virtuelle associée 4, calculer une valeur de déplacement de rappelâme;vers cette ancre , - Etape 3, à chaque objet M, appliquer un déplacement égal à la 20 somme du déplacement de ranging 55_>, et de la valeur de déplacement de rappel L précédemment calculés, - Etape 4, calculer le carré du terme d'erreur A2, entre l'estimation de la distance et la mesure de distance fournie par les dispositifs de ranging sur l'ensemble des noeuds, comparer cette quantité à un critère d'arrêt 25 défini au préalable par un opérateur, si A2,', Afin , ou bien max(Aii ) 0 (coordonnée ancrée) 1, si u = 0 (coordonnée ancrée fixe) 0, si u 0 (coordonnée ancrée) 1, si cr = 0 (coordonnée ancrée fixe) 0, si a- Ai fixée à une valeur arbitraire négative (par exemple, -1). Cette coordonnée du noeud sera dite « libre ». A chaque itération du procédé, on calcule pour chaque noeud M : 3054887 12 - La somme vectorielle des déplacements de ranging -b"_>, applicables au noeud Mi uniquement dus aux écarts par rapport aux mesures de ranging relatives au noeud M . Ce déplacement est calculé comme la somme sur l'ensemble des mesures de ranging R. des déplacements 5 dus à la mesure de ranging ru relative entre M, et m et à son incertitude 6ru ; Le vecteur qui lie les deux points Mi et M est défini comme suit: M M sj~i où iS>, = ço(Au,a, ^ avec Au les coordonnées de JER, MiMi M Mi, ip est une fonction de déplacement donnée et Ri 10 représente l'ensemble des mesures de ranging disponibles versMi. Si tout ou partie des coordonnées de Mi est « ancrée », on calcule un déplacement de rappel vers cette ancre âou correction d'ancrage. Pour limiter l'apparition d'éventuels phénomènes d'oscillation, le calcul de cette correction d'ancrage est effectué sur la position de M' 15 translatée de la correction de ranging associée. La correction d'ancrage est -éj__>, = T(A,Mi +5_,'iiA,), avec 'P une fonction de déplacement. Le choix des fonctions de déplacement ça et tif est libre sous réserve qu'il conduise à un déplacement vers un point d'équilibre 20 = M ) pour ço et (AiMi=i5) pour T. Ces fonctions sont, par exemple, sélectionnées pour refléter un certain degré de connaissance sur les distributions de probabilités associées aux mesures. Des exemples de fonction de déplacement sont donnés ci-après. 3054887 13 Pour des distributions gaussiennes, les déplacements sont proportionnels à une fonction intermédiaire : e2 1- e 2e2 , si o- > 0 (coordonnée ancrée) 1, si o- = 0 (coordonnée ancrée fixe) 0, si u 0 (coordonnée ancrée) 1, si u = 0 (coordonnée ancrée fixe) 0, si u i_' où I induit sur ce noeud Mi par la ;En; M JM totalité des autres noeuds disposant d'une mesure de ranging à partir du noeud M , Etape 2, 302, pour chaque noeud M1, possédant une coordonnée d'ancrage dans l'ancre virtuelle associée A, , calculer une correction 15 d'ancrage i.e. déplacement de rappel vers cette ancre, par la formule a = '14A,M, +5>5_,' 6Ai), i.e. déplacement de rappel fonction du vecteur AM, et d'un déplacement de ranging T , Etape 3, 303, à chaque noeud M1, appliquer un déplacement égal à la somme du déplacement de ranging &>, et de la correction d'ancrage à_>, 20 précédemment calculés. OM,(/ +1) = 0Mi(/)+ +âme, , N-1 Edu avec Ott = rij - d(M i) où Etape 4, 304, calcul A2,0, = A2, où i=0 jar A est interprété comme un terme d'erreur entre estimation de la distance j et mesure de distance fournie par les dispositifs de ranging, comparer cette quantité à un critère d'arrêt défini au préalable par un opérateur, par 25 exemple, si A2,0, A2fin , ou bien max(A,J1) REVENDICATIONS1 - Procédé pour déterminer la position d'un ou plusieurs objets susceptibles de se déplacer dans un réseau, un ou plusieurs objets étant doté d'une capacité de mesure de distance aux autres objets du réseau, au moins une partie des coordonnées d'un objet est connue, caractérisé en ce qu'il comporte au moins les étapes suivantes : - Définir un ensemble de points Ai ou ancres et les incertitudes associées à leurs coordonnées, les coordonnées des ancres et l'incertitude sur les coordonnées décrivant des informations sur la position des objets et l'incertitude sur ces informations, - Générer un ensemble de points contenant les positions estimées des objets et définir une position initiale des points, - Mesurer un ensemble de distances entre au moins deux objets Mi, Mj, avec des incertitudes associées et exécuter les étapes suivantes : - Etape 1, pour chaque objet M' calculer un déplacement correspondant à la somme vectorielle des déplacements de mesure ou ranging sur l'ensemble de mesures de ranging disponibles vers l'objet M, et induits sur cet objet M, par la totalité des autres objets disposant d'une mesure de ranging à partir dudit objet Mi , - Etape 2, (302), pour chaque objet Mi , possédant une coordonnée d'ancrage dans une ancre virtuelle associée 4, calculer une valeur de déplacement de rappel ei' vers cette ancre , - Etape 3, (303), à chaque objet M. appliquer un déplacement égal à la somme du déplacement de ranging (5, et de la valeur de déplacement de rappel à, précédemment calculés, - Etape 4, (304), calculer le carré du terme d'erreur At'Of entre l'estimation de la distance et la mesure de distance fournie par les 3054887 21 dispositifs de ranging sur l'ensemble des noeuds, comparer cette quantité à un critère d'arrêt défini au préalable par un opérateur, par exemple si 42,o, 2 - Procédé selon la revendication 1 caractérisé en ce que l'on définit une ancre et son vecteur d'incertitude de la manière suivante : 15 - Si une mesure externe mi' est supposée connue sur la coordonnée k de l'objet M, avec une incertitude °l'Ai , alors la kième coordonnée de l'ancre Ai est égale à mik et la kième coordonnée du vecteur d'incertitude er'Ai est égale à Cn , - Dans le cas contraire, la kième coordonnée de l'ancre Ai est fixée à une 20 valeur arbitraire et la kième coordonnée du vecteur incertitude crAi fixée à une valeur arbitraire négative. 3 - Procédé selon l'une des revendications 1 ou 2 caractérisé en ce que l'on utilise une fonction de déplacement proportionnelle à une fonction intermédiaire définie de la manière suivante : E2 25 f(£, = 1- e 2'72 , Si 6 > 0 (coordonnée ancrée) 1, si u = 0 (coordonnée ancrée fixe) 0, si u 4 - Procédé selon l'une des revendications 1 ou 2 caractérisé en ce que l'on utilise une fonction de déplacement proportionnelle à une fonction 5 intermédiaire définie de la manière suivante : f, où E [04, si o- > 0 (coordonnée ancrée) 1, si u = 0 (coordonnée ancrée fixe) 0, si u 5 - Procédé selon l'une des revendications 3 ou 4 caractérisé en ce que l'on tient compte dans une fonction de déplacement d'un paramètre de 10 convergence compris entre 0 et 0.5 comme coefficient. 6 - Procédé selon l'une des revendications précédentes caractérisé en ce que les coordonnées des ancres Ai sont définis de la manière suivante : ^ égales à des mesures connues a priori avec une incertitude positive 15 ou nulle (celle-ci est reportée dans la coordonnée correspondante du vecteur 6A,) les coordonnées sont des coordonnées d'ancrage, ^ en l'absence de mesures, la coordonnée correspondante sera inutilisée, les coordonnées sont libres. 20 7 - Procédé selon l'une des revendications précédentes caractérisé en ce que l'on définit une position initiale des points {Mi(0)}i=0 N-1 de la manière suivante : - de façon arbitraire déterministe, - de manière aléatoire, par tirage au sort des valeurs des coordonnées 25 des noeuds, - en utilisant les positions estimées résultantes d'une application précédente du procédé, f(c,o-)= 3054887 23 - en utilisant la solution de méthodes de résolution sous-optimale telles que la pseudo-linéarisation (PSL), - en utilisant des données d'ancrage disponibles pour Ai, ces coordonnées sont préférentiellement utilisées pour les coordonnées 5 initiales correspondantes de M, . 8 - Procédé selon l'une des revendications précédentes caractérisé en ce 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 à 7 et à 10 centraliser les résultats. 9 - Procédé selon l'une des revendications précédentes caractérisé en ce que chaque objet du réseau est adapté à exécuter les étapes du procédé selon l'une des revendications 1 à 7 et à centraliser les résultats. 15 10 - 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 réseau de communication. 20 11 - Dispositif permettant de déterminer la position d'un ou plusieurs objets susceptibles de se déplacer dans un réseau, un ou plusieurs objets étant doté d'un dispositif de mesures de distance inter-noeuds (21), les noeuds communiquant entre eux grâce à un moyen de communication (10), caractérisé en ce qu'il comporte au moins un processeur (12) adapté à 25 exécuter les étapes du procédé selon l'une des revendications 1 à 10, un dispositif de mesure (11, 20) de la position des noeuds.