Homotopy Class

Auch genannt: homotopy class of paths
Kategorie: Planning & manipulation › Motion planning
Schlagwörter: motion-planning, topology, trajectory-optimization, mobile-navigation

Eine Menge von Pfaden mit demselben Start und Ziel, die sich stetig ineinander verformen lassen, ohne ein Hindernis zu durchqueren, etwa alle Pfade, die links an einer bestimmten Säule vorbeiführen.

Definition

Zwei Pfade mit demselben Start- und Endpunkt sind homotop (homotopic), wenn sich der eine stetig in den anderen verbiegen lässt, während die Endpunkte fest bleiben und jeder Zwischenpfad im freien Raum bleibt. Diese Relation teilt alle möglichen Pfade in Äquivalenzklassen ein, die Homotopieklassen (homotopy classes) heißen. In einer Ebene mit einem Hindernis zwischen Start und Ziel bilden die Pfade, die links daran vorbeiführen, eine Klasse, und die Pfade, die rechts vorbeiführen, eine andere; Pfade, die das Hindernis vor Erreichen des Ziels ein- oder mehrmals umrunden, bilden weitere Klassen. Schon ein einziges Hindernis erzeugt also unendlich viele Klassen, die sich durch ihre Windungszahl unterscheiden. Jedes weitere Hindernis vervielfacht die Möglichkeiten.

Das Konzept ist wichtig, weil die meisten Pfadoptimierer lokal arbeiten. Gradientenbasierte Trajektorienoptimierer und Elastic Bands verformen einen Pfad, um ihn kürzer oder glatter zu machen, können ihn aber nicht durch ein Hindernis schieben; sie finden daher nur den besten Pfad innerhalb der Klasse, in der sie begonnen haben. Globale Planer entscheiden, welche Klasse verwendet wird, oft implizit. Ein samplingbasierter Planer wie RRT findet vielleicht zuerst einen Pfad durch eine Lücke und entdeckt später einen kürzeren durch eine andere, was sich als plötzlicher Abfall der Pfadkosten statt als allmähliche Verbesserung zeigt. Homotopiebewusste Planer machen dies explizit, indem sie mehrere Klassen parallel verfolgen und in jeder den besten Pfad optimieren.

In der Praxis verwenden Planer oft eine berechenbare Invariante statt der Homotopie selbst. Bei ebenen Problemen kennzeichnet eine H-Signatur (H-signature) oder eine Zählung des Windungswinkels um jedes Hindernis, auf welcher Seite jedes Hindernisses ein Pfad vorbeiführt; streng genommen identifiziert sie damit die verwandte, aber gröbere Homologieklasse. Im höherdimensionalen Konfigurationsraum eines Arms gibt es weiterhin Klassen, sie lassen sich aber schwer aufzählen, daher werden sie vor allem für mobile Roboter, Fahrzeuge und ebene Probleme diskutiert.

Warum es wichtig ist

Zu wissen, zu welcher Homotopieklasse ein Pfad gehört, erklärt, warum ein lokaler Optimierer in einem langen Umweg stecken bleibt, warum die Kosten eines Planers plötzlich springen und warum ein Roboter zwischen dem Passieren eines Hindernisses links und rechts hin und her pendeln kann. Planer, die über Klassen schlussfolgern, vermeiden diese Fehler und können wirklich unterschiedliche Routenoptionen anbieten.

Wichtige Anwendungen

Lokale Planer für mobile Roboter, die alternative Routen um Hindernisse vorhalten
Erklärung sprunghafter Änderungen der Lösungskosten bei Anytime- und asymptotisch optimalen Planern
Wahl von Anfangsschätzungen für die Trajektorienoptimierung
Navigation mehrerer Roboter und in Menschenmengen, bei der die Seite zum Passieren abgestimmt werden muss
Roboter mit Kabelanbindung, bei denen die Klasse des Kabels um Hindernisse die erreichbaren Pfade begrenzt

In der Praxis

Ein Lagerroboter nutzt einen lokalen Planer, der mehrere Kandidatentrajektorien vorhält, jede in einer anderen Homotopieklasse um nahe Paletten und Personen. In jedem Zyklus optimiert er jeden Kandidaten auf Zeit und Abstand und wählt dann den günstigsten. Ohne Vorkehrungen führen zwei nahezu gleichwertige Optionen dazu, dass der Roboter von einem Zyklus zum nächsten die Seite wechselt und auf der Stelle schwankt; daher fügt das Team eine Hysterese hinzu: Eine neue Klasse muss die aktuelle um eine Marge übertreffen, bevor der Roboter seine Entscheidung ändert. Außerdem begrenzt es die Zahl der untersuchten Klassen, damit der Planer innerhalb seiner Zykluszeit bleibt.

Häufige Missverständnisse

Homotope Pfade haben ähnliche Längen — Homotopie ist eine topologische Eigenschaft; zwei Pfade derselben Klasse können sich in der Länge stark unterscheiden
Es gibt nur so viele Klassen, wie es Wege um die Hindernisse gibt — wiederholtes Umrunden eines Hindernisses erzeugt unendlich viele Klassen
Ein lokaler Optimierer findet bei genügend Iterationen den global kürzesten Pfad — er bleibt in der Klasse seines Anfangspfades
Homotopie- und Homologieklassen sind dasselbe — Homologie ist gröber, und praktische Signaturen wie die H-Signatur identifizieren Homologieklassen

Wer das wissen sollte

Forscher in der Bewegungsplanung, die an optimaler und multimodaler Planung arbeiten
Ingenieure für die Navigation mobiler Roboter, die lokale Planer abstimmen
Praktiker der Trajektorienoptimierung, die Initialisierungen wählen
Studierende, die die Topologie des Konfigurationsraums studieren

Open Source Robotics