Control of Cellular Automata by Moving Agents with Reinforcement Learning

Diese explorative Studie zeigt, dass kognitive Agenten mittels Reinforcement Learning in der Lage sind, passive zelluläre Automaten durch lokale Sensierung global zu steuern, während diese Aufgabe bei aktiver Umgebungsdynamik unmöglich wird.

Das Wesentliche

Das große Ganze: Ein Team von Robotern gegen ein chaotisches Universum

Stell dir vor, du hast eine riesige, flache Wiese, die in ein Schachbrett aus kleinen Feldern unterteilt ist. Jedes Feld kann entweder leer (0) oder voll (1) sein. Diese Wiese ist dein „Universum".

Jetzt kommen kleine Roboter (die „Agenten") auf die Wiese. Jeder Roboter hat zwei Fähigkeiten:

1. Sehen: Er schaut sich ein kleines 3x3-Fenster um sich herum an (seine „Sensoren"). Er zählt, wie viele Felder in diesem Fenster voll sind.
2. Handeln: Er kann genau das Feld in seiner Mitte ändern (leer machen oder voll machen).

Das Ziel: Die Roboter wollen, dass auf der ganzen Wiese ein bestimmter Anteil der Felder „voll" ist. Zum Beispiel wollen sie, dass genau 50 % der Wiese voll ist.

Das Problem ist: Die Wiese ist nicht tot. Sie hat ihr eigenes Leben. Jedes Feld auf der Wiese ändert sich ständig von selbst, basierend auf den Nachbarn. Das ist wie ein Wetter, das sich ständig ändert, oder wie eine Menge Menschen, die sich unterhalten und ihre Meinung ändern, ohne dass du etwas sagst.

Die Roboter müssen lernen: „Wenn ich sehe, dass hier zu wenig voll ist, sollte ich dann ein Feld füllen? Oder ist es besser, es leer zu lassen?" Sie lernen durch Versuch und Irrtum (das nennt man „Reinforcement Learning" oder verstärkendes Lernen).

---

Szenario 1: Die ruhige Wiese (Der „Passive" Fall)

Stell dir vor, die Wiese ist wie ein Klebeblock. Wenn ein Roboter ein Feld ändert, bleibt es so, bis der Roboter es wieder ändert. Die Wiese bewegt sich nicht von selbst.

• Was passiert? Die Roboter lernen sehr schnell.
• Die Analogie: Stell dir vor, du versuchst, einen Haufen Sand so zu formen, dass er genau 10 cm hoch ist. Wenn der Wind (die Wiese) nicht weht, kannst du einfach Sand hinzufügen oder wegnehmen, bis es passt.
• Das Ergebnis: Die Roboter finden eine perfekte Regel. Wenn sie sehen, dass es zu wenig Sand ist, füllen sie nach. Wenn zu viel, nehmen sie weg. Sie erreichen ihr Ziel fast immer.

Szenario 2: Die wilde Wiese (Der „Aktive" Fall)

Jetzt wird es spannend. Stell dir vor, die Wiese ist wie ein lebendiger Organismus oder ein stürmischer Ozean. Die Felder ändern sich von selbst nach komplexen Regeln (wie beim berühmten „Game of Life").

• Was passiert? Die Roboter scheitern oft.
• Die Analogie: Stell dir vor, du versuchst, einen Sandhaufen zu formen, während ein Staubsauger daneben steht, der den Sand ständig wegsaugt, und ein Gießkanne, die ihn wieder aufschüttet.
  • Wenn du versuchst, den Haufen hoch zu machen, saugt der Staubsauger (die Naturgesetze der Wiese) ihn sofort wieder ab.
  • Wenn du versuchst, ihn niedrig zu halten, schüttet die Gießkanne ihn wieder auf.
• Das Problem: Die Roboter können nicht lernen, was sie tun sollen, weil sie keine stabilen Beispiele haben. Jedes Mal, wenn sie etwas ändern, wird es sofort von der Wiese „korrigiert" oder zunichte gemacht.

Die wichtigsten Erkenntnisse der Forscher

1. Wenn die Welt ruhig ist: Die Roboter sind Meister. Sie lernen schnell eine Regel, die funktioniert, und erreichen ihr Ziel.
2. Wenn die Welt aktiv ist: Die Roboter sind machtlos. Sie können das Ziel nur sehr schlecht erreichen.
   • Manchmal lernen sie, kleine Änderungen zu machen, aber die „natürliche" Tendenz der Wiese (z. B. dass alles leer wird oder alles voll wird) ist stärker als ihre Eingriffe.
   • Es gibt sogar Situationen, in denen die Roboter gar nicht erst lernen können, was sie tun sollen, weil die Wiese bestimmte Zustände einfach nicht zulässt (wie ein Roboter, der versucht, Wasser in ein Loch zu füllen, das sofort wieder ausläuft).

Ein konkretes Beispiel aus dem Papier: Das „Game of Life"

Die Forscher haben getestet, was passiert, wenn die Wiese die Regeln des berühmten Spiels „Game of Life" befolgt.

• Das Ziel: Die Roboter wollten verhindern, dass alles ausstirbt (dass die Wiese leer wird).
• Das Ergebnis: Ein einzelner Roboter konnte das nicht. Sobald er versuchte, Leben zu schaffen, starb es sofort wieder. Mit vielen Robotern zusammen konnten sie das Leben etwas länger am Leben erhalten, aber sie konnten es nicht kontrollieren. Die Wiese war einfach zu komplex und zu chaotisch für ihre kleinen Eingriffe.

Fazit in einem Satz

Die Forscher haben herausgefunden: Man kann eine Umgebung leicht steuern, wenn sie ruhig ist und auf deine Befehle wartet. Aber wenn die Umgebung ein eigenes, chaotisches Leben führt, sind selbst lernfähige Roboter oft machtlos und können ihre Ziele nicht erreichen.

Es ist wie der Versuch, einen Fluss mit einem Löffel umzuleiten: Wenn das Wasser stillsteht, klappt es. Wenn es reißt, vergeblich.

Technische Zusammenfassung

Titel: Steuerung von Zellulären Automaten durch bewegliche Agenten mit Reinforcement Learning

1. Problemstellung

Das Paper untersucht das Problem der Steuerung eines dynamischen Systems durch kognitive Agenten. Das Ziel ist es, dass Agenten lernen, ihre Umgebung (modelliert als zweidimensionaler boolescher Zellulärer Automat, CA) basierend auf lokaler Sensorik so zu manipulieren, dass ein globales Ziel erreicht wird.

• Ziel: Die asymptotische Dichte der "1"-Zellen im System soll einem vorgegebenen Zielwert $\bar{\rho}$ angenähert werden.
• Herausforderung: Die Umgebung entwickelt sich parallel zur Lernphase der Agenten. Die Schwierigkeit der Aufgabe hängt stark davon ab, ob die Umgebung passiv (träge) oder aktiv (dynamisch) ist.
  • Passiv: Die Umgebung behält Änderungen bei (Identitätsregel).
  • Aktiv: Die Umgebung folgt komplexen Evolutionsregeln (z. B. "Game of Life"), die Änderungen der Agenten oft rückgängig machen oder überlagern.

2. Methodik

Das Modell:

• Umgebung: Ein zweidimensionaler boolescher Zellulärer Automat ($N \times N$) mit Moore-Nachbarschaft (9 Zellen). Die Dynamik ist "outer totalistic" (der Zustand der Zelle selbst und die Summe der Nachbarn bestimmen den nächsten Zustand).
• Agenten: Werden als probabilistische, totalistische Zelluläre Automaten modelliert.
  • Sensorik: Erfasst die Anzahl der "1"-Zellen ($m$) in der Moore-Nachbarschaft (Größe $M=9$).
  • Aktorik: Kann den Zustand der zentralen Zelle (Actuator) ändern.
  • Strategie: Ein Wahrscheinlichkeitsvektor $P(m)$, der angibt, mit welcher Wahrscheinlichkeit die zentrale Zelle auf "1" gesetzt wird, wenn die Messung $m$ vorliegt.
• Lernprozess (Reinforcement Learning):
  • Agenten nutzen eine Belohnungsfunktion, um ihre Übergangswahrscheinlichkeiten $P(m)$ anzupassen.
  • Mechanismus: Ein Agent misst $m$, kippt die zentrale Zelle, misst $m'$ im nächsten Schritt und vergleicht dies mit dem Ziel $\bar{m}$.
  • Update-Regel: Wenn die Änderung $m \to m'$ das Ziel näher bringt, wird die Wahrscheinlichkeit für diese Aktion verstärkt ($\Delta P > 0$); wenn sie das Ziel entfernt, wird sie verringert. Die Wahrscheinlichkeiten konvergieren nach vielen Epochen meist zu deterministischen Werten (0 oder 1).

Analytischer Rahmen:

• Das Paper analysiert vorab das Verhalten deterministischer totalistischer Regeln (Majority- und Minority-Regeln) unter synchroner und asynchroner Aktualisierung, um die theoretischen Grenzen der asymptotischen Dichten zu verstehen.

3. Wichtige Ergebnisse

A. Passive Umgebung (Identitätsregel):

• Wenn die Umgebung keine eigene Dynamik hat (Änderungen bleiben erhalten), lernen die Agenten schnell eine optimale Strategie.
• Die gelernte Strategie entspricht einer deterministischen Minority-Regel (z. B. $MLE_s$), die die lokale Dichte in Richtung des Ziels $\bar{m}$ steuert.
• Das System erreicht eine asymptotische Dichte, die unabhängig vom Anfangszustand ist und das Ziel gut approximiert.
• Mehrere Agenten verbessern die Lerngeschwindigkeit, da sie mehr Variationen der Umgebungsdaten abdecken.

B. Komplexe/Aktive Umgebungen:

• Frustrierte Identitätsregeln: Wenn die Umgebung bestimmte lokale Konfigurationen "verboten" macht (z. B. eine Zelle mit $m=0$ Nachbarn wird immer invertiert), können Agenten für diese Zustände keine Strategie lernen. Die Wahrscheinlichkeiten bleiben im Zufallsbereich (0.5), da keine erfolgreiche Anpassung möglich ist.
• Game of Life ($H3H23p$): Dies stellt die größte Herausforderung dar.
  • Ein einzelner Agent führt das System fast immer zum Aussterben (Dichte $\to 0$), da die empfindlichen Strukturen des "Lebens" durch Störungen zerstört werden.
  • Auch mit mehreren Agenten können Ziele, die im "natürlichen" Bereich des Spiels liegen (z. B. $\bar{\rho} \approx 0.01$), nicht erreicht werden.
  • Agenten scheitern daran, für lokale Messungen $m=0$ eine sinnvolle Aktion zu lernen, da jede Aktion dort zu $C'=0$ führt.
  • Selbst das Setzen unrealistischer Ziele führt nur zu minimalen Abweichungen von der natürlichen asymptotischen Dichte der Umgebung.

4. Hauptbeiträge

1. Formalisierung des Problems: Definition eines Modells, in dem mobile Agenten durch Reinforcement Learning versuchen, die globale Dichte eines CA-Systems zu steuern.
2. Unterscheidung von Umgebungsarten: Klare Demonstration, dass die Steuerbarkeit stark von der "Passivität" der Umgebung abhängt.
   • Passive Umgebungen sind leicht zu steuern.
   • Aktive Umgebungen mit komplexer Dynamik stellen oft unüberwindbare Hindernisse dar, da die Agenten keine konsistenten Ursache-Wirkungs-Zusammenhänge lernen können.
3. Analyse von Lernlimitierungen: Identifikation von "verbotenen" Zuständen in der Umgebung, bei denen Agenten nicht lernen können, da keine Aktion zu einer Verbesserung führt (z. B. bei $m=0$ im Game of Life).
4. Verknüpfung von asynchroner Aktualisierung und Agentenverhalten: Zeigen, dass das Verhalten der Agenten im passiven Fall äquivalent zu einer asynchronen Aktualisierung einer Minority-Regel ist.

5. Bedeutung und Fazit

Das Paper liefert wichtige Erkenntnisse für das Feld der schwarmbasierten Steuerung und Reinforcement Learning in dynamischen Umgebungen.

• Es zeigt die fundamentalen Grenzen von Lernagenten auf: Wenn die Umgebung zu stark und unvorhersehbar auf die Aktionen der Agenten reagiert (hohe "Dynamik"), ist eine globale Steuerung unmöglich.
• Die Ergebnisse deuten darauf hin, dass für komplexe Umgebungen entweder die Agenten selbst die Umgebung verändern müssen (z. B. durch Koordination mehrerer Agenten, um die Dynamik zu stabilisieren) oder dass das Lernziel an die natürlichen Attraktoren der Umgebung angepasst werden muss.
• Die Studie dient als Grundlage für zukünftige Forschungen zur Steuerung von komplexen Systemen, wo die Interaktion zwischen Lernalgorithmus und physikalischer Welt entscheidend ist.