Introduction : Problématique et Programmation Émergente - Free

UNIVERSITé TOULOUSE III - PAUL SABATIER
U.F.R. Mathématiques, Informatique et Gestion. THESE
Pour obtenir le grade de
Docteur de l'université Toulouse III
Discipline : Informatique Présentée et soutenue par Jean-Pierre Georgé
Le 6 juillet 2004
Résolution de problèmes par émergence Étude d'un Environnement de Programmation Émergente
JUry Claudette Cayrol, Professeur, Université Paul Sabatier Présidente du jury,
François Charpillet, Directeur de recherche INRIA, Rapporteur,
Philippe Mathieu, Professeur, Université de Lille 1 Rapporteur,
Pierre Glize, Ingénieur CNRS Habilité, Directeur de thèse,
Marie-Pierre Gleizes, Maître de conférence, Université Paul Sabatier Co-
encadrante,
Jean-Pierre Georgé Résolution de problèmes par émergence Étude d'un Environnement de Programmation Émergente
Directeur de thèse :
Pierre Glize, Ingénieur de recherche CNRS, HDR,
IRIT
- Résumé - Nous proposons la réalisation d'un Environnement de Programmation
Emergente, permettant de concevoir des systèmes complexes adaptatifs afin
de répondre au problème de complexité croissante de la programmation, au
problème du dynamisme du système et de l'environnement, ainsi qu'à la
méconnaissance du problème et de la solution. Pour cela, nous utilisons
comme bases le concept de l'émergence et la technologie des systèmes multi-
agents dont le fonctionnement repose sur des mécanismes d'Auto-organisation
coopératifs conformes à la théorie AMAS (Adaptive Multi-Agent Systems). L'objectif général est alors de réaliser un langage complet de
programmation dans lequel chaque instruction est un agent autonome
cherchant à être coopératif avec les autres agents du système, ainsi
qu'avec l'environnement du système. En dotant ces agents-instructions de
mécanismes d'Auto-organisation, nous obtenons un système capable de
s'adapter continuellement à la tâche requise par le programmeur (i.e. de
s'auto-programmer suivant les besoins). Le travail présenté dans ce
document montre la faisabilité d'un tel concept en spécifiant, puis en
soumettant à expérimentation, un noyau consacré à un sous-ensemble du
calcul mathématique. Parallèlement, cette approche par Emergence est généralisée à tout type
de résolution de problèmes. Nous proposons une réflexion sur les
caractéristiques particulières du problème de la programmation émergente en
particulier et des problèmes traitables par auto-organisation en général.
Nous définissons alors un cadre strict pour l'utilisation des mécanismes de
réorganisation afin que ceux-ci permettent l'apparition de ce phénomène si
particulier, l'émergence.
Mots Clés : Systèmes Multi-Agents, adaptation, émergence, systèmes
complexes, auto-organisation, programmation, résolution de problèmes.
IRIT,
Université Paul Sabatier, 118 route de Narbonne, 31062 Toulouse Cedex 4.
Mes remerciements ...
à Pierre Glize, Ingénieur CNRS Habilité rattaché à l'IRIT, mon
directeur de thèse. Il n'y avait malheureusement que la place pour
mon nom au milieu de la première page de ce document, mais je
considère ce travail comme le fruit d'une réelle coopération et il
t'appartient autant qu'à moi (c'est-à-dire pas du tout puisqu'il
appartient désormais à la Science...). Dire que ce travail n'aurait
pu aboutir sans toi ne décrit pas à sa juste valeur tout le temps
que tu as consacré à ce travail, que tu m'as consacré. Tes
conseils, tes idées et nos discussions (ainsi que ton humour) ont
été un guide tout au long de ces années.
à Marie-Pierre Gleizes, Maître de Conférence à l'Université
Paul Sabatier, ma co-encadrante. Parmi les souvenirs les plus
fort au cours de ma thèse se trouvent indéniablement les nombreuses
réunions à trois où l'intense échange d'idées nous faisait explorer
des voies auxquelles nous n'aurions pu penser séparément, à l'image
du monde de la recherche. Et c'est ce que tu as été pour moi
pendant ces années à partager ton bureau : l'image de l'enseignant-
chercheur, concrètement, au-delà de mon imaginaire d'étudiant. Plus
que toute autre personne, tu m'as appris ce métier si particulier.
à Claudette Cayrol, Professeur à l'Université Paul Sabatier,
présidente du jury. Je vous remercie d'avoir accepté spontanément
de faire partie de mon jury, de l'avoir présidé consciencieusement
et surtout d'avoir montré autant d'intérêt pour mon document de
thèse.
à François Charpillet et Philippe Mathieu, respectivement
Directeur de recherche INRIA à Nancy et Professeur à l'Université
de Lille 1, rapporteurs. Quand l'Homme est jugé, il ne peut
qu'espérer en l'honnêteté, l'intégrité et la compétence de ses
juges. Je pense sincèrement n'avoir eu aucun souci à me faire quant
aux miens et je vous en suis très reconnaissant. De plus, le réel
intérêt scientifique que vous avez porté à mon travail, et ce
malgré les délais contraignants que vous avez bien voulu accepter,
a contribué à rasséréner cette période difficile pour tout
doctorant.
à Jean-Luc Soubie, Ingénieur de recherche INRIA Habilité,
rattaché à l'IRIT, mon ex-directeur de thèse pour raisons
administratives. Plus que le fait d'avoir bien voulu être mon
directeur sur le papier au début de ma thèse, c'est le regard sur
la recherche au-delà de l'équipe que je voudrais évoquer ici. Tu
m'as permis de mieux appréhender le dédale du monde de la recherche
et ses coulisses (le "panier à crabes" ?) grâce à ton honnêteté et
ta franchise.
à l'équipe SMAC et en particulier Gauthier Picard, Davy Capera,
Jean-Pierre Mano, Carole Bernon, Valérie Camps, Christine Régis et
André Machonin. Vous m'avez offert des conditions de travail et un
environnement de tous les jours si appréciables. C'est cet ensemble
de multiple petites choses que l'on remarque ou non, ces conseils
et ces discussions, scientifiques et autres, qui ont fait que même
en de périodes difficiles, mon lieu de travail est toujours resté
agréable.
à mes amis David Fauthoux, David Chemouil, Ulrich Roissard,
Vincent Labatut, Gauthier Picard et Davy Capera (pour ces deux
dernier, oui, on peut être dans deux catégories à la fois,
mélangeons donc le plaisir et le travail). On ne peut espérer
atteindre une plénitude professionnelle sans l'équilibrer avec un
épanouissement personnel. Et vous avez su, sciemment ou
inconsciemment, constamment agir sur la balance, que ce soit d'un
côté ou de l'autre (vous la relierez deux fois, celle-là...).
à ma famille, Gitti, Nico et Saskia, Oma und Opa. Ich weis dass
ihr immer an meinem erfolg geklaubt habt und ihr habt mir die
Möglichkeit geschenkt mein Traum zu realisieren. Eine bessere
Familie hätte ich mir nicht wünschen können. Danke für alles.
à Émilie. Ce document te doit une bonne part de sa clarté et de
sa qualité d'écriture. Les lecteurs apprécieront. Moi j'ai apprécié
la façon dont tu as su te faire une place dans ma vie de doctorant
surchargé d'activités pour finir par te rendre indispensable. Sommaire (vue d'ensemble) Introduction : Problématique et Programmation Émergente 15 1. Problématique 15
2. Description de l'idée de "programmation émergente" 18
3. Généralisation : la résolution de problèmes par émergence 20
4. Structure et contenu du document 22 Chapitre I. Le phénomène d'émergence et son utilisation 27 1. Émergence 27
2. Auto-organisation et systèmes multi-agents 41
3. Techniques diverses 52 Chapitre II. Théorie AMAS Technologie AMAS 73 1. Introduction aux travaux de l'équipe 73
2. La théorie AMAS 76
3. La Technologie AMAS 81
4. Vers une distribution industrielle : la méthodologie ADELFE 86
5. L'apport de mes travaux dans l'approche AMAS 89
6. Étude et discussion de quelques applications AMAS 92 Chapitre III. EPE : Environnement de Programmation Émergente 107 1. La programmation émergente : introduction et description détaillée 107
2. Le "Toy Problem" de la Factorielle : un sous-problème représentatif
124
3. Résultats expérimentaux et analyse des organisations 153
4. Comportements d'auto-organisation coopératifs informés dans un système
élémentaire 171 Chapitre IV. PE : implémentation 191 1. Introduction 191
2. Architecture 196
3. Le logiciel EPE 208 Conclusion : Enseignements et Perspectives 213 1. De l'Expérience aux Enseignements 213
2. Perspectives 218
3. Ma conclusion 224 Glossaire 227
Bibliographie 231 1. Problématique 231
2. Emergence 232
3. Auto-organisation et systèmes multi-agents 234
4. Techniques diverses 237
5. Théorie AMAS - Technologie AMAS 240
6. EPE et la Programmation Émergente 242
Sommaire (v