Do We Run Large-Scale Multi-Robot Systems on the Edge? More Evidence for Two-Phase Performance in System Size Scaling

Autoren: Jonas Kuckling, Robin Luckey, Viktor Avrutin, Andrew Vardy, Andreagiovanni Reina, Heiko Hamann · ICRA 2024

Lizenzen

Open Access
Paper: CC BY 4.0

Alles Folgende stützt sich auf das vollständige Paper unter seiner Lizenz CC BY 4.0; die Abbildung wird mit Nennung der Autoren gezeigt.

Kurz gesagt

Simulationen dreier Multi-Roboter-Systeme zeigen, dass sich die Leistung bei einer kritischen Schwarmgröße in nahezu optimale Läufe und Läufe nahe null aufspaltet; ein Populationsmodell führt dies auf Bifurkationen und lange Transienten zurück.

Warum es wichtig ist

Betreiber, die Roboterflotten oder Schwärme auf maximalen Durchsatz abstimmen, betreiben sie womöglich unwissentlich am Rand eines Zusammenbruchs, und lange Transienten können ein solches System eine Zeit lang gesund erscheinen lassen, bevor es kollabiert. Das Modell sagt außerdem Hysterese voraus, sodass das Hinzufügen oder Entfernen von Robotern im laufenden Betrieb, wie es manche Methoden für robuste Skalierbarkeit tun, plötzliche Leistungssprünge verursachen kann.

Problem

Die Schwarmleistung wird meist als Mittelwert über die Schwarmdichte angegeben, der ansteigt, bei einer kritischen Systemgröße seinen Höhepunkt erreicht und dann fällt. Dieser Mittelwert kann ein bimodales Ergebnis verbergen, bei dem nahe der kritischen Größe manche Läufe fast optimal arbeiten und andere in einen Stau kollabieren, sodass ein auf maximale mittlere Leistung abgestimmtes System nahe am Zusammenbruch liegen kann.

Lösungsansatz

Die Autoren simulieren drei Systeme (ein Lager mit an Schienen hängenden AFLE-Lagerrobotern mit mehr als 3000 Einheiten, Objekt-Clustering im Schwarm mit der lasso-Methode und emergente Taxis hin zu einer Lichtbake) und tragen statt des Mittelwerts die vollständige Leistungsverteilung über die Schwarmgröße auf. Anschließend modellieren sie den Effekt auf zwei Arten: eine M/M/1-Warteschlange, deren Bedienzeit von der Warteschlangenlänge abhängt, und ein Populationsmodell mit drei Zuständen (solo, grupo, fermo), das als gewöhnliche Differentialgleichungen formuliert und mit Werkzeugen der nichtlinearen Dynamik analysiert wird.

Wichtigste Erkenntnisse

Nahe der kritischen Systemgröße sind die Ergebnisse bimodal: Läufe arbeiten entweder nahe der maximalen Leistung oder brechen auf nahezu null Leistung ein, mit fast nichts dazwischen.
Im Populationsmodell bedeutet eine Sattel-Knoten-Bifurkation, dass ein zusätzlicher Roboter das System von hoher auf niedrige Produktivität umschalten kann, und das Entfernen von Robotern schaltet es erst bei einer kleineren Schwarmgröße zurück (Hysterese).
Die Transientenzeit wächst nahe dem kritischen Zustand überexponentiell (kritische Verlangsamung), was die Autoren auf eine Cusp-Bifurkation der Kodimension 2 im Parameterraum (N, k1) zurückführen; ein System kann daher auf 'geborgter Zeit' laufen, bevor es zusammenbricht.
Schon eine einfache modifizierte M/M/1-Warteschlange reproduziert den linearen Anstieg und den Zusammenbruch bei einer kritischen Ankunftsrate, und ihre Kurven ähneln denen des Populationsmodells.

Hauptergebnisse

Lager (96 Wiederholungen je Ankunftsrate): Der Durchsatz stieg linear mit der Ankunftsrate bis etwa 10⁴ AFLEs pro Stunde, danach kollabierten einige Läufe in einen Stau mit nahezu null Durchsatz, während andere am Maximum blieben.
Objekt-Clustering (1000 Läufe je Schwarmgröße, 1 bis 20 Roboter): beste Leistung bei etwa 6 Robotern; ab 10 Robotern spalteten sich die Ergebnisse in erfolgreiche und erfolglose Läufe auf.
Emergente Taxis (800 Läufe je Schwarmgröße, 2 bis 40 Roboter, Daten aus früheren Arbeiten): Die maximale Geschwindigkeit wurde bei etwa 15 Robotern erreicht, wo eine zweite Phase mit niedriger Geschwindigkeit auftrat.
Modifizierte M/M/1-Warteschlange (mittlere Ankunftsrate 0,4 bis 0,9, jeweils 500 Stichproben): Zusammenbruch bei einer kritischen mittleren Ankunftsrate von etwa 0,65.
Populationsmodell mit den Standardraten: Die Anzahl der solo-Roboter erreicht bei N = 31 ihren Höhepunkt und fällt dann rasch; mit k1 = 0,001 begrenzen zwei Sattel-Knoten-Bifurkationen einen bistabilen Bereich, und Fig. 6 zeigt den Zustandsraum bei N = 40 innerhalb dieses Bereichs.

Einschränkungen

Die Autoren geben an, dass offen bleibt, welches Modell die Zwei-Phasen-Leistung am besten beschreibt, und dass künftige Forschung zeigen muss, ob der Effekt real und in industriellen Anwendungen relevant ist.
Alle drei Szenarien sind Simulationen; das Lagermodell ist eine Gitterwelt mit Einbahnverkehr und ohne Physik, und Abschnitte der Lagerschienen werden nicht modelliert.
Die Ergebnisse zur emergenten Taxis sind aus einer früheren Veröffentlichung übernommen und nicht neu durchgeführt.
Die Konstanten der Warteschlange werden als willkürlich beschrieben, und von beiden Modellen heißt es, sie erfassten das Verhalten qualitativ; die Arbeit passt sie nicht an die Simulationsdaten an.

Wirkung auf das Fachgebiet

Gewinner des IEEE ICRA 2024 Best Paper Award on Multi-Robot Systems, mit 14 Zitierungen. Die Arbeit verlinkt den Open-Source-Code ihres Objekt-Clustering-Simulators und ein Video; eine Veröffentlichung des Lagersimulators wird nicht erwähnt.

Zusammenfassung

Da immer mehr mobile Roboter in realen Anwendungen ankommen, koexistieren mehr Roboter im selben Raum, interagieren und arbeiten möglicherweise zusammen. Methoden, die solchen Systemen Skalierbarkeit in der Systemgröße verleihen, sind beispielsweise aus der Schwarmrobotik bekannt. Beispielhafte Strategien sind selbstorganisierendes Verhalten, ein strikt dezentraler Ansatz und die Begrenzung der Roboter-Roboter-Kommunikation. Trotz der Anwendung solcher Strategien bricht jedes Multi-Roboter-System oberhalb einer bestimmten kritischen Systemgröße (d. h. Anzahl der Roboter) zusammen, da zu viele Roboter eine Ressource teilen (z. B. Raum, Kommunikationskanal). Wir liefern auf Grundlage von Simulationen zusätzliche Belege dafür, dass sich die Systemleistung bei diesen kritischen Systemgrößen in zwei Phasen aufspaltet: nahezu optimale und minimale Leistung. Wir vermuten, dass in realen Anwendungen, die auf die optimale Systemgröße ausgelegt sind, das vermeintlich leistungsstarke System tatsächlich auf geborgter Zeit leben könnte, da es sich in einem Übergang zum Zusammenbruch befindet. Wir stellen zwei Modellierungsoptionen vor (auf Basis der Warteschlangentheorie und eines Populationsmodells), die helfen können, diese Überlegung zu stützen.

Open Source Robotics