Citation du moment : Sensibilité.

"On ne voit bien qu’avec le coeur. L’essentiel est invisible pour les yeux." Antoine de Saint-Exupéry, "Le petit prince"

 

Fourmis !

Simuler le comportement des fourmis ? Tentative de ma part, jamais pleinement réalisée (projet de 1999)

Il y a quelques années, j’avais lu un article dans une revue scientifique, dans la rubrique programmation, mais je n’avais pas alors les moyens de faire ce programme.
Maintenant que je les ai, je ne parviens pas à retrouver l’article, néanmoins je me souviens du sujet. Je n’ai jamais terminé le programme dont je fais ici la description.

Je serai curieux de savoir si cette page a inspiré certaines créations (et pourquoi pas ajouter des liens vers celles-ci).

But du programme

Le but du programme serait de ranger plusieurs types de blocs par des fourmis, afin d’illustrer comment des êtres si petits au comportement si élémentaire sont capables de réaliser des opérations complexes.

Cette page expose le comportement de fourmi virtuelle qui a été retenu. Il ne repose que sur les connaissances que j’ai des fourmis, et n’ai pas été vérifié par rapport au connaissances scientifiques.

Fourmi portant du nectar

Les seules indications de départ sont qu’il y a des blocs dispersés sur l’écran, comme les fourmis, et qu’à la fin, le tout doit etre rangé...

Les plus initiés peuvent se poser la modélisation de la fourmi seuls et commencer à programmer s’il le veulent. Les débutants n’ont qu’à se laisser guider.
En informatique, on fait toujours une analyse descendante : du global, vers le précis. La difficulté en est scindée en éléments plus simples. Ecoutez la sagesse des anciens !
"... de diviser chacune des difficultés que j’examinerais en autant de parcelles qu’il se pourrait et qu’il serait requis pour les mieux résoudre..."
René Descartes, élève du collège de La Flèche de 1606 à 1614.

Film "Fourmiz"
(c) 1998 DreamWorks

S’il y a un premier problème, c’est bien d’écrire le programme ! Alors s’il y a un manque de motivation allez voir " Fourmiz’ " et revenez, ça ira beaucoup mieux...

Ensuite, voici deux sites intéressants : "http://www.multimania.com/lesfourmis", ce premier est sur les vraies fourmis, "http://www.archipress.org/ts/deneubourg.htm", ce second sur l’intelligence collective des insectes.

Modélisation du problème

Alors, c’est quoi une fourmi ?
Alors ici, je pourrais décrire une fourmi de la façon biologique mais cela ne servirait à rien ici (voyez les liens ci-dessus).

Le principal problème c’est de faire comprendre à l’ordinateur ce que c’est (qu’est ce que c’est bete ces machines !). Il faut donc décrire les fourmis avec des éléments de programmation.

La première caractéristique d’une fourmi, outre le fait d’exister (sous forme d’un nombre pour nous), c’est de ce déplacer. Mais où ? Dans la réalité, c’est dans un environnement en 3 dimensions, pour simplifier, le notre sera en deux dimensions, sans obstacles. Ce sera donc un tableau à deux dimensions.
Autre chose importante : la trace de phéromones que la fourmi laisse derrière elle, afin que les autres puissent la suivre. Ici encore, elle sera symbolisée par des nombres sur le tableau qui disparaiteront au fur et à mesure que le temps s’écoule.

Seconde chose : les éléments que la fourmi range seront des nombres, dispersés sur le tableau, et seront tous de la même taille.

Extension

Le jeu "Widelands"
Chaque point de déplacement des personnages est symbolisé par un drapeau, et les chemins entre chaque clairement visible. www.widelands.org

Plutôt qu’un tableau, on peut choisir de modéliser l’environnement de la fourmi virtuelle par une liste de points, chacun lié à ses voisins possibles. Pour faire une comparaison possible, comme une carte avec des villes reliées à d’autres par des routes.
Chaque point de n’environnement de la fourmi peut se voir attribuer une position dans l’espace (3D possible !), et chaque lien vers un point voisin peut se voir attribué une notion de longueur ou difficulté, notion qu’une fourmi virtuelle pourrait prendre en compte.
Cette modélisation est très semblable à celle utilisée pour trouver le meilleur chemin pour les transmissions internet sur la maille du réseau internet, parmis tous les chemins possibles pour aller d’un ordinateur à un autre. Chaque point du réseau a une adresse IP, et est relié aux autres par des lignes ayant un certain débit et un certain délai de traitement.
Les joueurs du jeu PC Settlers ((c) Ubisoft) verront dans le paragraphe précédent ici la méthode qui a du être utilisée par les créateurs de ce jeu. Il existe aussi Widelands (sur Linux).

Les actions de la fourmi

A partir de là, presque tout est possible et il faut analyser d’un peu plus près le comportement de la fourmi.
Une fois ce programme terminé, il sera possible de l’enrichir : paysage, blocs à transporter de taille différentes, deux colonies de fourmis qui se battent, case "fourmillière" pour y déposer plus d’un bloc...

- Deux fourmis ne pourront pas etre sur la meme case ;
- Les fourmis ne meurent pas et ne se reposent pas (où alors faites un "jeu de la vie", sujet d’une prochaine page) ;
- Pour les déplacements, nous ne considererons (pour simplifier) que les 4 direction principales, bien que comme il faut toujours essayer de faire des programmes evolutifs, nous regarderons s’il est aise de passer a 8 directions avec les algorithmes utilises. ;

- Pour les phéromones, leur durée de vie pourra etre modifiée, mais cette trace n’existera que si la fourmi transporte quelque chose, histoire d’aider (au début) la simulation, car sinon, les fourmis risquent de tourner en rond sur leurs propres traces ;

- Pour prendre un bloc, la fourmi devra etre dessus, mais ne pourra pas passer par dessus en temps normal ;
- Pour déposer un bloc, la fourmi devra etre sur une case libre ;
- Une fourmi peut porter un bloc toute seule. Ensuite, on pourra faire evoluer le programme avec des blocs plus gros.

- Si la fourmi n’a rien entre les pattes, elle erre au hasard, avec une plus faible probabilité de faire demi-tour, jusqu’à ce qu’elle trouve un bloc non rangé, ou une trace, alors elle prendra le bloc, ou suivra la trace ;
- Si la fourmi a un bloc entre les pattes, elle cherche une trace à suivre pour se rendre "au dépot" ou bien erre jusqu’à trouver un amas de bloc rangés, ou une trace ...

Où déposer et prendre les blocs ?

Jusqu’ici, c’était encore assez simple...

Mais il existe un problème de taille : où la fourmi doit-elle prendre et poser les blocs ? En effet, elle doit se débrouiller toute seule, car on ne lui indique pas les emplacement de prise et de dépose des blocs (c’est le but).
Il va donc falloir doter la fourmi d’une vision (ou odorat), pour complêter ses phéromones. C’est un peu plus compliqué.

La première solution, la plus simple est de faire regarder la fourmi (ou tater avec ses antennes, pour etre plus naturel) ce qui se trouve juste à ses abords. Si elle ne voit qu’un seul bloc, elle le prend et cherche un endroit ou elle en voie plusieurs. Le problème, c’est qu’au début, les blocs sont dispersés, et donc elle ne trouvera pas un tel endroit. Ensuite, lorsque plusieurs blocs se trouveront rangés, la fourmi, suivant les traces y arrivera, verra plusieurs blocs, posera son chargement (sur le chemin) et repartira. On risque fort de se retrouver avec une ligne de blocs infranchissables séparant l’écran en deux. C’est génant.

Voici une seconde solution, que je pense etre un peu plus proche de la realite. Puisque que tatonner à l’aveuglette est génant, la fourmi verra un peu plus loin, mais ne verra que le nombre de blocs (densité) qui l’entoure. C’est un odorat. Donc, la fourmi prendra un bloc s’il est isolé, pour aller le poser la où il y en a plus. Les blocs ne seront pas forcement rangés ’collés’ mais ils seront bien mieux regroupés. On peut alors essayer de prévoir une mémoire : emplacement et quantité de blocs rencontrés - dans un premier temps, on essayera de s’en passer.

C’est donc grace à sa vision que la fourmi s’orientera, s’il elle "voit" quelque chose d’intéressant.

Les structures de données

Alors maintenant que le problème est a peu près cerné, il faut prevoir les structures de données que nous allons utiliser. En effet le programme et l’algorithme utilisés dépendent des structures de données et pas l’inverse !

Le monde en deux dimensions sera un tableau, chaque case du tableau contiendra les informations suivantes (c’est une mémoire) :
- la présence ou non d’un bloc ;
- la densité de blocs a cet endroit ;
- la trace de phéromones laissée par les fourmis .

Les fourmis seront représentées par une liste, et pas posées dans le tableau, car sinon, pour traiter toutes les fourmis il faudrait parcourir tout le tableau, ce qui serait plus lent...
Ensuite une fourmi sera caracterisée par :
- sa position sur le tableau ;
- ce qu’elle porte ;
- éventuellement l’emplacemement des tas de blocs .
L’algorithme global
Maintenant, les choses sérieuses commencent, meme si une grosse partie du travail est faite (et pour cause, elle est essentielle !).

- Etape n°0, comme dans tout programme, les initialisations : tableau vide et pas de fourmis, pas de traces de pattes, un ’no man’s land’.

- Tout d’abord, il faut déposer les blocs et des foumis aléatoirememt sur le tableau. Il y a plusieurs méthodes, pour des résultats peut differents, que j’appelle ainsi :
* Poinconnage : on parcourt tout le tableau, choisissant a chaque case ses caractéristiques ;
* Saupoudrage : on choisit une caractéristique puis on choisit la case
* La surprise : on choisit une case au hasard, et la caractéristique aussi...

- Ensuite, comme on vient de poser des blocs, il faut calculer la densité sur tout le tableau ;

- Et alors, la simulation peut commencer. Tour à tour, on prend chacune des fourmis, et on lui fait exécuter une action... C’est le plus compliqué a mettre en oeuvre car les actions doivent se dérouler dans le bon ordre. Alors, pour ne pas se tromper, on y va étape par étape, sans s’impatienter, car au début, on teste chaque action séparement.

Une fourmi qui agit

La base des déplacements
Je passe sur les initialisations, tout le monde aura compris ce que c’est et comment faire (ou alors demandez moi). Je reviendrai sur le calcul de la densité plus tard.

Prenons une fourmi au hasard, qui se déplace au hasard. Elle peut rencontrer 3 types d’obstacles :
- un bord de son monde plat et en 2D (Galilée n’existe pas encore là-bas) ;
- un bloc ;
- une fourmi (à qui elle pourra dire bonjour, et tenter d’éliminer si elle ne fait pas partie de sa tribu, regarder comment cela se passe cet été) .
La fonction de déplacement se résume donc (pour l’instant) à :
- choisir une direction (on évite de faire demi-tour, sans éliminer cette possibilité)
- vérifier si celle direction est valable, et sinon recommencer (pas indéfiniment si possible, la fourmi peut etre bloquée, il est possible de faire une liste des directions possibles et ensuite de choisir) .

Décider les actions

Comme nous l’avons vu plus haut, la fourmi s’orientera en fonction de ce qu’elle porte, et de ce qu’elle sent. Il faut donc tenir compte de l’état d’occupation de la fourmi qui peut-etre :
- les pattes vides ;
- les pattes occupées .

1. La fourmi a les pattes vides :
Dans ce cas, il faut chercher un endroit où prendre quelque chose. Cela peut se faire, par ordre de préférence, et donc de priorité :
- s’il y a un bloc à proximité, on le prend, si la densité de blocs n’est pas trop forte ;
- en suivant une trace (vers les traces plus anciennes, vers là où se trouvent des blocs à déplacer) ;
- en se dirigeant vers les endroits où il y a plus de blocs, au risque de déplacer des blocs rangés (ce qui est contre-productif). Il faudra donc prévoir une majoration - la mémoire de la densité maximale rencontrée ? : si les blocs sont rangés, on ne les déplace pas) ;
- à tatons .

Pour l’instant, la fourmi peut porter un bloc toute seule. En realite, lorsqu’un bloc est trop lourd, elle recrute d’autres fourmis pour le porter, et ce, jusqu’a ce que le bloc soit deplacable. Cela pourra etre programme plus tard.

2. La fourmi porte un bloc :
Ici, il faut le déposer. Première chose, la fourmi doit laisser une trace derrière elle. Cela se fera en marquant la case sur laquelle elle se situe (on le verra plus tard). Voici la méthode à suivre :
- s’il y a beaucoup de blocs à proximité immédiate, on s’y dirige pour y déposer le bloc (cela évite aussi de déplacer un bloc rangé...) ;
- s’il y a une trace, on la suit en remontant ;
- sinon on essaie de se diriger vers les endroits à plus forte densité de blocs, ou à tatons .

L’odorat de la fourmi

Quand calculer la densité ?

Fourmis se battant

Un des problèmes est de calculer la densité de blocs lorsque nous en auront besoin. Il existe plusieurs solutions :
- calculer la densité à chaque fois que la fourmi en a besoin. Le temps de traitement est donc de l’ordre de O(nbr de fourmis) ;
- calculer la densité à chaque fois que celle-ci est modifiée, et enregistrer les résultats :
O(nbr de fourmis posant/prenant un bloc) . C’est un calcul incrémental, donc moins fréquent.

On sait aussi que
nbr fourmis posant/prenant un bloc < nbr fourmis se déplacant < nbr fourmis < nbr cases
et nbr blocs < nbr cases

Donc même si le nombre de fourmis manipulant des blocs est du même ordre de grandeur que le nombre total de fourmis, le choix préférable est la seconde solution.

Comment calculer la densité ?
La fourmi doit s’orienter selon les 4 directions cardinales (voire les 8), il va falloir tenir compte de cela dans les calculs. Les endroits ou il faut calculer la densite sont marques par "d", la fourmi par "F" :

              dN
         dW    F    dE
              dS

A première vue, pour calculer la densité en haut (nord), on peut calculer dN, puis dW pour l’ouest ... Seul problème, le calcul est passe deux fois sur les cases du nord-ouest. C’est génant, et de plus cet algorithme ne convient pas si on veut utiliser les 8 directions. Alors on peut faire comme ceci :

     d1    d2
        F
     d3    d4

Ici, dN= d1+d2, dW= d1+d3..., donc il y a deux fois moins de calculs que précedemment, et ces données conviennent très bien a une extension à un déplacemement dans les 8 principales directions.
Pour le calcul proprement dit, la densité c’est densité= masse de blocs / surface. Ici, les blocs sont tous identiques, ainsi que les surfaces, on se contentera de calculer le nombre de blocs a un endroit donné. Lorsqu’on voudra faire des blocs plus ou moins lourds, il y aura peu de changements à effectuer.

D’autre part, il faudra calculer la densité autour de la fourmi, afin qu’elle sache par rapport à quoi elle se dirige !

Le type de programmation

Programmation objet ?
Lorsque l’on lit ces lignes, on s’apercoit que c’est le programme qui gère les fourmis. Celles-ci n’ont pas d’individualité, et sont toutes absolument identiques. C’est un cerveau central qui les dirige et qui sait tout, comme un Dieu, à l’image des robots que nous fabriquons aujourd’hui dans les chaines de montage.
Pour se rapprocher encore de la réalite, elles devraient etre indépendantes... ce n’est pas la reine de la fourmilière qui donne les ordres ! Les constructions des fourmis sont le résultat de multiples interactions entre individus indépendants !

La programmation objet permet cette individualité des fourmis. Les fourmis seront donc des objets. Elles possederont les caractéristiques que nous avons définies, et les méthodes de gestion qui s’y rapportent (Action, Déplacer...)
Alors, il sera possible, pour une fourmi, de redéfinir sa facon de réagir, en réécrivant - partiellement - une méthode. Ce sera toujours une fourmi pour le programme qui ne verra donc pas la différence (c’est la notion d’héritage de propriétés et de méthodes chez les objets parents), et la fourmi se comportera comme on veut sans avoir eu à changer le "moteur" du programme...
- > Au lieu d’appliquer des opérations sur la fourmi, on appellera les méthodes de la fourmi, du genre "Fourmi[numero].Agit". Elle se débrouillera toute seule.

Programmation séquentielle ou multitache ?

Ouvrière fourmi

Toujours dans un souci de réalité, on constate que les fourmis sont indépendantes de leurs actions dans le temps. Elle n’agissent pas les unes après les autres.
Ici, au vu des structures de données, il faudra gérer les fourmis une par une, en suivant l’ordre du tableau. Encore peut-on choisir au hasard un certain nombre de fourmis ou dire que les actions ne sont pas toutes aussi rapides.
Sachant que les ordinateurs sont aujourd’hui capables de faire du multitache (en fait ils changent de tache très rapidement), il faut en tirer parti.
On pourrait créer un tache par fourmi, mais cela ferait trop (en général, 16 taches est le ’maximum’, surtout pour des systèmes comme Windows).

Il faut adopter la méthode utilisée pour les jeux : il existe 3 taches principales qui sont
- le calcul de la position des objets etc... (calcul de mouvement)
- l’affichage (régulier si possible)
- la prise en compte des actions de l’utilisateur (appui des touches, déplacement du point de vue...), qui permet de mettre à jour en temps réel les paramètres utilises dans les deux processus précédents. En général les jeux n’attendent pas une action du joueur pour afficher quelque chose !

La gestion des fourmis ce fera donc séquentiellement, mais indépendament de l’affichage, qui pourra se faire meme lorsque toutes les fourmis n’auront pas été activées. C’est ce qui se passe quand on déplace une fenetre ou un point de vue.
Bon. La fourmi sait maintenant choisir son déplacement et décider des actions à prendre, et comment nous allons programmer cela. On peut passer à la rédaction du programme, en écrivant l’algorithme.

Voici la suite : l’écriture de l’algorithme permettant de réaliser le programme.

Enfin, ce sera la suite lorsque j’aurai le temps d’écrire le programme ! Cela a été commencé début 1999... aujourd’hui en 2007, je l’écrirai en Java.

Les déclarations des données

Alors maintenant que le problème est a peu prés cerné, il faut prevoir les structures de données que nous allons utiliser. En effet le programme et l’algorithme utilisés dépendent des structures de données et pas l’inverse ! (Bon, d’accord, je me répète... )

Première chose, avant les données proprement dites, les valeurs servant à coder les informations. Ce sont en général des constantes. Enfin, en général, données et codage vont de pair.

Le "monde"
Nous avions dit que c’était un tableau, dont chaque case contient plusieurs informations, c’est un tableau de structures :
TInfoMonde = structure
Contenu : nombre entier ;
DensiteBlocs : nombre ;
Trace : nombre entier ;
fin
Monde = tableau[M][N] de TInfoMonde ;

Ici voici la signification des données :
Le contenu sera caractérisé par un nombre entier :
ctVide = 0 ;
ctBloc1 = 1 ;
ctBloc2 = 2 ;
ctFourmi = 4 ;

Pourquoi pas 3 pour ctFourmi ?
Parce que la fourmi doit pouvoir etre sur la case d’un bloc. Quelle serait alors la valeur de la case ? 1 ou 3 ?
Pour éviter cela, il faut se rapprocher la représentation binaire que les ordinateurs ont des nombres. Un nombre est codé en plusieurs bits, chacun représentant une puissance de 2 :

Puissance de 2 128 64 32 16 8 4 2 1
Utilisation ctFourmi ctBloc2 ctBloc1

La présence d’un bloc sera codée par 00000001 ou 00000010 (représentation binaire de ctBloc1 et 2).
Et la présence d’un fourmi et d’un bloc par 000001xx (x valant 0 ou 1). 3 est codé par 00000011...
/ !\ On constate qu’il est possible de superposer deux blocs.
La trace est un nombre entier : partant d’un maximum, cette valeur sera diminuée de 1 à chaque tour.
La densité pourra etre un nombre entier (notre cas, les blocs étant de masse fixe) ou réel.
Il y reste donc 3 constantes à déclarer (pour l’instant) :
M, N : les dimensions du monde (absicces, ordonnées) ;
TraceMax : la valeur déposée par les fourmis à leur passage.

La fourmi
Ici encore, c’est une structure de données :
TFourmi = structure
Emplacement : TPoint ;
Chargement : nombre entier ;
fin .

(je n’ai jamais terminé ! Un jour, peut-être)

Article du 1er août 2007 (51 visite(s)) - Première mise en ligne : 7 septembre 2005

Texte, photographies, séquences vidéos et code informatique de P. DELROT, sans autre but que le partage de connaissances. Merci de demander mon accord pour des utilisations commerciales ou à large diffusion. L’utilisation des codes informatiques proposés ne saurait engager ma responsabilité.



Electronique, Informatique, Professionnel



Bonne idée !Pyramide de chaussure !

Soutenez les victimes de mines antipersonnel et de BASM


Pyramide de chaussure !

44678 visites, 124 visite(s)/jour
Mis à jour le 23/02/2017 à 22:08
Version : avril 2014

© 1999-2017 Pascal DELROT

Contact / Mentions légales
Creative Commons License
Création(s) mises à disposition sous un contrat Creative Commons.

Site optimisé pour être visible

Site publié grâce à :
Site publié grâce à SPIP 3.1.6 [23598] Réalisé avec openSUSE Linux