🤖 AI

Learning to Communicate Locally for Large-Scale Multi-Agent Pathfinding

Dieser Beitrag stellt LC-MAPF vor, ein generalisierbares vortrainiertes Modell, das die dezentrale Multi-Agenten-Pfadfindung durch die Integration eines skalierbaren, lernfähigen Kommunikationsmoduls mit mehreren Runden für einen effizienten Feature-Austausch verbessert und dabei bestehende lernbasierte Löser in diversen Szenarien übertrifft, ohne die Skalierbarkeit zu beeinträchtigen.

Ursprüngliche Autoren: Valeriy Vyaltsev, Alsu Sagirova, Anton Andreychuk, Yuri Kuratov, Konstantin Yakovlev, Aleksandr Panov, Alexey Skrynnik

Veröffentlicht 2026-05-11

📖 4 Min. Lesezeit☕ Kaffeepausen-Lektüre

CC BY 4.0

Ursprüngliche Autoren: Valeriy Vyaltsev, Alsu Sagirova, Anton Andreychuk, Yuri Kuratov, Konstantin Yakovlev, Aleksandr Panov, Alexey Skrynnik

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Stellen Sie sich ein riesiges, geschäftiges Lagerhaus vor, gefüllt mit hunderten identischen Robotern. Ihre Aufgabe ist einfach: Ein Paket an einem Ort aufnehmen und an einem anderen ablegen. Doch hier liegt der Haken: Sie müssen sich alle gleichzeitig bewegen, und wenn zwei Roboter aufeinandertreffen, kommt der gesamte Betrieb zum Erliegen.

Dies ist das Problem des Multi-Agent Pathfinding (MAPF). Es ist, als würde man versuchen, tausende Ameisen über einen überfüllten Bürgersteig zu bringen, ohne dass sie aufeinander treten, wobei sie jedoch alle verschiedene Ziele haben.

Das Problem mit „stummen" Robotern

In der Vergangenheit versuchten Forscher, diese Roboter mittels Imitationslernen zu unterrichten. Stellen Sie sich dies so vor, dass man einem Roboter ein Video eines perfekten Experten zeigt, der das Labyrinth löst, und sagt: „Mach genau das, was der Experte getan hat."

Eine neuere Methode, genannt MAPF-GPT, war darin sehr gut. Sie lernte aus einer riesigen Bibliothek von Expertenvideos. Allerdings hatte sie einen gravierenden Mangel: Sie lehrte die Roboter, stumm zu sein. Die Roboter lernten, sich gut zu bewegen, aber sie sprachen nicht miteinander. Sie waren wie ein Chor, der perfekt in der Tonlage singt, aber sich nie ansieht, um den Takt anzupassen. Wenn die Situation zu überfüllt wurde, konnten sie keine Koordination zur Behebung eines Staus entwickeln, da sie lediglich basierend auf dem, was sie allein sahen, raten mussten, was zu tun war.

Andere Methoden versuchten, dies zu beheben, indem sie den Robotern erlaubten, zu sprechen, doch ihre Gespräche waren oft oberflächlich. Sie schrien vielleicht: „Ich bin hier!" oder „Ich gehe links!", aber sie verhandelten oder planten nicht wirklich gemeinsam. Es war wie eine Gruppe von Menschen, die versucht, ein Puzzle zu lösen, während ihnen nur erlaubt ist, ein einziges Wort zu sagen.

Die Lösung: LC-MAPF (Der „Runde-Tisch"-Ansatz)

Die Autoren dieses Papiers stellten ein neues System namens LC-MAPF vor. Anstatt nur einen Experten zu beobachten, lehrten sie die Roboter, vor dem Ausführen eines Zuges ein Gespräch über mehrere Runden zu führen.

So funktioniert es, anhand einer einfachen Analogie:

Das Setup: Stellen Sie sich vor, die Roboter sitzen um einen Tisch. Sie können nur die Personen sehen, die neben ihnen sitzen (ihre lokalen Nachbarn).
Runde 1: Jeder flüstert seinen aktuellen Plan seinen Nachbarn zu. „Ich werde vorwärts gehen."
Runde 2: Jetzt hört sich jeder seine Nachbarn an. Wenn ein Nachbar sagt: „Ich gehe auch vorwärts", erkennen Sie: „Oh, wir werden kollidieren!" Also flüstern Sie einen neuen Plan: „Okay, ich warte eine Sekunde."
Runde 3 & 4: Sie geben diese Flüstereien hin und her weiter. Mit jeder Runde verfeinern sie ihren Plan, lösen Konflikte und einigen sich auf einen reibungslosen Ablauf.
Der Zug: Nach vier Runden des Plaudernns bewegen sie sich alle gleichzeitig, perfekt koordiniert.

Die Magie von LC-MAPF besteht darin, dass die Roboter gelernt haben, selbstständig zu sprechen. Die Forscher programmierten sie nicht mit einer spezifischen Sprache und sagten ihnen nicht, was sie sagen sollen. Sie gaben ihnen lediglich das Ziel (nicht kollidieren, das Ziel erreichen) und ließen die KI herausfinden, dass „Sprechen" der beste Weg war, dies zu erreichen. Die Nachrichten, die sie austauschen, sind keine menschlichen Worte; es sind mathematische Signale, die genau genug Informationen tragen, um das Puzzle zu lösen.

Warum dies eine große Sache ist

Das Papier hebt drei Hauptvorteile hervor:

Es ist intelligenter: In Tests löste LC-MAPF mehr Labyrinth-Szenarien erfolgreich als jede andere lernbasierte Methode, einschließlich des berühmten MAPF-GPT. Es bewältigte überfüllte Räume besser, weil es tatsächlich mit seinen Nachbarn „verhandeln" konnte.
Es skaliert: Normalerweise wird ein sprechendes System, wenn man mehr Roboter hinzufügt, langsam und stürzt ab, weil es zu viel Geplauder gibt. LC-MAPF ist anders. Selbst mit tausenden Robotern bleibt es schnell. Es ist wie eine gut organisierte Menge, bei der jeder nur mit den Leuten direkt neben sich spricht, anstatt über das ganze Stadion zu schreien.
Es funktioniert in der realen Welt: Die Forscher führten dies nicht nur am Computer durch. Sie bauten ein physisches Labyrinth mit echten Robotern (basierend auf einem kleinen AI-Kit namens Jetbot). Sie brachten das LC-MAPF-Gehirn in die echten Roboter ein, und die Roboter navigierten erfolgreich durch das physische Labyrinth, ohne zu kollidieren, und bewiesen, dass die „Flüstereien" im echten Leben funktionieren.

Das Fazit

Dieses Papier stellt eine neue Art vor, Robotern beizubringen, zusammenzuarbeiten. Anstatt stumme Solisten oder oberflächliche Redner zu sein, sind diese Roboter nun kooperative Gesprächspartner. Sie halten kurze, effiziente Besprechungen mit ihren Nachbarn ab, um einen Plan zu vereinbaren, was es ihnen ermöglicht, sich reibungslos und sicher durch komplexe, überfüllte Umgebungen zu bewegen. Das System ist schnell, skalierbar und wurde bereits mit echter Hardware bewiesen.

Technische Zusammenfassung: Lernen der lokalen Kommunikation für die Multi-Agenten-Pfadfindung im großen Maßstab

Problemstellung

Die Multi-Agenten-Pfadfindung (MAPF) ist eine fundamentale Abstraktion zur Koordinierung mehrerer homogener Agenten in gemeinsamen Umgebungen, wie etwa automatisierten Lagern oder Flotten autonomer Fahrzeuge. Das Ziel besteht darin, individuelle Pläne für $n$ Agenten zu berechnen, die sich auf einem Graphen von Startknoten zu Zielknoten bewegen, ohne Kollisionen (Knoten- oder Kantenkonflikte) zu verursachen. Obwohl optimale MAPF-Löser existieren, ist das Problem NP-schwer, und die Skalierbarkeit verschlechtert sich rapide, wenn die Anzahl der Agenten steigt.

Dezentrale Ansätze, bei denen Agenten Entscheidungen auf Basis lokaler Beobachtungen treffen, bieten einen Weg zur Skalierbarkeit, kämpfen jedoch häufig mit der Koordinationsqualität. Jüngste lernbasierte Methoden, wie MAPF-GPT, haben starke Ergebnisse unter Verwendung von Imitationslernen (IL) auf großen Datensätzen erzielt. Diese Modelle verfügen jedoch typischerweise über keine explizite Inter-Agenten-Kommunikation und verlassen sich ausschließlich auf lokale Beobachtungen, um kollaboratives Verhalten zu inferieren. Bestehende kommunikationsbasierte dezentrale Methoden beschränken die Interaktion oft auf einstufige Austausche lokaler Beobachtungen, was zur Lösung komplexer Konflikte in dichten Umgebungen möglicherweise unzureichend ist.

Methodik: LC-MAPF

Die Autoren schlagen LC-MAPF (Local Communication for Multi-agent Pathfinding) vor, ein dezentraler, lernbasierter Rahmen, der ein lernbares, mehrstufiges Kommunikationsmodul zur Verbesserung der Agentenkoordination einführt.

Architektur

Das Modell basiert auf einer Transformer-Architektur mit etwa 3 Millionen Parametern. Der Arbeitsablauf für jeden Agenten $u$ zum Zeitpunkt $t$ umfasst:

Codierung der Beobachtung: Agenten erhalten eine strukturierte lokale Beobachtung $o^t_u$ , die in eine Sequenz tokenisiert wird, welche Kosten-zu-Geht-Matrizen, Eigenmerkmale (Position, Ziel, gierige Aktion, Verlauf) und Merkmale der $k$ nächsten Nachbarn enthält. Dies wird in eine Sequenz $X_{0,u}$ eingebettet.
Kompression des latenten Zustands: Um eine von der Beobachtungsgröße unabhängige Kommunikationsskalierbarkeit sicherzustellen, verarbeitet ein Transformer-Encoder die Eingabe, und ein „latenter Flaschenhals" (inspiriert von der Perceiver-Architektur) komprimiert die codierten Tokens in einen kompakten latenten Zustand $z_u \in \mathbb{R}^{T_{latent} \times d_{latent}}$ .
Iterative Kommunikation: Agenten führen $R_{comm}$ $R_{co mm}$ Runden lokaler Kommunikation durch (Standardwert $R_{comm}=4$ $R_{co mm} = 4$ ).
- In jeder Runde $r$ erhält ein Agent Nachrichten von seinen Nachbarn (und sich selbst).
- Ein Decoder verschmilzt den latenten Zustand $z_u$ des Agenten mit den empfangenen Nachbarnachrichten $C^r_u$ .
- Ein Nachrichten-Head generiert einen aktualisierten Nachrichtenvektor $m^r_u$ , der in der nächsten Runde gesendet wird.
- Entscheidend ist, dass Nachrichten nicht überwacht werden. Das Netzwerk lernt durch Backpropagation, welche Informationen notwendig sind, um den finalen Aktionsverlust zu minimieren, wodurch Kommunikationsstrategien auf natürliche Weise entstehen.
Aktionsvorhersage: Nach der letzten Kommunikationsrunde gibt ein Vorhersage-Head Aktions-Logits aus, die in eine Wahrscheinlichkeitsverteilung für die Aktionsauswahl umgewandelt werden.

Training

LC-MAPF wird mittels Imitationslernen unter Verwendung von Expertendemonstrationen trainiert. Der Trainingsdatensatz besteht aus etwa 750 Millionen Beobachtungs-Aktions-Paaren, die von einem zentralen Löser (LaCAM*) über diverse Kartentypen (Labyrinthe, Zufall, Haus) abgeleitet wurden. Das Ziel ist die Minimierung des Kreuzentropieverlusts zwischen den vorhergesagten Aktionen und den Expertenaktionen. Es erfolgt keine explizite Überwachung der Kommunikationsnachrichten; das Modell lernt ausschließlich, um die kollektive Aktionsqualität zu verbessern.

Hauptbeiträge

Neues Kommunikationsframework: Die Einführung von LC-MAPF, einem Framework, das Agenten ermöglicht, ausschließlich unter Verwendung von Expertenaktionsdemonstrationen zu kommunizieren, ohne explizite Kommunikationslabels oder Überwachung zu benötigen.
State-of-the-Art-Leistung: Ein 3-Millionen-Parameter-Transformer-Modell, das einen neuen State-of-the-Art unter lernbaren dezentralen MAPF-Lösern setzt und bestehende IL- und Reinforcement-Learning-(RL-)Ansätze (einschließlich MAPF-GPT, SCRIMP, DCC und MAGAT-Varianten) über diverse Metriken und Kartentopologien hinweg übertrifft.
Skalierbarkeit mit Kommunikation: Der Nachweis, dass der vorgeschlagene mehrstufige Kommunikationsmechanismus eine lineare Skalierbarkeit beibehält, wenn die Anzahl der Agenten wächst, und damit einen häufigen Engpass bei kommunikationsbasierten Lösern adressiert.
Ablations- und Robustheitsanalyse: Umfassende Studien zeigen, dass:
- Mehrstufige Kommunikation (insbesondere 4 Runden) für hohe Erfolgsraten entscheidend ist.
- Das System gegenüber Nachrichtenfehlern (bis zu 50 % Rauschen) in kleineren Agentenpopulationen robust ist.
- Eine Begrenzung der Kommunikationsnachbarschaftsgröße die Leistung in dichten Szenarien erheblich verschlechtert.

Experimentelle Ergebnisse

Experimente wurden auf dem POGEMA-Benchmark durchgeführt, der die Kartentypen Zufall, Labyrinthe, Lager und Städte abdeckt.

Erfolgsrate: LC-MAPF erzielte über alle Kartentypen und Agentenanzahlen hinweg Erfolgsraten, die denen aller Baselines gleichkamen oder diese übertrafen, einschließlich des 85-Millionen-Parameter-Modells MAPF-GPT (bis zu 256 Agenten in Standardtests und bis zu 5.000 Agenten in großskaligen Evaluierungen).
Lösungsqualität: Hinsichtlich der Summe der Kosten (Sum-of-Costs, SoC) relativ zum zentralen optimalen Planer (LaCAM*) erzielte LC-MAPF konsistent die besten oder nahezu besten Verhältnisse.
Skalierbarkeit: Bei großskaligen Tests mit bis zu 5.000 Agenten auf 256x256-Karten behielt LC-MAPF eine lineare Skalierbarkeit bei, wobei sich die Berechnungszeiten vorhersehbar erhöhten (z. B. ~0,12 s/Schritt für 1.000 Agenten bis ~0,65 s/Schritt für 5.000 Agenten).
Einsatz in der realen Welt: Die Autoren setzten LC-MAPF erfolgreich auf einer physischen Multi-Roboter-Plattform (modifizierte JetBots) in einer modularen Labyrinthumgebung ein. Durch die Überbrückung diskreter Planung mit kontinuierlicher Steuerung (unter Verwendung von Rotations-/Wartungs-Synchronisation) koordinierten sich die Agenten erfolgreich, um Ziele ohne Kollisionen zu erreichen, was die praktische Anwendbarkeit der Methode validierte.

Bedeutung und Behauptungen

Die Arbeit behauptet, dass LC-MAPF einen bedeutenden Fortschritt in der dezentralen Multi-Agenten-Koordinierung darstellt, indem gezeigt wird, dass effektive, iterative lokale Kommunikation implizit aus Expertentrajektorien gelernt werden kann. Im Gegensatz zu früheren Methoden, die entweder Kommunikation ignorieren oder auf einstufigen, überwachten Austauschen beruhen, nutzt LC-MAPF einen mehrstufigen, unüberwachten Kommunikationsmechanismus, der es Agenten ermöglicht, Konflikte dynamisch zu verhandeln und zu lösen.

Die Autoren betonen, dass dieser Ansatz erfolgreich Lösungsqualität und Skalierbarkeit in Einklang bringt und den typischen Zielkonflikt überwindet, bei dem kommunikationsbasierte Methoden unter rechenintensiven Engpässen leiden. Die Ergebnisse deuten darauf hin, dass LC-MAPF als generalisierbares, vortrainiertes Modell dient, das diverse, nicht gesehene Umgebungen und große Agentenpopulationen bewältigen kann, und bietet eine robuste Lösung für reale robotische Anwendungen wie Logistik und Suche und Rettung.