Topological Map

Auch genannt: topological graph, topometric map, place graph
Kategorie: State estimation & navigation › Navigation
Schlagwörter: navigation, mapping, graph-search, visual-navigation, mobile-robots

Eine Karte, die eine Umgebung als Graphen unterscheidbarer Orte darstellt, die durch befahrbare Verbindungen verknüpft sind, statt als präzise Geometrie, sodass ein Roboter Routen zwischen ihnen planen kann.

Definition

Topologische Karten (Topological Maps) stellen eine Umgebung als Graph dar. Knoten (Nodes) stehen für unterscheidbare Orte wie Räume, Türöffnungen, Kreuzungen oder gespeicherte Blickpunkte, und Kanten (Edges) halten fest, dass der Roboter direkt zwischen zwei Orten fahren kann. Anders als eine metrische Karte (Metric Map), etwa ein Belegungsgitter, braucht eine topologische Karte keine global konsistenten Koordinaten; sie erfasst, wie Orte verbunden sind, nicht genau, wo sie liegen.

Das entspricht der Art, wie Menschen Wege oft beschreiben: den Flur entlang, an der Küche abbiegen, das Labor ist die zweite Tür. Benjamin Kuipers' Spatial Semantic Hierarchy ist ein bekannter Rahmen, der in diesem Sinne Steuerungs-, Kausal-, topologisches und metrisches Wissen in Schichten anordnet. Viele praktische Systeme verwenden hybride topometrische Karten (Hybrid Topometric Maps), die einen Graphen für die Planung über große Distanzen und lokale metrische Karten für präzise Bewegungen innerhalb jedes Knotens vorhalten.

Die Navigation mit einer topologischen Karte hat zwei Ebenen. Eine Graphsuche, etwa der Dijkstra-Algorithmus oder A*, findet eine Folge von Knoten vom aktuellen Ort bis zum Ziel. Ein lokaler Regler bewegt den Roboter dann von einem Knoten zum nächsten, oft indem er den Zielort anhand von Sensordaten erkennt. Bei lernbasierter visueller Navigation speichern Knoten häufig Kamerabilder, und eine gelernte Policy fährt auf das Bild des nächsten Knotens zu.

Topologische Karten skalieren gut auf große Räume und vertragen Drift in der Odometrie, weil sich Fehler nicht über ein globales Koordinatensystem aufsummieren. Ihre Schwächen sind perzeptuelles Aliasing, bei dem zwei verschiedene Orte gleich aussehen, und fehlende Kanten, bei denen eine befahrbare Verbindung nie beobachtet wurde. Der Schleifenschluss (Loop Closure), also das Erkennen, dass der Roboter an einen bekannten Ort zurückgekehrt ist, hält den Graphen konsistent.

Warum es wichtig ist

Topologische Karten ermöglichen es Robotern, in großen Umgebungen mit kompaktem Speicher und ohne perfekte globale Lokalisierung zu navigieren. Sie passen natürlich zu gelernter visueller Navigation, bei der sich ein Roboter Orte daran merkt, wie sie aussehen, und nicht daran, wo sie in einem Koordinatensystem liegen.

Wichtige Anwendungen

Navigation über große Distanzen in Innen- und Außenbereichen mit bildbasiertem Ortsgedächtnis
Routenplanung über große Gebäude oder Campusgelände
Exploration, bei der neu gefundene Orte als Knoten hinzugefügt werden
Hierarchische Planung, die Graphrouten mit lokaler metrischer Regelung kombiniert

In der Praxis

Ein Team, das einen Roboter für visuelle Navigation einsetzt, könnte ihn zunächst durch ein Gebäude fahren und dabei in gewissen Abständen Kamerabilder als Graphknoten speichern, aufeinanderfolgende Bilder verknüpfen und zusätzliche Kanten dort hinzufügen, wo ein gelerntes Modell vorhersagt, dass zwei Bilder voneinander aus erreichbar sind. Zur Laufzeit lokalisiert sich der Roboter am nächstgelegenen Knoten, sucht im Graphen eine Route zum Zielbild und nutzt eine gelernte Policy, um auf jedes folgende Knotenbild zuzufahren, wobei er sich unterwegs neu lokalisiert.

Häufige Missverständnisse

Topologische Karten enthalten überhaupt keine Geometrie — viele speichern relative Posen oder lokale metrische Karten an den Knoten; was sie weglassen, ist ein einziges globales Koordinatensystem
Topologische und metrische Karten schließen sich gegenseitig aus — hybride topometrische Karten sind in der Praxis verbreitet
Eine topologische Karte ist nur eine Liste von Wegpunkten — sie ist ein Graph und unterstützt daher alternative Routen und Neuplanung, wenn eine Kante blockiert ist

Wer das wissen sollte

Navigationsingenieure für mobile Roboter
Forschende, die an gelernter visueller Navigation arbeiten
SLAM- und Kartierungsingenieure

Open Source Robotics