Control of Cellular Automata by Moving Agents with Reinforcement Learning

This exploratory paper investigates how reinforcement learning enables moving agents to modify a two-dimensional cellular automaton environment to achieve global goals, demonstrating that while agents can approximate these objectives in passive systems, the task becomes impossible when the environment exhibits active dynamics.

The Gist

Imagine a giant, digital checkerboard where every square is either black (0) or white (1). This board isn't static; it's alive. Every second, the squares change color based on their neighbors, following a strict set of rules. This is a Cellular Automaton, a simple computer model that can create complex patterns, like the famous "Game of Life."

Now, imagine a team of tiny, invisible robots (the Agents) walking across this board. Their job is to change the board's behavior to reach a specific goal: they want the board to be, say, 60% white and 40% black.

Here is the twist: The robots don't know the rules of the board. They have to learn by trial and error, using a method called Reinforcement Learning.

The Setup: The Robot and the Board

• The Robot's Eyes (Sensing): Each robot can only see a small 3x3 square around it (9 cells total). It counts how many are white.
• The Robot's Hand (Actuating): The robot can only touch the very center cell of that 3x3 square. It can flip it from black to white or vice versa.
• The Goal: The robot has a target number. If it sees too few white cells, it tries to make one. If it sees too many, it tries to make one black.
• The Learning: The robot tries a move. If the board gets closer to the goal, the robot thinks, "Good job, I'll do that again!" If it gets worse, it thinks, "Bad move, I'll stop doing that." Over time, the robot builds a perfect strategy.

The Two Worlds: Passive vs. Active

The paper tests these robots in two very different types of environments.

1. The "Passive" World (The Sticky Floor)

Imagine the board is like a floor covered in wet paint. When a robot steps on a square and changes its color, the paint stays that way. The board doesn't fight back; it just waits for the next robot to step on it.

• The Result: The robots are super successful. Because the board doesn't change on its own, the robots quickly learn the perfect strategy. They figure out exactly when to flip a switch to keep the board at the perfect 60% white. It's like learning to ride a bike on a flat, calm road.

2. The "Active" World (The Tidal Wave)

Now, imagine the board is like a turbulent ocean. Even if a robot changes a square to white, the "rules of the ocean" might immediately turn it back to black because of what its neighbors are doing. The environment is fighting back.

• The Result: The robots struggle and often fail.
  • The "Missing Puzzle Piece" Problem: Sometimes, the ocean rules make certain patterns impossible. For example, a rule might say, "If a cell has 0 white neighbors, it must become white." If a robot tries to make a cell black in that situation, the ocean immediately flips it back. The robot never gets a chance to learn that "black" is a bad idea because it never sees the result of its action. It's like trying to learn to swim in a whirlpool; you can't test your moves because the water keeps spinning you around.
  • The "Game of Life" Example: The paper tests a famous rule called the "Game of Life." In this world, patterns are very fragile. If a robot tries to keep a specific pattern alive, the slightest mistake causes everything to die out (turn all black). The robots can't learn how to maintain a specific density because the environment is too chaotic and unforgiving.

The Big Takeaway

The paper is essentially a story about control.

• In a quiet, passive world, a smart agent can learn to steer the system exactly where it wants to go.
• In a noisy, active world, the agent is often powerless. The environment's own internal rules are so strong that the agent's attempts to control it are washed away or blocked.

The Metaphor:
Think of the agents as gardeners trying to grow a specific type of flower (the target density).

• In the Passive World, the soil is obedient. The gardeners plant seeds, water them, and the flowers grow exactly as planned.
• In the Active World, the soil is a wild, stormy jungle. The gardeners try to plant, but the wind (the environment's rules) blows the seeds away or turns them into weeds. No matter how hard the gardeners learn or try, they can't force the jungle to look like a neat garden.

Conclusion

The authors conclude that while AI agents are great at controlling simple, static systems, they hit a wall when the system they are trying to control has its own complex, active life. You can't easily teach a robot to control a hurricane, no matter how smart the robot is.

Technical Summary

1. Problem Statement

The paper investigates the control problem of cognitive agents operating within a dynamic environment modeled as a two-dimensional Boolean Cellular Automaton (CA).

• The Goal: Agents aim to modify their local environment to achieve a specific global target: a desired asymptotic density of "1" cells (active states) in the system.
• The Challenge: The environment evolves according to its own intrinsic dynamics (parallel updating). Agents must learn a strategy to influence this evolution through local sensing and actuation.
• The Core Question: Can agents learn to steer a complex, active system toward a specific global state, or does the environment's intrinsic dynamics render this task impossible?

2. Methodology

A. System Model

• The Environment: Modeled as a 2D parallel, outer-totalistic Boolean CA. The state of a cell depends on its own state and the sum of its neighbors (Moore neighborhood, $M=9$).
  • Rules Tested: The study examines various rules, including the Identity rule (passive), Majority/Minority rules (active), and Conway's Game of Life.
• The Agents: Modeled as probabilistic, totalistic cellular automata.
  • Sensing: Agents observe the number of "1" cells ($m$) in their Moore neighborhood (9 cells).
  • Actuation: Agents can flip the state of the central cell (the actuator).
  • Strategy: An agent maintains a probability vector $P(m)$, representing the probability of flipping the central cell to "1" given a local measurement $m$.

B. Learning Mechanism

Agents utilize Reinforcement Learning (RL) to update their strategy $P(m)$:

1. Measurement: The agent measures the current local density $m$.
2. Action: The agent flips the central cell (changing the state to $s'$) and observes the new local density $m'$ in the next time step.
3. Reward/Update:
   • If the flip brings $m'$ closer to the target $\bar{m}$ than $m$ was, the probability of performing that flip is reinforced ($\Delta P > 0$).
   • If the flip moves the system further from the target, the probability is decreased ($\Delta P < 0$).
   • If the flip has no effect or crosses the target in a way that doesn't improve the immediate step, no change occurs.
4. Convergence: Over many epochs ($T$), the probabilities $P(m)$ tend to converge to deterministic values (0 or 1), effectively learning a specific CA rule.

C. Experimental Setup

• Environments:
  • Passive: Identity rule (changes made by agents are preserved; the environment does not evolve on its own).
  • Active: Frustrated Identity, Double Frustrated Identity, and Game of Life (where the environment evolves independently of agent actions).
• Metrics: The primary metric is the asymptotic density ($\rho_\infty$) of the system compared to the target density ($\bar{\rho}$).

3. Key Contributions

1. Distinction Between Passive and Active Control: The paper establishes a fundamental theoretical boundary: agents can successfully learn to control a system if the environment is passive (identity rule), but control becomes significantly hindered or impossible when the environment follows active, complex dynamics.
2. Characterization of Asynchronous vs. Synchronous Dynamics: The authors analyze how the learning outcome depends on the updating scheme. They show that fully asynchronous (serial) updating of minority rules leads to stable, initial-condition-independent densities, whereas synchronous updating often results in patterns dependent on initial conditions or chaotic behavior.
3. The "Natural Range" Limitation: The study identifies that active environments possess a "natural range" of achievable densities. Agents cannot force the system into states that are dynamically forbidden by the environment's rules (e.g., specific local configurations that the environment immediately corrects).

4. Key Results

A. Passive Environment (Identity Rule)

• Success: Agents successfully learn to reach the target density.
• Mechanism: The learned strategy converges to a minority rule (e.g., $MLE_s$). If the local density is below the target, the agent flips to "1"; if above, it flips to "0".
• Outcome: The system reaches an asymptotic density that is independent of the initial state and closely approximates the target $\bar{m}$.

B. Active Environments (Frustrated Rules & Game of Life)

• Partial Success / Failure:
  • Frustrated Identity: Agents can learn strategies for "allowed" local configurations but fail to learn strategies for "forbidden" configurations (e.g., $m=0$ or $m=9$). Since the environment immediately flips these states back, the agent never receives a reward signal to update $P(m)$ for these specific inputs.
  • Game of Life:
    • Low Targets: Agents fail to maintain low densities because the environment naturally tends toward extinction or complex "animals" that are sensitive to perturbations. A single agent drives the system to extinction; multiple agents can keep it alive but cannot precisely control the density.
    • High/Unreachable Targets: Setting an unreachable target (e.g., $\bar{m}=9$) forces all probabilities to 1, but the resulting density remains only slightly above the system's natural asymptotic density.
• The "Unnatural" Target Problem: For active rules, there are "unnatural" target densities that lie outside the system's dynamic attractors. Agents cannot learn to reach these because the environment's intrinsic evolution overrides the agent's local modifications.

5. Significance and Implications

• Limits of Local Control: The paper demonstrates that local control strategies (Reinforcement Learning) have hard limits when applied to complex, active systems. If the system's global dynamics are not compatible with the local actions of the controller, the controller cannot achieve arbitrary global goals.
• Role of Environmental Dynamics: The "physical" evolution of the environment is the primary bottleneck. In passive systems, learning is straightforward; in active systems, the lack of "examples" (states where the agent's action is preserved long enough to be reinforced) prevents learning.
• Multi-Agent Synergy: While single agents often fail in active environments, the presence of multiple agents can sometimes stabilize the system (e.g., preventing extinction in Game of Life), though precise density control remains elusive.
• Future Directions: The work suggests that controlling complex active systems may require agents that can anticipate environmental dynamics or coordinate more sophisticatedly than simple local reinforcement, rather than just reacting to immediate local feedback.

In conclusion, the paper provides a rigorous analysis of the feasibility of using learning agents to control cellular automata, highlighting that while passive environments are easily controllable, active environments impose fundamental constraints that often make global control impossible.