FLASH INFORMATIQUE FI

Le BioWall


Un tissu informatique pour le prototypage de systèmes bio-inspirés




André Stauffer

Christof TEUSCHER


Dans cet article, nous décrivons le BioWall, un tissu informatique reconfigurable géant développé dans le but d’y implémenter des machines mettant en oeuvre les principes de notre projet Embryonique. Bien que ses dimensions et ses caractéristiques en font d’abord un objet de démonstration publique, le BioWall constitue également un outil de recherche précieux, du fait que sa faculté de reprogrammation et sa structure cellulaire s’adaptent parfaitement à l’implémentation de toutes sortes de systèmes bio-inspirés. Pour illustrer ces capacités, nous décrivons un ensemble d’applications qui reflètent différentes sources d’inspiration biologique allant des systèmes biologiques ontogénétiques aux dispositifs évolutifs phylogénétiques, en passant par les réseaux neuromimétiques épigénétiques. Toutes ces applications ont été implémentées et testées matériellement dans le BioWall.

1 Introduction

Notre laboratoire travaille depuis plusieurs années dans la conception de systèmes matériels bio-inspirés. Au cours de ces recherches, nous avons exploré l’inspiration en question dans toutes ses grandes lignes [15]. Nos études se sont à la fois portées sur les systèmes phylogénétiques, inspirés par l’évolution des espèces, sur les systèmes ontogénétiques, inspirés par le développement et la croissance des organismes multicellulaires, et sur les systèmes épigénétiques, inspirés par l’adaptation des individus à leur environnement.

Parmi ces axes de recherche, l’effort principal déployé par notre laboratoire est concentré sur l’axe ontogénétique dans le cadre du projet Embryonique [9][10]. Ce projet tire son inspiration du développement des individus multicellulaires et vise à conférer au matériel informatique certaines propriétés des organismes biologiques comme la croissance et la tolérance aux pannes notamment.

Nos activités ont suscité un réel intérêt dans de nombreux milieux dont certains totalement inattendus. Ainsi l’intérêt le plus inattendu fut sans conteste celui de Mme Jacqueline Reuge qui a décidé de financer la construction d’une machine destinée à présenter les principes de l’Embryonique au grand public, dans un musée (la Villa Reuge [23]) dédié à la mémoire de son défunt mari. Son soutien généreux nous a servi à maintenir la tradition de vérification des concepts de nos projets sous forme d’une réalisation matérielle.

Cette bonne fortune nous a donc permis de construire une machine qui ne serait autrement demeurée qu’un rêve. La machine s’appelle BioWall [22] en raison de son inspiration biologique, d’une part, et de ses dimensions, d’autre part. Conçue principalement comme une plate-forme de démonstration publique des propriétés de nos systèmes embryoniques par le truchement d’interactions tactiles et visuelles, l’implémentation matérielle du BioWall (Figure 1) atteint finalement des dimensions impressionnantes (5.3mx0.6mx0.5m=3.68m3).

Sur cette machine, dont la description technique sera détaillée dans la section 2, nous avons pu, pour la première fois, implanter dans le matériel un organisme doté de toutes les propriétés d’une machine Embryonique, telle qu’elle a été fréquemment définie dans la littérature. Cet organisme, la BioWatch, détaillée dans le paragraphe 3.1 et dont la fonctionnalité se résume à compter les heures, les minutes et les secondes, permet de démontrer les capacités de croissance et d’autoréparation de nos systèmes.

En un sens, l’implémentation de la BioWatch suffirait à justifier l’effort investi dans la construction du BioWall (la réalisation de systèmes embryoniques étant primitivement le but de la machine). Cependant, tout en développant notre machine, nous avons rapidement réalisé que les capacités d’une telle plate-forme ne se réduisaient pas à une seule application. En fait, comme le montrera la description technique de la machine (dans la section 2), il s’agit d’une plate-forme idéale pour le prototypage de toutes sortes de systèmes cellulaires à deux dimensions, c’est-à-dire de systèmes composés d’un réseau de petits éléments interconnectés localement.

fig. 1 - Vue frontale du BioWall  

Les applications répondant à cette description sont nombreuses, en particulier dans le domaine des systèmes bio-inspirés. Les automates cellulaires, par exemple, constituent ainsi un environnement très courant dans le domaine de la recherche bio-inspirée [3]. Cela englobe, pour en citer quelques-uns dans un ordre de complexité croissante, le Jeu de la Vie de John Conway [2] (paragraphe 3.2), les boucles autoréplicatives développées initialement par Chris Langton (paragraphe 3.3) et le constructeur universel de von Neumann [20] (paragraphe 3.4). Et bien que le BioWall soit parfaitement adapté à l’implémentation des automates cellulaires, il ne se réduit de loin pas à cela. Comme autres exemples d’implantation de systèmes bio-inspirés, nous décrirons un type particulier de réseaux neuromimétiques artificiels développés par Alan Turing [19] (paragraphe 3.5) et la réalisation bidimensionnelle de Firefly [13], une machine que nous avions conçue et construite pour démontrer la faisabilité d’une évolution matérielle en ligne (paragraphe 3.6).

Nous avons parallèlement commencé à explorer les possibilités du BioWall en tant qu’outil de recherche. Dans la conclusion de cet article (section 4), nous définirons de futurs domaines de recherche dans lesquels la machine servira de plate-forme pour le prototypage de systèmes bio-inspirés.

2 Le BioWall

La réalisation de machines embryoniques demeure la raison principale qui se cache derrière la construction du BioWall. La structure des machines en question, décrite en détail ailleurs [9][10], est hiérarchique : les organismes (systèmes spécialisés) résultent de l’utilisation en parallèle de plusieurs cellules (petits processeurs), elles-mêmes implémentées sous forme d’un réseau de molécules (éléments logiques programmables). Pour la réalisation matérielle de telles machines, la structure du BioWall correspond à tissu bidimensionnel composé d’unités (représentant chacune une molécule), où chaque unité (fig. 2a) est constituée par un élément d’entrée (une membrane tactile), un élément de sortie (une matrice de 8x8=64 diodes électroluminescentes bicolores) et un élément de calcul programmable (un circuit FPGA Xilinx Spartan XCS10XL [21]). Le BioWall renferme 3200 unités, disposées en 20 rangées de 160 unités.

Figure 2  
(a) Représentation schématique d’une unité du BioWall, (b) Vue partielle des circuits FPGA Xilinx

Le tissu représente une puissance de calcul considérable (3200 circuits FPGA, dont la fig. 2b montre quelques exemplaires) couplée avec une interface d’entrée/sortie (les membranes et les matrices de diodes) qui assure une interaction tactile et visuelle à grande échelle. Les avantages de cette solution sont évidents : (1) la taille de l’affichage permet une interaction immédiate avec des applications qui se limitent normalement à des simulations logicielles sur l’écran d’un ordinateur (certaines de ces applications sont décrites dans la section suivante, d’autres sont mentionnées dans la conclusion) ; (2) la puissance de calcul et la faculté de reprogrammation inhérentes aux circuits FPGA permettent le prototypage de toutes sortes de systèmes bio-inspirés.

Pour le moment (le sujet sera développé dans la conclusion), chacun des circuits FPGA Xilinx du BioWall ne peut être programmé qu’avec la même configuration, ce qui réduit la fonctionnalité des unités aux 10’000 portes logiques équivalentes du circuit FPGA. D’autre part, les délais considérables engendrés par la propagation de signaux globaux sur des distances de plusieurs mètres limitent la fréquence du signal d’horloge à quelques MHz (une fréquence qui demeure plus qu’adéquate si l’on tient compte du parallélisme massif de la machine et qui reste considérablement trop élevée pour les interactions humaines dans la plupart des applications).

Outre les possibilités d’entrée/sortie des membranes et des diodes mentionnées précédemment, un ensemble de modules placés à la périphérie de la machine permettent d’interfacer le tissu avec des circuits logiques standard, soit via le PC ou directement avec des circuits conçus par l’utilisateur (les modules n’autorisent évidemment l’accès qu’à la périphérie du réseau mais, si cela s’avère nécessaire, les circuits FPGA peuvent être programmés de façon à assurer la propagation interne des signaux).

Les outils logiciels développés pour le BioWall sont rudimentaires mais complets. Une simple interface sur le PC permet à l’utilisateur de définir un ensemble de fichiers destinés à la configuration du tissu. Actuellement, il y a quatre types de fichiers (d’autres peuvent être ajoutés) : le fichier de configuration pour les circuits FPGA Xilinx et des fichiers présentant trois formats différents pour envoyer des données définies par l’utilisateur sur les bornes d’entrée disposées à la périphérie du tissu (pour initialiser l’état d’un automate cellulaire, par exemple). Les valeurs prises par les bornes de sortie à la périphérie du tissu peuvent être lues par le PC afin de les stocker sur disque ou de les utiliser directement.

Figure 3  
(a) L’organisme Counter, (b) Implémentation BioWall de la hiérarchie embryonique

3 Applications

Comme nous l’avons mentionné dans l’introduction, le BioWall a été initialement conçu dans un but précis : la réalisation de machines ontogéniques définies conformément aux spécifications du projet Embryonique. Les possibilités du BioWall ne se réduisent cependant pas à cette application. Sa structure cellulaire s’adapte en effet parfaitement à l’implémentation de toutes sortes d’applications bio-inspirées. Dans cette section, nous allons présenter quelques-unes de ces applications de façon à montrer comment le BioWall permet d’implémenter matériellement des inspirations biologiques découlant des trois axes du modèle POE [15] : phylogenèse (P), ontogenèse (O) et épigénèse (E).

3.1 BioWatch

Les principes du projet Embryonique ainsi que la théorie à la base de la BioWatch sont décrites en détail dans bon nombre de publications [9][10][16]. Pour illustrer l’implémentation de l’application BioWatch dans le BioWall, nous recourons à un exemple légèrement simplifié : tandis que la BioWatch complète est un organisme capable de compter les heures, les minutes et les secondes, l’application Counter (fig.3a) se limite au calcul des secondes. Le principe de fonctionnement des deux machines reste cependant identique.

Le compteur égrène les secondes de 00 à 59. De gauche à droite, l’affichage montre les dizaines de secondes (de 0 à 5), les unités de secondes (de 0 à 9) et une zone de réserve, qui reste inactive pendant le fonctionnement normal. On dira que le compteur est divisé en quatre cellules : deux cellules actives (indiquant respectivement les dizaines et les unités) et deux cellules de réserve. Chaque unité de la BioWall est une molécule de la hiérarchie embryonique. Chaque cellule est ainsi une mosaïque de 20x25=500 molécules (fig.3b) et chaque cellule inclut deux colonnes de réparation (2x25=50 molécules).

Le visiteur est maître de la vie de chaque molécule. Il peut insérer une faute dans n’importe quelle molécule par une simple pression du doigt sur la membrane de l’unité correspondante. Le dispositif de détection de faute, inclut dans la couche moléculaire, décèle l’erreur et active le mécanisme d’autoréparation moléculaire. La molécule sacrifiée est instantanément remplacée par sa voisine immédiate, à sa droite et ainsi de suite jusqu’à la plus proche colonne de réparation (fig.4a). Ce mécanisme d’autoréparation implique qu’on ne peut supprimer qu’une seule molécule par ligne, entre deux colonnes de réparation. Si cette contrainte est respectée, la cellule survit, au prix d’une déformation du chiffre affiché. Chaque cellule peut donc tolérer au plus deux fautes par ligne (une faute entre chaque paire de colonnes de réparation), c’est-à-dire 2x25=50 fautes au total.

Figure 4  
(a) Autoréparation moléculaire, (b) Autoréparation cellulaire (cicatrisation)

Si la règle précédente est transgressée, plusieurs fautes étant insérées à la cellule sur la même ligne entre deux colonnes de réparation, l’autoréparation moléculaire n’est plus possible, et la cellule meurt. Cependant, la mort de la cellule n’implique pas la mort de l’organisme : elle est instantanément remplacée par une cellule de réserve située immédiatement à sa droite (fig.4b). La cellule morte est éteinte, elle devient cicatrice. Il convient de noter qu’au cours de ce processus d’autoréparation cellulaire, le comptage du temps se poursuit imperturbablement : le tissu mémorise le temps écoulé et le sauve. De plus, nous implémentons actuellement un mécanisme de résurrection moléculaire. Lorsqu’un nombre suffisant de fautes ont été supprimées (en pressant la membrane des molécules fautives), la cellule morte se réactive et recommence le comptage tout en assurant le sauvetage du temps écoulé.

Les capacités d’autoréparation des machines embryoniques sont basées sur le principe général d’organisation des êtres vivants, la différentiation cellulaire [16]. Chaque organisme est un assemblage de cellules contenant chacune une copie complète du programme génétique, le génome. Cette architecture confère une très grande robustesse à l’ensemble, puisque chaque cellule en possède le plan complet, et peut donc remplacer n’importe quelle autre cellule défaillante. Toutefois, comme pour tous les organismes artificiels et naturels, la mort d’un nombre excessif de cellules n’autorise plus la réparation, entraînant la mort de l’organisme. L’environnement contrôlé dans lequel opèrent les machines leur permet, en cas de mort de l’organisme, d’effectuer une réinitialisation complète du système, effaçant ainsi toutes les fautes injectées et donnant vie à une nouvelle machine en parfait état de marche.

L’implémentation de la BioWatch complète sur le BioWall (fig.5) met en oeuvre huit cellules comportant chacune 20x20 molécules et deux colonnes de réparation. Six des huit cellules sont actives en fonctionnement normal alors que les deux dernières servent de réserve pour remplacer une cellule morte. Toutes les propriétés du projet Embryonique ont été vérifiées matériellement dans cette implémentation.

Figure 5  
Implémentation BioWall de la BioWatch complète

3.2 Jeu de la vie

La vie est complexité. Le tissage d’une toile par l’araignée, ou la construction d’une fourmilière par ses habitantes, suggèrent que ces insectes sont dotés d’intelligence. Il n’en est rien. Selon la démonstration des biologistes, c’est en suivant aveuglément des règles élémentaires, progressivement affinées par la sélection naturelle, que tout animal inférieur manifeste des comportements atteignant parfois l’extrême complexité.

Le jeu de la vie de John Conway [2] est un exemple frappant d’un comportement émergent de ce type. La réalisation du jeu se matérialise sous forme d’un automate cellulaire dont chaque élément représente un individu ne pouvant prendre que deux états : mort ou vif. L’état futur de chaque individu dépend de son propre état présent et de celui de ses huit voisins les plus proches conformément aux règles suivantes :
- si le nombre de voisins vivants est trop faible (zéro ou un), l’individu meurt d’isolement et son état futur est mort ;
- si l’individu a exactement deux voisins vivants, il conserve son état présent ;
- si l’individu a exactement trois voisins vivants, son état futur est vif ;
- si le nombre de voisins vivants est trop élevé (quatre ou plus), l’individu meurt de surpopulation et son état futur est mort.

A partir de ces simples règles locales, des comportements globaux étonnamment complexes apparaissent et se développent (fig. 6). En tant qu’application visuelle saisissante, le jeu de la vie s’implémente idéalement dans le BioWall où les membranes tactiles permettent de se substituer aux règles pour donner vie ou mort à des individus. Nous avons développé deux implémentations distinctes du jeu :

Figure 6  
Le dragon : une configuration globale de l’application Life16


- >Dans Life1, chacune des 3200 unités du BioWall représente un seul individu. La surface est toroïdale et les membranes tactiles permettent de complémenter l’état des individus.
- Dans Life16, chaque unité représente une matrice de 4x4=16 individus (pour un total de 51’200 individus sur le BioWall entier) et les membranes tactiles servent à insérer un planeur (une des configurations stables du jeu de la vie qui se déplace diagonalement à travers l’espace).

Cette application, bien que dépourvue d’un réel intérêt de recherche (elle est avant tout destinée à offrir une interaction directe au grand public), n’en demeure pas moins un bon exemple d’application bio-inspirée parfaitement adapté pour illustrer les atouts du BioWall (possibilités d’affichage, interactivité, etc.).

3.3 Boucles autoréplicatives

Initiée par von Neumann il y a plus de cinquante ans [20], l’étude des machines autoréplicatives a produit une pléthore de résultats au cours du temps [14]. L’essence de ce travail réside dans le désir de comprendre les principes fondamentaux du traitement de l’information et des algorithmes impliqués dans l’autoréplication, indépendamment de toute réalisation physique [12]. La construction de machines artificielles autoréplicatives s’avère indispensable dans diverses applications, allant de la nanotechnologie [4] à l’exploration spatiale [5], en passant par les tissus informatiques reconfigurables.

L’un des événements majeurs dans l’histoire de l’autoréplication artificielle fut la conception de la première boucle autoréplicative par Chris Langton [7]. Sa boucle de 86 cellules est définie dans un espace cellulaire bidimensionnel comportant huit états dans un voisinage de cinq cellules. Parmi ces huit états, l’un sert d’élément construit et un second permet d’implémenter une gaine autour de la structure réplicative. Reggia et d’autres coauteurs [12] ont proposé des versions simplifiées de la boucle de Langton. Dépourvue de gaine, la plus petite d’entre elles se compose de cinq cellules.

Toutes les boucles proposées à ce jour constituent des mondes pour eux-mêmes : une fois configurée dans l’univers de l’automate cellulaire (au temps initial), la boucle s’autoréplique automatiquement, sans interaction ultérieure et indépendamment de l’observateur. Pour rendre le processus d’autoréplication à la fois plus interactif et plus visible, nous avons implémenté une série de boucles dans le BioWall, de taille 2x2 d’abord [17], puis de taille variable (Figure 7).

Figure 7  
Le cycle de la boucle 3x3 au repos

Dans cette implémentation, où chaque unité du BioWall correspond à une cellule de l’automate, la pression sur la membrane d’une unité appartenant à la boucle engendre la réplication de cette dernière dans l’une des quatre directions cardinales (Figure 8).

Figure 8  
Boucles autoréplicatives de différentes tailles

3.4 Constructeur universel

Le pionnier, dans le domaine du matériel numérique bio-inspiré, fut John von Neumann. Mathématicien surdoué et figure emblématique du développement dans le domaine des ordinateurs, von Neumann a consacré les dernières années de sa vie à la théorie des automates [20]. Malheureusement interrompue par sa mort en 1957, cette recherche s’inspirait du parallèle existant entre les automates artificiels, tels les ordinateurs par exemple, et les automates naturels, comme le système nerveux, les organismes évolutifs, etc.

Pour entreprendre la réalisation physique de sa théorie des automates, von Neumann a développé un modèle connu sous le nom de constructeur universel. Il s’agit d’un automate cellulaire qui devint le point de départ des recherches sur les machines autoréplicatives entreprises dans les décennies suivant la conception de ce modèle.

Figure 9  
Constructeur universel de Von Neumann, (a) Opération de base, (b) Autoréplication

Dans l’oeuvre de von Neumann, l’autoréplication apparaît toujours comme un cas particulier de construction universelle (fig. 9a) : sa machine Uconst est capable de construire une autre machine M, pour autant qu’elle dispose de sa description D(M). Cette approche étant conservée dans la conception de son automate cellulaire, ce dernier s’avère être bien plus qu’une simple machine autoréplicative. La complexité de ses desseins se reflète dans la complexité de sa structure, basée sur trois composants distincts :
- Une bande de mémoire, contenant la description (une chaîne unidimensionnelle d’éléments) de la machine à construire. Dans le cas particulier de l’autoréplication, la bande de mémoire contient la description du constructeur universel lui-même (fig. 9b).
- Le constructeur proprement dit, une machine capable de lire la bande de mémoire et d’interpréter son contenu.
- Un bras constructeur, dirigé par le constructeur, utilisé pour construire le rejeton (la machine décrite dans la bande de mémoire). Le bras se déplace dans l’espace et met les éléments du rejeton dans l’état approprié.

Outre cette complexité déjà considérable, von Neumann postule la présence d’un ordinateur universel Ucomp (en pratique, une machine universelle de Turing [6], soit un automate capable d’opérer n’importe quel calcul fini). Cet ordinateur est attaché au constructeur universel et se réplique avec lui.

L’implémentation du constructeur universel sous forme d’automate cellulaire est d’une complexité considérable. Chaque cellule pouvant prendre 29 états et l’état futur d’une cellule dépendant de son propre état présent et de celui de ses quatre voisins cardinaux, le comportement de l’automate satisfait exhaustivement 295 = 20’511’149 règles de transition. Si l’on considère que la taille du constructeur de von Neumann avoisine les 100’000 éléments, il est facile de comprendre pourquoi l’automate n’a jamais été complètement simulé à ce jour.

Dans le cadre du projet Embryonique, nous avions réalisé une implémentation matérielle d’un ensemble d’éléments de l’automate de von Neumann [1]. En concevant soigneusement la structure matérielle de chaque élément, nous avions considérablement réduit l’espace mémoire requis pour loger les règles de transition. Usant de la même technique, nous avons encodé une cellule de l’automate de von Neumann dans chaque éléments du BioWall. Bien que les 3’200 éléments de ce dernier soient insuffisants pour implémenter le constructeur universel dans sa totalité, il nous permet de matérialiser plusieurs portions significatives (organes, dans la terminologie de von Neumann) de la machine (fig. 10).

Figure 10  
Un organe du constructeur universel de von Neumann, (a) Construction, (b) Configuration finale

3.5 Réseau neuromimétique

C’est en 1948 que Alan Turing rédigea un rapport peu connu intitulé Intelligent Machinery [19]. A cette époque, il était employé au National Physical Laboratory (NPL) de Londres et travaillait à la conception d’un ordinateur électronique dénommé Automatic Computing Engine (ACE). Turing n’ayant jamais été spécialement intéressé à partager ses idées, le papier demeura non publié jusqu’en 1968, soit 14 ans après sa mort.

Peu de gens savent que le papier Intelligent Machinery renferme une investigation fascinante concernant les modèles connexionistes que l’on appellerait aujourd’hui réseaux neuromimétiques. Etonnamment, son employeur au National Physical Laboratory, Sir Charles Darwin, petit-fils du naturaliste anglais bien connu, considéra alors le manuscrit comme un essai d’écolier. En décrivant des réseaux de neurones aléatoirement interconnectés, Turing a ainsi écrit l’un des premiers manifestes dans le domaine de l’intelligence artificielle (bien qu’il n’utilisa pas ce terme). Le réseau neuromimétique de Turing a fait récemment l’objet d’une étude détaillée [18].

Turing qualifiait ses réseaux de machines désorganisées. Il proposait essentiellement trois sortes de machines : les machines désorganisées de type A, de type B et de type P. Les machines de type A et de type B sont des réseaux booléens résultant de l’interconnexion aléatoire de portes NAND (les neurones) ayant chacune deux entrées (les synapses) provenant des autres neurones. Les neurones sont synchronisés avec un signal d’horloge global. Contrairement aux réseaux de type A, ceux de type B disposent de connexions modifiables (de simples interrupteurs) de sorte qu’un agent extérieur puisse organiser ces machines (en fermant ou en ouvrant les connexions) pour effectuer le travail requis. L’introduction de réseaux de type B permet de renforcer les liaisons utiles et de couper celles qui ne le sont pas. La motivation profonde restant la construction de machines capables d’apprendre, l’idée d’organiser initialement un réseau aléatoire de neurones et de connexions constitue sans aucun doute la contribution essentielle du papier de Turing.

Récemment, nous avons implémenté le réseau neuromimétique de Turing dans le tissu reconfigurable du BioWall. Chacune des 3’200 unités de la machine peut être configurée interactivement en choisissant l’une des cinq fonctions suivantes : (1) cellule vide, (2) neurone, (3) connexion, (4) synapse ou (5) cellule d’entrée. La fig. 11 montre une configuration possible. L’utilisateur (le superviseur externe) est invité à découvrir et à modifier le comportement de la machine désorganisée de type B en ouvrant ou fermant les synapses (en organisant la machine) et en faisant varier les entrées du réseau. Toutes les modifications résultent d’une simple pression sur les membranes tactiles correspondantes. Cette application constitue en premier lieu une réalisation du réseau neuromimétique de Turing dans du matériel reconfigurable (la première, à notre connaissance). Elle représente cependant également la fusion des axes ontogénétique et épigénétique dans un seul et même tissu artificiel.

Figure 11  
Implémentation BioWall du réseau neuromimétique de type B

3.6 Firefly 2D

En 1997, le Laboratoire de systèmes logiques avait réalisé Firefly [13], un système matériel évolutif de programmation cellulaire, dans lequel les cellules d’un automate évoluent en parallèle pour résoudre un problème spécifique. Le problème, étudié et résolu avec succès, était celui de la synchronisation d’un automate cellulaire unidimensionnel : à partir d’une configuration initiale quelconque de 0 et de 1, l’automate non-uniforme doit atteindre, en M pas de temps, une configuration finale dans laquelle l’ensemble de ses cellules oscillent de manière synchrone en présentant toutes simultanément des 0 et des 1 à chaque pas de temps. La nouveauté introduite par la matérialisation de Firefly consiste à opérer sans se référer à un dispositif externe (tel qu’un ordinateur réalisant les opérations génétiques). Le système implémente par conséquent une évolution autonome en ligne.

Alors que la machine Firefly originale résolvait le problème de la synchronisation d’un automate cellulaire unidimensionnel, l’implémentation réalisée dans les 3’200 circuits FPGA du BioWall apporte une solution à ce problème dans le cas d’un automate bidimensionnel (fig.12). Les bases théoriques de l’extension d’une à deux dimensions du problème de la synchronisation sont présentées dans [13].

Figure 12  
Problème de la synchronisation 2D : automate cellulaire co-évolué non-uniforme à 2 états et 5 voisins

L’implémentation bidimensionnelle BioWall matérialise un automate cellulaire non-uniforme à deux états et cinq voisins, dans lequel chaque cellule (chaque circuit FPGA du BioWall) admet une table de règles différente. Dans la cellule, cette table est encodée sous forme d’une chaîne de bits, appelée génome, dont la longueur s’élève à 25=32 bits. Au lieu de faire appel à une population d’automates cellulaires évolutifs, notre algorithme opère l’évolution d’un seul automate cellulaire non-uniforme de la taille du BioWall dans son entier (une cellule de l’automate par unité du BioWall, soit 3’200 cellules), dont les tables de règles sont initialisées aléatoirement. De nouvelles configurations initiales sont générées aléatoirement par la suite et utilisées chacune par l’automate cellulaire pendant M pas de temps. Le fitness accumulé de chaque cellule résulte de la sommation des fitness individuels obtenus au cours de C configurations successives. A partir de chacune de ces configurations initiales, le fitness individuel de la cellule vaut 1 lorsque la séquence d’états 0-1-0-1 est obtenue lors des pas de temps M+1 à M+4, 0 dans le cas contraire. Les tables de règles sont modifiées toutes les C configurations par crossover et par mutation sur la base des fitness accumulés. Ce processus d’évolution est réalisé de manière locale car les opérations génétiques d’une cellule n’impliquent que la cellule elle-même et ses quatre voisins cardinaux.

Contrairement aux algorithmes génétiques standard, dans lesquels une population de solutions au problème évolue de manière globale, notre approche repose sur un réseau de tables de règles qui co-évoluent de manière locale. Les cellules de l’automate réalisent ainsi des calculs dans lesquels n’interviennent que les états de leurs voisins les plus proches. Il en va de même pour le processus d’évolution, car tant la détermination des fitness que les opérations génétiques s’effectuent localement.

L’implémentation de l’approche de type programmation cellulaire précédemment décrite dans le BioWall nous prouve qu’il est possible d’évoluer un automate cellulaire non-uniforme de rayon 1 pour résoudre le problème de la synchronisation. Après avoir déterminé un ensemble de tables de règles satisfaisant le problème, la modification de l’état de chaque cellule de l’automate résulte d’une simple pression sur la membrane tactile correspondante. L’utilisateur peut alors observer comment la machine réalise la synchronisation de ses 3’200 cellules.

4 Conclusions

Les applications présentées dans ce papier ne constituent qu’un petit exemple des capacités du BioWall, capacités que nous continuons de découvrir. Sa structure cellulaire fait de cette machine une plate-forme idéale pour le prototypage de systèmes bio-inspirés. Ceux-ci exploitent en effet souvent une telle structure, que l’on retrouve communément à tous les niveaux dans la nature. La taille du BioWall impose cependant un certain nombre de limitations (fréquence d’horloge, par exemple), mais sa faculté de reprogrammation lui confère une remarquable souplesse d’emploi. Les interactions visuelles et tactiles du système constituent des supports incomparables pour la dissémination des idées et pour la vérification matérielle de concepts souvent réduits aux simulations logicielles.

Parmi les autres applications bio-inspirées que nous avons implémentées ou que nous projetons d’implémenter, nous citerons, par exemple, les L-systèmes [8], les fourmis, les environnements proie-prédateur, d’autres espèces d’automates cellulaires et des réseaux neuromimétiques plus conventionnels. Une application (ou plus précisément un groupe d’applications) mérite cependant une mention spéciale.

Comme nous l’avons évoqué précédemment, l’inspiration biologique pour la conception de machines informatiques découle essentiellement de trois modèles biologiques [15] : la phylogenèse (P), soit le développement des espèces au cours de l’évolution, l’ontogenèse (O), soit le développement de l’individu dirigé par son code génétique, et l’épigénèse (E), soit le développement de l’individu à l’aide d’un processus d’apprentissage (système nerveux, système immunitaire) influencé à la fois par le code génétique (l’inné) et par l’environnement (l’acquis). Ces trois modèles partagent une base commune : une description unidimensionnelle de l’organisme, le génome. Alors que ces trois modèles ont tous déjà servi séparément comme source d’inspiration pour le développement de machines informatiques, leur fusionnement au sein d’un même système demeure un réel défi.

Depuis septembre 2001, en collaboration avec l’Université de York (Angleterre), l’Université polytechnique de Catalunya (Espagne), L’Université de Glasgow (Ecosse) et l’Université de Lausanne (Suisse), notre laboratoire poursuit un projet de recherche dans le cadre du programme Information Society Technologies (IST) de la communauté européenne. D’une durée de trois ans, ce projet vise au développement d’un substrat informatique optimisé pour l’implémentation de systèmes numériques inspirés par les trois modèles biologiques précités.

Le tissu POEtique sera une surface cellulaire composée d’un nombre variables d’éléments. Chacune de ses cellules sera capable de communiquer avec l’environnement (à l’aide de senseurs et d’actuateurs) et avec les cellules voisines (par des canaux bidirectionnels) pour exécuter une fonction spécifique. Toutes les cellules du tissu présenteront une structure de base identique mais pourront acquérir des fonctionnalités diverses, au même titre que les cellules totipotentes ou cellules souches dans les organismes vivants [11]. La flexibilité résultera d’une organisation à trois couches : la couche génotype, la couche configuration et la couche phénotype. La couche génotype de chaque cellule contiendra la description complète de l’organisme sous forme d’un génome numérique. La couche configuration déduira du génome une chaîne de configuration destinée à la commande de l’unité de traitement de la couche phénotype. Le tissu sera ainsi organisé sous forme d’une structure informatique multicellulaires massivement parallèle. Dans cette structure, des groupes de cellules pourront collaborer pour réaliser une tâche donnée et créeront de la sorte des sous-structures semblables aux organes dans les organismes vivants.

Bien que le projet POEtique révélera en fin de compte des capacités supérieures à celles du BioWall, il sera nécessaire, au cours des étapes initiales du projet, de pouvoir prototyper rapidement des tissus pour non seulement analyser leurs qualités et leurs défauts mais également leur faisabilité matérielle (une considération souvent ignorée par les simulations logicielles). La versatilité du BioWall en fera par conséquent un outil indispensable pour le succès du projet POEtique.

Le BioWall décrit dans cet article est actuellement exposé au musée de la Villa Reuge [23]. Grâce au soutien généreux de Mme Reuge, nous avons cependant conservé une version réduite de la machine (2’000 unités) comme outil de recherche dans notre laboratoire [22]. Nous sommes ainsi en mesure de développer de nouvelles applications tout en améliorant les caractéristiques du tissu. Les modifications envisagées incluent le perfectionnement de l’interface d’entrée/sortie et la possibilité de configurer chacun des circuits FPGA indépendamment des autres, de façon à accroître encore la versatilité du tissu.

Pour conclure, nous vous invitons tous à venir « jouer » avec la machine, soit au musée de la Villa Reuge, soit dans notre laboratoire. Et plus sérieusement, nous sommes prêts à mettre notre machine à disposition d’autres groupes de recherche pour leur permettre de matérialiser leurs idées et leurs concepts.

Remerciements

Ce travail est partiellement financé par le Fonds national suisse de la recherche scientifique (20-63711.00), la Fondation Leenaards à Lausanne et la Villa Reuge à Ste-Croix.

Nous remercions Moad Brahami et Martin Duvanel pour l’implémentation du constructeur universel, Julien Pilet et Maciej Kupiec Gavillet pour l’implémentation du réseau neuromimétique et Hans Jaeckle pour l’implémentation de Firefly 2D.

Nous remercions également André Badertscher pour quelques-unes des photographies utilisées dans cet article.

Finalement, nous remercions la communauté européenne en général et le programme IST en particulier pour les moyens mis à disposition en vue de la poursuite du développement du matériel bio-inspiré.

Références

[1] J.-L. Beuchat, J.-O. Haenni. Von Neumann’s 29-State Cellular Automaton : A Hardware Implementation. IEEE Trans. on Education, Vol. 43, No 3, pp. 300-308, August 2000.

[2] E.R. Berlekamp, J.H. Conway, R.K. Guy. Winning Ways for your Mathematical Plays. Vol.2 : Games in Particular. Academic Press, London, 1985.

[3] A. Burks (ed.) Essays on Cellular Automata. University of Illinois Press, Urbana IL, 1970.

[4] K.E. Drexler. Nanosystems : Molecular Machinery, Manufacturing and Computation. John Wiley, New York, 1992.

[5] R.A. Freitas and W.P. Gilbreath (eds.). Advanced automation for space missions : Proceedings of the 1980 NASA/ASEE summer study. NASA, Scientific and Technical Information Branch (available from U.S.G.P.O., Publication 2255), Washington D.C., 1980.

[6] J.E. Hopcroft, J.D. Ullman. Introduction to Automata Theory Languages and Computation. Addison-Wesley, Redwood City, CA, 1979.

[7] C. Langton. Self-reproduction in cellular automata. Physica D, 10:135-144, 1984.

[8] A. Lindenmayer. Mathematical models for cellular interaction in development, parts I and II. Journal of Theoretical Biology, 18:280-315, 1968.

[9] D. Mange, M. Sipper, A. Stauffer, G. Tempesti. Towards Robust Integrated Circuits : The Embryonics Approach. Proceedings of the IEEE, vol. 88, no. 4, pp. 516-541, April 2000.

[10] D. Mange and M. Tomassini (eds.) Bio-Inspired Computing Machines, Presses Polytechniques et Universitaires Romandes, Lausanne, Switzerland, 1998

[11] H. Pearson. The Regeneration Gap. Nature, vol. 414, 22, p. 388-390, November 2001.

[12] J.A. Reggia, S.L. Armentrout, H.-H. Chou, and Y. Peng. Simple systems that exhibit self-directed replication. Science, 259:1282-1287, February 1993.

[13] M. Sipper. The Evolution of Cellular Automata : The Cellular Programming Approach. Springer-Verlag, Berlin 1997.

[14] M. Sipper. Fifty years of research on self-replication : An overview. Artificial Life, 4:237-257, 1998.

[15] M. Sipper, E. Sanchez, D. Mange, M. Tomassini, A. Pérez-Uribe, and A. Stauffer. A phylogenetic, ontogenetic, and epigenetic view of bio-inspired hardware systems. IEEE Transactions on Evolutionary Computation, vol. 1, no. 1, pp. 83-97, April 1997.

[16] A. Stauffer, D. Mange, G. Tempesti, and C. Teuscher. BioWatch:A giant electronic bio-inspired watch. In D. Keymeulen, A. Stoica, J. Lohn and R.S. Zebulum (eds.), Proceedings of the Third NASA/DOD Workshop on Evolvable Hardware (EH-2001), pp.185-192, IEEE Computer Society, Pasadena CA, 2001.

[17] A. Stauffer and M. Sipper. Externally controllable and destructible self-replicating loops. In J. Kelemen and P. Sosik (eds.), Advances in Artificial Life : Proceedings of the 6th European Conference on Artificial Life (ECAL 2001), Lecture Notes in Artificial Intelligence, 2159:282-291, Springer-Verlag, Heidelberg, 2001.

[18] C. Teuscher. Turing’s Connectionism. An Investigation of Neural Network Architectures. Springer-Verlag, London, 2001.

[19] A.M. Turing. Intelligent Machinery. In B. Meltzer and D. Michie (eds.), Machine Intelligence, volume 5, pages 3-23. Edinburgh University Press, Edinburgh, 1969.

[20] J. von Neumann. The Theory of Self-Reproducing Automata. A.W. Burks (ed.), University of Illinois Press, Urbana, IL, 1966.

[21] Xilinx Corp. Spartan/XL Families FPGAs Data Sheet. Available online at http://www.xilinx.com

[22] http://lslwww.epfl.ch/biowall/

[23] http://www.villareuge.ch/

[24] http://www.poetictissue.org/



Cherchez ...

- dans tous les Flash informatique
(entre 1986 et 2001: seulement sur les titres et auteurs)
- par mot-clé

Avertissement

Cette page est un article d'une publication de l'EPFL.
Le contenu et certains liens ne sont peut-être plus d'actualité.

Responsabilité

Les articles n'engagent que leurs auteurs, sauf ceux qui concernent de façon évidente des prestations officielles (sous la responsabilité du DIT ou d'autres entités). Toute reproduction, même partielle, n'est autorisée qu'avec l'accord de la rédaction et des auteurs.


Archives sur clé USB

Le Flash informatique ne paraîtra plus. Le dernier numéro est daté de décembre 2013.

Taguage des articles

Depuis 2010, pour aider le lecteur, les articles sont taggués:
  •   tout public
    que vous soyiez utilisateur occasionnel du PC familial, ou bien simplement propriétaire d'un iPhone, lisez l'article marqué tout public, vous y apprendrez plein de choses qui vous permettront de mieux appréhender ces technologies qui envahissent votre quotidien
  •   public averti
    l'article parle de concepts techniques, mais à la portée de toute personne intéressée par les dessous des nouvelles technologies
  •   expert
    le sujet abordé n'intéresse que peu de lecteurs, mais ceux-là seront ravis d'approfondir un thème, d'en savoir plus sur un nouveau langage.