Les Fourmis (ou the Ants)

Téléchargement du code source

Dans ce projet de TP, on se propose de simuler une planète dont chaque hémisphère serait le siège d'une colonie de fourmis. Les fourmis du nord et du sud ont la même intelligence artificielle et déposentent toutes deux des phéromones de deux types :

• lorsque la fourmis transporte de la nourriture et qu'elle recherche la colonie, elle se dirige à l'aide de phéromones de type retour et dipose des phéromones aller pour guider les autres fourmis vers les arbres.
• réciproquement, lorsque la fourmis recherche de la nourriture, elle se dirige à l'aide de phéromones de type aller et dipose des phéromones retour pour guider les autres fourmis vers la colonie.

On a séparé les deux hémisphères par une étendue d'eau infranchissable par les fourmis, située dans le plan équatorial de la planète. La quantité de nourriture totale est la même dans les deux hémisphères. Mais on a une différence de densité, celle-ci étant beaucoup plus faible au nord qu'au sud.

Utilisation

Commencez par compiler l'application :

$ cd projet
$ make clean ; make

Puis lancez une simulation, à partir de la description d'un fichier de planète au format OFF, par exemple :

$ ./ants off/satellite.off

Une fenêtre sera ouverte pour l'affichage OpenGL, permettant de suivre la progression de la simulation.
Deux fichiers ants-datas-north.txt et ants-datas-south.txt sont également créés, qui indiquent la nourriture récoltée au nord et au sud à chaque itération.

Il est possible d'accéder à des options de contrôle de l'affichage en faisant un clic droit dans la fenêtre. On peut, de la même façon, faire une pause dans la simulation en appuyant sur espace et quitter proprement la simulation en appuyant sur la touche q. Il est nécessaire de quitter de cette façon pour pouvoir retracer la progression de la simulation après-coup (voir ci-dessous).

Une fois la simulation terminée, on peut retracer les résultats sous forme d'un graph, et obtenir les effectifs finaux au nord et au sud par la commande suivante :

$ make plot ; tail -1 ants-datas-*.txt

Pour le développeur

Documentation

La référence complète du code source générée à partir des commentaires et à l'aide de doxygen est disponible.

Cibles pour make

$ make doc # pour régénérer la documentation
$ make tags # pour refaire les tags emacs

Options de débogage

De nombreuses options de débogage sont accessibles à travers une petite modification du Makefile. Leur nom correspond en général à la classe ou au fichier qu'ils permettent de déboguer. Une fois activées, elles provoquent l'affichage d'informations sur stdout et l'activation de vérifications internes supplémentaires non requises dans le cadre d'une utilisation ordinaire du proramme (vérification de la consistance de listes par exemple). En voici la liste complète :

Classe Ant

• DEBUG_ANT
• BASIC_BRAIN, active une intelligence artificielle très simple sans gestion des phéromones.

Classe Colony

• DEBUG_COLONY

Classe Land

• DEBUG_LAND

Classe Pheromone

• DEBUG_PHEROMONE

Classe Plant

• DEBUG_PLANT

Classe Portion

Du fait de la complexité relative de la classe, on a prévu plusieurs flux de débogage :

• DEBUG_PORTION
• DEBUG_PORTION_CONSTRUCTOR, plus sécifiquement consacré au constructeur
• DEBUG_PORTION_PH, pour ce qui concerne l'interaction aux phéromones
• DEBUG_PORTION_UPDATE, si on s'intéresse au processus de mises à jour itératives

Classe Water

• DEBUG_WATER

Classe World

• DEBUG_WORLD, dans le cas d'un débogage de routine
• DEBUG_WORLD_HARD, qui génère beaucoup d'output, la simulation sera très ralentie ; à réserver aux cas extrèmes donc

Fichier principal

• DEBUG_ANTS

Global

• OPTIM_ANT_BRAIN
  Active le mode batch par défaut et coupe le programme automatiquement après un nombre fixé d'itérations. A permis de générer des données rapidement pendant la phase d'ajustement et d'optimisation empirique des différents paramètres de l'intelligence artificielle.
• SF
  Pour faire rire l'assistance pendant les démonstrations

Quelques lois qui régissent le monde...

L'intelligence des fourmis

Le comportement des fourmis est déterminé par 5 paramètres :

• Moutonerie aller : la probabilité pour que la fourmis, si elle est en recherche de nourriture, suive le gradient de phéromones aller. L'alternative est qu'elle se dirige vers une parcelle aléatoire, de préférence différente de celle d'où elle vient.
• Moutonerie retour : la probabilité pour que la fourmis, si elle est à la recherche de la colonie, suive le gradient de phéromones retour. L'alternative est qu'elle se dirige vers une parcelle aléatoire, de préférence différente de celle d'où elle vient.
• Sensibilité aux phéromones : la quantité de phéromones à partir de laquelle la fourmis considère que des phéromones sont présentes sur la parcelle.
• qté phéromones aller déposées par fourmi : quelle quantité de phéromones la fourmis dépose-t-elle à chaque fois qu'elle arrive sur une parcelle, lorsqu'elle est à la recherche de la colonie.
• qté phéromones retour déposées par fourmi : quelle quantité de phéromones la fourmis dépose-t-elle à chaque fois qu'elle arrive sur une parcelle, lorsqu'elle recherche de la nourriture.

Chacune dispose par ailleurs d'un nom unique forgé à partir du numéro de la parcelle de naissance, de l'ordre de la naissance sur la parcelle, et de l'hémisphère d'origine. Ce nom peut être affiché à sa verticale, en rouge pour les fourmis du nord, et en bleu pour celles du sud. Il permet notamment de suivre une fourmi en particulier, pour peu qu'on ait pas trop de fourmis sur la planète.

Diffusion des phéromones

Les phéromones agissent comme un moyen de communication. De local, la diffusion permet d'un faire un outil de communication et de signalisation à distance. Voici comment nous l'avons implémenté :

Au hasard, parmis les 4 possibilités qui suivent :

• dans 25% des cas, un certain pourcentage des phéromones (le pourcentage de diffusion) ira au voisin #1, que ce soit un terrain, une étendue d'eau ou une colonie
• dans 25% des cas, un certain pourcentage des phéromones ira au voisin #2, que ce soit un terrain, une étendue d'eau ou une colonie
• dans 25% des cas, un certain pourcentage des phéromones ira au voisin #3, que ce soit un terrain, une étendue d'eau ou une colonie
• dans les 25% restants, on considère que les phéromones ne diffusent pas.

Puis, dans tous les cas, la quantité de phéromones est diminuée d'un certain pourcentage : le pourcentage d'extinction.

Analyse des résultats

Typiquement, l'allure des courbes de rapatriement de nourriture en fonction du temps ont l'allure suivante :

Au démarrage, les fourmis du sud sont les plus rapides, mais elles sont rapidement rejointes par les fourmis du nord qui possèdent deux arbres à proximité immédiate de la colonie.

On voit que la progression se fait par sacades au nord, palier par palier, alors que celle-ci est plus nivellée au sud, même si on peut distinguer des altérations périodiques dans la pente de la courbe.

Au sud aussi, la progression se fait paliers, mais ceux-ci sont plus rapprochés car la végétation est bien plus dense qu'au nord, et les arbres moins hauts. En fait, leur hauteur est de 25 unités de nourriture, grandeur qu'on peut retrouver par lecture graphique sur la courbe rouge : sur le segment qui va de l'itération 500 à l'itération 1500, on a 4 points d'inflexion pour une augmentation totale de 100 unités. 100 / 4 = 25 unités par arbre.

Au nord, les paliers sont plus espacés et plus marqués mais on ne peut pas retrouver la taille de l'arbre qui est de 400, car l'exploitation des deux permiers arbres est simultanée.

La courbe qui suit a été obtenue avec des paramètres différents :

moutonerie aller = 40%, moutonerie retour = 40%, seuil sensibilité aux phéromones = 1, itérations = 2500, diffusion phéromones = 10%, extinction phéromones = 5%, qté phéromones déposées par fourmi = 100, qté maximale de phéromones par parcelle = 500

On retrouve les caractéristiques précédentes, à savoir une courbe sud plus rapide au démarrage, mais rapidement dépassée par la courbe nord. Mais ici, la courbe sud rattrape et dépasse à nouveau la courbe nord autour de 2500 itérations. La tendance est encore plus clair si on calcule jusqu'à 10.000 itérations :

moutonerie aller = 40%, moutonerie retour = 40%, seuil sensibilité aux phéromones = 1, itérations = 10.000, diffusion phéromones = 10%, extinction phéromones = 5%, qté phéromones déposées par fourmi = 100, qté maximale de phéromones par parcelle = 500

On peut pousser jusqu'à 20.000 itérations :

moutonerie aller = 40%, moutonerie retour = 40%, seuil sensibilité aux phéromones = 1, itérations = 20.000, diffusion phéromones = 10%, extinction phéromones = 5%, qté phéromones déposées par fourmi = 100, qté maximale de phéromones par parcelle = 500

Après 20.000 itérations, les 50 fourmis du nord ont pu rassembler 1064 unités de nourriture, soit un peu plus de 2,5 arbres, contre 1344 (soit 53,76 arbres) au sud.

Après un départ net, la courbe nord s'infléchit autour de 600 unités de nourritures et prend une allure similaire à celle de la courbe sud. La raison est illustrée par cette capture d'écran :

Si les fourmis peuvent arriver à se placer de façon à former un chemin vers un arbre, la situation ne dure pas, car les fourmis rassasiées vont suivre les traces des fourmis en recherche de nourriture, et réciproquement. La résultante de ces deux tendances est un phénomène d'accrétion, les fourmis ayant une forte tendance à se regrouper en amas dynamiques auto-entretenus d'une certaine étendue comme en témoigne la capture suivante :

Les 6 fourmis noires sont toutes "captives" des phéromones retour déposées par la fourmis blanche. Il n'y a pas d'arbre à 10 cases à la ronde, la situation peut donc perdurer longtemps avant que l'une ou l'autre ne parvienne à s'échapper. En fait, le problème se résoud vite si la fourmis blanche parvient par hasard à grignoter un arbre. Le groupe se dissous alors rapidement du fait de la diffusion / disparition des phéromones retour et chaque fourmis va rejoindre un autre groupe d'accrétion.

On peut demander l'affichage des phéromones pour mieux se rendre compte du phénomène avec un autre exemple :

amas, sans affichage des phéromones

amas, avec affichage des phéromones aller

amas, avec affichage des phéromones retour

La prison de l'amas est faite de ce que phéromones aller et retour sont situés au même endroit, ce qui rend difficile la création d'un gradient orienté vers la colonie dans un sens, et vers les arbres dans l'autre sens, en conséquence de quoi les fourmis restent dans la région délimitée par les phéromones.

Pour éviter ce genre de comportement, on ne peut pas augmenter la part de hasard (qui est de 60%, contre 40% de moutonerie) sans perdre le comportement groupé des fourmis. A 30% de moutonerie (et 70% de comportement aléatoire donc), chacune fait bande à part, ce qui n'est pas le but recherché. A l'inverse, si on réduit ne serais-ce que légèrement (à 50% par exemple) la moutonerie, on arrive très vite à des comportements où les fourmis sont prisonières quasi-permanentes de pstructures d'amas. Au sud surtout, on observe des empilements de fourmis sur un espace très restreint situé à une dizaine de case de la colonie.

Pour remédier à ce problème, on a alors tenté d'améliorer les paramètres de l'intelligence artificielle de la fourmis et de rendre les paramètres du monde plus propice à l'apparition des comportements souhaités en expérimentant l'effet en terme de nourriture rapportée après 1250 ou 2500 itérations d'un certain de nombre de paramètres. Cette tentative est résumée dans le tableau suivant :

Optimisation "artisanale" des paramètres de la simulation en vue de maximiser la quantité de nourriture rapportée

Configuration									Résultats
Conf#	moutonerie aller	moutonerie retour	seuil sensibilité phéromones	#itérations	diffusion phéromones	extinction phéromones	Modification phéromone par fourmis	Qté max phéro. par portion	North	South
1	0,4	0,4	1,5	1250	0,1	0,05	1	55	282	398
2	0,4	0,4	1,5	1250	0,1	0,05	2	55	455	699
3	0,4	0,4	1,5	1250	0,1	0,05	4	55	727	412
4	0,4	0,4	1,5	1250	0,1	0,05	6	55	240	366
5	0,4	0,4	1,5	1250	0,25	0,05	6	55	240	366
6	0,4	0,4	1,5	1250	0,33	0,05	30	55	372	552
7	0,4	0,4	1,5	1250	0,33	0,05	30	100	669	521
8	0,4	0,4	1,5	1250	0,33	0,05	30	150	621	468
9	0,4	0,4	1,5	2500	0,33	0,05	30	100	793	658
10	0,7	0,7	1,5	1250	0,33	0,05	30	100	270	208
11	0,5	0,5	1,5	1250	0,33	0,05	30	100	93	457
12	0,3	0,3	1,5	1250	0,33	0,05	30	100	465	574
13	0,4	0,4	1,5	1250	0,33	0,05	60	200	324	600
14	0,4	0,4	1,5	2500	0,33	0,05	1500	10000	794	590
15	0,4	0,4	15	2500	0,33	0,05	1500	10000	739	600
16	0,4	0,4	1,5	2500	0,33	0,05	3000	10000	195	689
17	0,4	0,4	1,5	2500	0,33	0,05	750	10000	812	582
18	0,4	0,4	1,5	2500	0,33	0,05	320	10000	809	641
19	0,4	0,4	1,5	2500	0,33	0,05	1500	100000	842	486
20	0,4	0,4	1,5	2500	0,1	0,05	1500	100000	842	486
21	0,4	0,4	1,5	2500	0,1	0,05	150	100000	830	659
22	0,4	0,4	75	2500	0,1	0,05	150	100000	844	589
23	0,4	0,4	1	2500	0,1	0,05	100	1000	803	655
24	0,4	0,4	1	10000	0,1	0,05	100	1000	869	937
25	0,4	0,4	1	2500	0,1	0,05	100	500	577	642
26	0,4	0,4	1	10000	0,1	0,05	100	500	923	988
27	0,4	0,4	1	20000	0,1	0,05	100	750	1241	1108
28	0,4	0,4	1	20000	0,1	0,05	100	500	1064	1344
29	0,4	0,4	1	130876	0,1	0,05	100	750	2118	2612

Malheuresement, nous n'avons pu trouver le bon jeu de paramètres. Une recherche automatisée et systématique sur grille n'est sans doutes pas envisageable ici, étant donné le nombre, la variabilité et la sensibilité des paramètres ainsi que le temps de calcul nécessaire pour obtenir une simulation significative (5000 à 10.000 itérations).
Nous avons conservé le jeu de paramètres numéro 27 qui semblait donner les meilleurs résultats, et nous avons réalisé une simulation plus longue afin de voir si les fourmis parviendraient à manger toute la végétation de leur hémisphère...

moutonerie aller = 40%, moutonerie retour = 40%, seuil sensibilité aux phéromones = 1, itérations = 130876, diffusion phéromones = 10%, extinction phéromones = 5%, qté phéromones déposées par fourmi = 100, qté maximale de phéromones par parcelle = 750

La réponse est évidemment oui, mais 130876 itérations ne sont pas suffisantes avec ce jeu de paramètres.
On pourrait proposer comme solution que la fourmis passe en mode aléatoire pur, avec découragement de retour en arrière, si elle est en voyage depuis plus de n itérations. Cela lui permettrait de s'échaper des amas. Mais nous n'avons pas testé cette solution.

Nous envisagions également la mise en place d'un fichier de configuration pour centraliser les options et les initialisations de paramètres du programme à un seul endroit. Mais cela posait des problèmes de parsing que nous n'avions plus le temps de régler car l'apprentissage de lex et yacc se serait révélé trop long.

Epilogue (et fin heureuse)

En dernier recours, nous avons pensé à faire varier la quantité de phéromones déposées avec le passé immédiat de la fourmis. Une fourmis qui vient de trouver un arbre ou de rentrer à la colonie avec de la nourriture déposera soudainement beaucoup plus de phéromones qu'une fourmis en vadrouille depuis 10 itérations. On a pris une décroissance de la quantité de phéromones déposées en fonction du temps exponentielle.

En appliquant ce principe, on observe une répartition intéressante des phéromones. Celles de type aller se trouvent sous les arbres, celles de type retour sont autour de la colonie. La diffusion aidant, il se crée des bassins d'attractions qui orientent les fourmis dans la bonne direction.

Le résultat en terme de nourriture rapportée est bien meilleur, comme peut en témoigner le graph suivant :

Dans cette configuration, la nourriture dans les deux hémisphères a été consommée en 31936 itérations, avec beaucoup de temps nécessaire à la dernière fourmis pour trouver son chemin jusqu'à la colonie dû au manque de fourmis potentiellement capables de la guider.

On remarque que l'equi-répartition de la nourriture au nord et au sud n'a pas été respecté. Cela tient à la méthode utilisée pour la répartir qui se fonde sur une probabilité et n'assure que l'égalité des espérances mathématiques. Avec un nombre aussi faible d'arbres, la loi des grands nombres n'est pas respectée, il faudrait revoir ce point.

On peut aussi délimiter trois régions sur la courbe. Un début où la dérivée est importante et décroit jusqu'à devenir constante (après 1000 itération). A ce stade, les arbres à proximité de la colonie ont été consommé et le véritable mécanisme se met en marche.
Entre 1000 et 19000 itérations, on a un domaine quasi-linéaire (plus vrai au sud qu'au nord), ce qui est un résultat surprenant. Il indique que la quantité de nourriture rapportée en fonction du temps est constante (0.1879 unités de nourriture par itération, selon une regression linéaire effectuée entre 1000 et 20000 itérations au sud) et donc indépendante de la distance de la nourriture qui va en augmentant, tant qu'il reste plus d'une certaine quantité de nourriture.
Enfin, après 20000 itérations au sud ou 25000 au nord, la courbe s'applatit puisqu'il ne reste plus de nourriture dans l'hémisphère.