Einführung in die Schwarmsteuerung (Mehrere Roboter) – Aufbau von Schwarmverhalten, Formationen und Konsens

Wenn Hunderte von Drohnen in einer Drohnenshow gleichzeitig ihre Formation verändern oder eine Flotte von Lagerrobotern sich kollisionsfrei bewegt, gibt es keine zentrale „Kommandozentrale“, die jede Bewegung in Echtzeit berechnet. In den meisten Fällen betrachtet jeder Roboter lediglich begrenzte Informationen über seine Umgebung und folgt einfachen Regeln – und daraus entsteht ein geordnetes, sinnvolles Verhalten für die Gruppe als Ganzes. Dieser Artikel beleuchtet das Konzept der Schwarmsteuerung (Mehrrobotersteuerung) – die Bildung eines komplexen Ganzen aus einfachen Teilen – aus drei Perspektiven: Schwarmverhalten, Konsensbildung und Formationssteuerung.

Ein Schwarmroboter im Einsatz (Kilobot)

Bild: Kilobot Roboterschwarm (asuscreative, CC BY-SA 4.0), Wikimedia Commons. Ein repräsentatives Beispiel für Schwarmrobotikforschung, die ausschließlich mit lokalen Regeln arbeitet, nicht mit den im Text besprochenen Drohnen oder Lagerrobotern.

0. Inhalt dieses Artikels

• Welches Problem die Schwarmsteuerung zu lösen versucht und warum ein einzelner Roboter nicht ausreicht.

• Der Zusammenhang zwischen den Informationen, die jeder Roboter tatsächlich erhalten kann (Eingabe), und der daraus abgeleiteten Ausgabe (Geschwindigkeitsbefehl).

• Der architektonische Unterschied zwischen zentralisierten und dezentralisierten Designs.

• Wie regelbasiertes Schwarmverhalten, beispielhaft dargestellt durch Boids, funktioniert.

• Die Mathematik der Konsensbildung mittels Konsensalgorithmen.

Die Unterschiede zwischen drei Ansätzen der Formationssteuerung: Leader-Follower, virtuelle Struktur und verhaltensbasiert.

• Wie Kommunikationsbeschränkungen (Latenz, Verbindungsabbrüche, Bandbreite) das Design der Schwarmsteuerung beeinflussen.

Welcher Ansatz für welche Anwendung geeignet ist – Drohnenshows, Lagerroboter, Katastrophenhilfe und mehr.

1. Fazit: Was ist Schwarmsteuerung?

In einem Satz: Schwarmsteuerung ist ein Steuerungsrahmen, der sinnvolle Ergebnisse liefert. Das kollektive Verhalten der gesamten Gruppe – Ausrichtung, Formationserhaltung, Konsensfindung, Arbeitsteilung – basiert auf den begrenzten Informationen und einfachen Verhaltensregeln, die jedem einzelnen Roboter zur Verfügung stehen.**

Der entscheidende Punkt ist: „Niemand besitzt zwangsläufig den Plan für das Ganze.“ So wie ein Vogelschwarm keinen Dirigenten hat, sind viele Schwarmsteuerungsalgorithmen so konzipiert, dass jeder Roboter nur Informationen über die anderen Roboter in seiner Nähe (seine Nachbarn) nutzt. Selbst ohne den vollständigen Zustand der gesamten Gruppe zu kennen, bewegt sich der Schwarm als Ganzes als eine zusammenhängende Einheit. Diese Idee – „globale Ordnung aus lokalen Informationen schaffen“ – unterscheidet die Schwarmsteuerung grundlegend von der Steuerung einzelner Roboter.

2. Warum ist Schwarmsteuerung notwendig?

Wenn ein Problem von einem einzelnen Hochleistungsroboter gelöst werden kann, ist Schwarmsteuerung nicht erforderlich. Schwarmsteuerung wird in der Praxis in Situationen gewählt, in denen eine einzelne Einheit prinzipiell oder praktisch im Nachteil ist – zum Beispiel:

• Räumliche Abdeckung: Ein einzelner Roboter bräuchte zu lange, um ein großes Katastrophengebiet oder Feld von einem Ende zum anderen abzusuchen. Die Aufteilung der Arbeit auf viele Roboter verkürzt die Suchzeit in etwa proportional zur Anzahl der Roboter.

• Redundanz und Fehlertoleranz: Bei einer Konfiguration mit nur einer Einheit stoppt ein Ausfall die gesamte Mission; ein Schwarm aus vielen Robotern kann die Mission mit den verbleibenden Einheiten fortsetzen, selbst wenn einige ausfallen.

• Gleichzeitiges Arbeiten an mehreren Orten: Manche Missionen erfordern zwangsläufig die gleichzeitige Anwesenheit an mehreren Orten – beispielsweise das Formen von Figuren bei einer Drohnenshow oder der gleichzeitige Transport von Waren zu verschiedenen Orten in einem Lager.

• Kosten pro Einheit: Anstatt einen Hochleistungsroboter zu bauen, kann der Einsatz vieler einfacher, kostengünstiger Roboter hinsichtlich der Gesamtkosten und der Einsatzflexibilität vorteilhaft sein.

Um diese Vorteile tatsächlich zu nutzen, reicht es nicht aus, einfach die Anzahl der Roboter zu erhöhen. Es bedarf Steuerungsgesetze, die Kollisionen verhindern und gleichzeitig das kollektive Verhalten zielorientiert gestalten. Genau das ist die Aufgabe der Schwarmsteuerung.

3. Welche Eingaben werden benötigt?

Die Informationen, die jeder Roboter für die Schwarmsteuerung nutzen kann, lassen sich je nach Kommunikations- und Sensorkonfiguration wie folgt klassifizieren:

• Eigenzustand: Position, Geschwindigkeit und Orientierung des Roboters. Diese Daten werden üblicherweise per GPS, Odometrie oder einem Selbstlokalisierungsverfahren wie VIO/LIO erfasst.

• Relative Informationen über benachbarte Roboter: Die relative Position und Geschwindigkeit von Robotern in der Nähe, direkt erfasst mit Sensoren wie Kameras, LiDAR oder UWB-Entfernungsmessung (Ultrabreitband).

• Kommunikationsnachrichten: Positions-, Geschwindigkeits- und Zielinformationen (Zielrichtung), die von anderen Robotern drahtlos gesendet werden. - (In zentralisierten Systemen) Befehle von einem zentralen Knotenpunkt: Zielpositionen oder Rollenzuweisungen, die von einem zentralen Computer (z. B. einer Bodenstation) an die einzelnen Roboter verteilt werden. Dieser Computer überwacht den Zustand des gesamten Schwarms.

Wichtig ist, dass viele praktische Schwarmsteuerungsalgorithmen nicht den „vollständigen Zustand des gesamten Schwarms“ als Eingabe benötigen. Algorithmen, die lediglich relative Informationen von wenigen Robotern in der Nähe nutzen, sind der gängigste Ansatz. Genau dadurch wird verhindert, dass die Informationsmenge, die jeder Roboter verarbeiten muss, mit zunehmender Anzahl der Roboter explosionsartig ansteigt.

4. Was ist das Ziel? Was sind die Ergebnisse?

Die Schwarmsteuerung gibt letztendlich für jeden Roboter die Anweisung, wie er sich im nächsten Moment bewegen soll (ein Geschwindigkeitsbefehl oder eine Zielposition). Der „wünschenswerte Zustand für den gesamten Schwarm“, den diese Anweisung erreichen soll, lässt sich je nach Ziel in folgende Kategorien unterteilen:

• Konsens: Angleichung einer Zustandsgröße (Position, Geschwindigkeit oder Schätzung) aller Roboter an einen gemeinsamen Wert.

• Formation: Jeder Roboter hält kontinuierlich eine festgelegte relative Position zu den anderen (Dreieck, Linie, Kreis usw.).

• Schwarmverhalten: Ohne vorgegebene Zielformation bewegt sich der Schwarm als zusammenhängende Masse, vermeidet Kollisionen und passt seine Geschwindigkeit an die der Nachbarn an.

• Aufgabenverteilung: Entscheidung, welche der verschiedenen Aufgaben – Suche, Transport – jeder einzelne Roboter übernehmen soll.

Allen diesen Prozessen ist gemeinsam, dass „die Summe der lokalen Ausgaben jedes Roboters eine gewünschte kollektive Eigenschaft für das Ganze erfüllt“. Die grundlegende Architektur im nächsten Abschnitt veranschaulicht diesen Akkumulationsprozess.

5. Grundlegende Architektur

Die Verarbeitungsschleife in jedem Roboter durchläuft unabhängig vom verwendeten Schwarmsteuerungsalgorithmus im Wesentlichen dieselben vier Phasen.

Abbildung 1 – Jeder einzelne Roboter durchläuft eine hochfrequente Schleife: Er sammelt Informationen über seine Nachbarn, wendet lokale Regeln an, gibt einen Geschwindigkeitsbefehl aus und speist die resultierende Bewegung in die Erfassung des nächsten Zyklus ein.

Diese Schleife, die gleichzeitig auf vielen Robotern läuft, ermöglicht es dem Schwarm als Ganzes, ein geordnetes Verhalten zu zeigen, obwohl kein einzelner Roboter jemals den gesamten Ablaufplan kennt. Die Designentscheidung, wer die Informationen über das Ganze besitzt, führt zu dem im Folgenden beschriebenen architektonischen Unterschied.

Abbildung 2 – Eine zentralisierte Architektur ist eine Sternstruktur, in der ein zentraler Knoten den Zustand jedes Roboters kennt und Befehle aussendet. Eine dezentrale Architektur ist eine Netzstruktur, in der Roboter Informationen nur mit ihren Nachbarn austauschen, sodass ein Ausfall des zentralen Knotens nicht das gesamte System lahmlegt.

6. Repräsentative Algorithmen

Boids – Erzeugung von Schwarmverhalten durch lokale Regeln

Boids ist ein Modell, das Craig W. Reynolds 1987 in seiner Arbeit „Flocks, Herds, and Schools: A Distributed Behavioral Model“ vorschlug, um das Schwarmverhalten von Vögeln und Fischen in Computergrafiken nachzubilden. Jedes Individuum (Boid) achtet nur auf seine Nachbarn und bewegt sich in eine Richtung, die durch Gewichtung und Addition dreier einfacher Regeln bestimmt wird.

• Trennung: Abstand zu zu nahen Nachbarn halten.

• Ausrichtung: Die eigene Geschwindigkeit an die durchschnittliche Richtung der Nachbarn anpassen.

• Zusammenhalt: Sich auf die durchschnittliche Position der Nachbarn zubewegen.

Bei jeder dieser Regeln kennt ein Individuum lediglich die relative Position und Geschwindigkeit einiger weniger Nachbarn – niemand verfolgt explizit die Form oder den Mittelpunkt des gesamten Schwarms. Und doch entsteht allein aus der Überlagerung dieser drei Regeln die natürliche Schwarmbewegung: Die Gruppe vermeidet Kollisionen und bewegt sich als eine einzige Masse. Dieses Phänomen – „komplexe globale Muster, die aus der Überlagerung einfacher lokaler Regeln entstehen“ – ist die grundlegendste Idee im gesamten Bereich der Schwarmsteuerung.

Potentialfelder – Bewegung durch Anziehung und Abstoßung

Oussama Khatibs Methode der künstlichen Potentialfelder, die er 1986 in seiner Arbeit „Real-Time Obstacle Avoidance for Manipulators and Mobile Robots“ vorstellte, war ursprünglich für die Hindernisvermeidung einzelner Roboter konzipiert. Durch die Kombination eines anziehenden Potentials zum Ziel hin mit einem abstoßenden Potential benachbarter Roboter lässt sie sich jedoch auch auf die Schwarmsteuerung anwenden.

Eine Bewegung in Richtung des abnehmenden Gradienten des anziehenden Potentials U_{\text{att}}, das sich mit Annäherung an das Ziel verringert, und des abstoßenden Potentials U_{\text{rep}}, das sich bei Annäherung an einen Nachbarn stark erhöht, erzeugt eine Bewegung zum Ziel hin, die Kollisionen mit anderen Robotern vermeidet. Die Trennungsregel der Boids basiert im Wesentlichen auf demselben Prinzip wie dieses abstoßende Potential.

Das Vicsek-Modell und Konsensalgorithmen – Die Mathematik der Konsensbildung

Während Boids aus einer ingenieurtechnischen und visuellen Motivation heraus entstanden – „die Bewegung von Tieren nachzubilden“ –, beschritt die Physik einen anderen Weg und untersuchte Schwarmbewegungen mithilfe eines vereinfachten mathematischen Modells. Das Vicsek-Modell, 1995 von Tamás Vicsek und Kollegen in den Physical Review Letters veröffentlicht, ist ein einfaches Modell – fast so, als würde man nur die Ausrichtungsregel von Boids extrahieren –, in dem sich jedes Partikel mit konstanter Geschwindigkeit bewegt und dabei der durchschnittlichen Richtung seiner Nachbarpartikel zuzüglich Rauschen folgt. Es zeigte, dass der Schwarm, abhängig von der Stärke dieses Rauschens, einen Phasenübergang zwischen einer geordneten Phase, in der sich die gesamte Gruppe kohärent bewegt, und einer ungeordneten Phase, in der die Bewegung verstreut ist, durchläuft.

Der Rahmen, der diese Idee des Vicsek-Modells in regelungstechnischen Begriffen rigoros formalisiert, ist der Konsensalgorithmus. Im Rahmen des von Reza Olfati-Saber und Richard M. Murray in ihrer 2004 in den IEEE Transactions on Automatic Control veröffentlichten Artikels entwickelten Modells wird der Zustand x_i jedes Roboters (der beliebige Werte wie Position, Orientierung oder eine Schätzung annehmen kann) kontinuierlich in die Richtung aktualisiert, die die Differenz zu seinen Nachbarn verringert.

Die Summe dieser Werte für alle Roboter ergibt die Form \dot{\mathbf{x}} = -L\mathbf{x}. L ist eine Matrix, die als Graph-Laplace-Matrix bezeichnet wird und die Struktur des Kommunikationsnetzwerks repräsentiert – wer mit wem kommunizieren kann. Solange der Kommunikationsgraph zusammenhängend ist (es existiert ein Pfad, direkt oder über andere, zwischen jedem Roboterpaar), führt diese einfache Aktualisierungsregel nachweislich dazu, dass der Zustand jedes Roboters auf einen einzigen gemeinsamen Wert konvergiert. Dies ist der mathematische Kern von Konsensalgorithmen, die auf eine Vielzahl von Problemen jenseits der Schwarmausrichtung anwendbar sind – beispielsweise Zeitsynchronisation, verteilte Mittelwertbildung von Schätzungen und vieles mehr.

Formationssteuerung – Leader-Follower, Virtuelle Struktur und Verhaltensbasiert

Wenn Sie eine bestimmte geometrische Formation (Dreieck, Reihe usw.) aufrechterhalten möchten, verwenden Sie Formationssteuerung, ein konkreteres Verfahren. Es gibt drei repräsentative Designansätze.

• Leader-Follower: Ein Roboter (oder eine Teilmenge) fungiert als Leader, die anderen folgen ihm und halten ihre relative Position dazu ein. Das von Jaydev P. Desai, James P. Ostrowski und Vijay Kumar auf der ICRA 1998 und anschließend in den IEEE Transactions on Robotics and Automation 2001 vorgestellte Verfahren ist ein typisches Beispiel. Es nutzt die Graphentheorie, um explizit festzulegen, welcher Roboter welchem anderen folgt. Es ist intuitiv und einfach zu implementieren, hat aber den Nachteil, dass die gesamte Formation zusammenbrechen kann, wenn der Leader ausfällt.

• Virtuelle Struktur: Ein Ansatz, den M. Anthony Lewis und Kar-Han Tan 1997 in ihrer Arbeit „High Precision Formation Control of Mobile Robots Using Virtual Structures“ vorschlugen. Dabei wird die gesamte Formation als eine virtuelle, starre Struktur behandelt, auf der jeder Roboter eine feste Position einnimmt. Dies gewährleistet eine hohe Genauigkeit der gesamten Formation, erfordert jedoch die Berechnung der Zieltrajektorie, was ein vollständig dezentrales Design erschwert.

Verhaltensbasiert: Ein Ansatz, den Tucker Balch und Ronald C. Arkin 1998 in den IEEE Transactions on Robotics and Automation vorstellten. Hierbei werden mehrere reaktive Verhaltensweisen – „Formation beibehalten“, „Ziel ansteuern“, „Hindernisse vermeiden“ – parallel berechnet und mit Gewichtungen kombiniert, um die tatsächliche Bewegung zu erzeugen. Ähnlich wie Boids verleiht dieser Ansatz jedem Roboter hohe Autonomie und Robustheit, die geometrische Genauigkeit der Formation ist jedoch tendenziell geringer als bei den anderen beiden Ansätzen.

7. Unterschiede der Algorithmen

Generell gilt: Je höher die Priorität auf geometrischer Genauigkeit der Formation (virtuelle Struktur) liegt, desto mehr Informationsaustausch und Rechenaufwand sind erforderlich; je höher die Priorität auf Dezentralisierung und Robustheit (Boids, verhaltensbasiert) liegt, desto mehr wird die Genauigkeit der Formation selbst beeinträchtigt. Konsensalgorithmen stellen einen theoretisch praktikablen Mittelweg zwischen diesen beiden Extremen dar. Sie erreichen sowohl eine strenge mathematische Konvergenzgarantie als auch eine Dezentralisierung, die lediglich die Kommunikation mit benachbarten Robotern erfordert.

8. Herausforderungen / Schwierige Umgebungen

Viele der Schwierigkeiten, mit denen die Schwarmsteuerung bei Implementierung und Betrieb konfrontiert ist, sind kollektivspezifische Probleme, die bei der Steuerung einzelner Roboter nicht auftreten.

• Kommunikationslatenz und -unterbrechungen: Die meisten Konvergenzgarantien für Konsensalgorithmen setzen einen zusammenhängenden Kommunikationsgraphen voraus. In realen Umgebungen kann die Kommunikation durch Funkreichweite oder Hindernisse unterbrochen oder verzögert werden. Sobald diese Annahme nicht mehr zutrifft, entstehen Probleme – der Konsens konvergiert nicht oder gegen einen falschen Wert.

• Skalierbarkeit: In einer zentralisierten Architektur steigen die Rechenlast und die Anforderungen an die Kommunikationsbandbreite des zentralen Knotens mit zunehmender Anzahl an Robotern stark an. Ab einer bestimmten Anzahl kann die Echtzeitfähigkeit nicht mehr aufrechterhalten werden. Selbst in dezentralen Architekturen steigt die Last für Sensorik und Kommunikation in dichten Umgebungen mit vielen Nachbarn.

• Lokale Minima und Blockaden: Potenzialfeldmethoden können dazu führen, dass ein Roboter in einem „lokalen Minimum“ feststeckt, in dem sich mehrere abstoßende und anziehende Kräfte aufheben und er das Ziel nicht erreichen kann (ein typisches Beispiel ist eine Blockadesituation, in der mehrere Roboter gleichzeitig versuchen, in einen engen Durchgang einzufahren).

• Unzureichende Fehlertoleranz: Dezentrale Designs gelten theoretisch als robust gegenüber Teilausfällen, aber in der Praxis können Designs mit einer gewissen inhärenten Asymmetrie – wie Leader-Follower-Systeme – anfälligere Fehlermodi aufweisen als erwartet.

• Mixed heterogene Roboter und Sensoren: In realen Anwendungen, in denen Robotermodelle und Onboard-Sensoren nicht einheitlich sind, unterscheiden sich die Genauigkeit und Häufigkeit der von jedem Roboter erfassten Informationen, und Algorithmen, die auf einem einzigen idealisierten Modell basieren, funktionieren in der Praxis oft nicht gut.

9. Praktische Entscheidungen

Die Wahl eines Schwarmsteuerungsalgorithmus hängt maßgeblich davon ab, ob die Anwendung Wert auf „Formationsgenauigkeit“ oder „Robustheit/Dezentralisierung“ legt.

• Drohnenshows: Vorgegebene Flugbahnen und Formationen müssen mit extrem hoher Präzision dargestellt werden. Viele Produktionssysteme setzen daher auf ein Design mit nahezu zentralisierter/virtueller Struktur, bei dem vorab berechnete Flugbahnen auf die einzelnen Drohnen verteilt werden (Genauigkeit und Reproduzierbarkeit haben Vorrang vor autonomen Entscheidungen im Flug).

• Roboterflotten in Lager und Logistik: Viele Transportroboter müssen dynamisch wechselnde Aufgaben aufteilen (z. B. welches Regal zu welchem Zielort). Ein hybrides zentralisiertes/dezentralisiertes Design ist üblich: Ein zentrales Managementsystem übernimmt die Aufgabenverteilung, während die Pfadgenerierung und Kollisionsvermeidung der einzelnen Roboter dezentral erfolgen. Die Grundlagen der Pfadplanung finden Sie im Pfadplanungs-Leitfaden.

Katastrophensuche, landwirtschaftliche Überwachung und andere großflächige Abdeckung: Da die Kommunikation in diesen Umgebungen oft instabil ist, werden dezentrale Ansätze mit geringer Abhängigkeit von einer zentralen Steuerung bevorzugt (z. B. Boids-ähnliches Schwarmverhalten oder konsensbasierte Abdeckung). Die Verhaltensentscheidungen einzelner Roboter werden häufig mit einem Verhaltensplanungs-Framework kombiniert.

Kleinskalige Forschungs- und Bildungs-Schwarmroboter: Da es sich hierbei um experimentelle Aufbauten mit wenigen Robotern und stabiler Kommunikation handelt, werden häufig virtuelle Strukturen oder Leader-Follower-Systeme eingesetzt, die auf Formationsgenauigkeit abzielen.

Unabhängig von der Anwendung bilden die drei Fragen „Wie viele Roboter werden eingesetzt?“, „Wie stabil ist die Kommunikationsumgebung?“ und „Welche Anforderung ist ausfallsicherer: Formationsgenauigkeit oder Robustheit?“ den Ausgangspunkt für die Wahl einer Schwarmsteuerungsarchitektur.

10. Zusammenfassung (Dreizeilige Übersicht)

• Schwarmsteuerung ist ein Rahmenwerk, das geordnetes Verhalten für die gesamte Gruppe durch lokale Regeln erzeugt, die nur die begrenzten Informationen jedes Roboters über seine Nachbarn nutzen.

• Boids und Potentialfeldmethoden realisieren dezentrale Schwarmbewegungen, während Konsensalgorithmen eine Konsensbildung mit einer mathematisch über den Graph-Laplace-Operator garantierten Konvergenz realisieren.

• Leader-Follower-, virtuelle Struktur- und verhaltensbasierte Formationssteuerung nehmen unterschiedliche Positionen im Kompromiss zwischen Formationsgenauigkeit und Robustheit/Dezentralisierung ein und müssen je nach Anwendung ausgewählt werden.

Referenzen

• Craig Reynolds, "Boids (Flocks, Herds, and Schools: a Distributed Behavioral Model)"
• Vicsek et al., "Novel Type of Phase Transition in a System of Self-Driven Particles"
• Crazyswarm2 (Schwarmsteuerungssoftware für mehrere Crazyflie-Drohnen)