Time Optimal Ergodic Search

Autoren: Dayi Dong, Henry Berger, Ian Abraham · RSS 2023

Lizenzen

Open Access
Paper: CC BY 4.0

Alles Folgende stützt sich auf das vollständige Paper unter seiner Lizenz CC BY 4.0; die Abbildung wird mit Nennung der Autoren gezeigt.

Kurz gesagt

Minimiert die Suchzeit unter einer oberen Schranke γ für die ergodische Metrik: Ein Parameter legt fest, wie gründlich die Abdeckung ist, und der Optimierer wählt die Dauer der Trajektorie.

Warum es wichtig ist

Bei Such- und Rettungs- oder Vermessungsflügen kann der Bediener festlegen, wie gründlich ein Durchgang sein muss, und erhält die schnellste Trajektorie, die dies erfüllt, statt eine Dauer zu raten. Nebenbedingungen wie Geschwindigkeitsgrenzen und Hindernisbarrieren stehen in derselben Optimierung, und die geplanten Zeiten ließen sich auf einen realen Quadrocopter mit einer Abweichung von höchstens 1,5 s übertragen.

Problem

Ergodische Suche plant kontinuierliche Trajektorien, die in jeder Region Zeit proportional zu deren Information verbringen, doch bestehende Methoden legen den Planungshorizont im Voraus fest, sodass der Nutzer die Gründlichkeit der Suche nicht gegen die Zeit abwägen kann. Die Zeit zu minimieren und gleichzeitig die ergodische Metrik zu minimieren, ist schlecht gestellt, weil eine Trajektorie erst vollständig ergodisch wird, wenn die Zeit gegen unendlich geht.

Lösungsansatz

Die ergodische Metrik wird zu einer Ungleichungsnebenbedingung E ≤ γ in einem Minimalzeitproblem, sodass γ festlegt, wie grob oder fein die Abdeckung sein muss, und die Endzeit tf eine Entscheidungsvariable ist. Die Autoren beweisen lokale Optimalitätsbedingungen mit dem Maximumprinzip von Pontryagin unter Verwendung eines 'erweiterten ergodischen Zustands' und lösen das Problem in der Praxis durch direkte Transkription über N Stützstellen (Δt = tf/N) mit einem eigenen Augmented-Lagrangian-Löser. Hindernisse werden mit Nebenbedingungen aus diskreten Control Barrier Functions behandelt.

Wichtigste Erkenntnisse

Ergodizität als Schranke statt als Zielfunktion zu behandeln, macht die Minimalzeitsuche wohlgestellt; für γ → 0 wächst die optimale Zeit unbeschränkt, im Einklang mit der Ergodentheorie
Eine Senkung von γ um zwei Größenordnungen (0,1 auf 0,001) auf einer Informationskarte mit vier Spitzen verdoppelte die optimale Zeit ungefähr (9,86 s auf 19,59 s), wobei selbst der grobe Plan jede Spitze besuchte
Der auf die Zeit normierte Stellaufwand ist in der Mitte des γ-Bereichs, wo die Trajektorie Abdeckung gegen Zeit abwägen muss, höher als an beiden Extremen
Glatte Anfangsschätzungen (lineare Interpolation) liefern konsistente Lösungen; verrauschte oder zufällige Anfangstrajektorien fallen in ebenso ergodische lokale Minima mit längeren Zeiten

Hauptergebnisse

Gleichmäßige Abdeckung mit einer 2-D-Punktmasse: Die Variation von γ ergibt Trajektorien von 5–10 s mit einer Abdeckung, die einer ergodischen Trajektorie mit festem Horizont von 10 s entspricht (E = 0,007)
Ungleichmäßige Informationskarte: optimale Zeiten von 9,86 s bei γ = 0,1 und 19,59 s bei γ = 0,001
Sensitivität bei γ = 0,05: Die Variation des anfänglichen tf von 4 bis 8 s ergibt eine optimale Zeit von 4,97 ± 0,23 s; die Variation der Stützstellenzahl N von 50 bis 600 ergibt 5,45 ± 0,39 s
Zugestellte 2-D-Umgebung mit Control Barrier Functions: optimale Zeiten von 7,79 s bei γ = 0,2 bis 11,85 s bei γ = 0,002, wobei die Barriere-Nebenbedingungen die Trajektorien von jedem Hindernis fernhalten
Drohnenexperimente bei γ = 0,1, 0,05 und 0,01: Die tatsächlichen Flugzeiten lagen höchstens 1,5 s von den optimierten Zeiten entfernt; die Trajektorie in Fig. 1 deckt das zugestellte Gebiet in 13,5 s ab
Der Löser erzeugte auch Trajektorien gleichmäßiger Abdeckung für ein nichtlineares 3-D-Flugzeugmodell zwischen zufälligen ellipsoidischen Hindernissen

Einschränkungen

Die Autoren geben an, dass die Lösungen nur lokal optimal sind, weil die ergodische Metrik stark nichtlinear und nichtkonvex ist
Die Autoren fanden die Optimalitätsbedingungen von Pontryagin bei langen Horizonten numerisch instabil, daher ist der praktische Löser eine Methode der direkten Transkription
Die Planung erfolgt offline mit bekannten Hindernissen; die Autoren nennen Echtzeitplanung mit unbekannten Hindernissen und Umgebungsunsicherheit als künftige Arbeit
Die Ergebnisse hängen von der Anfangstrajektorie und von N ab; für sehr kleine γ, bei denen die benötigte Zeit sehr groß wird, liefert der Löser keine Lösungen mehr
Die Autoren merken an, dass der Rechenaufwand mit der Dimension des Erkundungsraums wächst

Wirkung auf das Fachgebiet

Gewinner des RSS 2023 Best Paper Award. Die Autoren veröffentlichen Code unter github.com/ialab-yale/time_optimal_ergodic_search sowie eine Multimedia-Demonstrationsseite.

Zusammenfassung

Roboter, die Zeit gegen die Gründlichkeit einer Suche abwägen können, haben das Potenzial, zeitkritische Unterstützung in Anwendungen wie Suche und Rettung zu leisten. Jüngste Fortschritte bei Suchmethoden auf Basis ergodischer Abdeckung haben es Robotern ermöglicht, ein Gebiet in einer festen Zeitspanne vollständig zu erkunden und abzusuchen. Die Optimierung der Zeit gegenüber der Qualität einer autonomen ergodischen Suche wurde jedoch noch nicht gezeigt. In diesem Paper untersuchen wir Lösungen des zeitoptimalen ergodischen Suchproblems für eine schnelle und adaptive robotische Suche und Erkundung. Wir formulieren das Problem als Minimalzeitproblem mit einer ergodischen Ungleichungsnebenbedingung, deren obere Schranke die Granularität der Suche reguliert und gegen die Zeit abwägt. Lösungen des Problems werden analytisch mithilfe der Optimalitätsbedingungen von Pontryagin dargestellt und numerisch über einen Optimierungsansatz mit direkter Transkription demonstriert. Wir zeigen die Wirksamkeit des Ansatzes bei der Erzeugung zeitoptimaler ergodischer Suchtrajektorien in der Simulation und in Drohnenexperimenten in einer zugestellten Umgebung. Es wird gezeigt, dass sich Hindernisvermeidung leicht in unsere Formulierung integrieren lässt, und wir führen Ablationsstudien durch, die die Abhängigkeit der optimierten Zeit von den Parametern und die Sensitivität der Trajektorie für die Suche untersuchen.

Open Source Robotics