Résumé Technique : Graph-Loc

Énoncé du Problème

L'opération autonome à long terme utilisant le LiDAR nécessite un suivi de pose robuste par rapport aux a priori de cartes embarquées. Un conflit fondamental existe dans les déploiements pratiques : la carte embarquée doit être compacte pour permettre un stockage évolutif et une récupération rapide, tout en étant suffisamment discriminante pour supporter une association de données robuste dans des environnements caractérisés par des structures répétitives, une visibilité partielle et des occlusions fréquentes.

Les cartes de nuages de points denses préservent une géométrie riche mais deviennent coûteuses en termes de calcul à stocker et à interroger à mesure que la couverture augmente. Inversement, les cartes structurelles compactes (par exemple, les contours de polygones, les mises en page CAO) offrent un stockage efficace mais souffrent souvent d'une association de données fragile lorsque l'environnement est géométriquement dégénéré (par exemple, de longs couloirs rectilignes) ou fortement occulté. Les méthodes existantes s'appuyant sur des a priori compacts ont souvent recours à la division de longs contours en segments plus courts pour augmenter leur capacité d'appariement, ce qui gonfle la taille de la carte et la complexité du traitement hors ligne. De plus, les stratégies d'association de type "plus proche voisin" standard deviennent fragiles dans les configurations répétitives, menant à des correspondances incorrectes et à de la dérive.

Méthodologie

Les auteurs proposent Graph-Loc, un cadre de localisation basé sur les graphes qui suit la pose de la plateforme par rapport à des a priori structurels compacts représentés par un graphe point-ligne léger. Le système fonctionne sans nécessiter d'annotations sémantiques de haut niveau ou de mise à jour de la carte en ligne.

1. Représentation par Graphe Structurel

• Carte A Priori : La carte embarquée est représentée par un graphe fixe $\mathcal{M} = (\mathcal{V}_M, \mathcal{E}_M)$, où les nœuds encodent des caractéristiques géométriques (points et lignes) et les arêtes capturent le contexte du voisinage local. Cette représentation supporte des sources hétérogènes, incluant des contours de polygones vectorisés à partir de cartes d'occupation/grilles et des mises en page CAO/plans d'étage.
• Graphe d'Observation : Pour chaque scan LiDAR entrant, le système extrait des caractéristiques structurelles éparses pour former un graphe d'observation $\mathcal{S}_t$. Cela implique un processus d'extraction à double flux :
  • Caractéristiques Éparses Courtes : Caractéristiques de bords et de plans de type LOAM extraites des discontinuités de portée.
  • Longues Lignes Structurelles : Extraction par secteurs de longues caractéristiques linéaires pour fournir des indices stables et répétables.
  • Fusion et Filtrage : Les deux flux sont fusionnés pour supprimer les interférences dynamiques (ex: piétons) et gérer les motifs d'occlusion (ex: inférer des jonctions douces ou mettre à jour conservateurement les points terminaux).
• Récupération Conditionnée par la Pose : En utilisant une prédiction de mouvement à vitesse constante, le système effectue une simulation de rayon LiDAR sur la carte a priori pour récupérer un sous-graphe visible $\mathcal{M}_t$. Cela restreint l'appariement aux candidats plausibles, réduisant l'ambiguïté dans les configurations répétitives.

2. Transport Optimal Déséquilibré (UOT) pour l'Association

Au lieu d'un appariement de type "plus proche voisin" glouton, Graph-Loc formule l'association scan-à-carte comme un problème de transport optimal déséquilibré sur les nœuds du graphe. La fonction objectif minimise :
$$\gamma^* = \arg \min_{\gamma \ge 0} \langle \gamma, C(P) \rangle + \beta \Omega_{rel}(\gamma) + \rho D_{UOT}(\gamma) + \varepsilon H(\gamma)$$

• Appariement Géométrique ($\langle \gamma, C(P) \rangle$) : Évalue la compatibilité par paire entre les caractéristiques de points et de lignes (incluant les associations croisées point-à-ligne).
• Couplage de Contexte ($\Omega_{rel}$) : Un régularisateur de second ordre qui impose la cohérence des relations de voisinage local (ex: distance entre les points, angle entre les lignes), réduisant l'ambiguïté dans les structures répétitives.
• Relaxation de Masse ($D_{UOT}$) : Une formulation déséquilibrée pénalisée par la divergence KL qui relaxe la conservation stricte de la masse. Cela permet au système de tolérer des caractéristiques manquantes, parasites ou fragmentées causées par l'occlusion sans les forcer dans de mauvaises correspondances un-à-un.
• Solveur : Le problème est résolu efficacement en ligne à l'aide d'un algorithme d'échelle itératif de type Sinkhorn avec lissage entropique.

3. Optimisation Différée Sensible à la Dégénérescence

Pour traiter les mises à jour de pose mal conditionnées dans les segments à faible observabilité (ex: longs couloirs rectilignes où les contraintes latérales sont fortes mais les contraintes longitudinales sont faibles), le système emploie une stratégie d'optimisation différée sensible à la dégénérescence :

• Détection : Le système analyse la matrice d'information (équations normales) pour identifier les directions de mouvement faiblement contraintes via la décomposition en valeurs propres.
• Mise à jour Masquée : Dans les états dégénérés, les mises à jour selon les directions faibles sont supprimées (masquées), et seules les corrections bien contraintes sont appliquées immédiatement.
• Libération Différée : Les contraintes des trames dégénérées sont mises en mémoire tampon. Une fois l'observabilité rétablie (état non dégénéré), les preuves mises en tampon sont agrégées avec les contraintes actuelles pour libérer une correction complète et stable.

Contributions Clés

1. Cadre Structurel Compact : Un cadre de localisation qui représente les a priori hétérogènes et les observations sous forme de graphes structurels point-ligne, permettant le suivi de pose avec des a priori éparses mais géométriquement significatives sans division de contours.
2. OT Déséquilibré Sensible au Contexte : Une formulation de l'association de caractéristiques via le transport optimal déséquilibré avec régularisation de contexte de graphe. Cela réduit l'ambiguïté locale et empêche les observations occultées ou dynamiques d'être forcées dans de mauvaises correspondances.
3. Optimisation Différée Sensible à la Dégénérescence : Une stratégie qui sépare les corrections bien contraintes des corrections peu fiables dans les segments à faible observabilité, stabilisant le suivi dans les environnements géométriquement dégénérés.
4. Évaluation Complète : Validation étendue sur des benchmarks publics (KITTI, ERPoT, MulRan), des simulations contrôlées (CMU-EXPLORATION) et des déploiements réels (DOALS, robots intérieurs/extérieurs), démontrant une précision compétitive avec des a priori de l'ordre du Ko (KB) sous occlusion et changements de scène.

Résultats Expérimentaux

Le papier évalue Graph-Loc à travers quatre contextes distincts :

• Benchmarks Publics (KITTI, ERPoT, MulRan) : Graph-Loc atteint une erreur de trajectoire moyenne (ATE) plus faible que les méthodes de pointe (incluant ALOAM, FLOAM, KISS-MCL, HDL LOC, et ERPoT) tout en utilisant des a priori de cartes nettement plus petits (ex: ~0,25 Mo contre ~56 Mo pour les nuages de points). Notamment, sur le jeu de données Mulran DCC (itinéraires répétés à long terme), Graph-Loc a maintenu un suivi stable avec un a priori de 0,72 Mo, là où les bases ont échoué ou ont nécessité des cartes beaucoup plus grandes.
• Occlusion Dynamique (DOALS & CMU-EXPLORATION) : Dans des séquences avec mouvement de piétons réel et occlusion de haute densité contrôlée, Graph-Loc a démontré une robustesse supérieure. Il a maintenu des trajectoires stables là où les bases ont divergé, particulièrement dans les configurations structurellement dégénérées. La formulation de l'OT déséquilibré a efficacement géré les retours transitoires et les données manquantes.
• Déploiements Réels :
  • Intérieur : Testé sur un itinéraire de type couloir avec une occlusion prolongée par des piétons à courte portée. Graph-Loc a surpassé les bases de comparaison en nuages de points et en polygones utilisant un a priori CAO.
  • Extérieur : Testé dans un parking avec des changements de scène graduels (véhicules stationnés, obstacles). Graph-Loc a obtenu l'ATE le plus bas avec un a priori polygonal compact, démontrant une stabilité malgré les décalages entre l'a priori et l'observation.
• Études d'Ablation : Le retrait du module d'OT déséquilibré a causé la dégradation de performance la plus significative, confirmant son rôle de mécanisme central de robustesse. L'optimisation différée était critique pour la stabilité dans les segments dégénérés, et le filtrage dynamique a amélioré la robustesse dans les scènes dynamiques.
• Temps d'Exécution : L'implémentation GPU atteint une latence moyenne de 24,5 ms, surpassant la base de comparaison ERPoT (100 ms) grâce à l'efficacité du solveur Sinkhorn sur GPU.

Signification

Le papier affirme que Graph-Loc répond au compromis critique entre la compacité de la carte et la robustesse de la localisation. En passant d'une association locale et gloutonne à un appariement global et sensible au contexte via le transport optimal déséquilibré, le système permet un suivi fiable sans nécessiter l'inflation de la taille de la carte par la division de contours. L'optimisation différée sensible à la dégénérescence assure en outre la stabilité dans les environnements géométriquement faibles où les filtres traditionnels dérivent souvent.

Le travail démontre que les a priori structurels compacts (de l'ordre du Ko) dérivés de sources hétérogènes (cartes d'occupation, CAO, plans d'étage) sont suffisants pour une opération autonome à long terme, à condition que le mécanisme d'association soit robuste à l'occlusion et à la dégénérescence. Cela rend le système apte à une intégration directe ("drop-in") dans des piles de navigation avec des contraintes strictes de mémoire embarquée et de récupération, particulièrement dans les environnements structurés comme les bâtiments, les couloirs et les sites industriels.