Les différents algorithmes de localisation intérieure

Le développement du système mondial de navigation par satellite (GNSS) a changé la donne pour les applications de navigation et de géolocalisation. Disponible pour des usages civils depuis 1983, les premiers systèmes de navigation mobiles grand public ont été mis sur le marché à partir de 2004. Mais c’est l’adoption par les fabricants de smartphones depuis 2007 qui a rendu cette technologie omniprésente. Aujourd’hui, il s’agit de la fonctionnalité smartphone la plus utilisée après l’accès à Internet.

Cependant, les applications de localisation basées sur le GNSS s’arrêtent aux portes des bâtiments : Le signal GNSS y est affaiblit et la précision de localisation est trop faible pour permettre une application réelle. Qu’il s’agisse de trouver un objet perdu, de suivre des biens dans une usine, de trouver son chemin dans un aéroport ou de sécuriser et contrôler l’accès à des zones restreintes, les scénarios de localisation intérieure sont de plus en plus nombreux. En conséquence, un nombre important de solutions techniques ont été développées et commercialisées dans les années 2010-2020, mais aucune d’entre elles ne s’est imposée jusqu’à présent. Et, Il peut être difficile de choisir parmi l’offre pléthorique actuelle.

Deux grandes classes de solutions existent en fonction de l’usage ou non d’objets communicants fixes (réseau d’ancres). Les solutions sans réseau sont bien sûr les moins chères à déployer, mais ne fournissent généralement pas la meilleure précision. Les solutions basées sur des réseaux d’ancres peuvent fournir une précision de l’ordre du centimètre mais sont coûteuses à déployer et à entretenir. D’une manière générale, le compromis entre coûts, précision et latence constitue le principal défi technique des concepteurs de solution de localisation indoor.

Dans cet article, nous allons passer en revue les différents algorithmes de localisation intérieure disponibles aujourd’hui, pour vous aider à comprendre et à choisir parmi les différentes solutions.

1. La détection de proximité

Les méthodes de positionnement dites de « détection de proximité » utilise l’information de présence d’un objet mobile (objet fixe) dans le « champ de vision » d’un objet fixe (mobile) sans faire appel à une information d’angle ou de distance. La connaissance préalable de la localisation de l’objet fixe et celle très grossière de la taille du champ de vision permet alors d’estimer une zone dans laquelle se trouve l’objet mobile à localiser. La détection de proximité est la méthode de positionnement la plus simple utilisée pour les applications qui ne nécessitent pas une très grande précision.

2. Barycentres

L’estimation de la position à l’aide du barycentre consiste à faire coïncider la position de l’objet mobile avec celle du barycentre des ancres visibles par l’objet mobile (ou voyant l’objet mobile). Cette méthode de positionnement peu complexe est facile à mettre en œuvre. En revanche, elle offre une faible précision, car elle ne prend en compte que les données de proximité et effectue simplement la moyenne des coordonnées pour obtenir la position de la cible. La localisation par barycentre pondéré (Weighted Centroid Localization (WCL) est une amélioration de la méthode de détermination du barycentre. Plusieurs solutions de calculs des poids peuvent être envisagée : intensité du signal, distances entre ancres… plus le nombre de paramètres pris en compte est grand et meilleure est la précision, mais la complexité du système augmente et pose des problème de coûts d’installation, de calibration et de maintenance.

3. La tri-latéralisation

La Tri-latéralisation consiste à utiliser des mesures simultanées de la distance entre l’objet mobile et, au moins, trois ancres de position connue. La position de l’objet mobile correspond alors à l’intersection des cercles ou des sphères centrées respectivement sur les ancres et de rayons égales au distances mesurées (Fig. 1). Lorsque l’estimation de la distance est précise, la tri-latéralisation offre une très grande précision de positionnement.

4. La Tri-Angulation

La tri-angulation est un algorithmes de localisation intérieure similaire à la tri-latéralisation, sauf qu’elle détermine la position de la cible en utilisant des mesures d’angles entre des directions connues et les droites reliant l’objet mobile aux ancres (Fig. 2). Comme pour la tri-latération, la précision de positionnement en triangulation dépend de l’erreur de mesure d’angle.

5. Fingerprinting

Les algorithmes dit de Fingerprinting s’appliquent plus particulièrement aux systèmes de localisation sans réseau d’ancres fixes. Ils sont basés sur l’identification d’un ou plusieurs éléments caractéristiques d’un environnement. La plupart du temps ces éléments sont les indicateurs de force du signal reçu (RSSI) des signaux de radiofréquence (RF), mais l’on retrouve aussi les signaux audio, les champs magnétiques, les informations optiques ou une combinaison de toutes ces informations. Ces algorithmes opèrent généralement en deux phases. La première est la phase de calibration et consiste à créer une carte des empreintes (RF, sonore,…) du lieu. La deuxième phase, opérationnelle, consiste à comparer la mesure en temps réel des l’empreinte par rapport à celles mesurées pendant la phase de calibration et prédire la position de la cible. Différents algorithmes d’apprentissage (supervisés ou non) peuvent y être appliquer. Les algorithmes de fingerprinting ont comme avantage des coûts de déploiement réduits, mais comme inconvénients des coûts de maintenances élevés (recalibration) et une précision faible.

6. Dead Recknoning ou calcul à l’estime

La navigation à l’estime est le processus d’estimation de la position de la cible à l’aide de positions antérieures connues ou estimées, ou de vitesses ou d’accélération connues ou estimées. La démocratisation des unités de mesure inertielle (IMU) conçues selon la technologie des capteurs microélectromécaniques (MEMS) à fortement contribuer au développement d’algorithme de navigation à l’estime. Cependant, l’imprécision de ces algorithmes est cumulative, ce qui signifie que la position estimée s’éloigne de la position réelle avec un écart croissant au fil du temps. Ainsi, sans système de recalibration routinier de la position les algorithmes d’estimes peuvent être très peu précis.

7. Map Matching ou correspondance avec la carte

Lorsque la mesure exacte de la position d’un objet mobile est impossible, par exemple en cas de mauvaise réception de signal, les algorithmes dits de Map Matching permettent de déterminer, corriger ou mettre à jour cette position en utilisant une base de données cartographique. Pour cela ils utilisent les information de trajectoire antérieure et les éléments de cartographie (couloir, porte, table) pour estimer la position actuelles la plus probable. Ces algorithmes sont généralement utilisés en conjonction ou en complément des autres.

8. Combinaison des méthodes de positionnement

Dans le cas de certaines architectures de systèmes de positionnement, plusieurs principes de mesure ou algorithmes de localisation intérieure sont utilisés. Par exemple, l’angulation peut être utilisée en combinaison avec la latéralisation pour réduire les mesures d’angle nécessaires à l’estimation de la position de la cible ou pour améliorer la précision du positionnement. En plus des mesures d’angle et de distance, d’autres informations telles que la proximité ou divers types de données de capteurs peuvent être utilisées pour améliorer les performances d’un système de positionnement. Récemment, les méthodes de positionnement utilisant des informations hétérogènes et les techniques de fusion de données sont au centre des recherches dans le domaine du positionnement intérieur.

Comment choisir le bon algorithmes de localisation intérieure ?

Il existe aujourd’hui de nombreux algorithmes de localisation intérieure offrant plus ou moins de précision et demandant des investissements plus ou moins coûteux en fonction de l’infrastructure réseau. Afin de choisir la solution la plus adaptée à vos besoins, il convient de définir en amont, le niveau de précision dont vous avez besoin.

Dans un second article, nous vous invitons à découvrir les méthodes de gognométrie et de télémétrie, ainsi que les technologies de positionnement permettant de localiser des personnes ou des équipements en intérieur.