ii
Les Systèmes Multi Agents: vers une intelligence
collective
Jacques Ferber
1995
ii
Contents
Pr eface
Avant-propos
xiii
1
1 Principes des systèmes multi-agents
1.1.1 De la machine pensante...
1.1.2
1.1 Pour une intelligence collective . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
... à lorganisation articielle . . . . . . . . . . . . . . . . . . .
5
5
5
7
1.2 Agent et soci et e . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.2.1 Quelques d enitions
. . . . . . . . . . . . . . . . . . . . . . . 12
1.2.2 Niveaux dorganisation . . . . . . . . . . . . . . . . . . . . . . 17
Social ou biologique? . . . . . . . . . . . . . . . . . . . . . . . 19
1.2.3
1.2.4 Architecture et comportement . . . . . . . . . . . . . . . . . . 24
1.2.5 Langages, communications et repr esentations . . . . . . . . . . 25
1.3 Un peu dhistoire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
1.3.1 Les premiers ages . . . . . . . . . . . . . . . . . . . . . . . . . 28
1.3.2 L age classique
. . . . . . . . . . . . . . . . . . . . . . . . . . 29
1.3.3 Linuence de la vie articielle . . . . . . . . . . . . . . . . . . 31
. . . . . . . . . . . . . . . . . . . . . . . 32
1.3.4 Les temps modernes
1.4 Domaines dapplication . . . . . . . . . . . . . . . . . . . . . . . . . . 34
1.4.1 La r esolution de problèmes . . . . . . . . . . . . . . . . . . . . 34
. . . . . . . . . . . . . . . . . . . . 38
1.4.2 La simulation multi-agent
1.4.3 La construction de mondes synth etiques
. . . . . . . . . . . . 43
1.4.4 La robotique distribu ee . . . . . . . . . . . . . . . . . . . . . . 50
. . . . . . . . . . . . 52
1.4.5 La conception k en etique de programmes
1.5 Les grands thèmes de la k en etique . . . . . . . . . . . . . . . . . . . . 54
1.5.1 La probl ematique de laction . . . . . . . . . . . . . . . . . . . 54
1.5.2 Lindividu et sa relation au monde
. . . . . . . . . . . . . . . 54
1.5.3 Linteraction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
1.5.4 Ladaptation . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
1.5.5 La r ealisation et limpl ementation des SMA . . . . . . . . . . 56
. . . . . . . . . . . . . . 56
1.6.1 Lintelligence articielle
. . . . . . . . . . . . . . . . . . . . . 57
1.6.2 La syst emique . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
1.6.3 Les systèmes distribu es . . . . . . . . . . . . . . . . . . . . . . 58
1.6 Domaines voisins des systèmes multi-agents
v
vi
CONTENTS
. . . . . . . . . . . . . . . . . . . . . . . . . . . 60
1.6.4 La robotique
1.6.5 Ce qui ne relève pas de la k en etique . . . . . . . . . . . . . . . 60
2 Interactions et coop eration
63
2.1 Situations dinteraction . . . . . . . . . . . . . . . . . . . . . . . . . . 63
. . . . . . . . . . . . . . . . . . . . . . 65
2.2 Composantes des interactions
2.2.1 Buts compatibles et incompatibles . . . . . . . . . . . . . . . . 65
2.2.2 Relations aux ressources . . . . . . . . . . . . . . . . . . . . . 67
2.2.3 Capacit es des agents par rapport aux t aches . . . . . . . . . . 68
2.3 Types dinteraction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
Ind ependance . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
2.3.1
2.3.2 Collaboration simple . . . . . . . . . . . . . . . . . . . . . . . 70
. . . . . . . . . . . . . . . . . . . . . . . . . . 70
2.3.3 Encombrement
2.3.4 Collaboration coordonn ee
. . . . . . . . . . . . . . . . . . . . 70
2.3.5 Comp etition individuelle pure . . . . . . . . . . . . . . . . . . 71
2.3.6 Comp etition collective pure
. . . . . . . . . . . . . . . . . . . 71
2.3.7 Conit individuel pour des ressources . . . . . . . . . . . . . . 71
2.3.8 Conits collectifs pour des ressources . . . . . . . . . . . . . . 71
2.3.9 Niveau danalyse des situations dinteraction . . . . . . . . . . 72
2.4 Formes de coop eration . . . . . . . . . . . . . . . . . . . . . . . . . . 74
2.4.1 La coop eration comme attitude intentionnelle . . . . . . . . . 74
2.4.2 La coop eration du point de vue de lobservateur . . . . . . . . 75
2.4.3 Lam elioration de la survie . . . . . . . . . . . . . . . . . . . . 78
2.4.4 Laccroissement des performances . . . . . . . . . . . . . . . . 79
2.4.5 La r esolution de conit . . . . . . . . . . . . . . . . . . . . . . 81
2.5 Les m ethodes de coop eration . . . . . . . . . . . . . . . . . . . . . . . 82
2.5.1 Le regroupement et la multiplication . . . . . . . . . . . . . . 82
2.5.2 La communication . . . . . . . . . . . . . . . . . . . . . . . . 83
2.5.3 La sp ecialisation . . . . . . . . . . . . . . . . . . . . . . . . . 84
2.5.4 La collaboration par partage de t aches et de ressources . . . . 84
2.5.5 La coordination dactions
. . . . . . . . . . . . . . . . . . . . 85
2.5.6 La r esolution de conit par arbitrage et n egociation . . . . . . 85
2.6 Organisations et coop eration . . . . . . . . . . . . . . . . . . . . . . . 86
2.6.1 Le système des activit es de coop eration . . . . . . . . . . . . . 86
2.6.2 Avantages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
2.6.3 Contraintes sociales et emergences de structures . . . . . . . . 89
3 Organisations multi-agents
91
3.1 Quest-ce quune organisation? . . . . . . . . . . . . . . . . . . . . . . 91
3.1.1
Structures organisationnelles et organisations concrètes . . . . 92
3.1.2 Les niveaux dorganisation . . . . . . . . . . . . . . . . . . . . 93
3.1.3 Comment etudier une organisation? . . . . . . . . . . . . . . . 94
3.2 Lanalyse fonctionnelle . . . . . . . . . . . . . . . . . . . . . . . . . . 95
3.2.1 Les fonctions dune organisation . . . . . . . . . . . . . . . . . 95
3.2.2 Les dimensions danalyse . . . . . . . . . . . . . . . . . . . . . 99
CONTENTS
vii
3.2.3 Analyse dimensionnelle dune organisation . . . . . . . . . . . 100
3.2.4 Grille danalyse fonctionnelle des organisations . . . . . . . . . 106
3.3 Lanalyse structurale . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
. . . . . . . . . . . . . . . . . . . . . . . . . 110
3.3.1 Agents et t aches
3.3.2 Relations abstraites . . . . . . . . . . . . . . . . . . . . . . . . 115
3.3.3 Les modes de couplage . . . . . . . . . . . . . . . . . . . . . . 116
3.3.4
Structures de subordination et prises de d ecision . . . . . . . . 117
3.3.5 Types de constitution des structures organisationnelles . . . . 118
3.4 Les paramètres de concr etisation . . . . . . . . . . . . . . . . . . . . 119
3.5 Analyse dune organisation concrète . . . . . . . . . . . . . . . . . . . 122
3.5.1 Lexemple des robots explorateurs . . . . . . . . . . . . . . . . 123
3.5.2 Organisations à structure xe-hi erarchique-pr ed enie . . . . . 125
3.5.3 Organisations à structure variable- egalitaire- emergente . . . . 126
. . . . 127
3.5.4 Organisations à structure variable- egalitaire-pr ed enie
3.5.5 Organisations à structure evolutive . . . . . . . . . . . . . . . 127
3.5.6 Autres travaux sur les organisations . . . . . . . . . . . . . . . 128
3.6 Organisations individuelles . . . . . . . . . . . . . . . . . . . . . . . . 129
3.6.1 Tableau des principales architectures . . . . . . . . . . . . . . 130
3.6.2 Architecture modulaire horizontale . . . . . . . . . . . . . . . 131
3.6.3 Les architectures à base de tableaux noirs
. . . . . . . . . . . 132
3.6.4 Larchitecture de subsomption . . . . . . . . . . . . . . . . . . 135
3.6.5 Les t aches comp etitives . . . . . . . . . . . . . . . . . . . . . . 136
3.6.6 Les systèmes de production . . . . . . . . . . . . . . . . . . . 137
3.6.7 Les systemes a base de classieurs . . . . . . . . . . . . . . . . 139
3.6.8 Les architectures connexionistes . . . . . . . . . . . . . . . . . 140
3.6.9 Les architectures a base de systeme dynamique
. . . . . . . . 142
3.6.10 Architectures multi-agents et acteurs . . . . . . . . . . . . . . 144
Publicité
4 Action et comportement
4.2 Laction comme transformation dun etat global
147
4.1 La mod elisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147
4.1.1 Des modèles... . . . . . . . . . . . . . . . . . . . . . . . . . . . 147
... et de leur utilit e pour les SMA . . . . . . . . . . . . . . . . 148
4.1.2
4.1.3 Que mod eliser? . . . . . . . . . . . . . . . . . . . . . . . . . . 149
4.1.4 Agents et actions: des notions faussement el ementaires
. . . . 149
4.1.5 Mod eliser laction . . . . . . . . . . . . . . . . . . . . . . . . . 151
. . . . . . . . . . . . 152
4.2.1 Une repr esentation fonctionnelle de laction . . . . . . . . . . 152
4.2.2 Les op erateurs de type STRIPS . . . . . . . . . . . . . . . . . 153
4.2.3 Planier avec des op erateurs de type STRIPS . . . . . . . . . 155
4.2.4 Quelques cat egories de plans . . . . . . . . . . . . . . . . . . . 158
4.2.5 Limites des planicateurs de type STRIPS . . . . . . . . . . . 160
4.2.6 Limites des repr esentations classiques de laction . . . . . . . . 161
. . . . . . . . . . . . . . . . 164
4.3.1 Pr esentation g en erale . . . . . . . . . . . . . . . . . . . . . . . 164
4.3.2 Les etats . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165
4.3 Laction comme r eponse à des inuences
viii
CONTENTS
4.5 Laction comme d eplacement physique
4.5.1 D eplacements dans un champ de potentiel
4.5.2
4.3.3 Actions et r eactions . . . . . . . . . . . . . . . . . . . . . . . . 166
Int er et du modèle inuences/r eactions pour les SMA . . . . . 168
4.3.4
4.4 Laction comme processus informatique . . . . . . . . . . . . . . . . . 169
4.4.1 Repr esentation de processus par automates à etats nis . . . . 171
4.4.2 Automates à registres . . . . . . . . . . . . . . . . . . . . . . . 174
4.4.3 Repr esentation de processus par r eseaux de Petri
. . . . . . . 176
4.4.4 Autres modèles ev enementiels . . . . . . . . . . . . . . . . . . 182
. . . . . . . . . . . . . . . . . 182
. . . . . . . . . . . 184
Int er et de cette conception de laction . . . . . . . . . . . . . . 186
4.6 Laction comme modication locale . . . . . . . . . . . . . . . . . . . 187
4.6.1 Les automates cellulaires . . . . . . . . . . . . . . . . . . . . . 188
4.6.2 Repr esentation dun automate cellulaire
. . . . . . . . . . . . 189
4.6.3 Automates cellulaires et systèmes multi-agents . . . . . . . . . 190
4.7 Laction comme commande . . . . . . . . . . . . . . . . . . . . . . . . 191
4.8 Agents tropiques et hyst er etiques
. . . . . . . . . . . . . . . . . . . . 192
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 194
4.9 Agents tropiques
. . . . . . . . . . . . . . . . . . . . . . . . 194
4.9.1 Approche formelle
. . . . . . . . . . . . . . . . 194
4.9.2 Un système multi-agent tropique
. . . . . . . . . . . . . . . 195
4.9.3 Agents tropiques et actions situ ees
Souplesse des actions situ ees . . . . . . . . . . . . . . . . . . . 200
4.9.4
4.9.5 Les buts sont dans lenvironnement . . . . . . . . . . . . . . . 202
. . . . . . . . . . . . . . . . . . . . . . . . . . . 206
4.10.1 Approche formelle
. . . . . . . . . . . . . . . . . . . . . . . . 206
4.10.2 Un système multi-agent hyst er etique . . . . . . . . . . . . . . 207
. . . . . . 207
4.10.3 Mod elisation dagents hyst er etiques par automates
4.11 Mod elisation de SMA en BRIC . . . . . . . . . . . . . . . . . . . . . 209
. . . . . . . . . . . . 209
4.11.1 D ecrire des SMA à laide de composants
4.11.2 Mod elisation de SMA purement communicants . . . . . . . . . 211
. . . . . . . . . . . . . . . . 212
4.11.3 Mod elisation des environnements
4.11.4 Mod elisation dun SMA situ e
. . . . . . . . . . . . . . . . . . 218
4.11.5 Mod elisation dun SMA complet . . . . . . . . . . . . . . . . . 220
4.11.6 Un exemple: les agents transporteurs . . . . . . . . . . . . . . 221
4.10 Agents hyst er etiques
5 Lagent dans tous ses etats
225
5.1 Etats mentaux et intentionnalit e . . . . . . . . . . . . . . . . . . . . . 225
5.1.1
Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 225
5.1.2 La notion de cogniton . . . . . . . . . . . . . . . . . . . . . . 227
5.1.3 Une nomenclature des cognitons . . . . . . . . . . . . . . . . . 228
5.2 Le système interactionnel . . . . . . . . . . . . . . . . . . . . . . . . . 231
5.3 Le système repr esentationnel . . . . . . . . . . . . . . . . . . . . . . . 233
5.3.1 Quest-ce que la connaissance? . . . . . . . . . . . . . . . . . . 233
5.3.2 Repr esenter les connaissances et les croyances
. . . . . . . . . 240
5.3.3 Logiques des savoirs et des croyances . . . . . . . . . . . . . . 246
5.3.4 Ad equation et r evision des croyances . . . . . . . . . . . . . . 255
CONTENTS
ix
5.5 Le système conatif
5.4 Que croire? Les contenus des repr esentations . . . . . . . . . . . . . . 263
. . . . . . . . . . . . . . . . 264
5.4.1 Croyances environnementales ( )
5.4.2 Croyances sociales ( )
. . . . . . . . . . . . . . . . . . . . . . 265
5.4.3 Croyances relationnelles ( ) . . . . . . . . . . . . . . . . . . . 265
5.4.4 Croyances personnelles ( ) . . . . . . . . . . . . . . . . . . . . 268
. . . . . . . . . . . . . . . . . . . . . . . . . . . . 268
5.5.1 Rationalit e et survie . . . . . . . . . . . . . . . . . . . . . . . 269
5.5.2 Un modele du systeme conatif . . . . . . . . . . . . . . . . . . 271
5.6 Les motivations: les sources de laction . . . . . . . . . . . . . . . . . 273
5.6.1 Les motivations personnelles: plaisir et contraintes . . . . . . . 274
5.6.2 Les motivations environnementales: le d esir de lobjet . . . . . 275
5.6.3 Les motivation sociales: le poids de la soci et e . . . . . . . . . . 276
5.6.4 Les motivations relationnelles: la raison cest les autres . . . . 278
5.6.5 Les engagements: des motivations et contraintes relationnelles
5.7 Le passage à lacte r eactif
et sociales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 279
. . . . . . . . . . . . . . . . . . . . . . . . 284
5.7.1 Actes consommatoires et comportements app etitifs
. . . . . . 285
5.7.2 Modes de s election et de contr ole des actions . . . . . . . . . . 286
. . . . . . . . . 294
5.7.3
5.8 Passages à lacte intentionnels . . . . . . . . . . . . . . . . . . . . . . 298
5.8.1 Th eories logiques de lintention . . . . . . . . . . . . . . . . . 299
5.8.2 La th eorie de laction rationnelle de Cohen et Levesque . . . . 301
S election daction ou combinaison dynamique
6 Communications
6.2 Les actes de langage
309
6.1 Aspects de la communication . . . . . . . . . . . . . . . . . . . . . . 309
6.1.1
Signes, indices et signaux . . . . . . . . . . . . . . . . . . . . . 309
6.1.2 D enition et modèles de communication . . . . . . . . . . . . 310
6.1.3 Cat egories de communication . . . . . . . . . . . . . . . . . . 312
6.1.4 A quoi sert la communication? . . . . . . . . . . . . . . . . . . 317
. . . . . . . . . . . . . . . . . . . . . . . . . . . 320
6.2.1 Dire, cest faire . . . . . . . . . . . . . . . . . . . . . . . . . . 320
6.2.2 Actes locutoires, illocutoires et perlocutoires . . . . . . . . . . 322
Succès et satisfaction . . . . . . . . . . . . . . . . . . . . . . . 323
6.2.3
. . . . . . . . . . . . . . . 325
6.2.4 Composantes des actes illocutoires
6.3 Les conversations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 326
. . . . . . . . . . . . 328
. . . . . . . . . . . . . . . . 329
6.3.1 Conversations et automates à etats nis
6.3.2 Conversations et r eseaux de Petri
6.3.3 Une classication des actes de langage pour des structures
. . . . . . . . . . . . . . . . . 330
6.4 KQML . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 338
conversationnelles multi-agents
7 Collaboration et r epartition des t aches
343
7.1 Modes dallocation des t aches . . . . . . . . . . . . . . . . . . . . . . 343
Publicité
7.1.1 Critères de d ecomposition des t aches . . . . . . . . . . . . . . 344
7.1.2 R oles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 344
x
CONTENTS
7.4
7.1.3 Formes dallocation . . . . . . . . . . . . . . . . . . . . . . . . 345
7.2 Allocation centralis ee des t aches par m ediateur . . . . . . . . . . . . . 346
7.3 Allocation distribu ee des t aches . . . . . . . . . . . . . . . . . . . . . 350
. . . . . . . . . . . . . . 350
7.3.1 Allocation par r eseau daccointances
7.3.2 Allocation par appel dore: le r eseau contractuel
. . . . . . . 361
7.3.3 Variantes et allocations hybrides . . . . . . . . . . . . . . . . . 376
7.3.4 Contrats et engagements . . . . . . . . . . . . . . . . . . . . . 378
Int egrer les t aches et les etats mentaux . . . . . . . . . . . . . . . . . 379
7.4.1 Le système SAM . . . . . . . . . . . . . . . . . . . . . . . . . 379
7.4.2 La hi erarchie des architectures . . . . . . . . . . . . . . . . . . 380
7.4.3 Les r esultats . . . . . . . . . . . . . . . . . . . . . . . . . . . . 381
7.4.4 Limpl ementation des architectures . . . . . . . . . . . . . . . 383
7.4.5 Le niveau 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 383
7.4.6 Le niveau 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 384
7.4.7 Le niveau 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 385
7.5 Allocation emergente . . . . . . . . . . . . . . . . . . . . . . . . . . . 388
7.6 Un exemple: le système Manta . . . . . . . . . . . . . . . . . . . . . . 391
. . . . . . . . . . . . . . . . . . . . . . . 391
7.6.1 Description g en erale
7.6.2 Larchitecture du système . . . . . . . . . . . . . . . . . . . . 391
7.6.3 Les exp erimentations . . . . . . . . . . . . . . . . . . . . . . . 394
7.6.4 Des fourmis aux robots fourmis . . . . . . . . . . . . . . . . . 397
8 Coordination dactions
8.2.1
8.2.2
8.1 Quest-ce que la coordination dactions?
399
. . . . . . . . . . . . . . . . 399
8.1.1 D enitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 400
8.1.2 La coordination comme r esolution de problème
. . . . . . . . 402
8.1.3 Caract eristiques des systèmes de coordination . . . . . . . . . 405
8.1.4 Formes de coordination daction . . . . . . . . . . . . . . . . . 409
8.2 Synchronisation dactions . . . . . . . . . . . . . . . . . . . . . . . . . 411
Synchronisation de mouvements . . . . . . . . . . . . . . . . . 411
Synchronisation dacces a une ressource . . . . . . . . . . . . . 411
8.3 Coordination dactions par planication . . . . . . . . . . . . . . . . . 413
8.3.1 Planication multi-agent . . . . . . . . . . . . . . . . . . . . . 415
8.3.2 Planication centralis ee pour agents multiples . . . . . . . . . 419
. . . . . . . . . . 421
8.3.3 Coordination centralis ee pour plans partiels
8.3.4 Coordination distribu ee pour plans partiels . . . . . . . . . . . 427
8.4 Coordination r eactive . . . . . . . . . . . . . . . . . . . . . . . . . . . 432
8.4.1 Coordination par actions situ ees . . . . . . . . . . . . . . . . . 432
. . . 433
8.4.2 Du comportement de meute aux systèmes anti-collisions
8.4.3 Marquage de lenvironnement
. . . . . . . . . . . . . . . . . . 438
8.4.4 Actions de coordination . . . . . . . . . . . . . . . . . . . . . 444
8.5 R esolution par coordination : l eco-r esolution . . . . . . . . . . . . . . 446
8.5.1 Principes de l eco-r esolution . . . . . . . . . . . . . . . . . . . 447
8.5.2 Les eco-agents . . . . . . . . . . . . . . . . . . . . . . . . . . . 448
8.5.3 Exemples simples d eco-problèmes . . . . . . . . . . . . . . . . 450
CONTENTS
xi
. . . . . . . . . . . . . . . . . . . . . . . . . 459
8.5.4 Univers evolutifs
8.5.5 Formalisation . . . . . . . . . . . . . . . . . . . . . . . . . . . 461
8.5.6 R esolution de contraintes par eco-r esolution . . . . . . . . . . 462
9 Conclusion
465
A BRIC
469
A.1 Les composants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 469
. . . . . . . . . . . . . . . . . . . . . . . . . 470
A.2 Composants composites
A.3 Constitution des composants el ementaires
. . . . . . . . . . . . . . . 470
A.4 Liens de communication . . . . . . . . . . . . . . . . . . . . . . . . . 472
A.5 Conventions de notations et equivalences . . . . . . . . . . . . . . . . 472
A.6 Traduction sous forme de r eseaux de Petri
. . . . . . . . . . . . . . . 473
A.7 Exemple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 473
R ef erences bibliographiques
Index
475
493
xii
CONTENTS
Pr eface
Ce livre r epond a un besoin: celui de donner un contenu informatique pr ecis a
lexpression système multi-agents. Quelles notions, quelles tendances, quelles pos-
sibilit es nouvelles se cachent sous ce terme à la mode? Cest avant tout une ques-
tion de mod elisation. Les langages actuels obligent les programmeurs dapplications
a d ecrire les ph enomenes quils traitent dune manière strictement m ecaniste et
hi erarchis ee. On arrive tout au plus a b atir une application a partir de mod-
ules construits ind ependamment comme un immeuble moderne fait d el ements
pr efabriqu es au lieu de pierres taill ees sur place. Le processus est parfait pour un pro-
gramme traitant du fonctionnement dun immeuble. Mais quid de la vie de ses habi-
tants? La belle ordonnance qui explique, par exemple, la structure complexe dun
etage comme une composition de pièces et de parois r eput ees plus simples na man-
ifestement plus cours. Il faut prendre en compte lind ependance op erationnelle des
individus (et non plus seulement leur ind ependance conceptuelle), les ph enomènes
de communication, de libre arbitre, de croyance, de concurrence, de consensus et
aussi de discorde. Cela nest pas chose facile. Rien cependant n echappe à lapp etit
des ordinateurs! La repr esentation en machine de b atiments, dimmeubles, voire de
cit es entieres etant a peu près devenue chose courante (demandez aux architectes),
il sagit maintenant de sattaquer aux etre humains et aux soci et es qui habitent ces
lieux. Comment va-t-on proc eder? Les systèmes multi-agents bien s ur...
Plusieurs forces sont sans doute a lSuvre derriere cette evolution. Je crois que
la mont ee du lib eralisme et de lindividualisme à lam ericaine nous poussent plus
fortement que jamais à vouloir mod eliser toute situation un tant soit peu complexe en
termes economiques de concurrence et de march e. Ce faisant, nous avons tendance à
privil egier les modèles informatiques mettant en jeu les m emes concepts. On peut lire
le m eme mouvement did ees dun Sil plus optimiste, parler dune salutaire tendance
à la d ecentralisation, dun utile correctif au jacobinisme ou invoquer les richesses
de la cr eation collective. Dans un sens comme dans lautre, notre epoque se veut
plurielle et il nest pas surprenant que cette id eologie cherche à se re eter jusque
dans les modèles informatiques de la r ealit e. Les machines evoluent dans le m eme
sens que les id ees: la mont ee des architectures parallèles et des r eseaux a d etr on e le
processeur unique, image dèle du cerveau unique et de ladministration centralis ee.
La aussi, place au pluralisme et a la concurrence!
Comme toujours, il y a loin de la coupe aux lèvres. La t ache des sp ecialistes
de systemes multi-agents et dintelligence articielle distribu ee (deux manieres de
d esigner la m eme communaut e) est dune part de trouver les bonnes manières
de ma 1triser la fabuleuse puissance de calcul de nos machines (en d enissant ce
xiv
Pr eface
quen jargon on appelle des architectures logicielles et mat erielles) et dautre part
dexpliquer aux utilisateurs ce quils peuvent en attendre. La dicult e est alors
de dire les choses de manière susamment claire et evocatrice sans masquer pour
autant les limitations et les insusances des systèmes propos es, qui sont souvent
enormes: après tout, ces constructions ne reposent que sur des machines! De ce
point de vue, linformatique est tributaire des sciences cognitives, puisquil sagit de
mettre en correspondance les processus intellectuels de lutilisateur avec ceux (sic)
de la machine. En retour, cette confrontation apporte à l etude de la cognition des
eclairages nouveaux. Cest ce que fait Jacques Ferber dans son livre, arm e de pens ee
syst emique et de psychologie cognitive. Ce nest pas un ouvrage sur les techniques
de programmation, bien que lauteur soit parfaitement conscient des possibilit es et
des limitations des moyens informatiques actuels. Cest en fonction de ces moyens,
mais de manière implicite, quil analyse les nombreux facteurs qui entrent dans les
systèmes multi-agents que lon sait actuellement construire. Certains exemples sur
lesquels il fonde son argumentation ont dailleurs et e r ealis es dans son equipe et ont
fait lobjet de thèses de doctorat.
Comme on le verra, la mod elisation complète dune soci et e humaine par un
système multi-agent est encore assez loin de nous pour des raisons qui ne tien-
nent pas toutes à la stupidit e des machines. La simulation de La vie devant soi
nest pas pour demain. En revanche, nous savons mod eliser certaines activit es des
collectivit es humaines, par exemple le r egime des p eches dans le delta central du
Niger, où entrent en concurrence divers facteurs climatiques, culturels, economiques
et halieutiques. Nous savons aussi repr esenter les caract eristiques de certaines popu-
Publicité
lations de fourmis, chaque insecte etant trait e individuellement comme un agent très
simple et linteraction à grande echelle de ces agents multiples faisant emerger des
comportements globaux fort proches de ceux quobservent les entomologistes dans
leurs laboratoires d ethologie ce qui ouvre des voies de recherche nouvelles. Et,
pour revenir a des pr eoccupations ding enierie, de systemes qui servent à r esoudre
des problèmes, Jacques Ferber vous proposera tout un eventail de techniques de
r esolution de problemes qui saverent prometteuses.
Ce livre est un commencement, cest vous, lecteur, qui ecrirez la suite!
Jean-Fran cois Perrot
Professeur à luniversit e
Pierre et Marie Curie
Avant-propos
Depuis quelques ann ees, les systèmes multi-agents ont pris une place de plus en plus
importante en informatique, que ce soit dans le domaine de lintelligence articielle,
dans ceux des systèmes distribu es, de la robotique, ou m eme dans ce champ dis-
ciplinaire nouveau quest la vie articielle, en introduisant la probl ematique de
lintelligence collective et de l emergence de structures par interactions. En situant
la question au niveau de lautonomie des individus, que lon appelle agents, et des in-
teractions qui les lient, les systemes multi-agents soulevent de nombreuses questions.
Quels sont en eet les concepts fondateurs de ce domaine? Comment se di erencie-
t-il des autres disciplines et en particulier de lintelligence articielle, des systèmes
distribu es et de la robotique? Quels sont ses apports aux sciences cognitives et à la
r eexion philosophique en g en eral?
Science int egratrice plus quanalytique, la recherche sur les systèmes multi-
agents suscite un certain nombre dinterrogations: quest-ce quun agent qui interagit
avec dautres agents? Comment peuvent-ils coop erer? Quels sont les modes de
communication n ecessaires pour quils se r epartissent des t aches et coordonnent
leurs actions? Quelle architecture peut-on leur donner pour quils satisfassent leurs
buts? Ces questions sont pos ees avec une vigueur particulière car lenjeu porte sur la
r ealisation de systemes disposant de caract eristiques particulierement int eressantes:
souplesse, adaptation aux changements, int egration de programmes h et erogènes,
rapidit e dobtention de r esultats, etc.
Les recherches dans le domaine des systèmes multi-agents poursuivent deux
objectifs majeurs: le premier concerne lanalyse th eorique et exp erimentale des
m ecanismes dauto-organisation qui ont lieu lorsque plusieurs entit es autonomes
interagissent; le second sint eresse à la r ealisation dartefacts distribu es capables
daccomplir des t aches complexes par coop eration et interaction. Leur position est
donc double: dun c ot e elles se placent au sein des sciences cognitives et sociales
(psychologie, ethologie, sociologie, philosophie...) et naturelles ( ecologie, biologie...)
pour a la fois mod eliser, expliquer et simuler des ph enomenes naturels, et susciter des
modèles dauto-organisation; de lautre, elles se pr esentent comme une pratique, une
technique tendue vers la r ealisation de systemes informatiques complexes a partir des
concepts dagents, de communication, de coop eration et de coordination dactions.
Ce livre est issu de lenseignement des systèmes multi-agents (ou SMA) que
jeectue dans le DEA IARFA à luniversit e Pierre et Marie Curie (Paris 6) depuis
plusieurs ann ees. Il nexiste, à ma connaissance, aucun manuel (textbook) sur les
SMA. Les seuls ouvrages disponibles sont des thèses publi ees ou des compilations
darticles ecrits par des sp ecialistes pour dautres sp ecialistes du domaine, ce qui
2
Avant-propos
ne permet pas a un etudiant ou a un non-sp ecialiste davoir un aper cu global et
synth etique de la question. L eventail des recherches men ees depuis bient ot vingt
ans sur les systèmes multi-agents est extr emement vaste, et il nexiste pas (encore)
de fondements susamment simples et pr ecis de cette discipline pour quil soit facile
de pr esenter de manière progressive et didactique les travaux dans ce domaine. Il
fallait donc commencer par unier les positions et etablir un cadre conceptuel pour le
d eveloppement de th eories futures. Cest à cet objectif que cet ouvrage est consacr e,
celui de synth etiser les connaissances majeures dans ce domaine en commen cant
à poser les fondations dune science de linteraction, que jai appel ee la k en etique,
daprès le terme grec ko 1non, ce qui est commun.
Pour linstant cette tentative est encore timide et sappuie essentiellement sur
la d enition de cadres conceptuels, de quelques classications et formalisations et
sur la pr esentation dune m ethode modulaire de construction de systèmes multi-
agents. Lint er et dune telle synthese est double: elle permet de saranchir, a
terme, des di erences de notations et des m eandres l egitimes eectu es par les
chercheurs dans lexploration de leur domaine, et de montrer un visage uni autour
dune probl ematique claire pouvant s enoncer pr ecis ement et simplement. Nous nen
sommes pas encore la, mais jespere que cet ouvrage contribuera a la fois a faire
comprendre au lecteur non sp ecialiste les r esultats et les enjeux des systèmes multi-
agents sous la forme dun langage uni e et a donner a l etudiant ou au chercheur
des bases solides pour laider a elaborer de nouvelles connaissances et a apporter sa
propre pierre à ces fondations.
Contenu de louvrage
On trouvera dans cet ouvrage:
1. un etat de lart sur la question,
2. un point de vue sur les systèmes multi-agents pr esent es comme une nouvelle
syst emique qui met en avant la probl ematique de linteraction et de ses
cons equences,
3. une analyse conceptuelle du domaine à partir dune classication des princi-
paux problèmes et r esultats et, surtout, une analyse fonctionnelle et struc-
turale des organisations servant de cadre à lensemble des travaux men es dans
ce domaine,
4. un formalisme, Bric, permettant la conception modulaire et incr ementale de
SMA, par la mod elisation des comportements, des structures de communica-
tion et des principales formes dinteractions que sont lallocation de t aches et
la coordination dactions,
5. une tentative de formalisation des SMA et de linteraction, a partir dun modele
de laction fond e sur un couple inuence/r eaction.
Avant-propos
A qui sadresse-t-il?
3
Cet ouvrage sadresse tout dabord à des professionnels de linformatique non
sp ecialistes de la question qui d esirent avoir un point de vue synth etique sur ce
domaine. Il sadresse aussi à des non-informaticiens sp ecialistes des sciences sociales
ou des sciences de la nature qui veulent utiliser les systèmes multi-agents pour
mod eliser des comportements naturels et etudier l emergence de ph enomènes com-
plexes. Il sadresse aussi aux non sp ecialistes de linformatique souhaitant avoir une
connaissance des concepts essentiels permettant de comprendre ce quest une in-
telligence collective et avoir une vue densemble de la probl ematique multi-agent.
Il sadresse enn aux etudiants en deuxieme et troisieme cycles dinformatique qui
voudraient se sp ecialiser dans ce domaine et pour lesquels il fournit un support de
cours.
Organisation de louvrage
Lorganisation de cet ouvrage suit une d emarche volontairement constructive et
ascendante: apres une breve pr esentation du domaine et la pr esentation dun cadre
g en eral danalyse des organisations multi-agents, les concepts et m ecanismes mis en
Suvre dans les systèmes multi-agents sont progressivement etudi es et analys es. Les
notions de base sont pr esent ees dans une première partie. Le chapitre 1 donne un
aper cu g en eral du domaine, les thèmes principaux et leurs relations avec dautres
disciplines. Le chapitre 2 introduit le concept de situation dinteraction et propose
un cadre g en eral pour appr ehender les di erentes composantes de la coop eration.
Le chapitre 3 propose une analyse fonctionnelle et structurale des organisations
ainsi que les di erentes architectures utilis ees g en eralement pour les concevoir. Le
chapitre 4 propose une transition entre les g en eralit es de la partie pr ec edente et les
descriptions plus d etaill ees des parties suivantes. Il aborde la probl ematique de la
formalisation de laction et du comportement ainsi que celle de la mod elisation des
systèmes multi-agents et introduit la plupart des notations utilis ees dans le reste
de louvrage. On y montre que les conceptions classiques de laction ne sont pas
susantes pour bien comprendre les interactions, ce qui aboutit au d eveloppement
dune th eorie de laction consid er ee comme le r esultat dun ensemble dinuences
produites par les agents. Ce chapitre pr esente aussi un formalisme de mod elisation
des agents et des systemes multi-agents, Bric, qui associe des r eseaux de Petri a
une structure modulaire. Le chapitre 5 fait le point sur la notion d etat mental dun
agent (croyances, intentions, engagements, etc.) et propose une repr esentation de sa
dynamique mentale sous la forme dune architecture modulaire d ecrite en termes
de composants Bric. La dernière partie est consacr ee aux di erentes m ethodes et
outils conceptuels utilis es pour construire des organisations coop eratives. Le chapitre
6 porte sur les communications et fournit une mod elisation des principales structures
de communications a laide de r eseaux de Petri. Le chapitre 7 est d edi e a l etude des
organisations de collaboration dans lesquelles le travail est r eparti dynamiquement
entre les agents. Le chapitre 8 pr esente enn les principaux modèles de coordination
4
Avant-propos
daction qui gèrent larticulation dynamique de la planication et de lex ecution des
t aches et tentent d eviter les conits. On y montre aussi quil est possible de r esoudre
des problèmes par interaction entre agents simples.
Remerciements
Ce livre naurait pu voir le jour sans laide dun grand nombre de personnes qui
mont apport e leurs remarques, leurs critiques et surtout leur soutien. Je pense
en particulier a Jacqueline Zizi qui, au dela de son amiti e, a relu mon livre de
fond en comble. Son exigence et sa rigueur mont beaucoup aid e, sa diplomatie
et ses encouragements mont permis de garder conance dans ce projet. Quelle
re coive ici le t emoignage de ma reconnaissance. Je pense egalement à Philippe
Laublet, Alexis Drogoul et Anne Collinot qui ont su apporter les commentaires
et critiques constructives à ce qui etait encore un brouillon. Leurs remarques mont
et e pr ecieuses.
Je remercie les membres de l equipe Miriad, Stephane Bura, Thierry Bouron,
Patrice Carle, Christophe...