de.wedoany.com-Bericht: Ein chinesisches Forschungsteam hat ein neues Paradigma namens DPCN (Decentralized-Planning-Centralized-Negotiation) zur Lösung des Multi-Agent Path Finding (MAPF)-Problems vorgestellt. Dieses Paradigma behält die Skalierbarkeit dezentraler Methoden bei, während es durch einen zentralen Verhandlungsmechanismus dynamische Konflikte effektiv behandelt und in Standard-Benchmark-Tests eine bessere Leistung als bestehende Reinforcement-Learning-Methoden erzielt.
Multi-Agent Path Finding zielt darauf ab, konfliktfreie Pfade für mehrere Agenten in einer gemeinsamen Umgebung zu planen und wird häufig in der automatisierten Lagerhaltung, der Einsatzplanung von Servicerobotern und der Flughafenlogistik eingesetzt. Traditionelle zentrale Planungsstrategien liefern bei kleinen Problemen hervorragende Ergebnisse, aber die Rechenkomplexität steigt bei großen Agententeams drastisch an. Dezentrale Methoden, die auf Reinforcement Learning basieren, bieten zwar Skalierbarkeit und Anpassungsfähigkeit an die Umgebung, sind jedoch durch die lokale Beobachtungsperspektive eingeschränkt, was leicht zu Blockaden, Kollisionen oder sogar Deadlocks führen kann.
DPCN unterteilt jeden Zeitschritt in zwei Phasen: In der Planungsphase generiert jeder Agent basierend auf lokalen Beobachtungsinformationen o_i^t (Sichtfeld 3×3) unabhängig eine Handlungsabsicht; in der Verhandlungsphase erkennt das System alle potenziellen Konflikte (einschließlich Vertex-Konflikten und Swap-Konflikten) und fasst die an Konflikten beteiligten Agenten dynamisch zu einem „Super-Agenten" zusammen. Über das lernfähige PNSE-Netzwerk (Pointer Network Special Edition) wird basierend auf dem Umgebungszustand ein „Gewinner" aus der Konfliktgruppe ausgewählt, der seine ursprüngliche Absicht ausführt, während die anderen Agenten stillstehen oder eine neue Aktion neu abtasten.
Angesichts der Probleme inkonsistenter Aktionsräume des Super-Agenten und dynamischer Trainingsschwierigkeiten ist das PNSE-Netzwerk von Pointer Networks inspiriert und kann mit variablen Eingabelängen und inkonsistenten Aktionsräumen umgehen. Das Forschungsteam schlug einen maßgeschneiderten Policy-Gradient-Reinforcement-Learning-Trainingsmechanismus vor, der eine Mean-Field-Approximation zur fairen Verteilung der globalen Belohnung verwendet, um ein effektives Training des dynamischen Super-Agenten zu ermöglichen.
Die Experimente wurden auf Standard-MAPF-Benchmarks und zufälligen Karten durchgeführt, wobei zwei Arten von zentralen Planern (ODrM*, BALANCE) und drei führende RL-Methoden (SCRIMP, DCC, PICO) verglichen wurden. Die Experimente mit zufälligen Karten umfassten Kartengrößen von 30×30 bis 100×100, Hindernisdichten von 0% bis 30% und Agentenzahlen von 32 bis 256. Jede Einstellung wurde 200 Mal wiederholt, wobei die Erfolgsrate und die Anzahl der Schritte zur Aufgabenerfüllung gemeldet wurden. Die Ergebnisse zeigen, dass DPCN bei hohen Hindernisdichten (30%) und in groß angelegten Szenarien stets eine hohe Erfolgsrate und eine niedrige Aufgabenbearbeitungszeit beibehält, andere RL-Methoden deutlich übertrifft und sogar die zentralen Planer übertrifft.
Bei der Bewertung der Generalisierungsfähigkeit auf strukturierten Karten verwendeten die Experimente drei typische Kartentypen: eine Multi-Raum-Umgebung der Größe 32×32 (Raumgröße 3×3), eine Auditorium-Umgebung der Größe 162×141 und eine Lagerumgebung der Größe 170×84 (Regalgangbreite nur 2 Gitter). Jede Karte enthielt 25 Problemfälle. DPCN behält in diesen komplexen Strukturen die Fähigkeit, große Teams effizient zu koordinieren.
Das Forschungsteam weist darauf hin, dass DPCN durch seine innovative Architektur aus dezentraler Planung und zentraler Verhandlung die Herausforderungen der Konfliktkoordination unter lokaler Perspektive effektiv löst, während die Skalierbarkeit erhalten bleibt. Zukünftig wird die Anwendung auf dynamische Hindernisse, heterogene Agenten und reale Roboterplattformen untersucht.
