Multi-Agent Path Finding

Auch genannt: MAPF, multi-agent pathfinding, multi-robot path planning
Kategorie: Learning & autonomy › Multi-robot
Schlagwörter: multi-robot, path-planning, warehouse-automation, coordination, graph-search

Das Problem, kollisionsfreie Pfade für viele gleichzeitig auf einem gemeinsamen Graphen fahrende Agenten zu berechnen, etwa Lagerroboter auf einem Gitter, sodass jeder Agent sein Ziel ohne Konflikte erreicht.

Definition

Multi-Agent Path Finding (MAPF) ist das Problem, Pfade für eine Gruppe von Agenten zu planen, die sich eine Umgebung teilen, sodass jeder Agent von seinem Start zu seinem Ziel gelangt, ohne dass zwei Agenten zur selben Zeit denselben Ort belegen oder entlang derselben Kante die Plätze tauschen. Die Umgebung wird meist als Graph modelliert, oft als Gitter, und die Zeit ist in diskrete Schritte unterteilt, in denen jeder Agent entweder zu einem benachbarten Knoten zieht oder wartet.

MAPF-Lösungen werden meist nach der Kostensumme (Sum of Costs) beurteilt, der Gesamtzeit, die alle Agenten bis zu ihren Zielen brauchen, oder nach dem Makespan, der Zeit bis zur Ankunft des letzten Agenten. Eine optimale Lösung unter diesen Zielen zu finden, ist im Allgemeinen NP-schwer, daher hat das Fachgebiet Algorithmen entwickelt, die Optimalität gegen Geschwindigkeit eintauschen. Zu den optimalen Verfahren gehört Conflict-Based Search (CBS), das jeden Agenten unabhängig plant und Kollisionen dann durch Hinzufügen von Nebenbedingungen in einem Suchbaum auflöst. Suboptimale Verfahren wie die priorisierte Planung, bei der Agenten nacheinander planen und früher geplante Agenten als bewegliche Hindernisse behandeln, skalieren auf viel größere Teams.

Lifelong MAPF ist eine Variante, bei der Agenten neue Ziele erhalten, sobald sie die alten erreichen, was der tatsächlichen Arbeitsweise von Lager- und Sortierrobotern entspricht. Die Planung läuft dann fortlaufend, oft über ein begrenztes Zeitfenster, und der Durchsatz wird zum wichtigsten Maß.

Reale Roboter brechen auch die Lehrbuchannahmen: Sie haben eine Größe, Beschleunigungsgrenzen und Ausführungsverzögerungen, daher werden MAPF-Pläne meist mit einer zusätzlichen Koordinationsschicht ausgeführt, die die Roboter sicher hält, wenn einige hinter dem Zeitplan zurückfallen. Lernbasierte Verfahren, einschließlich Imitationslernen von suchbasierten Planern, sind eine aktive Forschungsrichtung für die Skalierung auf sehr große Flotten.

Warum es wichtig ist

Lager, Fabriken und Sortierzentren betreiben wachsende Flotten mobiler Roboter auf gemeinsamen Flächen, und ihr Durchsatz hängt davon ab, wie gut diese Roboter koordiniert sind. MAPF liefert die Algorithmen, die die Roboter ohne Kollisionen oder Deadlocks in Bewegung halten, während die Flotten wachsen.

Wichtige Anwendungen

Roboterflotten in Lagern und Fulfillment-Centern
Paketsortiersysteme mit vielen mobilen Robotern
Koordination fahrerloser Transportfahrzeuge (AGVs) in Fabriken
Koordination von Mehrdrohnensystemen und des Bodenverkehrs auf Flughäfen
Figurenbewegung in Videospielen und Menschenmengensimulation

In der Praxis

Ein Team, das eine Lagerflotte betreibt, modelliert die Fläche typischerweise als Gitter- oder Roadmap-Graphen, wobei jede Zelle so bemessen ist, dass ein Roboter hineinpasst. Ein zentraler Planer erhält Ziele vom Auftragssystem und berechnet koordinierte Pfade, oft mit einer priorisierten oder zeitfensterbasierten Suche, die alle paar Sekunden neu plant, statt das ganze Problem optimal zu lösen. Die Pfade werden in zeitlich festgelegte Wegpunkte umgewandelt und an die Roboter gesendet, und eine Ausführungsschicht, etwa ein Action Dependency Graph, stellt sicher, dass ein Roboter eine Zelle erst betritt, wenn der vorausfahrende Roboter sie freigegeben hat. Ingenieure messen Durchsatz, Wartezeit und Deadlock-Häufigkeit in der Simulation mit voller Flottengröße, bevor sie Flächenlayout oder Algorithmus am realen System ändern.

Häufige Missverständnisse

Jeder Roboter kann seinen eigenen kürzesten Pfad unabhängig planen — unabhängige Pfade kollidieren, daher müssen Roboter in der Zeit wie im Raum koordiniert werden
Optimales MAPF skaliert auf jede Flottengröße — optimales Lösen ist NP-schwer, daher sind große Flotten auf suboptimale oder zeitfensterbasierte Verfahren angewiesen
Ein MAPF-Plan kann genau wie berechnet ausgeführt werden — reale Roboter sind zu früh oder zu spät, daher braucht die Ausführung eine eigene Sicherheits- und Koordinationsschicht

Wer das wissen sollte

Ingenieure für Lagerautomatisierung und Flottenmanagement
Forschende in der Mehrroboterplanung
Systemintegratoren für AMR und AGV
Operations-Research-Fachleute, die an Logistik arbeiten

Open Source Robotics