Multi-Agenten-Koordination erklärt
Multi-Agenten-Koordination fragt, wie mehrere eigenständige Akteure (Kräne, Fahrzeuge, Roboter) ihre Aufgaben untereinander verteilen, ohne dass ein zentraler Planer alles entscheidet. Alle acht Stücke dieser Linie teilen dasselbe kleine Vehikel: Kran-Aufträge mit Positionen entlang einer Achse, Ziel ist ein möglichst früher Fertigstellungszeitpunkt (Makespan), gemessen am zentralen Optimum von Google OR-Tools. Ehrlich eingeordnet bleibt der zentrale Solver der praktische Industriestandard; dezentrale Verfahren tauschen globale Optimalität gegen Dezentralität.
In short: Covers multi-agent coordination and decentralized task allocation: contract net protocol, negotiation, DCOP, multi-agent learning, auctions and learned mechanisms such as RegretNet. Interactive demos share one small crane-scheduling example.
Hintergrund zum Thema: Hafenlogistik.
Diese Seite gehört zu Algorithmen und Verfahren erklärt. So lesen Sie sie: Das Diagramm zeigt, wie die Stücke zusammenhängen. Jede Kachel darunter öffnet eine interaktive Demo, wo es eine gibt, mit einer Erklärseite für Einsteiger und Fachleute. Auf der Suche nach einer Lösung für ein konkretes Problem? Zu den Interaktiven Demos.
Hinweis: Alle Demos rechnen mit synthetischen oder frei verfügbaren Beispieldaten und laufen auf einem externen Anbieter (Datenschutz). Bitte geben Sie darin keine vertraulichen oder personenbezogenen Daten ein. Die Ergebnisse gelten für die jeweilige Demo-Instanz und lassen sich nicht ungeprüft auf reale Fälle übertragen; für darauf gestützte Entscheidungen übernehme ich keine Gewähr.
Zuletzt aktualisiert:
Welches Verfahren passt zu Ihrem Fall? Zum Entscheidungsbaum ↓
Zum Nachlesen: erst einfach, dann fachlich
Auftragsvergabe per Gebot verständlich erklärt
Wie Kräne Aufträge per Gebot untereinander verteilen, ohne dass eine Zentrale plant, und warum ein einmal vergebener Auftrag das Gesamtergebnis hinter einen Plan mit Vorwissen zurückwerfen kann: erst für Einsteiger ohne Formeln, dann für Fachleute mit Modell, Gebotsformel und Befunden.
Die acht Stücke im Überblick
Ein Graph statt eines Pfades: Contract Net ist die Wurzel: Aufgaben werden ausgeschrieben, geboten und zugeschlagen, und der Zuschlag bleibt für immer bestehen. Von dort gehen vier Wege aus, die je eine Schwäche angehen: Die Task-Swap-Verhandlung korrigiert nachträglich per paarweisem Tausch, DCOP mit DPOP löst ein globales Modell exakt (und verfehlt den echten Makespan, weil das Modell nur ein Summen-Ersatz ist), Multi-Agenten-Lernen lässt die Agenten ihre Gebote anpassen (fortgesetzt von MAPPO, das die Nicht-Stationarität mit einem zentralen Kritiker angeht), und kombinatorische Auktionen lassen auf Bündel statt auf Einzelaufträge bieten (fortgesetzt von RegretNet, das den Mechanismus selbst lernt, mit einem teils negativen Ergebnis). Learning-augmented DCOP läuft als Konvergenzpunkt aus DCOP und den lernenden Stücken zusammen.
Die Kästen sind klickbar und öffnen die jeweilige Demo direkt.
- behebt eine Schwäche des Vorgängers oder baut darauf auf
- Zusammenfluss mehrerer Stränge
- eigene oder frische Forschung, kein etablierter Standard
Learning-augmented DCOP ist als einziger Knoten orange umrahmt: eine frische Forschungsrichtung, kein etablierter Standard wie die übrigen Stücke. Die Demo ist eine kleine, ehrliche Rekonstruktion der Idee, keine Reproduktion einer veröffentlichten Methode. Der Doppelrahmen zeigt zugleich den Zusammenfluss aus DCOP und den lernenden Stücken.
Verwandt in anderen Linien
- Exakte Suche — DPOP in der DCOP-Demo ist verteilte dynamische Programmierung auf einem Pseudo-Baum; seine Tabellen wachsen exponentiell (App-Grenze 2²² Einträge), wie die der Dynamischen Programmierung. Exakter Referenzwert aller Kran-Demos ist ein CP-SAT-Löser (Constraint Programming), und die Auktion stellt den Teilmengen-DP der Gewinnerermittlung gegen CP-SAT, das dort schon bei n = 11 bis 12 scheitert.
- Spieltheorie — Die Gegenfrage, wer welchen Anreiz hat, wenn Agenten nur den eigenen Vorteil verfolgen: das Nash-Gleichgewicht bei der Torwahl, dazu Maut und Kostenteilung. Die VCG-Zahlungsregeln der hiesigen Auktion dienen dort als Vergleich.
- Neuronale Netze — Das Politiknetz der MAPPO-Demo und das von RegretNet gelernte Zuteilungsnetz sind beides MLPs mit Backpropagation wie in der Neuronale-Netze-Linie, dort selbst erklärt.
- Reinforcement Learning — Beide lernenden Stücke hier bauen auf dem Ein-Agenten-Fundament dieser Linie auf: unabhängiges Q-Learning ist mehrmals gleichzeitig laufendes Q-Learning, und der zentrale Kritiker der MAPPO-Demo ist derselbe Baustein wie beim dortigen Actor-Critic, nur mit Einblick in den Zustand aller Agenten.
Contract Net Protocol an der Kran-Auftragsvergabe
Verfolgen Sie, wie Aufträge ausgeschrieben, von Kränen geboten und an das niedrigste Gebot vergeben werden: dezentral, ohne zentralen Planer, aber unwiderruflich. Ein Vergleich mit dem exakten OR-Tools-Optimum zeigt live, dass die Lücke selbst bei gleichmäßigen Auftragsdauern stark schwankt: schon die Reihenfolge-Struktur macht eine frühe, unumkehrbare Zuteilung teuer.
Verständlich erklärt: erst für Einsteiger, dann für Fachleute
Demo starten →Task-Swap-Verhandlung nach dem Contract Net Protocol
Sehen Sie, wie Agenten nach der Vergabe paarweise Aufträge tauschen, solange ein Tausch den Fertigstellungszeitpunkt verbessert. Ein Reichweiten-Regler und ein Dreier-Vergleich (Contract Net, Verhandlung, OR-Tools-Optimum) zeigen live, was Dezentralität kostet, und dass die Verhandlung die Lücke oft, aber nicht immer ganz schließt, weil paarweise Tausche im lokalen Optimum steckenbleiben können.
Demo starten →DCOP mit DPOP an der Kran-Auftragsvergabe
Verfolgen Sie, wie DPOP ein verteiltes Optimierungsproblem über einen Pseudo-Baum exakt löst: beweisbar optimal für sein Modell. Zwei getrennte Vergleiche zeigen live, dass die Lücke zum echten Makespan trotzdem oft bleibt: Das Modell ist ein Summen-Ersatz, nicht der Makespan, und die Tabellen wachsen exponentiell mit der Auftragszahl.
Demo starten →Unabhängiges Q-Learning an der Kran-Auftragsvergabe
Sehen Sie, wie Kräne aus wiederholter Interaktion lernen, ihre Gebote anzupassen: jeder Agent für sich, die anderen als Teil der Umgebung. Ein Umschalter zwischen wiederkehrendem Szenario und zufälligen Instanzen zeigt live die Lehre: gelernt wird nur, was wiederkehrt.
Demo starten →MAPPO mit zentralem Kritiker an der Kran-Auftragsvergabe
Verfolgen Sie, wie ein zentraler Kritiker im Training den gemeinsamen Zustand sieht, während im Einsatz jeder Akteur nur lokal entscheidet. Ein Vergleich mit IPPO und ein Umschalter für das Clipping zeigen live das überraschende Messergebnis: Nicht der zentrale Kritiker stabilisiert das Training, sondern das Clipping von PPO.
Demo starten →Kombinatorische Auktionen an der Kran-Auftragsvergabe
Sehen Sie, wie Kräne statt auf Einzelaufträge auf Bündel bieten. Mit allen Bündeln ist die Auktion das exakte Optimum. Gemessen werden die Kosten: Vier Gebotssprachen zeigen live, wie stark die Zahl der Gebote (12 285 statt 36 beim Contract Net bei zwölf Aufträgen und drei Kränen) und die NP-harte Gewinnerermittlung wachsen.
Demo starten →RegretNet: ein gelernter Mechanismus für die Kran-Auftragsvergabe
Verfolgen Sie, wie ein neuronales Netz Zuteilung und Zahlung einer Auktion lernt und gegen die exakte Analytik gemessen wird. Ausdrücklich ein teils negatives Ergebnis: Bei einem privaten Parameter je Agent schlägt die exakte Analytik das gelernte Netz bei Lücke, Überzahlung und Regret; bei Bündelkosten approximiert das Netz nur wahrheitsgetreue Varianten von VCG und bricht ab vier Aufträgen ein.
Demo starten →Learning-augmented DCOP an der Kran-Auftragsvergabe
Verfolgen Sie, wie Lernen an zwei Stellen in die verteilte Auftragsvergabe der Kräne eintritt: als gelerntes Kostenmodell und als gelernte Nachrichten statt der exponentiell wachsenden DPOP-Tabelle. Ein Vergleich trennt beide Effekte live. Ehrlich gemessen bleibt der zentrale Löser CP-SAT vorn, und eine einfache lokale Suche ist ab 16 Aufträgen gleich gut oder besser als die gelernten Nachrichten. Frische Forschungsrichtung, keine Reproduktion einer veröffentlichten Methode.
Demo starten →Welches Verfahren passt zu meiner Aufgabe?
Ein Entscheidungsbaum als Faustregel: Er führt von der Art der Aufträge und der Kommunikation zum passenden Verfahren. Die Aussagen stammen aus Vergleichen an erzeugten Kran-Instanzen, nicht aus einem Praxiseinsatz.
Beige Kästen sind Fragen (nicht klickbar), weiße Kästen sind Ergebnisse (klickbar, sie öffnen die jeweilige Demo). Ehrlich dazu: Lernen garantiert keine bessere Lösung. Auf zufälligen Instanzen verliert das Multi-Agenten-Lernen gegen Contract Net und lernt nur bei einem wiederkehrenden Szenario. DCOP mit DPOP gewinnt je nach Einstellung nur in 27 bis 50 % der Instanzen gegen Contract Net, weil das Summenmodell die echte Fertigstellungszeit verfehlt. Bei RegretNet schlägt in den Tests ein exakter Schwellenwert-Mechanismus das gelernte Netz, und in der Demo zu Learning-augmented DCOP (im Baum nicht enthalten) hält ab etwa 16 Aufträgen eine einfache lokale Suche mit den gelernten Nachrichten mit.
Weitere Linien in diesem Bereich
Spieltheorie
Wer hat welchen Anreiz? Zehn Verfahren zu eigennützigen Lkw und zu Spediteuren, die Kosten teilen, jedes mit seinem gemessenen Befund.
Wiederholte Spiele
Zwei Spediteure, die sich jede Woche wiedersehen: elf Stücke von Tit-for-Tat über das Folk-Theorem und Preiskriege bis zu lernenden Preis-Algorithmen.
Turnierplanung
Wie plant man ein faires Turnier mit vertretbarer Rundenzahl, und was zählt sonst noch: Heimrecht, Reisedistanz, eine zweite Chance, der Gleichstand? Acht Antworten, jede gegen echte Referenzdaten oder Literatur geprüft.
Adversarische Suche
Wie entscheidet eine Maschine ihren nächsten Zug gegen einen Gegner, der das Gegenteil will? Von der erschöpfenden Minimax-Suche über Effizienz-Tricks und Bewertungsfunktionen bis zum Selbstspiel-Training.
Ranking
Wie wird aus Vergleichen eine Rangfolge, und wie sicher ist sie? Ein simuliertes Turnier mit bekannter Stärke, siebzehn Stücke von der Siegtabelle über Bradley-Terry und Elo bis zu Rangintervallen und Learning to Rank.
Abstimmen und Fair Teilen
Wie aus verschiedenen Wünschen eine Entscheidung oder eine faire Verteilung wird: fünfzehn Stücke von der Wahlregel bis zur Kuchenteilung.