Anytime Multi-Agent Path Finding (MAPF) ist ein vielversprechender Ansatz zur skalierbaren Pfadoptimierung in großen Multi-Agentensystemen. Der aktuelle Stand der Technik bei MAPF basiert auf der Large Neighborhood Search (LNS), bei der eine schnelle Ausgangslösung iterativ durch Zerstörung und Reparatur einer festen Anzahl von Teilen, d.h. der Nachbarschaft der Lösung, unter Verwendung von randomisierten Zerstörungsheuristiken und priorisierter Planung optimiert wird.
Trotz ihres jüngsten Erfolges in verschiedenen MAPF-Instanzen mangelt es den derzeitigen LNS-basierten Ansätzen an Exploration und Flexibilität aufgrund der gierigen Optimierung mit einer festen Nachbarschaftsgröße, was im Allgemeinen zu Lösungen geringer Qualität führen kann. Bislang wurden diese Einschränkungen mit umfangreichen Vorleistungen im Tuning oder Offline-Maschinenlernen über die eigentliche Planung hinaus angegangen.
In dieser Arbeit konzentrieren wir uns auf das Online-Lernen in LNS und schlagen eine Bandit-basierte adaptive LArge-Nachbarschaftssuche in Kombination mit Exploration (BALANCE) vor. BALANCE verwendet ein zweistufiges mehrarmiges Bandit-Schema, um die Auswahl der Zerstörungsheuristiken und Nachbarschaftsgrößen während der Suche anzupassen. Wir evaluieren BALANCE auf mehreren Karten aus dem MAPF-Benchmark-Set und zeigen empirisch eine Leistungsverbesserung von mindestens 50 % im Vergleich zu MAPF, das immer auf dem neuesten Stand der Technik ist, in groß angelegten Szenarien. Wir stellen fest, dass Thompson Sampling im Vergleich zu alternativen mehrarmigen Bandit-Algorithmen besonders gut abschneidet.
Quelle: Adaptive Anytime Multi-Agent Path Finding Using Bandit-Based Large Neighborhood Search