Roboter brauchen Orientierung – genau wie wir. Egal, ob sie Pakete durch Lagerhallen fahren, Medikamente im Krankenhaus ausliefern oder auf fremden Planeten unterwegs sind: Sie müssen ihren Weg selbst finden, Hindernissen ausweichen und ihr Ziel erreichen. Das klingt selbstverständlich, ist aber eine der größten Herausforderungen der modernen Robotik. Denn in komplexen, sich ständig verändernden Umgebungen kann Navigation schnell zur Rechenqual werden.
Forschende der University of Kent in Großbritannien haben nun einen Algorithmus entwickelt, der das ändern könnte. Sein Name: LiteRBS – kurz für Lightweight and Rapid Bidirectional Search. Dahinter steckt ein Verfahren, das Wege in Rekordzeit berechnet, ohne den Rechner in die Knie zu zwingen.
„LiteRBS kombiniert hohe Geschwindigkeit mit geringem Speicherbedarf“, schreiben die Autoren in ihrer Studie, die im ELSP Journal erschienen ist. Damit könnte das Verfahren zum neuen Standard für mobile Roboter werden – überall dort, wo in Echtzeit Entscheidungen gefragt sind.
Inhaltsverzeichnis
Alte Pfadfinder kommen an ihre Grenzen
Seit Jahrzehnten verlassen sich Roboter auf Klassiker wie A* oder Dijkstra, um den kürzesten Weg von A nach B zu berechnen. Diese Methoden sind präzise und liefern stets den optimalen Pfad. Doch sie haben einen Haken: Je größer oder verwinkelter die Karte, desto stärker explodiert der Rechenaufwand – und irgendwann geht gar nichts mehr.
Gerade bei Robotern mit begrenzter Hardware zählt jede Millisekunde. Wer in der Industrie ein automatisiertes Transportsystem betreibt, kann nicht warten, bis ein Roboter „nachdenkt“.
Es gibt zwar schnellere Varianten wie Bidirectional A*, Jump Point Search (JPS) oder den Shortest Path Faster Algorithm (SPFA). Doch sie alle haben Schwächen: Sie verbrauchen viel Speicher oder verlieren an Genauigkeit.
Zwei Wege, ein Ziel – der Trick hinter LiteRBS
LiteRBS geht einen anderen Weg – im wahrsten Sinne des Wortes. Statt nur von einem Punkt aus zu suchen, startet der Algorithmus gleich zwei Suchfronten: eine vom Start und eine vom Ziel. Diese bewegen sich aufeinander zu, treffen sich irgendwo in der Mitte – und sparen dabei massiv Rechenleistung.
Neu ist das Prinzip nicht, aber die Umsetzung. LiteRBS steuert die Annäherung dynamisch. Die Forschenden beschreiben das als eine Art „Anziehungskraft“, die die beiden Suchfronten zueinander zieht – selbst dann, wenn der ideale Treffpunkt wegen Hindernissen gar nicht zentral liegt.
Das macht den Algorithmus flexibel. Er erkennt, wo sich Rechenaufwand lohnt, überspringt überflüssige Schritte und spart dadurch Speicherplatz. In der Studie heißt es: „Diese adaptive Zusammenführung ermöglicht eine stabile Konvergenz auch in unregelmäßigen Umgebungen.“
Mit Leichtigkeit zum Ziel
Die Zahlen beeindrucken: In rund 100.000 Simulationen mit unterschiedlich großen Karten und Hindernisdichten zwischen 1 und 30 % zeigte LiteRBS, was in ihm steckt. Die Zahl der verarbeiteten Knoten sank um über 40 %, die Rechenzeit um bis zu 98 %, und der Speicherbedarf um bis zu 96 %.
Trotz der enormen Beschleunigung blieb das Ergebnis stabil: In mehr als 93 % der Fälle lag der berechnete Weg höchstens 10 % länger als der theoretisch optimale Pfad – ein fairer Kompromiss, wenn Geschwindigkeit entscheidend ist.
Für Ingenieurinnen und Ingenieure besonders interessant: Auch bei großen Karten mit bis zu 1.000 × 1.000 Rasterzellen blieb LiteRBS stabil. Selbst wenn die Umgebung dichter wurde, hielt der Algorithmus sein Tempo – ein entscheidender Vorteil für autonome Fahrzeuge, Drohnen oder Serviceroboter in komplexen Szenarien.
Praxistest bestanden
Wie schlägt sich LiteRBS außerhalb des Labors? Das Team testete den Algorithmus auf einem Turtlebot3 Waffle, einem kleinen mobilen Roboter. Dieser musste sich in einer Umgebung zurechtfinden, in der nicht alle Hindernisse bekannt waren – so wie im echten Leben.
Tauchte ein neues Hindernis auf, berechnete LiteRBS den Weg in Millisekunden neu. Das System kam also auch mit unvollständigen Sensordaten klar – ein echter Pluspunkt, denn reale Sensoren liefern selten ein vollständiges Bild.
Damit könnte LiteRBS künftig Roboter in Lagern, Krankenhäusern oder Baustellen unterstützen – überall dort, wo sich Menschen und Maschinen permanent bewegen. Selbst Rettungsroboter in Trümmerlandschaften könnten davon profitieren.
Ein Beitrag von:
