Ergodic Coverage

Aussi appelé: ergodic search, ergodic exploration, ergodic control
Catégorie: State estimation & navigation › Navigation
Mots-clés: coverage-planning, exploration, active-sensing, trajectory-optimization, search

Manière de planifier des trajets de recherche de sorte que le temps passé par un robot dans chaque région corresponde à la quantité d'information que cette région est censée contenir.

Définition

Couverture ergodique (ergodic coverage) : méthode qui planifie la trajectoire d'un robot de sorte que, au fil du temps, la fraction du temps qu'il passe dans toute région de la zone de recherche corresponde à la masse de probabilité qu'une distribution cible attribue à cette région. La distribution cible encode l'endroit où l'on s'attend à trouver de l'information : emplacements probables d'une personne disparue, d'une fuite de gaz ou d'un élément qui mérite d'être inspecté. Une trajectoire possédant cette propriété est dite ergodique par rapport à la distribution, terme emprunté aux systèmes dynamiques, où il décrit des moyennes temporelles égales aux moyennes spatiales.

La manière standard de la mesurer a été introduite par George Mathew et Igor Mezić en 2011. Les statistiques moyennées dans le temps de la trajectoire et la distribution cible sont toutes deux développées dans une base de Fourier sur la zone de recherche. La métrique ergodique (ergodic metric) est une somme pondérée des carrés des différences entre les deux ensembles de coefficients de Fourier, avec des poids qui décroissent avec la fréquence, de sorte que les écarts à grande échelle comptent davantage que les détails fins. Une valeur nulle signifie que la trajectoire est parfaitement ergodique. La métrique peut être réduite par une loi de rétroaction, comme dans la couverture spectrale multi-échelle (spectral multiscale coverage), ou servir de coût en optimisation de trajectoire, une ligne de travaux développée par Todd Murphey et ses collègues.

La couverture ergodique se situe entre deux stratégies plus simples. L'exploitation pure envoie le robot à l'endroit le plus probable et l'y maintient ; la couverture uniforme, comme un motif en tondeuse à gazon, ignore ce que l'on sait déjà. Une trajectoire ergodique visite toutes les zones de probabilité non nulle mais s'attarde là où la distribution est plus élevée, et elle s'étend naturellement à des équipes de robots dont la moyenne temporelle combinée est comparée à la cible. Les principales limites sont que le nombre de termes de Fourier croît rapidement avec la dimension de l'espace de recherche, et que les résultats dépendent de la qualité de la carte d'information.

Pourquoi c'est important

La recherche, l'inspection et la mesure environnementale ont rarement un seul meilleur endroit à visiter. La couverture ergodique offre un moyen fondé et réglable de répartir l'effort de mesure selon les connaissances a priori, et elle fournit un coût unique qui peut être combiné avec la dynamique, des limites de temps et la coordination multi-robots.

Applications principales

Recherche et sauvetage avec des drones et des robots terrestres
Perception active et localisation de cibles
Surveillance environnementale de champs de gaz, de température ou de pollution
Couverture multi-robots avec des cartes d'information partagées
Mouvement exploratoire pour l'inspection tactile ou visuelle d'objets

En pratique

Une équipe qui mène une recherche par drone sur un versant construit une carte de probabilité de l'endroit où un randonneur égaré a des chances de se trouver, à partir des sentiers, du terrain et de la dernière position connue. Elle calcule les coefficients de Fourier de la carte jusqu'à un ordre choisi, puis optimise une trajectoire de vol qui respecte les limites de vitesse et d'accélération du drone tout en réduisant la métrique ergodique, par exemple par collocation directe avec un temps final fixe ou libre. Le trajet obtenu balaie de manière répétée les tronçons de sentier probables tout en passant aussi au-dessus du terrain moins probable. À mesure que les détections de la caméra arrivent, la carte est mise à jour, les coefficients sont recalculés et le plan est ré-optimisé. Avec plusieurs drones, la moyenne temporelle combinée de tous les trajets est utilisée dans la métrique pour qu'ils se répartissent le travail.

Idées reçues

La couverture ergodique consiste à couvrir toute la zone uniformément — elle répartit le temps proportionnellement à la distribution cible, de sorte que les zones riches en information reçoivent plus d'attention
Une trajectoire ergodique va directement à l'emplacement le plus probable — elle continue délibérément à visiter les régions moins probables, proportionnellement à leur probabilité
La métrique passe facilement à n'importe quel nombre de dimensions — la base de Fourier croît exponentiellement avec la dimension, ce qui limite son usage direct dans les espaces de grande dimension

Qui devrait le savoir

Ingénieurs en drones et en robotique de terrain qui planifient des missions de recherche
Chercheurs en perception active et en exploration
Développeurs de coordination multi-robots
Ingénieurs en optimisation de trajectoire

Technologies associées

Couverture spectrale multi-échelle (Spectral Multiscale Coverage)
Optimisation de trajectoire (Trajectory Optimization)
Analyse de Fourier (Fourier Analysis)
Planification fondée sur la théorie de l'information (Information-Theoretic Planning)
Motifs de couverture en tondeuse à gazon (Lawnmower Coverage Patterns)

Termes associés

Projets associés

PyRoki: Modular Python toolkit for kinematic optimization across CPU, GPU, and TPU via JAX
Fields2Cover: Coverage path planning library for autonomous agricultural vehicles
STLCG: JAX toolbox for differentiable Signal Temporal Logic robustness