Control of Cellular Automata by Moving Agents with Reinforcement Learning

Cette étude exploratoire démontre que des agents cognitifs utilisant l'apprentissage par renforcement peuvent apprendre à modifier un automate cellulaire passif pour atteindre un objectif global, mais que cette tâche devient impossible lorsque l'environnement suit une dynamique active.

L'essentiel

🌍 Le Scénario : Un monde de pixels et des petits jardiniers

Imaginez un immense tableau de pixels (une grille), où chaque case est soit noire (0) soit blanche (1). Ce tableau bouge tout seul selon des règles précises, comme une fourmilière ou un jeu de vie. C'est notre environnement.

Maintenant, imaginez des petits agents (des robots ou des jardiniers) qui se promènent sur ce tableau.

• Leur outil : Ils ont une "main" qui peut changer la couleur d'un seul pixel (l'actuateur).
• Leur vision : Ils ont des "yeux" qui voient les 8 cases autour d'eux (un carré de 3x3).
• Leur but : Ils veulent que le tableau ait une certaine proportion de cases blanches. Disons qu'ils veulent exactement 50 % de blanc.

Le défi ? Le tableau change tout le temps tout seul. Les agents doivent apprendre à intervenir pour guider ce chaos vers leur objectif.

---

🧠 Comment ils apprennent ? (L'Intelligence Artificielle)

Ces agents ne savent pas au début comment faire. Ils utilisent une méthode appelée Apprentissage par Renforcement. C'est comme un enfant qui apprend à faire du vélo :

1. Il regarde autour de lui (combien de blancs voit-il ?).
2. Il essaie de changer la case du milieu (il la met en blanc ou en noir).
3. Il regarde ce qui se passe une seconde plus tard.
   • Si ça a rapproché le tableau de son but (plus de blancs quand il en voulait) : "Super ! Je vais faire ça plus souvent !" (Il renforce la probabilité).
   • Si ça a éloigné le tableau du but : "Oups, mauvaise idée." (Il diminue la probabilité).

Au fil du temps, ces agents deviennent des experts et leurs décisions deviennent automatiques.

---

🛌 Cas 1 : Le monde "Passif" (Le mur de Lego)

Imaginez que le tableau est comme un mur de Lego que vous construisez. Si vous posez une brique, elle reste là. Le monde ne bouge pas tout seul.

• Résultat : C'est facile ! Les agents apprennent très vite. Ils découvrent rapidement la règle parfaite : "Si je vois trop de noir, je mets du blanc. Si je vois trop de blanc, je mets du noir."
• Analogie : C'est comme si vous essayiez de garder une pièce à 20°C. Si vous allumez le chauffage quand il fait froid et l'éteignez quand il fait chaud, vous atteignez vite la température idéale.

---

🌪️ Cas 2 : Le monde "Actif" (La tempête ou le jeu de la vie)

Maintenant, imaginez que le tableau n'est pas un mur, mais une tempête ou un jeu vidéo (comme le célèbre "Jeu de la Vie" de Conway). Les cases changent de couleur toutes seules, selon des règles complexes, même si vous ne touchez à rien.

• Le problème : Les agents sont comme des nageurs essayant de garder une bouée à un endroit précis, mais l'océan est en furie.
• Ce qui se passe :
  • Parfois, l'agent essaie de mettre une case en blanc, mais la "tempête" la remet en noir immédiatement. L'agent ne comprend pas pourquoi son action a échoué.
  • Il manque d'exemples pour apprendre. Il ne peut pas tester toutes les situations car le monde change trop vite.
  • Résultat : Les agents échouent souvent. Ils ne peuvent pas atteindre leur objectif exact. Ils ne font que de petites modifications locales, mais le "naturel" du monde (la tempête) reprend le dessus.

---

💡 Les enseignements clés (La morale de l'histoire)

1. L'environnement est le maître : Si le monde est calme (passif), les agents apprennent vite et contrôlent tout. Si le monde est agité (actif), le contrôle est presque impossible.
2. La coopération aide un peu : Si plusieurs agents travaillent ensemble, ils peuvent perturber le monde un peu plus, mais ils ne peuvent pas vaincre une dynamique trop forte.
3. Le paradoxe de l'apprentissage : Pour apprendre, il faut pouvoir tester des choses. Mais si le monde change trop vite, les agents ne peuvent jamais voir le résultat de leurs actions, et donc ils ne peuvent pas apprendre.

En résumé

Ce papier nous dit que contrôler un système complexe est facile si le système est passif, mais devient un défi quasi impossible si le système a sa propre "volonté" (ses propres règles d'évolution). C'est une métaphore puissante pour comprendre pourquoi il est si difficile pour nous, humains, de contrôler des systèmes complexes comme le climat, l'économie ou les réseaux sociaux : ils ont une dynamique "active" qui résiste à nos petites interventions.

Résumé technique

1. Problématique

L'article aborde le problème du contrôle d'un environnement dynamique par des agents cognitifs mobiles. L'objectif est de déterminer dans quelle mesure des agents, capables de percevoir localement leur environnement et d'agir sur celui-ci, peuvent apprendre à modifier la dynamique globale d'un système pour atteindre un objectif spécifique.

• Système cible : Un automate cellulaire (AC) booléen bidimensionnel, régi par des règles « outer totalistic » (la nouvelle valeur d'une cellule dépend de son état actuel et de la somme des états de ses voisins, mais pas de la configuration spatiale exacte).
• Objectif global : Atteindre une densité asymptotique spécifique de cellules « 1 » (actives) dans l'ensemble du système.
• Défi principal : La difficulté réside dans l'interaction entre l'apprentissage de l'agent et l'évolution de l'environnement. Si l'environnement est passif (ne modifie pas les changements apportés), le contrôle est aisé. Si l'environnement suit une dynamique active (ses propres règles d'évolution), l'apprentissage peut être entravé, voire rendu impossible, car les actions de l'agent peuvent être annulées ou déformées par la dynamique naturelle du système.

2. Méthodologie

Modélisation

• L'Environnement (Le Monde) : Un réseau 2D de taille $N \times N$ évoluant selon des règles d'automates cellulaires déterministes (ex: règles de majorité, de minorité, ou le « Jeu de la Vie »). L'évolution est parallèle (synchrone).
• Les Agents : Modélisés comme des automates cellulaires probabilistes totaux.
  • Capteurs : Ils observent le voisinage de Moore (9 cellules : la cellule centrale + 8 voisins). La mesure $m$ est le nombre de cellules « 1 » dans ce voisinage.
  • Actionneur : Ils ne modifient que la cellule centrale.
  • Stratégie : Un vecteur de probabilités $P(m)$ qui détermine la probabilité d'imposer la valeur 1 à la cellule centrale en fonction de la mesure locale $m$.

Processus d'Apprentissage (Reinforcement Learning)

Les agents utilisent un algorithme d'apprentissage par renforcement simple pour ajuster leur stratégie $P(m)$ :

1. Mesure : L'agent mesure la densité locale $m$.
2. Action : Il applique une stratégie probabiliste pour inverser ou non l'état de la cellule centrale.
3. Évaluation : Il mesure la nouvelle densité locale $m'$ à l'étape suivante.
4. Mise à jour :
   • Si l'action rapproche la densité locale de la cible $\bar{m}$, la probabilité d'effectuer cette action est renforcée ($\Delta P > 0$).
   • Si l'action éloigne la densité de la cible, la probabilité est diminuée.
   • Si l'action n'a pas d'effet ou si la densité dépasse la cible de l'autre côté, la probabilité reste inchangée.
   • Après un nombre d'époques $T$, les probabilités convergent généralement vers des valeurs déterministes (0 ou 1).

3. Contributions Clés

1. Distinction Environnement Passif vs Actif : L'article établit une frontière théorique et pratique entre la contrôlabilité d'un environnement passif (règle d'identité, où les changements sont maintenus) et d'un environnement actif (règles dynamiques complexes).
2. Analyse des Stratégies Pures : Les auteurs caractérisent les résultats des stratégies déterministes (règles de minorité asynchrones) sur des environnements passifs, montrant qu'elles peuvent stabiliser une densité indépendante de la condition initiale.
3. Limites de l'Apprentissage dans les Systèmes Complexes : La démonstration que l'apprentissage échoue lorsque l'environnement possède des « zones interdites » ou des dynamiques qui contredisent l'objectif de l'agent (ex: le Jeu de la Vie tendant vers l'extinction).

4. Résultats

Cas de l'Environnement Passif (Règle d'Identité)

• Apprentissage réussi : Les agents apprennent rapidement une stratégie de type « règle de minorité » (ex: $MLE_s$).
• Résultat : La densité asymptotique du système converge vers la cible $\bar{m}$, indépendamment de la densité initiale.
• Observation : La présence de plusieurs agents accélère l'apprentissage en augmentant la variabilité des échantillons de densité locale.

Cas d'Environnements Actifs Complexes

Les auteurs testent trois règles d'environnement :

1. Identité Frustrée ($H0HGE1p$) : L'environnement modifie certaines configurations locales (ex: si le voisinage est vide, la cellule s'inverse).
   • Résultat : Si la cible est dans la « plage naturelle » de l'environnement, l'apprentissage fonctionne. Si la cible est dans une plage interdite par la règle, l'agent ne peut pas apprendre une stratégie efficace pour ces configurations locales (les probabilités restent à 0,5 car l'agent ne peut jamais réussir à atteindre la cible dans ces cas précis).
2. Identité Doublement Frustrée : Similaire au cas précédent mais avec des contraintes supplémentaires.
3. Jeu de la Vie ($H3H23p$) :
   • Résultat : L'apprentissage échoue presque totalement. Un seul agent conduit inévitablement le système à l'extinction (densité 0). Même avec plusieurs agents, le système reste sensible aux perturbations.
   • Échec de la généralisation : Les agents ne peuvent pas apprendre à gérer les configurations locales où $m=0$ car toute action sur une cellule isolée dans le Jeu de la Vie conduit à sa mort immédiate ($C'=0$), empêchant toute convergence vers une densité non nulle.

5. Signification et Conclusion

L'étude démontre que la capacité d'un agent cognitif à contrôler un système complexe dépend intrinsèquement de la nature de la dynamique de cet environnement.

• Environnements passifs : Le contrôle est réalisable et robuste ; l'agent peut apprendre à imposer une dynamique asynchrone qui stabilise le système à une densité désirée.
• Environnements actifs : La tâche devient souvent impossible si la dynamique naturelle du système s'oppose à l'objectif de l'agent. Les agents ne peuvent pas apprendre à corriger des configurations locales qui sont « fatales » ou stables selon les règles de l'environnement, limitant ainsi leur capacité d'action à de simples modifications locales sans impact global significatif.

Conclusion : Ce travail met en lumière les limites fondamentales de l'apprentissage par renforcement dans des systèmes dynamiques complexes où l'agent ne contrôle qu'une partie du système et où la dynamique globale peut annuler ou déformer les actions locales. Cela suggère que pour des environnements très actifs, des stratégies de contrôle collectives ou des modifications de la dynamique de l'environnement elle-même seraient nécessaires.