Success Weighted by Path Length

Auch genannt: SPL
Kategorie: State estimation & navigation › Navigation
Schlagwörter: navigation, evaluation-metrics, embodied-ai, benchmarking, simulation

Eine Navigationsmetrik, die über Episoden den Erfolg multipliziert mit dem Verhältnis der kürzesten Weglänge zur Länge des tatsächlich gefahrenen Wegs mittelt.

Definition

Success weighted by Path Length (SPL) ist eine Bewertungsmetrik für zielgerichtete Navigationsagenten, vorgeschlagen von Anderson und Kollegen im Bericht On Evaluation of Embodied Navigation Agents von 2018. Sie verbindet, ob der Agent das Ziel erreicht hat, mit der Effizienz, mit der er es erreicht hat. Für N Testepisoden gilt SPL = (1/N) Σ Sᵢ · ℓᵢ / max(pᵢ, ℓᵢ), wobei Sᵢ gleich 1 ist, wenn Episode i erfolgreich war, und sonst 0, ℓᵢ die Länge des kürzesten Wegs vom Start zum Ziel und pᵢ die Länge des tatsächlich vom Agenten zurückgelegten Wegs ist.

Die Länge des kürzesten Wegs ℓᵢ ist der geodätische Abstand durch den befahrbaren Raum, berechnet auf der Karte oder dem Navigationsnetz der Umgebung, nicht der Luftlinienabstand durch Wände. Ein Agent, der das Ziel auf dem kürzesten Weg erreicht, erhält für diese Episode 1, ein Agent, der es nach der doppelten Strecke erreicht, 0,5, und eine fehlgeschlagene Episode erhält 0, unabhängig davon, wie nahe der Agent kam. Was als Erfolg gilt, legt der Benchmark fest, typischerweise das Anhalten innerhalb eines festgelegten Abstands zum Ziel, und viele Benchmarks verlangen, dass der Agent eine explizite Stopp-Aktion ausgibt. SPL ist die Standard-Leitmetrik für PointGoal- und ObjectGoal-Navigation in Simulatoren für verkörperte KI wie Habitat, und es gibt Varianten für Objektzielaufgaben, bei denen ℓᵢ der Abstand zur nächsten gültigen Zielinstanz ist.

SPL hat bekannte Schwächen. Da ein Fehlschlag mit null bewertet wird, ist die Metrik auf Episodenebene binär und kann Agenten verbergen, die regelmäßig sehr nahe herankommen. Sie misst nur die Weglänge, nicht Zeit, Kollisionen, Energie oder die Anzahl der Drehungen. In unbekannten Umgebungen, in denen ein Agent erkunden muss, um das Ziel zu finden, sind selbst für gute Agenten Werte deutlich unter 1 zu erwarten, da der kürzeste Weg eine Karte voraussetzt, die der Agent nicht hat. Varianten wie SoftSPL, das binären Erfolg durch den Fortschritt in Richtung Ziel ersetzt, und Metriken auf Basis von Zeit oder Aktionen wurden vorgeschlagen, um einige dieser Probleme anzugehen.

Warum es wichtig ist

SPL gab der Forschung zur verkörperten Navigation einen gemeinsamen Maßstab zum Vergleich von Agenten, der sowohl das Erreichen des Ziels als auch das Vermeiden von Umwegen belohnt, und wird in den meisten Arbeiten zu simulierten Navigations-Benchmarks berichtet. Zu wissen, was sie misst und was sie ignoriert, ist nötig, um diese Ergebnisse zu lesen und zu beurteilen, ob sich ein hoher Wert auf einen realen Roboter übertragen lässt.

Wichtige Anwendungen

Benchmarking von PointGoal- und ObjectGoal-Navigationsagenten
Wettbewerbe zu verkörperter KI in Simulatoren wie Habitat
Vergleich gelernter und klassischer Navigations-Stacks
Bewertung von Agenten für Vision-and-Language-Navigation
Verfolgung der Sim-to-Real-Navigationsleistung auf physischen Robotern

In der Praxis

Ein Team bewertet zwei Navigations-Policies an 1.000 Episoden in zurückgehaltenen simulierten Wohnungen. Für jede Episode berechnet der Simulator den geodätischen kürzesten Weg vom Start zum Ziel auf dem Navigationsnetz, und das Auswerteskript protokolliert, ob der Agent innerhalb des Erfolgsradius angehalten hat und wie weit er gefahren ist. Policy A ist häufiger erfolgreich, macht aber lange Umwege; Policy B ist seltener erfolgreich, nimmt aber im Erfolgsfall nahezu optimale Routen. Das Team berichtet Erfolgsrate und SPL nebeneinander sowie die Anzahl der Kollisionen, weil SPL allein nicht zeigen würde, dass eine Policy viel öfter gegen Möbel stößt als die andere.

Häufige Missverständnisse

SPL verwendet den Luftlinienabstand zum Ziel — es verwendet den geodätischen kürzesten Weg durch den befahrbaren Raum
SPL belohnt die Annäherung an das Ziel — eine fehlgeschlagene Episode erhält null, egal wie nahe der Agent anhielt; SoftSPL wurde vorgeschlagen, um Teilpunkte zu vergeben
Von einem guten Agenten ist ein SPL nahe 1 zu erwarten — in unbekannten Umgebungen muss ein Agent erkunden, daher liegen selbst starke Agenten deutlich unter dem Ideal des kürzesten Wegs
SPL erfasst die gesamte Navigationsqualität — Zeit, Kollisionen, Glattheit und Energie werden ignoriert und müssen in der Regel separat berichtet werden

Wer das wissen sollte

Forschende in verkörperter KI und Navigation
Ingenieure, die Navigations-Stacks mobiler Roboter benchmarken
Gutachter und Leser, die Navigationsarbeiten vergleichen
Entwickler von Simulationen und Benchmarks

Open Source Robotics