Ergodic Coverage

Auch genannt: ergodic search, ergodic exploration, ergodic control
Kategorie: State estimation & navigation › Navigation
Schlagwörter: coverage-planning, exploration, active-sensing, trajectory-optimization, search

Ein Weg, Suchpfade so zu planen, dass die Zeit, die ein Roboter in jedem Bereich verbringt, der Menge an Information entspricht, die dieser Bereich voraussichtlich enthält.

Definition

Ergodische Abdeckung (ergodic coverage) plant die Trajektorie eines Roboters so, dass der Anteil der Zeit, den er im Laufe der Zeit in einem beliebigen Bereich des Suchgebiets verbringt, der Wahrscheinlichkeitsmasse entspricht, die eine Zielverteilung diesem Bereich zuweist. Die Zielverteilung kodiert, wo Information erwartet wird: wahrscheinliche Aufenthaltsorte einer vermissten Person, ein Gasleck oder ein Merkmal, das eine Inspektion wert ist. Eine Trajektorie mit dieser Eigenschaft heißt ergodisch bezüglich der Verteilung; der Begriff ist den dynamischen Systemen entlehnt, wo er Zeitmittel beschreibt, die gleich den Raummitteln sind.

Das Standardmaß dafür wurde 2011 von George Mathew und Igor Mezić eingeführt. Sowohl die zeitgemittelte Statistik der Trajektorie als auch die Zielverteilung werden in eine Fourier-Basis über dem Suchgebiet entwickelt. Die ergodische Metrik (ergodic metric) ist eine gewichtete Summe der quadrierten Differenzen zwischen den beiden Sätzen von Fourier-Koeffizienten, mit Gewichten, die mit der Frequenz abnehmen, sodass großräumige Abweichungen stärker zählen als feine Details. Ein Wert von null bedeutet, dass die Trajektorie perfekt ergodisch ist. Die Metrik lässt sich mit einem Rückführgesetz senken, wie bei Spectral Multiscale Coverage, oder als Kosten in der Trajektorienoptimierung verwenden, eine Linie, die Todd Murphey und Kollegen entwickelt haben.

Ergodische Abdeckung liegt zwischen zwei einfacheren Strategien. Reine Ausnutzung schickt den Roboter an die wahrscheinlichste Stelle und hält ihn dort; gleichmäßige Abdeckung, etwa ein Rasenmähermuster, ignoriert, was bereits bekannt ist. Eine ergodische Trajektorie besucht alle Bereiche mit von null verschiedener Wahrscheinlichkeit, verweilt aber länger dort, wo die Verteilung höher ist, und sie lässt sich natürlich auf Roboterteams erweitern, deren kombiniertes Zeitmittel mit dem Ziel verglichen wird. Die wichtigsten Einschränkungen sind, dass die Zahl der Fourier-Terme mit der Dimension des Suchraums schnell wächst und dass die Ergebnisse von der Qualität der Informationskarte abhängen.

Warum es wichtig ist

Suche, Inspektion und Umweltmessung haben selten einen einzigen besten Ort, den man ansteuern sollte. Ergodische Abdeckung bietet einen prinzipientreuen, einstellbaren Weg, den Messaufwand gemäß dem Vorwissen zu verteilen, und sie liefert eine einzige Kostenfunktion, die sich mit Dynamik, Zeitgrenzen und Mehrroboterkoordination kombinieren lässt.

Wichtige Anwendungen

Suche und Rettung mit Drohnen und Bodenrobotern
Aktive Wahrnehmung und Ziellokalisierung
Umweltüberwachung von Gas-, Temperatur- oder Schadstofffeldern
Mehrroboter-Abdeckung mit gemeinsamen Informationskarten
Explorative Bewegung zur taktilen oder visuellen Objektinspektion

In der Praxis

Ein Team, das eine Drohnensuche über einem Hang durchführt, erstellt aus Wegen, Gelände und letzter bekannter Position eine Wahrscheinlichkeitskarte dafür, wo sich ein verirrter Wanderer wahrscheinlich aufhält. Es berechnet die Fourier-Koeffizienten der Karte bis zu einer gewählten Ordnung und optimiert dann einen Flugweg, der die Geschwindigkeits- und Beschleunigungsgrenzen der Drohne einhält und dabei die ergodische Metrik senkt, zum Beispiel mit direkter Kollokation über eine feste oder freie Endzeit. Der resultierende Pfad überstreicht die wahrscheinlichen Wegabschnitte wiederholt und führt dennoch auch über das weniger wahrscheinliche Gelände. Wenn Kameradetektionen eintreffen, wird die Karte aktualisiert, die Koeffizienten werden neu berechnet und der Plan wird neu optimiert. Bei mehreren Drohnen wird das kombinierte Zeitmittel aller Pfade in der Metrik verwendet, sodass sie die Arbeit aufteilen.

Häufige Missverständnisse

Ergodische Abdeckung bedeutet, das ganze Gebiet gleichmäßig abzudecken — sie verteilt die Zeit proportional zur Zielverteilung, sodass informationsreiche Bereiche mehr Aufmerksamkeit erhalten
Eine ergodische Trajektorie geht direkt zum wahrscheinlichsten Ort — sie besucht bewusst weiterhin Bereiche mit geringerer Wahrscheinlichkeit, proportional zu ihrer Wahrscheinlichkeit
Die Metrik skaliert problemlos auf jede Zahl von Dimensionen — die Fourier-Basis wächst exponentiell mit der Dimension, was die direkte Nutzung in hochdimensionalen Räumen begrenzt

Wer das wissen sollte

Ingenieure für Drohnen und Feldrobotik, die Suchmissionen planen
Forschende in aktiver Wahrnehmung und Exploration
Entwickler für Mehrroboterkoordination
Ingenieure für Trajektorienoptimierung

Open Source Robotics