Td corrigé Patricia Guillierme - La Forge pdf

Patricia Guillierme - La Forge

Le sujet de stage a donc évolué vers une étude comparative des ..... E ssentiellement utilisée pour créer des comportements adaptatifs, les systèmes à base ...... des outils de filtrage de l'information et d'assistance électronique au contrôleur.




part of the document



Patricia Guillierme 
SCIA Promotion 2002
Projet de fin d’étude
Janvier à juin 2002










Plates-formes de développement
et d’exécution pour
les systèmes multi-agents






Intitulé :
Stage pragmatique ayant pour objectif le développement
d’une plate-forme générique dédiée à la conception
de systèmes multi-agents pour la société PACTE NOVATION


Maîtres de stage :
Jacques Couvreur et Boris Gonnot














Pacte Novation
2, rue du Docteur Lombard
92441 Issy-Les-Moulineaux Cedex REMERCIEMENTS





Je tiens tout d’abord à remercier l’ensemble de PACTE NOVATION et particulièrement Christian Tora et Bruno Gaudinat, directeurs, de m’avoir accueilli pendant mon projet de fin d’études. Je tiens à souligner l’ambiance chaleureuse et les diverses compétences que j’ai pu trouver au sein de leur société.


Je remercie également l’équipe technique, Pierre Bourliatoux et Antoine Aminian, pour leur encadrement et leurs précieux conseils.


Je remercie vivement l’ensemble de mes professeurs pour m’avoir encadrée pendant cette année de spécialisation et fait découvrir les technologies d’informatique d’avancée.


Enfin, je tiens à remercier toute ma reconnaissance à Jacques Couvreur et Boris Gonnot, mes responsables de stage, sans qui rien de tout cela ne serait arrivé. Ils ont me donner les conseils et les bonnes indications qui m’ont permis d’avancer dans mon travail, même dans les moments de doute. Ils ont su partager avec moi leur expérience ainsi que leur passion pour les systèmes multi-agents. SOMMAIRE
 TOC \o "2-3" \h \z \t "Titre 1;1;Style1;1;Chapter;1;Titre;1;Chapter1;2;Chapter2;3;Chapter3;4;Chapter4;5;Annexe;2"  HYPERLINK \l "_Toc11159675" REMERCIEMENTS  PAGEREF _Toc11159675 \h 2
 HYPERLINK \l "_Toc11159676" INTRODUCTION  PAGEREF _Toc11159676 \h 5
 HYPERLINK \l "_Toc11159677" PRESENTATION DE PACTE NOVATION  PAGEREF _Toc11159677 \h 7
 HYPERLINK \l "_Toc11159678" 1. Le secteur d’activité  PAGEREF _Toc11159678 \h 7
 HYPERLINK \l "_Toc11159679" 2. L'entreprise  PAGEREF _Toc11159679 \h 8
 HYPERLINK \l "_Toc11159680" 2.1. Présentation  PAGEREF _Toc11159680 \h 8
 HYPERLINK \l "_Toc11159681" 2.2. Le service  PAGEREF _Toc11159681 \h 10
 HYPERLINK \l "_Toc11159682" 2.2.1. Clients  PAGEREF _Toc11159682 \h 10
 HYPERLINK \l "_Toc11159683" 2.2.2. Compétences  PAGEREF _Toc11159683 \h 11
 HYPERLINK \l "_Toc11159684" 2.2.3. Projets  PAGEREF _Toc11159684 \h 12
 HYPERLINK \l "_Toc11159685" 2.3. Le stage  PAGEREF _Toc11159685 \h 13
 HYPERLINK \l "_Toc11159686" 2.3.1. Intitulé initial  PAGEREF _Toc11159686 \h 13
 HYPERLINK \l "_Toc11159687" 2.3.2. Evolution  PAGEREF _Toc11159687 \h 13
 HYPERLINK \l "_Toc11159688" LES AGENTS  PAGEREF _Toc11159688 \h 15
 HYPERLINK \l "_Toc11159689" 1. Histoire de l’IAD  PAGEREF _Toc11159689 \h 15
 HYPERLINK \l "_Toc11159690" 1.1. Blackboard  PAGEREF _Toc11159690 \h 15
 HYPERLINK \l "_Toc11159691" 1.2. Modèle acteur  PAGEREF _Toc11159691 \h 17
 HYPERLINK \l "_Toc11159692" 1.3. Le protocole Contract Net  PAGEREF _Toc11159692 \h 18
 HYPERLINK \l "_Toc11159693" 1.4. DVMT  PAGEREF _Toc11159693 \h 19
 HYPERLINK \l "_Toc11159694" 2. Le concept d’agent  PAGEREF _Toc11159694 \h 19
 HYPERLINK \l "_Toc11159695" 2.1. Définition  PAGEREF _Toc11159695 \h 19
 HYPERLINK \l "_Toc11159696" 2.2. Classification des agents  PAGEREF _Toc11159696 \h 21
 HYPERLINK \l "_Toc11159697" 2.2.1. Agents réactifs  PAGEREF _Toc11159697 \h 21
 HYPERLINK \l "_Toc11159698" 2.2.2. Agents cognitifs  PAGEREF _Toc11159698 \h 23
 HYPERLINK \l "_Toc11159699" 2.2.3. Agents hybrides  PAGEREF _Toc11159699 \h 24
 HYPERLINK \l "_Toc11159700" 2.3. Architectures diverses  PAGEREF _Toc11159700 \h 25
 HYPERLINK \l "_Toc11159701" 2.3.1. Architecture modulaire horizontale  PAGEREF _Toc11159701 \h 25
 HYPERLINK \l "_Toc11159702" 2.3.2. Tableaux noirs ou blackboard  PAGEREF _Toc11159702 \h 25
 HYPERLINK \l "_Toc11159703" 2.3.3. Architecture de subsomption  PAGEREF _Toc11159703 \h 26
 HYPERLINK \l "_Toc11159704" 2.3.4. Tâches compétitives  PAGEREF _Toc11159704 \h 27
 HYPERLINK \l "_Toc11159705" 2.3.5. Les systèmes de production (ou SE)  PAGEREF _Toc11159705 \h 27
 HYPERLINK \l "_Toc11159706" 2.3.6. Les architectures connexionnistes à base de réseaux de neurones.  PAGEREF _Toc11159706 \h 28
 HYPERLINK \l "_Toc11159707" 3. Conclusion  PAGEREF _Toc11159707 \h 28
 HYPERLINK \l "_Toc11159708" LES SYSTEMES MULTI-AGENTS  PAGEREF _Toc11159708 \h 30
 HYPERLINK \l "_Toc11159709" 1. Définition  PAGEREF _Toc11159709 \h 31
 HYPERLINK \l "_Toc11159710" 2. Interaction et coopération  PAGEREF _Toc11159710 \h 32
 HYPERLINK \l "_Toc11159711" 3. Coordination entre agents  PAGEREF _Toc11159711 \h 36
 HYPERLINK \l "_Toc11159712" 4. Négociation entre agents…  PAGEREF _Toc11159712 \h 38
 HYPERLINK \l "_Toc11159713" 5. Planification  PAGEREF _Toc11159713 \h 40
 HYPERLINK \l "_Toc11159714" 6. Communication  PAGEREF _Toc11159714 \h 41
 HYPERLINK \l "_Toc11159715" 6.1. Architecture de communication  PAGEREF _Toc11159715 \h 44
 HYPERLINK \l "_Toc11159716" 6.2. Mode de communication  PAGEREF _Toc11159716 \h 45
 HYPERLINK \l "_Toc11159717" 6.3. Actes de langages  PAGEREF _Toc11159717 \h 46
 HYPERLINK \l "_Toc11159718" 7. Conclusion  PAGEREF _Toc11159718 \h 46
 HYPERLINK \l "_Toc11159719" METHODOLOGIES ET OUTILS DE DEVELOPPEMENT  PAGEREF _Toc11159719 \h 48
 HYPERLINK \l "_Toc11159720" 1. Méthodologies  PAGEREF _Toc11159720 \h 48
 HYPERLINK \l "_Toc11159721" 1.1. CASSIOPEE  PAGEREF _Toc11159721 \h 48
 HYPERLINK \l "_Toc11159722" 1.2. Approche AEIO  PAGEREF _Toc11159722 \h 50
 HYPERLINK \l "_Toc11159723" 1.3. Approche Agent-Groupe-Rôle  PAGEREF _Toc11159723 \h 52
 HYPERLINK \l "_Toc11159724" 1.4. Conclusion  PAGEREF _Toc11159724 \h 53
 HYPERLINK \l "_Toc11159725" 2. Plates-formes SMA  PAGEREF _Toc11159725 \h 55
 HYPERLINK \l "_Toc11159726" 2.1. AGENTBUILDER  PAGEREF _Toc11159726 \h 56
 HYPERLINK \l "_Toc11159727" 2.2. JACK  PAGEREF _Toc11159727 \h 57
 HYPERLINK \l "_Toc11159728" 2.3. MADKIT  PAGEREF _Toc11159728 \h 58
 HYPERLINK \l "_Toc11159729" 2.4. ZEUS  PAGEREF _Toc11159729 \h 59
 HYPERLINK \l "_Toc11159730" 3. LA PLATEFORME JADE  PAGEREF _Toc11159730 \h 61
 HYPERLINK \l "_Toc11159731" 3.1. Standards FIPA  PAGEREF _Toc11159731 \h 61
 HYPERLINK \l "_Toc11159732" 3.2. Description  PAGEREF _Toc11159732 \h 63
 HYPERLINK \l "_Toc11159733" 3.3. Evaluation  PAGEREF _Toc11159733 \h 68
 HYPERLINK \l "_Toc11159734" 3.4. Application au suivi du trafic aérien  PAGEREF _Toc11159734 \h 69
 HYPERLINK \l "_Toc11159735" 3.4.1. Problématique  PAGEREF _Toc11159735 \h 69
 HYPERLINK \l "_Toc11159736" 3.4.2. Modélisation du problème  PAGEREF _Toc11159736 \h 75
 HYPERLINK \l "_Toc11159737" 3.4.3. Développement du SMA réactif  PAGEREF _Toc11159737 \h 77
 HYPERLINK \l "_Toc11159738" 3.4.4. Résultats  PAGEREF _Toc11159738 \h 79
 HYPERLINK \l "_Toc11159739" CONCLUSION  PAGEREF _Toc11159739 \h 81
 HYPERLINK \l "_Toc11159740" BIBLIOGRAPHIE  PAGEREF _Toc11159740 \h 83
 HYPERLINK \l "_Toc11159741" GLOSSAIRE  PAGEREF _Toc11159741 \h 94
 HYPERLINK \l "_Toc11159742" ANNEXES  PAGEREF _Toc11159742 \h 102
 HYPERLINK \l "_Toc11159743" Abréviations utilisées  PAGEREF _Toc11159743 \h 103
 HYPERLINK \l "_Toc11159744" Annexe I : Mail de J. FERBER  PAGEREF _Toc11159744 \h 104
 HYPERLINK \l "_Toc11159745" Annexe II : Evolution des systèmes de blackboard  PAGEREF _Toc11159745 \h 105
 HYPERLINK \l "_Toc11159746" Annexe III : Comparatif entre  PAGEREF _Toc11159746 \h 106
 HYPERLINK \l "_Toc11159747" Annexe IV : KQML  PAGEREF _Toc11159747 \h 107
 HYPERLINK \l "_Toc11159748" Annexe V : Le free flight  PAGEREF _Toc11159748 \h 110
 HYPERLINK \l "_Toc11159749" Annexe VI : Méthode XP  PAGEREF _Toc11159749 \h 123
 INTRODUCTION



Ce document constitue une synthèse du travail que j’ai réalisé dans le cadre de mon stage de fin d’étude de janvier à juin 2002 au sein de la société PACTE NOVATION. Société de Service en Ingénierie Informatique, PACTE NOVATION a pour ambition d’intervenir sur des projets à forte valeur ajoutée au travers de missions de conseil, d’assistance à maîtrise d’œuvre et d’ouvrage, d’assistance technique et de réalisations clés en main.

Soucieuse à terme de pourvoir proposer à ses clients une alternative aux technologies d’informatique avancée jusqu’à présent utilisées dans la résolution de problèmes telles que les systèmes experts, la programmation par contrainte, etc., PACTE NOVATION a proposé ce travail portant sur l’analyse, la conception et la mise en œuvre de systèmes multi-agents (SMA).

Les systèmes multi-agents font partie de ce qu’il est convenu d’appeler l’Intelligence
Artificielle Distribuée (IAD), branche relativement récente de l’Intelligence Artificielle (IA). L’IAD s’intéresse à la conception d’agents artificiels capables de s’organiser efficacement pour accomplir collectivement les fonctionnalités qui leur sont demandées.

Les recherches qui sont menées dans ce domaine mettent moins l’accent sur le comportement individuel des agents que sur leurs capacités d’organisation et de fonctionnement collectif, et, à ce titre, rompent avec presque quarante ans de recherches en IA consacrées exclusivement aux performances individuelles d’agents « autarciques », dont l’interaction avec l’extérieur était balisée sous la forme d’entrées-sorties soigneusement identifiées.

Construire des organisations d’agents artificiels nécessite bien sûr, à un moment donné ou à un autre, de devoir se pencher sur leur architecture individuelle, et donc la manière dont ils stockent ou manipulent leurs connaissances, leurs capacités de planification, ou leurs compétences. Cette définition de « modèles d’agents » constitue une partie non négligeable des travaux conduits en IAD.

Cependant, les recherches conduites en IAD sont menées dans une perspective légèrement différente de l’IA, puisqu’on s’intéresse à des agents devant fonctionner en interaction avec d’autres agents : elles s’intéressent principalement aux mécanismes de communication, de coopération, de coordination ou de négociation pouvant conduire des agents à accomplir ensemble les tâches qui leur seront confiées, en mobilisant aussi bien leurs facultés individuelles que les ressources de l’organisation qu’ils forment.

Les six mois de stage devaient initialement conduire à la réalisation d’une plate-forme générique (minimale) pour les SMA ainsi qu’au développement d’un SMA applicatif pour illustrer son utilisation.

Contrairement à cela, suite à la quantité de plate-formes existantes révélées dans l’état de l’art, mais aussi et surtout sur les conseils avisés de Jacques Ferber, il a semblé préférable de se « faire la main sur une plate-forme existante plutôt que de refaire une nième plate-forme qui ira nécessairement dans un placard à la fin de votre stage […] sinon prévoyiez deux ans de travail minimum pour qu'elle puisse entrer en compétition avec les plate-formes existantes!! » [Annexe I]

Aussi le stage a-t-il été redéfini, le nouvel objectif étant de choisir une plate-forme de développement parmi celles existantes, et de réaliser un SMA au travers de celle-ci pour tester ses fonctionnalités. 

Les motivations qui ont conduit au choix de la plate-forme JADE, Java Agent DEvelopment framework, distribuée par TILAB, Telecom Italia Lab, de Turin (Italie) sont multiples : disponible en open source sous la licence LGPL (GNU LESSER GENERAL PUBLIC LICENCE) et dotée d’un collectif de « JADErs » très actifs, JADE est une plate-forme agent distribuée (il est possible de distribuer la plateforme sur plusieurs machines hôtes), dotée d’une IHM permettant la gestion de plusieurs agents (locaux ou à distance), compatible avec le standard FIPA, Foundation of Intelligent and Physical Agents, et qui intègre des outils de « debug ».

Ebauche d’une situation réelle simplifiée à l’extrême, la modélisation d’un outil de suivi du trafic aérien m’a semblé offrir les conditions idéales à une bonne compréhension des enjeux et de l’emploi des systèmes multi-agents dans des applications industrielles. Aussi, afin de mettre en évidence les caractéristiques des SMA réactifs, j’ai testé la plate-forme JADE au travers du développement un SMA de suivi du trafic aérien constitué exclusivement d’agents réactifs.

Le document est organisé de la manière suivante : je commencerai tout d’abord, au chapitre 1, par effectuer une présentation de la société PACTE NOVATION, en définissant le secteur d’activité dans lequel elle s’inscrit, les services qu’elle propose ainsi que le positionnement du stage dans l’entreprise afin de justifier l’utilité et la finalité du travail demandé. J’introduirai ensuite, au chapitre 2, les éléments théoriques nécessaires à la compréhension des agents : comment s’inscrivent-ils dans l’évolution des langages et des technologies de programmation ? Quels sont les motivations et les concepts de base des agents ? Je m’intéresserai au chapitre 3 aux comportements collectifs produits par les interactions de plusieurs agents en traitant les différentes questions que soulèvent la problématique des SMA, en particulier : la coopération, la coordination, la planification et la communication. Le chapitre 4 présentera quelques unes des plateformes de développement dédiées aux SMA ainsi qu’une réflexion sur les différentes étapes de la construction d’un SMA à savoir l’analyse, la conception, le développement et le déploiement de SMA. Enfin, le chapitre 5 présentera plus particulièrement la plate-forme JADE ainsi que le SMA de suivi du trafic aérien que j’ai développé.

PRESENTATION DE PACTE NOVATION

Le secteur d’activité
Donnée forte du paysage industriel, l'externalisation des investissements informatiques a conduit au développement d'un secteur d'opérateurs de ces prestations : les SSII ou Société de Service en Ingénierie Informatique.
Malgré un ralentissement général, la croissance reste au rendez-vous dans le secteur des services informatiques. Les SSII constituent toujours une voie d'entrée privilégiée dans la vie active pour un grand nombre de jeunes diplômés.
Les grands secteurs
employeurs d’informaticiens à fin 2001
Effectifs salariés
Croissance entre 2000 et 2001

DSI des 100 premières grandes entreprises
140 000
+ 4 %

DSI des petites et moyennes entreprises
98 000
+ 4 %

Administration / Collectivités / Services publics
42 000
+ 2,5 %

Autres utilisateurs (services R & D)
22 000
+ 5 %

SSII et éditeurs de logiciels (code NAF 72)
292 000
+ 8 %

Constructeurs de matériel informatique
28 000
+ 3%

Distribution / négoce de matériel informatique
23 000
- 8 %

Autres : conseil, intérim, recherche, enseignement, formation, fournisseurs d'accès, multimédia informatique,…
34 000
+ 6 %

TOTAL
679 000
+ 5,3 %

Sources  HYPERLINK "http://www.passinformatique.com/40-metiers/20-10-10_secteurs.asp" http://www.passinformatique.com/40-metiers/20-10-10_secteurs.asp

Depuis une dizaine d'années, le secteur des services informatiques ne cesse de se développer. Les SSII bénéficient d'un mouvement général conduisant les entreprises à se recentrer sur leur cœur d'activité et à déléguer certaines activités importantes comme l'informatique à des spécialistes. Autre moteur de croissance: le fait que désormais les systèmes d'information constituent des éléments essentiels dans la stratégie de développement des entreprises. Parmi les prestations les plus demandées par les entreprises, on trouve le conseil en organisation ou en technologie, le paramétrage de progiciels, l'intégration de systèmes, l'infogérance ou la formation. Le CRM (Customer Relationship Management) et le SCM (Supply Chain Management) constituent aussi des préoccupations de plus en plus partagées. Quant à la sécurité, elle représente désormais un souci majeur pour les directions des systèmes d'information.

L'entreprise
Présentation
Fondée en avril 1994 par Bruno GAUDINAT et Christian TORA, ses actuels dirigeants, PACTE NOVATION est une Société Anonyme au capital de 512 000 euros comptant 85 ingénieurs à ce jour.



Société d’ingénierie logicielle pluridisciplinaire, PACTE NOVATION intervient dans des secteurs d’activités très variés comme le transport, la finance, les télécommunications, l’énergie, l’industrie et le tertiaire.


Son savoir-faire, reconnu auprès des très grands comptes, lui permet d’intervenir sur des applications à haute valeur ajoutée. Près de 40% de son activité est réalisée au forfait, ce qui lui a permis de fortement capitaliser autour de trois axes :

Technologies orientées objets
Conception et réalisation à base de technologies orientées objets
Conseil et pratique des méthodes orientées objets
Intégration d’applications distribuées dans des environnements Client / Serveur

Interfaces Homme Machine avec une spécialisation en ergonomie du logiciel
Le domaine des Interfaces Homme/Machine est par essence pluridisciplinaire car elle implique le travail d’ergonomes, de cogniticiens, de graphistes, d’ingénieurs, d’opérationnels, etc.
Prise en compte du facteur humain lors de l’informatisation du processus
Analyse de la tâche et spécification des Interfaces Homme/Machine
Evaluation et recommandation ergonomiques sur des IHM existantes
Réalisation d’IHM graphiques et d’outils utilisant le Langage Naturel

Outils d’Aide à la Décision 
Les systèmes d’aide à la décision ont pour objectif de mettre en valeur un savoir-faire pointu des clients à l’aide de systèmes experts eu encore de techniques issues de la Recherche Opérationnelle, de la Programmation Par Contrainte et de l’Intelligence Artificielle (IA). Il s’agit d'une véritable coopération entre l’utilisateur qui conserve la décision finale, une IHM support intuitive et des processus complexes producteurs à forte valeur ajoutée.
Résolution de problèmes intégrant des raisonnements d’experts, une forte complexité ou bien une grande combinatoire.
Systèmes à base de connaissances : spécification, conception et développement, de systèmes à base de connaissances, modélisation et capitalisation des savoir-faire,
Systèmes à base de contraintes : allocation des ressources, planification et ordonnancement, optimisation des processus, …

Partenariats PACTE NOVATION
Très souvent enrichie par une double compétence fonctionnelle, l’offre de PACTE NOVATION lui a permis de nouer des partenariats durables avec :

Partenariats éditeurs :
 HYPERLINK "http://www.ilog.fr/html/partners/pacte.htm" \t "_blank"  INCLUDEPICTURE "http://www.pactenovation.fr/images/ImagesLogoSponsors/logo_ilog.gif" \* MERGEFORMATINET  ILOG
Leader mondial des composants logiciels.
 HYPERLINK "http://www.bea.com/index.shtml" \t "_blank"  INCLUDEPICTURE "http://www.pactenovation.fr/images/ImagesLogoSponsors/logo_bea.gif" \* MERGEFORMATINET  BEA
Historiquement éditeur de Tuxedo, BEA a racheté la société WEB Logic pour devenir un des leaders dans le monde des serveurs d’applications et du B2B.
 HYPERLINK "http://www.rational.com" \t "_blank"  INCLUDEPICTURE "http://www.pactenovation.fr/images/ImagesLogoSponsors/logo_rational.gif" \* MERGEFORMATINET  RATIONAL
Le n°1 mondial des outils de conception orientés objet
 HYPERLINK "http://www.temposoft.fr/" \t "_blank"  INCLUDEPICTURE "http://www.pactenovation.fr/images/ImagesLogoSponsors/logo_temposoft.gif" \* MERGEFORMATINET  TEMPOSOFT
Editeur de logiciels Intranet pour la gestion et l'optimisation des ressources humaines.
 HYPERLINK "http://www.virtools.com" \t "_blank"  INCLUDEPICTURE "http://www.pactenovation.fr/images/ImagesLogoSponsors/logo_virtools.gif" \* MERGEFORMATINET  VIRTOOLS
Editeur d'outils logiciels de développement à 3 dimensions appliqués à l'enseignement à distance, au télémarketing ou aux jeux électroniques
Partenariats Clients et Européens :
 HYPERLINK "http://www.cordis.lu/esprit/src/intro-f.htm" \t "_blank"  INCLUDEPICTURE "http://www.pactenovation.fr/images/ImagesLogoSponsors/Sans%20titre%20-%201%20copier.jpg" \* MERGEFORMATINET  ProACTIVE
Projet de recherche mené dans le cadre du programme Esprit sous l’égide de la Communauté Européenne.
 HYPERLINK "http://www.eurocontrol.fr/" \t "_blank"  INCLUDEPICTURE "http://www.pactenovation.fr/images/ImagesLogoSponsors/Logo_euroteam_2.gif" \* MERGEFORMATINET  EUROTEAM
Consortium accrédité par EUROCONTROL, l’organisme européen fédérant les recherches et développements dans le domaine du contrôle aérien.
 HYPERLINK "http://www.sachem.com.fr/" \t "_blank"  INCLUDEPICTURE "http://www.pactenovation.fr/images/ImagesLogoSponsors/logo_sachem.jpg" \* MERGEFORMATINET  SOLLAC
Le plus gros projet d'industrie utilisant des techniques d'Intelligence Artificielle.

Le service

Clients
PACTE NOVATION intervient dans des domaines aussi divers que :
 EMBED Excel.Chart.8 \s 
Energie : EDF, GDF, CEA, Eurysis, SPSE
Finance : BNP, Caisse des dépôts, Crédits Agricole Indosuez, Crédit Lyonnais, Société Générale, Deutsche Bank, Dresdner Bank, AGF AM, ING Direct
Transport : Alstom, CSEE-Transports, MTI, SNCF, Peugeot Sport, Renault Sport, ADP, Eurocontrol, Snecma, Gefco
Télécom : Alcatel, Nortel, Bouygues Telecom, Eutelsat
Industrie : Thomson, Sagem, Eraam Lockheed Martin, La Poste, Médasys, Société le Nickel, Sollac, Spie Trindel, Honeywell

Prestations
Le Conseil, le Forfait et l'Assistance Technique sont le cœur de l'offre de PACTE NOVATION. Ils permettent de répondre aux attentes de nos clients tout en offrant à nos collaborateurs de réelles opportunités de carrière.
 EMBED Excel.Chart.8 \s 
L’assistance technique
L’assistance technique incarne pleinement la notion de service. Elle requiert curiosité, efficacité, sens du service ainsi que d’indispensables qualités relationnelles. La variété et la richesse des missions proposées permettront à l’ingénieur de mieux découvrir ses aptitudes et ainsi d’orienter sa carrière.

Le forfait
Bien souvent délaissé par nos confrères car jugé trop risqué, il représente pour PACTENOVATION un véritable crédo et un challenge quotidien. Il offre la colonne vertébrale qui supporte tant la capitalisation (technique et métier) que l’intégration et l’évolution de nouveaux collaborateurs.

Le conseil
Activité noble par excellence, le conseil a pour vocation d’apporter à nos clients l’expertise de PACTE NOVATION sur des sujets aussi variés que les architectures informatiques distribuées, l’aide à la décision, la maîtrise d’œuvre, la maîtrise d’ouvrage ou l’ergonomie du logiciel.


Compétences
PACTE NOVATION dispose dans ses rangs:
De cogniticiens et d’ergonomes chargés d’analyser le métier mais aussi le besoin exact du client en vue de rédiger un cahier des charges précis et exhaustif.
De spécialistes de la résolution de problèmes complexes et combinatoires ou de la mise en place de systèmes à base de connaissances, problèmes pour lesquels une expérience significative est indispensable pour envisager sereinement l’aboutissement des projets qui y ont trait.
D’architectes capables de concevoir et mettre en place des architectures distribuées ainsi que des modélisations objets complexes et évolutives.
D’ingénieurs motivés curieux et à forte compétence dans les domaines fonctionnels de prédilection de nos clients.
Enfin, d’une direction technique composée de consultants et de chefs de projet à forte compétence technique se chargeant de garantir la fourniture d’un service de qualité irréprochable.

Projets
PACTE NOVATION est une société à fortes compétences et de grande expérience dans tous les domaines avancés de l’aide à la décision. Au-dessus des technologies objet, elle a su réunir et mettre en valeur une équipe soudée, complémentaire, curieuse des métiers de ses clients ainsi que des techniques informatiques à forte valeur ajoutée. Ces compétences s’expriment et trouvent leur place à toutes les étapes d’un projet.


Afin de préciser un peu mieux les compétences de PACTE NOVATION, voici quelques exemples de réalisations significatives :

ALICE : système expert de supervision de moteurs de formule 1
Créé spécifiquement pour Renault Sport dans le contexte de la formule 1, ALICE (Application Logicielle Intelligente pour Courses et Essais) analyse les données envoyées par télémesure à chaque tour de piste et déduit les alarmes moteur.

Simulateur de trafic ferroviaire
Exploitant la souplesse apportée par les technologies objets dans la conduite de projets informatiques, PACTE NOVATION a développé pour ALSTOM une série de simulateurs de trafic ferroviaire. Vendus à l’exportation, ces simulateurs sont destinés à valider des commandes centralisées de métro ou de trains comme pour Le Caire, Hong-Kong, Athènes, Jakarta, Istanbul, Singapour.

AGATE pour SPSE : Planification et optimisation de transport pétrolier
Planification des arrivées de navires aux môles du Port Autonome de Marseille, placement intelligent des produits pétroliers dans les réservoirs du dépôt, planification des livraisons par pipeline et optimisation des coûts de transport : AGATE a procuré une souplesse incomparable pour tout le personnel de la Société du Pipeline Sud Européen.

STORIA : Suivi du trafic aérien dans un browser Web
Le projet Storia sur Internet dont le maître d'oeuvre est le Centre Expérimental d' HYPERLINK "http://www.eurocontrol.fr" \t "_blank" Eurocontrol consiste à visualiser, via une applet dans un browser internet standard, le trafic aérien civil sur l'Europe. Eurocontrol a présenté la version LIVE pendant 3 jours consécutifs sur 2 stands du salon ATC-Maastricht en février 2001. Ce fut un succès technique total et, de l'avis des participants, c'était une grande première et l'innovation la plus "décapante" du salon.


MATOS : Modélisation et Allocation de Tâches entre Opérateurs et Systèmes
MATOS est un outil logiciel supportant les activités de modélisation des tâches sur lesquelles s’appuie la démarche de formalisation du besoin et de spécification d’IHM de PACTE NOVATION. MATOS implémente en partie les principes de MAD (Scapin, Sébillotte, …de l’INRIA).

Communication voyageur sur le réseau Ile-De-France de la SNCF
La société SORIDIS s’est associée à PACTE NOVATION pour répondre à une problématique de la SNCF : réécrire à l’aide de nouvelles technos le système de gestion de la communication voyageur (gestion des différents panneaux ou périphériques vidéo sur les quais et dans les gares et pilotage du « MODAN » pour les appels vocaux) en mettant au premier plan l’aspect ergonomique des postes opérateurs.

ADP : optimisation d’affectations aéroportuaire
L’outil d’optimisation des affectations aéroportuaires développé par PACTE NOVATION est destiné au développement Stratégie d’ADP. L’objectif est d’affecter l’ensemble des vols à l’arrivée ou au départ de Paris aux différents aérogares des aéroports parisiens. Indépendamment de l’objectif très concret lié au trafic réel, l’outil permet d’effectuer des projections en simulant l’ouverture de nouvelles capacités comme, par exemple, un nouveau terminal ou un 3ième aéroport.

Le stage
Passeport pour la vie active, PACTE NOVATION considère le stage comme une période de pré embauche délibérément orientée vers une future collaboration. Aussi, les sujets proposés sont-ils exclusivement réservés aux étudiants de dernière année. Soucieuse à terme de pourvoir proposer à ses clients une alternative aux technologies d’informatique avancée jusqu’à présent utilisées dans la résolution de problèmes telles que les systèmes experts, la programmation par contrainte, la recherche opérationnelle, etc., PACTE NOVATION a proposé ce stage portant sur l’analyse, la conception et la mise en œuvre de systèmes multi-agents (SMA).

Intitulé initial
Encadrés par deux ingénieurs confirmés, Jacques Couvreur et Boris Gonnot, tous deux passionnés par les technologies multi-agents, le stage se devait d’être un stage pragmatique ayant pour objectif la conception d’une plate-forme générique (minimale) dédiée à la réalisation de systèmes multi-agents.

Le stage devait s’organiser de la façon suivante : après avoir réalisé une synthèse des technologies agents et des systèmes multi-agents, le stage devait se poursuivre par un état de l’art des plate-formes existantes. A la lumière de l’évaluation de ses dernières, une modélisation d’une plate-forme minimale devait être réalisée : choix du langage, définition des caractéristiques et fonctionnalités de la plate-forme, etc. Enfin, le stage devait se clôturer par la réalisation d’une application au travers de la plate-forme pour illustrer l’utilisation des technologies agents pour la résolution d’une problématique industrielle, le domaine d’application (ferroviaire, financier, etc.) étant laissé au choix du stagiaire.

Evolution
Mes responsables de stage étant tous deux en missions chez leur client, il a été convenu d’une réunion hebdomadaire pour faire régulièrement le point sur l’avancement de mon travail.

Le premier mois de stage s’est révélé déterminant : l’état de l’art a révélé une quantité incroyable de plate-formes (ou autres utilitaires agent) développées aussi bien dans un but éducatif que commercial tant et si bien qu’il nous a paru préférable de redéfinir les objectifs du stage. En effet, en s'appuyant sur un mail de Jacques Ferber [Annexe1], il est apparu plus judicieux d'utiliser une plateforme déjà existante. Le sujet de stage a donc évolué vers une étude comparative des plateformes existantes, afin d'en choisir une. Après en avoir testé les fonctionnalités, il a été décidé d’utiliser cette plate-forme pour la résolution d’une problématique métier. Le choix du domaine restant là encore le choix du stagiaire.




LES AGENTS

Ce chapitre introduit la notion d’agent. Dans un premier temps, on s’intéressera à l’histoire de l’Intelligence Artificielle Distribuée (IAD) afin de comprendre la légitimité des agents : à travers l’évolution des langages et des techniques de programmation, on essaiera de faire le point sur les motivations qui ont conduit à l’apparition de ce nouveau concept. On donnera ensuite la définition d’un agent et on identifiera les caractéristiques des deux grandes familles d’agents : les agents réactifs et les agents cognitifs. On terminera par l’étude des différentes architectures d’un agent.
Histoire de l’IAD
Beaucoup de personnes parlent d'agent sans clairement spécifier ce qui peut différencier un agent de tout autre programme informatique. C’est pourquoi assez souvent la discussion sur les agents se concentre sur des choses qui ne semble pas les différencier de beaucoup avec les objets distribués comme par exemple quand il est question d’existence indépendante, de contrôle distribué, d’encapsulation et d’autonomie, de communication et d’interaction avec d'autres entités d'une façon structurée, etc. Aussi, pour bien comprendre le pourquoi de la notion d’agent, faut-il retourner à l'histoire de la programmation et placer le concept d'agent dans une progression historique, une progression des techniques pour la description et l'action. Voici donc quelques modèles qui ont marqué l’histoire de l’IAD.

Blackboard
Le modèle de blackboard définit une architecture qui organise la résolution de problèmes par coopération de plusieurs modules, appelés sources de connaissances (SC), autour d'une base de données partagée appelée blackboard.

Fig.1 : Architecture de blackboard

Chaque SC vient lire ou écrire sur le blackboard de façon simultanée et opportuniste. D'une façon générale, le rôle d'une SC est de résoudre un sous-problème particulier en fonction de l'état du blackboard : la SC apporte ainsi sa contribution à la résolution des problèmes identifiés. Ce modèle vise la mise en oeuvre d'une résolution opportuniste, où le choix de la SC à activer est déterminé en fonction des critères de contrôle actifs. (Fig.1 Architecture de blackboard)

En 1973 Hayes-Roth mis au point la première architecture à base de blackboard : Hearsay II. Ce système devait intégrer des connaissances pour résoudre les problèmes d'incertitude en reconnaissance de la parole. En effet, la problématique était l’interprétation de l'anglais parlé pour identifier une requête sur une base de données de résumés d’article d’Intelligence Artificielle (IA) comme par exemple répondre à la question : Quel résumé fait référence à la théorie des jeux ? Quels articles J. Ferber a-t-il écrit ?

Pour réaliser cela, le système part d'une représentation paramétrée du signal de la parole. Il génère ensuite des hypothèses intermédiaires sur les segments acoustiques/phonétiques, les syllabes, les mots, les séquences de mots, les phrases que le signal représente. (fig.2 : niveaux et sources de connaissances dans Herasay II)



Fig.2 : Niveaux et sources de connaissances

Depuis de nombreux autres systèmes se sont développés comme en témoigne le graphique donné en annexe montrant l’évolution des systèmes de blackboard. (Annexe II : Evolution des systèmes de blackboard).

Le Blackboard a apporté un cadre de travail pour structurer et contrôler le comportement d'un système de résolution mettant en œuvre des sources de connaissance multiples, variées et pouvant donner lieu à des erreurs. Il constitue la première tentative intéressante d'organisation de composants logiciels autonomes. A ce titre, il a gagné ses lettres de noblesse dans de nombreuses applications (reconnaissance des formes, de la parole, analyse de plans, aide à la conception, etc.) et continue à être extrêmement employé. Les tendances actuelles s'orientent vers la parallélisation des SC et le fonctionnement temps-réel.

Cependant, le modèle de blackboard est insatisfaisant quant à son aspect centralisé, en particulier en donnant une vision globale du problème sous forme d'une base de données partagée. Le contrôle, pour des raisons de cohérence de la base de connaissance, est souvent centralisé et n'est pas laissé à l'initiative des SC. Aucune communication autre que celle concernant le domaine n'est admise entre les SC. De ce fait, la plupart des applications à base de blackboard ne sont guère différentes d'un système expert organisant les règles de production par paquet...! Ce sont les travaux sur le modèle acteur qui ont abouti à une nouvelle conception des systèmes d'IAD.

Modèle acteur
Le modèle acteur est développé au MIT par l'équipe de C. Hewitt. A l'origine, ce modèle a été conçu pour résoudre des problèmes d'IA, il a abouti à une conception des systèmes distribués, en l'occurrence, les systèmes ouverts. Devant fonctionner de la manière la plus indépendante possible, ces systèmes sont selon Hewitt des systèmes distribués, ayant les caractéristiques suivantes :
ils sont concurrents et asynchrones, avec un contrôle décentralisé ;
ils sont composés d'entités indépendantes en évolution continue ;
ils sont facilement extensibles ;
chaque entité ne possède qu'une vision partielle du système ;
elle doit négocier avec les autres pour coopérer.

Acteur vs. Objet
Le modèle acteur est une extension du modèle objet par ajout de la notion d'activité. Dans les modèles objets, le modèle de calcul est un transfert de contrôle de l'objet expéditeur à l'objet receveur de message, ce qui signifie que l'activité principale est l'allocation du processeur à un objet. Un seul objet est donc actif à la fois et ce sont les messages qui activent les objets. Au contraire, dans le modèle acteur le modèle de calcul est un transfert d'information (requête) entre processus concurrents :
Les acteurs sont des objets actifs, autonomes, communiquant par envoi de messages asynchrones avec les autres acteurs.
Ils peuvent être concurrents ; on parle alors de Programmation Orientée Objet Concurent (POOC).
Ils sont composés d’un ensemble limité de connaissances : les acteurs connus d’un acteur sont appelés ses accointances et son comportement est défini par un script.
Ils peuvent déléguer des messages à d’autres acteurs quand ils ne peuvent le traiter seuls.
Ainsi le modèle d'acteur de C. Hewitt et G. Agha est un modèle pour les calculs concurrents. Il offre une approche modulaire de la concurrence et un mécanisme de communication qui repose uniquement sur l'envoi de messages. Simple et anthropomorphique, il permet la description naturelle des problèmes sous forme d'une communauté dynamique d'entités autonomes et indépendantes, les acteurs, qui communiquent entre elles et coopèrent pour la résolution d'un but commun. Les acteurs modélisent des objets conceptuels ou physiques, et les messages correspondent à des demandes ou à des transferts d'information.
Les acteurs sont des objets concurrents qui encapsulent chacun une partie de la connaissance et du contrôle répartis. Le comportement d'un acteur est composé d'une partie accointances et d'une partie opératoire. Un acteur traite en série les messages qu'il reçoit. En réponse à un message un acteur peut simultanément créer dynamiquement de nouveaux acteurs, envoyer des messages aux acteurs qu'il connaît, et remplacer son comportement courant par celui qui va traiter le prochain message. Les acteurs sont identifiés de manière unique par une adresse.
Analogue à un service postal, la communication est asynchrone, point à point, unidirectionnelle et sûre. L'ordre aléatoire d'arrivée des messages rend le calcul non déterministe.

Le protocole Contract Net
En 1982, R.G.Smith crée le protocole du Contract Net, un système de résolution de problème distribué. Ce dernier fut une des premières solutions au problème d’allocation de tâches auquel fait face généralement un ensemble de résolveurs de problèmes.

Dans ce protocole, les agents peuvent prendre deux rôles: gestionnaire ou contractant. L’agent qui doit exécuter une tâche donnée (le gestionnaire) commence tout d’abord par décomposer cette tâche en plusieurs sous tâches. Il doit ensuite annoncer les différentes sous tâches au reste des agents de l’environnement. Les agents qui reçoivent une annonce de tâche à accomplir peuvent ensuite faire une proposition devant refléter leur capacité à remplir cette tâche. Le gestionnaire rassemble ensuite toutes les propositions qu’il a reçues et alloue la tâche à l’agent ayant fait la meilleure proposition.

Ce protocole utilise ainsi le concept de négociation pour adjuger des contrats et l'architecture de base contient des noeuds ayant des rôles de chef (le gestionnaire) et d'exécutants (le contractant).

DVMT
La surveillance de véhicules motorisés tournait, quant à elle, autour du système DVMT (Distributed Vehicle Monitoring Task) [Corkill 83]. Ce système avait comme tâche principale d’identifier quel type de véhicule circulait dans la zone où étaient placés ses senseurs. À partir de ces interprétations, il devait tenter d’établir une description des mouvements des véhicules dans la région qu’il supervisait. Comme bien d’autres système s multi-agents de l’époque, le système DVMT utilisait un blackboard pour coordonner les efforts de ses différents agents.

Devant les limitations des technologies jusqu’alors développé, une nouvelle approche en IAD s’est développée dont l’objectif est de faire interagir / coopérer des entités auxquelles sont rattachées des caractéristiques de bas ou haut niveau, tout en essayant de respecter les principes des systèmes ouverts. Ces entités seront désormais nommées agents et les systèmes correspondants seront appelés systèmes multi-agents.

Le concept d’agent
Définition
Le concept d’agent a fait l’objet d’études depuis plusieurs décennies dans différentes disciplines. Il a été non seulement utilisé dans les systèmes à base de connaissances, la robotique, le langage naturel et d’autres domaines de l’IA, mais aussi dans des disciplines comme la philosophie et la psychologie. Tant et si bien qu’on utilise le terme à tort et à travers dans bien des cas…

Il n’existe pas encore un consensus sur la définition d’un agent ; en plus de la relative jeunesse du domaine, diverses communautés revendiquent ce terme avec des problématiques parfois au départ assez différentes (par exemple en ce qui concerne les agents mobiles) même si ces différentes problématiques sont complémentaires et conduites à se rencontrer à terme.

Les multiples définitions d’agent trouvées dans la littérature diffèrent selon le type d’application pour laquelle est conçu l’agent : diverses caractéristiques sont alors plus ou moins affectées à la terminologie agent qui voit alors ces capacités accrues ou non. Nous trouvons dans « Is it an agent or a program ? »[1] une discussion sur les différentes définitions attribuées aux agents ainsi que la différence entre un agent et un programme classique.

Pour ôter toute ambiguïté sur l’utilisation future du terme, nous utiliserons tout au long de ce rapport l’une des premières définitions de l’agent donnée par Jacques Ferber [2] :

« On appelle agent une entité physique ou virtuelle
Qui est capable d’agir dans un environnement,
Qui peut communiquer directement avec d’autres agents,
Qui est mue par un ensemble de tendances (sous la forme d’objectifs individuels ou d’une fonction de satisfaction, voire de survie qu’elle cherche à optimiser),
Qui possède des ressources propres,
Qui est capable de percevoir (mais de manière limitée) son environnement,
Qui ne dispose d’une représentation partielle de cet environnement (et éventuellement aucune),
Qui possède des compétences et offre des services,
Qui peut éventuellement se reproduire,
Dont le comportement tend à satisfaire ses objectifs, en tenant compte de des ressources et de des compétences dont elle dispose, et en fonction de sa perception, de ses représentations et des communications qu’elle reçoit. »

Dès lors, les agents sont en général situés dans un environnement (par exemple, topologique) contenant également des entités passives, manipulées par les agents (par exemple, des ressources, des données, des objets physiques…) et communément appelées objets.

Il ressort de cette définition des propriétés clés comme
l’autonomie et l’action : l’agent est capable d’agir sans l’intervention d’un tiers (humain ou agent) et contrôle ses propres actions ainsi que son état interne;
la perception : c’est par la perception que l’agent acquiert des informations sur le monde pour lui permettre d’élaborer son action en poursuivant ses buts.
la communication : elle permet aux agents d’agrandir leur capacités de perception en leur permettant d’échanger des informations ou de véhiculer des requêtes.

D’autres propriétés peuvent être attribuées aux agents. Nous citons en particulier :
la réactivité : l’agent perçoit son environnement (monde physique, utilisateur via une IHM, un ensemble d’autres agents, Internet ou peut-être tous ceux-là ensemble) et réponds dans le temps aux changements qui y arrivent.
la rationalité : d’après Ferber, « un agent est rationnel s’il ajuste ses fins aux moyens qu’il se propose de faire, ce que l’on peut résumer en écrivant qu’un agent qui a l’intention de faire P le fera s’il en a la compétence. »
l’engagement : en construisant un plan pour atteindre un but, l'agent se donne les moyens d'y parvenir et donc s'engage à accomplir les actions qui satisfassent ce but.
l’intention : elle décrit ce qui meut l’agent, ce qui lui permet de passer à l’acte

Si l’on replace maintenant la notion d’agent dans l’histoire de la programmation, on peut voir l’évolution à deux niveaux.

Au plan individuel, l’agent se caractérise par une notion d’action persistante [3], qui tente de manière autonome (et avec initiative) d’accomplir une certaine mission qui lui a été assignée. On sort donc du cadre procédural classique, ce qui permet à l’agent de faire face à des situations non nécessairement prévues à l’avance par le concepteur. On sort également du cadre uniquement déclaratif, puisque l’agent doit pouvoir contrôler lui-même (forme supplémentaire d’autonomie) l’utilisation de ses ressources pour accomplir sa mission.

Au plan collectif, on peut aussi considérer l’idée de système multi-agents comme une évolution de la notion de composant logiciel (objet) pour lequel le couplage entre composants est abordé au niveau des connaissances et pas au niveau des types de données [4]. Ceci permet donc un couplage sémantiquement de niveau plus élevé et donc moins rigide et plus adaptable. C’est ce que nous verrons plus en détail plus loin avec l’étude à proprement parlé des SMA.


Les agents ont deux tendances :
une tendance sociale tournée vers la collectivité (les mécanismes et connaissances associés concernent les activités du groupe) : c’est ce que nous verrons plus en détail dans le prochain chapitre consacré aux systèmes multi-agents
une tendance individuelle avec des mécanismes et des connaissances contenant les règles de fonctionnement interne de l'agent : c’est ce que nous allons voir avec l’étude des architectures d’agents réactifs et cognitifs.


Classification des agents

Bien qu’il existe une multitude de classification possible des agents 13] (collaborative agent, interface agent, mobile agent, information agent, etc.), on les classe généralement en fonction de leurs capacités de résolution de problèmes en deux grandes familles : les agents réactifs et les agents cognitifs. [Annexe III : Comparatif entre agents cognitifs et agents réactifs]

Agents réactifs

Les défenseurs de cette approche partent du principe suivant : dans un système multi-agents, il n'est pas nécessaire que chaque agent soit individuellement « intelligent » pour parvenir à un comportement global intelligent. En effet, des mécanismes simples de réactions aux événements peuvent faire émerger des comportements correspondant aux objectifs poursuivis. Cette approche propose la coopération d'agents de faible granularité (fine grain) mais beaucoup plus nombreux.

Les agents réactifs sont donc bas niveau, ils ne disposent que d'un protocole et d'un langage de communication réduits, leurs capacités répondent uniquement à la loi stimulus/action.
Les premiers travaux relatifs à cette approche ont été réalisés au MIT en 1986 par R. Brooks. D'après lui, plusieurs milliers de micro-robots identiques, d'une taille aussi petite que possible, travaillant ensemble sur une tâche donnée pourront être plus efficaces qu'un seul gros robot spécialisé
Ainsi, au sein de son programme de recherche, il a développé l’architecture subsumption. Dans cette architecture, on bâtit des agents sans utiliser de représentation symbolique ni de raisonnement. Un agent est alors vu comme un ensemble de comportements accomplissant une tâche donnée. Chaque comportement est une machine à états finis qui établit une relation entre une entrée sensorielle et une action en sortie.

Typiquement, l’ensemble des comportements est représenté sous forme d’une hiérarchie dans laquelle les couches des niveaux inférieurs représentent des comportements moins abstraits et les couches des niveaux supérieurs, des comportements plus abstraits. Le développement d’un agent devient donc un processus où l’on devra expérimenter avec les nouveaux comportements. Ceci est habituellement accompli en plaçant l’agent dans son environnement et en observant les résultats.

En France on peut citer les travaux de J. Ferber à l'Université de Paris VI, qui a travaillé sur le langage MERING [5], un langage concurrent pour la représentation des connaissances qui peut être utilisé comme une plate-forme pour la conception de systèmes multi-agents réactifs.

Les agents réactifs n’ont donc pas de connaissances explicites de l’environnement, ni des autres agents, ni de leur passé, pas plus que de leurs buts (pas de planification de leurs actions, pas de moyens de mémorisation). Ils possèdent une fonction de perception / action sur l’environnement qui constitue l’unique protocole de communication avec les autres agents. Il s’agit d’une communication via l’environnement. La figure ci-dessous présente un modèle d’agent réactif.



Critiques :
Bousquet et Lepage [6] reviennent en détails sur ce type d’approche généralement utilisée pour la simulation. Malgré la simplicité apparente et les bon résultats obtenus pour certaines applications, bien des reproches ont été adressés à cette approche dite “réactive”, parmi lesquels, il convient de voir que:
si les agents ne possèdent pas de modèle de leur environnement, ils doivent posséder suffisamment d’informations locales leur permettant de choisir une action acceptable;
comme les agents basent leurs décisions sur des informations locales, il est difficile de voir comment ils pourraient tenir compte des informations non locales ;
il est difficile de voir comment un agent purement réactif peut apprendre de son expérience et améliorer ainsi ses performances;
le comportement global d’un agent devrait émerger des interactions entre les divers comportements qui le composent, cette émergence rend donc très difficile la tâche de construire un agent dans le but d’effectuer une tâche spécifique;
s’il est assez simple de bâtir un agent qui comporte très peu de couches, l’exercice devient beaucoup plus compliqué lorsqu’on a besoin de plusieurs couches. Les interactions dynamiques entre les diverses couches deviennent trop complexes à comprendre.

Agents cognitifs

A l’opposé des agents réactifs, les agents cognitifs sont capables à eux seuls de réaliser des opérations relativement complexes et généralement coopèrent les uns avec les autres pour atteindre un but commun (résolution d’un problème, tâche complexe, etc.).

Ils possèdent un ensemble de représentations explicites (sur l’environnement, sur les autres agents et sur eux-mêmes) décrits dans une base de connaissances sur laquelle ils peuvent raisonner. Les théories de avec les agents BDI (Beliefs-Desires-Intention) [10] [10a] [10b] leur attribuent même des attitudes « mentales » comme :
Les croyances : ce que l’agent connaît de son environnement,
Les désirs : les états possibles vers lesquels l’agents peut vouloir s’engager,
Les intentions : les états envers lesquels l’agent s’est engagé et envers lesquels il a engagé des ressources.
Un agent BDI doit donc mettre à jour ses croyances avec les informations qui lui proviennent de son environnement, décider quelles options lui sont offertes, filtrer ces options afin de déterminer de nouvelles intentions et poser ses actions au vu de ses intentions. Voir également celle de Shoham avec AOP (Agent-Oriented Programming).[7]

Ils réagissent ainsi en fonction de leurs connaissances, de leurs buts, de leurs échanges avec les autres agents et de la perception de l’environnement en organisant leurs actions suivant une planification.

Ils sont dotés de moyens et mécanismes de communication pour gérer les interactions avec les autres agents (coopération, négociation). La figure ci-dessous présente un modèle d’agent cognitif.



Critiques :
On peut reprocher aux agents cognitifs d’avoir une implémentation lente et de poser quelques problèmes d’apprentissage. Néanmoins, l’école cognitive a donné lieu jusqu’à maintenant aux applications les plus avancées, la complexité des systèmes réactifs exigeant le développement de nouvelles théories dans le domaine de la coopération, de la communication et de la compréhension de nouveaux phénomènes telle que l’émergence.


Agents hybrides

Dès le début des années 90, on savait que les systèmes réactifs pouvaient bien convenir pour certains types de problèmes et moins bien pour d’autres. De même, pour la plupart des problèmes, les solutions de l’IA classique, basées uniquement sur la planification, ne conviennent pas non plus. On commence dès lors à investiguer la possibilité de combiner les deux approches afin d’obtenir une architecture hybride [8] [9]. Dans ce cas, un agent est composé de plusieurs couches, arrangées selon une hiérarchie, la plupart des architectures considérant que trois couches suffisent amplement :
Au plus bas niveau de l’architecture, on retrouve habituellement une couche purement réactive, qui prend ses décisions en se basant sur des données brutes en provenance des senseurs.
La couche intermédiaire fait abstraction des donnés brutes et travaille plutôt avec une vision qui se situe au niveau des connaissances de l’environnement.
Finalement, la couche supérieure se charge des aspects sociaux de l’environnement, c’est à dire du raisonnement tenant compte des autres agents.


Architectures diverses

Malgré une évolution continue et un progrès récent considérable, les architectures d'agents utilisées actuellement sont pour la plupart basées sur des modèles anciens et elles dérivent de quelques familles de modèles largement décrites. Dans son livre [2], Jacques Ferber détaille l'aspect fonctionnel des architectures d'agents les plus utilisées dans la littérature :

Architecture modulaire horizontale
Il s’agit d’un ensemble de module effectuant une fonction horizontale particulière comme : les fonctions perceptives et motrices, l’émission et l’interprétation de communications, la base des croyances (modélisation de l’environnement et des autres agents), gestion des engagements, expertises du domaine de compétence, gestion des buts et prise de décision, planification des actions, etc. Le mode de circulation des informations est fixe (déterminé par le concepteur).



Tableaux noirs ou blackboard
Ils comprennent 3 sous-systèmes :

les Knowledge sources (KS) qui communique via le tableau noir (ou BB),

La base partagée (ou BB) comprends les états partiels du problème en cours de résolution, les hypothèses et les résultats intermédiaires.

Un dispositif de contrôle qui gère les conflits d’accès entre les KS qui interviennent de manière opportuniste. C’est cette partie qui a fait l’objet de plus de modifications au cours de l’évolution des architectures.







L’architecture BB1 de B. Hayes-Roth (1985), le système ATOME de Lâasri et Maître (1989) sont des illustrations de cette architecture. [11] [12]

Cette architecture est très pratique pour réaliser la structure interne d’agents cognitifs symboliques mais pas pour les SMA car le contrôle est trop centralisé, il manque de mémoire locale et l’information est trop localisée.


Architecture de subsomption


Proposée par R. Brooks, elle décompose un agent en modules verticaux, chacun d’eux n’étant responsable que d’un type de comportement très limité. Les interactions sont fixes et hiérarchiques : les modules effectuent leur tâches en parallèles et les informations fournies par le module dominant seront prioritaires par rapport à celles du module inférieur. En voici un exemple pour un agent dont l’objectif est la découverte d’un planète : déplacement, cartographie du site, prélèvement d’objet, etc.


Tâches compétitives
Cette architecture introduit une certaine mutualité dans les liens inter-modules. L’agent est alors composé d’un ensemble de tâches (une seule active à la fois) en compétition pour être élue par un mécanisme de décision selon le poids de la tâche à l’instant t, le contexte d’application, les informations extérieures, etc.

L’architecture MANTA de Drogoul et Ferber (1994) en est une illustration. (Fig. Architecture Manta ci-dessous)

Fig. Architecture MANTA


Les systèmes de production (ou SE)
Il est composé par une base de faits (BF), d’une base de règles (BR) et d’un interprète, le moteur d’inférence (MI).

Cette architecture présente cependant des inconvénients majeurs :
Le SE n’est pas tolérant à l’absence de règles dans la base,
Les règles dans la BR ne sont pas combinables,
Enfin, le résultat du MI dépend de l’ordre d’application des règles.

Fig. : Architecture à base de système expert


Essentiellement utilisée pour créer des comportements adaptatifs, les systèmes à base de classifieurs sont en vérité une variante des systèmes de production pour lesquels la base de règle est alimentée par un systèmes de reproduction de règles par algorithme génétique et doté d’un système d’attribution de crédit (pour récompenser les règles qui ont permis à l’aboutissement d’un but).

Les architectures connexionnistes à base de réseaux de neurones.
Les poids de connexions entre les neurones sont définis soit à la main, soit par apprentissage (backpropagation), soit en les faisant évoluer à l’aide d’algorithmes génétiques.


Conclusion
On pose souvent la question de savoir ce qui distingue la notion d’agent de celle d’objet ou d’acteur. La réponse est simple : dans le domaine informatique, les termes “objet” et “acteur” désignent des entités informatiques caractérisées par leur structure et leurs mécanismes d’exécution. [14]

La notion d’objet est définie par trois concepts :
la relation classe/instance, qui décrit la classe comme un modèle structural et comportemental et l’instance comme un représentant d’un modèle ;
l’héritage, qui permet de dériver une classe d’une autre et de faire bénéficier la première des caractéristiques de la seconde ;
enfin l’envoi de message, qui permet de définir des procédures polymorphes, c’est-à-dire des procédures dont le code diffère en fonction du receveur du message.

Si le concept d’agent comme objet distribué est très proche de celui de l’objet, il n’en est pas de même de l’agent comme entité intentionnelle. En effet les objets n’ont ni but ni recherche de satisfaction et le mécanisme d’envoi de message se résume à un simple appel de procédure. Il n’y a pas de langage de communication à proprement parler. Les mécanismes d’interaction sont donc à la charge du programmeur.

Plus encore, il existe une différence essentielle entre les objets et les agents : un objet est défini par un certain nombre de services (ses méthodes) qu’il ne peut refuser d’exécuter si un autre objet le lui demande et les messages sont donc nécessairement des invocations de méthodes. Le développeur d’un logiciel “objet” doit donc vérifier que tous les objets recevront bien des ordres sensés qu’ils seront effectivement capables d’exécuter. Par rapport aux objets, les agents peuvent recevoir des messages qui ne sont pas uniquement des demandes d’exécution mais aussi des informations ou des demandes d’informations sur leurs capacités, etc. De ce fait, les services que peut rendre un objet, sont donc filtrés par une couche logicielle qui découple les demandes et le fonctionnement interne de l’agent.

Enfin, comme nous l’avons dit, les agents tentent de satisfaire des objectifs, ce qui leur procure une autonomie supplémentaire par rapport aux objets. En effet, l’agent, à l’encontre de l’objet, peut refuser d’accepter d’effectuer un certain travail, ce refus pouvant s’expliquer par son manque de compétence (il ne possède pas le savoir-faire nécessaire) ou par sa trop grande occupation à une autre tâche ou par toute autre raison. Un agent “encapsule” les méthodes qu’un objet peut offrir sous la forme d’un ensemble de services qui ne sont accessibles que par un langage particulier connu de l’ensemble des agents et qui utilise généralement la théorie des actes de langages.

Mais le lien qui existe entre objets et agents ne doit pas non plus être sous estimé. Si un agent purement communicant, peut être considéré comme une sorte d’objet amélioré, inversement, un objet peut passer pour un agent dégénéré, c’est-à-dire un agent dont le langage d’expression se résume à l’emploi des mots clés correspondant à ses méthodes.

Enfin, et c’est d’ailleurs ce qui augmente encore la confusion possible, on implémente souvent, pour des raisons pratiques, les agents sous la forme d’objets ou d’acteurs. Ceci n’est pourtant qu’une des implémentations possibles. On peut de la même manière implémenter des agents en Fortran, C ou Lisp, qui ne sont pas naturellement des langages à objets, sans que cela modifie en quoi que ce soit leur caractère d’agent.
LES SYSTEMES MULTI-AGENTS


Les systèmes multi-agents (SMA) mettent en œuvre un ensemble de concepts et de techniques permettant à des logiciels hétérogènes, ou à des “agents” de coopérer suivant des modes complexes d’interaction.

La technologie des SMA s’est développée ces dernières années sous une quadruple pression :

La première est due aux limites de l’IA classique sur le plan de la structuration et de l’organisation des connaissances. La difficulté qu’il y a à traduire un ensemble d’expertises sous une forme unifiée a amené les chercheurs à développer ce que l’on a d’abord appelé des systèmes multi experts, c’est-à-dire des systèmes mettant en jeu plusieurs bases de connaissances plus ou moins coordonnées. Ce faisant, on a pu constater que le problème de la coopération entre plusieurs bases de connaissances se révélait un enjeu crucial qui dépassait de loin le problème de la multi expertise.

La deuxième trouve son origine dans la nécessité de trouver des techniques de modélisation et de simulation performantes dans le domaine des sciences du vivant au sens large du terme. L’évolution des écosystèmes habités, notamment, montre qu’il est difficile de rendre compte de leur évolution par un ensemble d’équations différentielles. Une approche dans laquelle les individus sont directement représentés sous forme d’entités informatiques semble une voie prometteuse et a contribué à l’essor du domaine.

La troisième provient de la robotique. Le développement de la miniaturisation en électronique permet de concevoir des robots qui disposent d’une certaine autonomie quant à la gestion de leur énergie et à leur capacité de décision. On a pu alors montrer qu’un ensemble de petits robots ne disposant que de capacités élémentaires de décision et d’intelligence pouvait facilement rivaliser avec les performances d’un seul robot “intelligent”, nécessairement plus lourd et plus difficile à gérer. Le problème alors revient, ici encore, à faire coopérer ces entités de manière à ce qu’elles assurent les fonctions désirées.

Enfin, la quatrième est issue du développement de l’informatique et des systèmes distribués en particulier. Avec la généralisation des réseaux et des ordinateurs parallèles, il devient de plus en plus important de pouvoir faire coopérer plusieurs composants logiciels au sein d’environnements hétérogènes, distribués, à très grande échelle et ouverts. Le problème ne réside plus dans le contenu des programmes, qui peuvent avoir des fonctionnalités diverses, mais dans leur capacité à collaborer avec d’autres programmes à la réalisation d’un objectif commun.


Ce chapitre détaille les différentes questions que soulèvent la problématique des SMA, en particulier : les interactions et la coopération, la coordination, la planification et la communication.




Définition

On appelle systèmes multi-agents (ou SMA) [2] un système composé des éléments suivants :

Un environnement E, c’est-à-dire un espace disposant généralement d’une métrique.
Un ensemble d’objets O. Ces objets sont situés c’est-à-dire que pur tout objet il est possible à un moment donné d’associer une position dans E. Ces objets sont passifs c’est-à-dire qu’ils peuvent être perçus, créés, détruits et modifiés par les agents.
Un ensemble A d’agents qui sont des objets particuliers (A ( O) lesquels représentent les entités actives du système
Un ensemble de relations R qui unissent des objets (et donc des agents) entre eux.
Un ensemble d’opérations Op permettant aux agents de A de percevoir, produire, consommer, transformer et manipuler des objets de O.
Des opérateurs chargés de représenter l’application de ces opérations et la réaction du monde à cette tentative de modification que l’on appellera les lois de l’univers.

La figure ci-dessous donne une représentation imagée d’un agent en interaction avec son environnement et les autres agents :

 SHAPE \* MERGEFORMAT 
Contrairement aux systèmes d’IA, qui simulent dans une certaine mesure les capacités du raisonnement humain, les SMA sont conçus et implantés idéalement comme un ensemble d’agents interagissant, le plus souvent, selon des modes de coopération, de concurrence ou de coexistence. [15] [16]

Chaque agent possède des informations et des capacités de résolution (compétences) restreintes et ainsi chaque agent n’a qu’un point de vue partiel du système. Les données et les informations sont dès lors décentralisées. Fonctionnant en mode asynchrone, le SMA ne disposant alors d’aucun système centrale de contrôle.

Les SMA sont des systèmes idéaux pour représenter des problèmes possédant de multiples méthodes de résolution, de multiples perspectives et/ou de multiples résolveurs.

Ces systèmes possèdent les avantages traditionnels de la résolution distribuée et concurrente de problèmes comme la modularité, la vitesse (avec le parallélisme), et la fiabilité (due à la redondance).

Ils héritent aussi des bénéfices envisageable de l’Intelligence Artificielle comme le traitement symbolique (au niveau des connaissances), la facilité de maintenance, la réutilisation et la portabilité mais surtout, ils ont l’avantage de faire intervenir des schémas d’interaction sophistiqués. Les types courants d’interaction incluent la coopération (travailler ensemble à la résolution d’un but commun), la coordination (organiser la résolution d’un problème de telle sorte que les interactions nuisibles soient évitées ou que les interactions bénéfiques soient exploitées), et la négociation (parvenir à un accord acceptable pour toutes les parties concernées).

Cependant, bien que les SMA offrent de nombreux avantages potentiels, ils doivent aussi relever beaucoup de défis.
Comment formuler, décrire, décomposer, et allouer les problèmes et synthétiser les résultats ?
Comment permettre aux agents de communiquer et d’interagir ? Quoi et quand communiquer ?
Comment assurer que les agents agissent de manière cohérente en prenant leurs décisions ou actions, en gérant les effets non locaux de leurs décisions locales et en évitant les interactions nuisibles ?
Comment permettre aux agents individuels de représenter et raisonner sur les actions, plans et connaissances des autres agents afin de se coordonner avec eux? Comment raisonner sur l’état de leurs processus coordonnés (comme l’initialisation ou la terminaison) ?
Comment reconnaître et réconcilier les points de vue disparates et les intentions conflictuelles dans un ensemble d’agents essayant de coordonner leurs actions ?
Comment trouver le meilleur compromis entre le traitement local au niveau d’un seul agent et le traitement distribué entre plusieurs agents (traitement distribué qui induit la communication) ? Plus généralement, comment gérer la répartition des ressources limitées ?
Comment éviter ou amoindrir un comportement nuisible du système global, comme les comportements chaotiques ou oscillatoires ?

Interaction et coopération

Un système multi-agents (SMA) se distingue d’une collection d’agents indépendants par le fait que les agents interagissent en vue de réaliser conjointement une tâche ou d’atteindre conjointement un but particulier.

Une interaction est une mise en relation dynamique de deux ou plusieurs agents par le biais d’un ensemble d’actions réciproques. Les interactions s’expriment ainsi à partir d’une série d’actions dont les conséquences exercent en retour une influence sur le comportement futur des agents.

Pour interagir, les agents sont donc en contact les uns avec les autres en communiquant :
soit directement entre eux,
soit par l’intermédiaire d’un autre agent
soit en agissant sur leur environnement.

Les interactions des agents d’un SMA sont motivées par l’interdépendance des agents selon ces trois dimensions:
leurs buts peuvent être compatibles ou non;
les agents peuvent désirer des ressources que les autres possèdent;
un agent X peut disposer d’une capacité nécessaire à un agent Y pour l’accomplissement d’un des plans d’action de Y.

Dans le cadre des système s multi-agents on doit traiter la question fondamentale qui est l’implantation de la coopération entre les agents. Durfee et ses collègues [20] ont proposé quatre buts génériques pour établir la coopération dans un groupe d’agents:
augmenter le taux de finalisation des tâches grâce au parallélisme;
augmenter le nombre de tâches réalisables grâce au partage de ressources (information, expertise, dispositifs physiques, etc.);
augmenter les chances de finaliser des tâches en les dupliquant et en utilisant éventuellement des modes de réalisation différents;
diminuer les interférences entre tâches en évitant les interactions négatives.

En fait, on peut caractériser un système par le type de coopération mis en œuvre qui peut aller de la coopération totale à l’antagonisme total [Moulin 96].
Des agents totalement coopératifs peuvent changer leurs buts pour répondre aux besoins des autres agents afin d’assurer une meilleure coordination entre eux. Cela peut résulter en des coûts de communication élevés.
Les agents antagonistes par contre, ne vont pas coopérer et dans ce cas, leurs buts respectifs vont se trouver bloqués. Dans de tels systèmes, les coûts de communication sont minimaux.

La plupart des systèmes réels se situe entre les deux extrêmes : coopération totale et antagonisme total.

La coopération totale est mise en oeuvre par exemple dans les approches de résolution coopérative de problèmes distribués (“cooperative distributed problem solving” ou CDPS) proposée par Durfee et ses collègues [21]. Dans ces approches, les agents coopèrent pour résoudre des problèmes qu’ils ne peuvent pas résoudre individuellement. Tout d’abord chaque agent utilise ses connaissances et ressources pour résoudre localement un ou plusieurs sous-problèmes. Les solutions partielles à tous les sous problèmes sont par la suite intégrés. C’est par exemple le cas des avions qui volent dans un même espace aérien et qui, de ce fait, ont différentes perceptions de leur espace environnant obtenues par leurs senseurs respectifs. Ce n’est qu’en combinant ces différentes perceptions que ces avions peuvent obtenir une vue globale afin de résoudre les conflits potentiels qui peuvent se produire entre eux.

Ferber [2] remarque que les chercheurs ont développé différents points de vue sur la coopération. Ainsi, on peut considérer la coopération comme une attitude adoptée par les agents qui décident de travailler ensemble ou on peut adopter le point de vue d’un observateur extérieur au système multi-agents qui interprète a posteriori les comportements des agents pour les qualifier de coopératifs ou non suivant des critères préétablis tels que l’interdépendance des actions ou le nombre de communications effectuées. Dans le cas de la coopération vue comme une attitude intentionnelle, les agents s’engagent dans une action après avoir identifié et adopté un but commun.

Interactions entre agents coopératifs

La planification pour un seul agent ne fait que construire une séquence d’actions en ne considérant que les buts de l’agent, ses capacités et les contraintes imposées par son environnement. Par contre, dans un environnement multi-agents, on se doit de tenir compte
des contraintes que les actions des autres agents placent sur le choix des actions de l’agent;
des contraintes que les engagements de l’agent envers les autres imposent sur son propre choix d’action;
ainsi que l’évolution imprévisible de l’environnement due à des agents qui
ne sont pas modélisés.

Les premiers travaux en intelligence artificielle distribuée étaient principalement concentrés sur des groupes d’agents qui poursuivaient des buts communs. On choisit alors de privilégier une approche selon laquelle on planifie avant d’agir. Ainsi, afin de produire un plan cohérent, les agents doivent être en mesure de reconnaître les interactions entre les différents sous-buts pour pouvoir, soit les ignorer, soit les résoudre.

Une autre approche intéressante pour résoudre les interdépendances entre les sous-buts a été le “Functionnally Accurate Model” [22], [23] dans lequel les agents n’ont pas besoin d’avoir toutes les informations nécessaires pour résoudre les conflits localement. Les interactions se font plutôt par un échange asynchrone de résultats partiels. À partir de ces modèles ont apparus plusieurs principes de coordination, parmi lesquels on retrouve le Partial Global Planning [24], [25].

La Planification Partielle Globale (en anglais GPP pour Global and Partial Planning) est une approche flexible qui permet aux divers agents d’un système de se coordonner dynamiquement. Les agents interagissent en se communiquant leurs plans et leurs buts selon un niveau d’abstraction approprié. Ces communications permettent à chacun d’anticiper quelles seront les actions futures d’un ou de plusieurs autres agents, augmentant ainsi la cohérence de l’ensemble des agents. Comme les agents coopèrent, le receveur d’un message peut utiliser les informations reçues afin d’ajuster sa propre planification.

Un autre courant de recherche sur la coordination des agents consiste à modéliser explicitement le travail d’équipe qu’effectuent les agents. Cette approche s’avère très pratique dans des environnements dynamiques où les membres de l’équipe peuvent échouer dans leurs tâches ou découvrir de nouvelles opportunités. Dans de telles situations, l’équipe doit pouvoir évaluer sa performance et être en mesure de se réorganiser en conséquence. Dans cet ordre d’idées, on parle alors du modèle des “intentions conjointes” [26], [27]. Dans ce modèle, on cherche à modéliser l’état mental d’une équipe en action. L’équipe aura une intention conjointe si chaque membre de l’équipe est engagé à compléter l’action de l’équipe. Préalablement à cette intention collective, tous les membres de l’équipe auront établi les croyances et les engagements communs appropriés, et ce en s’échangeant des actes (du langage naturel) de requête et de confirmation.

Interactions entre agents égocentrés

Les interactions entre agents égocentrés se basent principalement sur la négociation. Cette dernière devient donc une méthode de coordination et de résolution de conflits. Elle a également été utilisée comme métaphore pour la communication de changements dans les plans, l’allocation de tâches ainsi que la résolution centralisée de violation de contraintes. On peut donc voir que la définition de la négociation est aussi imprécise que celle du concept d’agent. On arrive malgré tout à retrouver certaines caractéristiques importantes de la négociation: la présence d’une forme de conflit qui doit être résolu de façon décentralisée par de agents égocentrés ayant une rationalité limitée et des informations incomplètes. De plus, les agents communiquent et échangent de façon itérative des propositions et des contre-propositions.

Le système PERSUADER de Sycara [28] et les travaux de Rosenschein [29], [30] sont les premiers travaux de l’intelligence artificielle distribuée sur la négociation entre agents égocentrés. Le système PERSUADER puise son modèle dans les négociations de conventions collectives. Les négociations impliquent donc trois agents (un syndicat, une compagnie et un médiateur) et s’inspirent des négociations entre êtres humains. On y modélise les multiples itérations pendant lesquelles les parties impliquées s’échangent offres et contre-offres, et l’utilité des agents est multidimensionnelle et privée. Les croyances des agents sont révisées de telle sorte qu’on peut atteindre une entente grâce à une argumentation persuasive. Rosenschein, quant à lui, base son travail sur la théorie des jeux. L’utilité est le seul paramètre considéré par les agents, et on suppose que les agents sont omniscients. Les valeurs de l’utilité des différentes alternatives sont représentées par une matrice des gains qui est commune aux parties impliquées dans la négociation. Chaque partie choisira donc l’alternative qui maximisera son utilité. Malgré l’élégance mathématique de la théorie des jeux, les négociations telles que modélisées par Rosenschein s’appliquent mal à des problèmes du monde réel où :

les négociations se déroulent dans une certaine incertitude;
les négociations impliquent des critères beaucoup plus complexes qu’une
utilité à une seule dimension;
les utilités des agents sont secrètes;
les agents ne sont pas omniscients dans la réalité.

Comme le commerce électronique devient de plus en plus une réalité, le besoin de techniques de négociations qui tiennent compte des complexités du monde réel grandit. On se doit donc de tenir compte des informations incomplètes, des problèmes de négociations multiples, des échéances pour les négociations et la possibilité de briser des contrats. On a donc ajouté la possibilité d’établir des contrats moins rigides au sein du protocole Contract Net, des pénalités étant attribuées lorsqu’un contrat n’est pas rempli complètement [31].
Coordination entre agents

De nombreux exemples de coordination existent dans la vie quotidienne : deux déménageurs déplaçant un meuble lourd, deux jongleurs échangeant des balles avec lesquelles ils jonglent, des personnes qui parlent à tour de rôle en se passant un micro, etc.

Malone [32] note que deux des composantes fondamentales de la coordination entre agents sont l’allocation de ressources rares et la communication de résultats intermédiaires. Dans ce contexte, les agents doivent être capables de communiquer entre eux de façon à pouvoir échanger les résultats intermédiaires.

Pour l’allocation des ressources partagées, les agents doivent être capables de faire des transferts de ressources. Ceci peut d’ailleurs imposer certains comportements à des agents particuliers. Malone conclut qu’il peut être utile de distinguer les liens de contrôle comme une catégorie spéciale de liens de communication par lesquels certains agents transmettent des instructions que d’autres vont être motivés à suivre.

En étudiant les communautés humaines, Mintzberg [33] a identifié trois processus fondamentaux de coordination : ajustement mutuel, supervision directe et coordination par standardisation.

L’ajustement mutuel est la forme de coordination la plus simple qui se produit quand deux ou plusieurs agents s’accordent pour partager des ressources en vue d’atteindre un but commun. Habituellement les agents doivent échanger de nombreuses informations et faire plusieurs ajustements à leurs propres comportements en tenant compte des comportements des autres agents. Dans cette forme de coordination aucun agent n’a un contrôle sur les autres agents et le processus de décision est conjoint. La coordination dans les groupes de pairs (“peer groups”) et dans les marchés (“market”) est habituellement une forme d’ajustement mutuel.

La supervision directe apparaît quand un ou plusieurs agents ont déjà établi une relation dans laquelle un des agents a un contrôle sur les autres. Cette relation est habituellement établie par ajustement mutuel comme par exemple dans le cas d’un employé ou d’un sous-contractant qui accepte de suivre les instructions du superviseur. Dans cette forme de coordination l’agent superviseur contrôle l’utilisation des ressources partagées (comme par exemple les ressources humaines, le temps de calcul ou l’argent) par les agents subordonnés. Il peut aussi imposer certains comportements.

Dans les cas de coordination par standardisation le superviseur coordonne les activités en établissant des procédures que doivent suivre les subordonnés dans des situations identifiées. On trouve par exemple de telles procédures dans les entreprises, mais aussi dans les systèmes informatiques.


Malone [32] suggère qu’en utilisant ces processus de coordination fondamentaux “à la Mintzberg”, il est possible de construire des systèmes de coordination sophistiqués dont les plus répandus sont les hiérarchies et les marchés basés respectivement sur les processus de supervision directe et d’ajustement mutuel. Le travail en petit groupe se prête bien à l’ajustement mutuel. Par contre, dès que la taille du groupe grandit et que le nombre de tâches augmente, le nombre de liens et la quantité d’informations échangées peuvent devenir rapidement un handicap sérieux. Un groupe important peut être partagé efficacement en sous groupes de manière à ce que la plupart des interactions s’effectuent dans les sous groupes et que les quelques interactions nécessaires entre les sous-groupes soient prises en charge par les superviseurs de ces sous-groupes. Les sous-groupes peuvent être coordonnés par contrôle hiérarchique ou par ajustement mutuel suivant les caractéristiques du domaine d’application et des tâches à accomplir. Les marchés sont aussi considérés comme une activité d’organisation de groupe basée sur l’ajustement mutuel dans laquelle chaque agent contrôle des ressources rares (par exemple la main d’oeuvre, les matières premières, les marchandises et l’argent). Les agents s’accordent pour partager leurs ressources respectives afin d’atteindre un but commun. Les ressources échangées ont un prix explicite ou implicite. Lorsqu’un contrat est conclu, il y a un accord pour que l’agent contracteur devienne le superviseur de l’agent contractant. De nombreuses organisations mettent en œuvre des processus de coordination mixtes basées sur l’ajustement mutuel, la supervision directe et la standardisation. Ces cadres organisationnels peuvent être des sources d’inspiration quand on doit établir une structure organisationnelle pour un SMA.

Bien entendu, la coordination est une question centrale pour les SMAs et la résolution de systèmes distribués. En effet, sans coordination un groupe d’agents peut dégénérer rapidement en une collection chaotique d’individus. On pourrait penser que la façon la plus simple de s’assurer un comportement cohérent du groupe d’agents serait de le faire par un agent centralisateur qui détiendrait des informations de haut niveau sur ces agents. Ainsi, l’agent centralisateur pourrait créer des plans d’action et assigner les tâches aux divers agents du groupe. Cette approche est pratiquement impossible à mettre en oeuvre dans des applications réalistes en raison de la difficulté de réaliser un tel agent centralisateur qui puisse tenir compte des buts, des connaissances et des activités de chaque agent : la charge en communication serait énorme, sans compter qu’on perdrait les avantages d’un SMA composé d’agents autonomes [34]. Le contrôle et les informations doivent alors être distribués parmi les agents.

À cette fin, Jennings [26] propose un modèle intéressant qui se base sur l’hypothèse de la centralité des engagements et des conventions. Les engagements sont vus comme des promesses en vue de réaliser certaines actions, alors que les conventions constituent le moyen de faire le suivi de ces engagements dans des circonstances changeantes. Grâce aux engagements des autres agents, un agent peut prédire les actions qu’il est susceptible d’effectuer et déterminer ainsi les interdépendances avec ses propres actions. Mais comme le monde extérieur et les croyances des agents évoluent constamment, un agent doit aussi posséder un moyen pour déterminer si les engagements existants sont encore valides. Les conventions offrent un tel mécanisme en définissant les conditions sous lesquelles les engagements doivent être réévalués et en spécifiant les actions à entreprendre dans de telles circonstances.

Du point de vue du concepteur d’un SMA diverses questions doivent être traitées comme notamment [02] : Avec quels agents un agent doit-il coordonner ses actions? Quand et où ces actions de coordination doivent-elles être accomplies? Comment détecter et traiter les interactions entre actions (conflits et renforcement) ? Détecter les relations existant entre des actions est une activité nécessaire lorsqu’on veut coordonner ces actions.

Von Martial [35] de son côté, a identifié deux grandes catégories de relations pouvant exister entre les actions accomplies simultanément par plusieurs agents : les relations négatives et les relations positives.
Les relations négatives (ou conflictuelles) sont celles qui gênent ou empêchent plusieurs actions de s’accomplir simultanément et sont dues en général à des incompatibilités de buts ou des conflits de ressources. Par exemple dans une vente aux enchères, agent X et agent Y veulent acquérir un même meuble M.
Les relations positives (ou synergiques) sont celles qui permettent aux actions de bénéficier les unes des autres. Ainsi, la réalisation d’une action a accomplie par l’agent Y réalise du même coup une action x = b que devait accomplir l’agent X ou favorise la réalisation d’une action c par l’agent Z. Par exemple X, Y et Z sont dans une pièce dont les fenêtres sont fermées et les stores baissés. X a chaud et Z aimerait avoir de la lumière. Y monte les stores et ouvre une fenêtre.

Négociation entre agents…
La négociation joue un rôle fondamental dans les activités de coopération en permettant aux personnes de résoudre des conflits qui pourraient mettre en péril des comportements coopératifs.

Durfee et ses collègues [36] définissent la négociation comme le processus d’améliorer les accords (en réduisant les inconsistances et l’incertitude) sur des points de vue communs ou des plans d’action grâce à l’échange structuré d’informations pertinentes.

En général les chercheurs en IA distribuée utilisent la négociation comme un mécanisme pour coordonner un groupe d’agents. Différentes approches ont été développées en s’appuyant sur la riche diversité des négociations humaines dans divers contextes :

Cas des agents coopératifs
Un des protocoles les plus étudiés pour la négociation s’appuie sur une métaphore organisationnelle [37]. Le protocole du réseau contractuel (“Contract-Net”) a été une des approches les plus utilisées pour les SMA [38].

Les agents coordonnent leurs activités grâce à l’établissement de contrats pour atteindre des buts spécifiques. Un agent, agissant comme un gestionnaire (“manager”) décompose son contrat (une tâche ou un problème) en sous-contrats qui pourront être traités par des agents contractants potentiels. Le gestionnaire annonce chaque sous-contrat sur un réseau d’agents. Les agents reçoivent et évaluent l’annonce. Les agents qui ont les ressources appropriées, l’expertise ou l’information requise envoient au gestionnaire des soumissions (“bids”) qui indiquent leurs capacités à réaliser la tâche annoncée. Le gestionnaire évalue les soumissions et accorde les tâches aux agents les mieux appropriés. Ces agents sont appelés des contractants (“contractors”). Enfin, gestionnaires et contractants échangent les informations nécessaires durant l’accomplissement des tâches.

Un autre important protocole de négociation a été proposé par Cammarata et ses collègues [39], [40] qui ont étudié les stratégies de coopération pour résoudre des conflits entre des plans d’un ensemble d’agents. Ces stratégies ont été appliquées au domaine du contrôle de trafic aérien avec le but de permettre à chaque agent (représentant un avion) de construire un plan de vol qui permettrait de garder une distance sécuritaire par rapport aux autres avions et de satisfaire des contraintes telles que “atteindre la destination désirée avec une consommation de carburant minimale”.

La stratégie choisie, appelée “centralisation de tâche” permettait aux agents impliqués dans une situation conflictuelle potentielle (des avions se rapprochant trop compte tenu de leurs caps respectifs) de choisir l’un d’eux pour résoudre le conflit. Cet agent agissait comme un planificateur centralisé et développait un plan multi-agents qui spécifiait les actions concurrentes de tous les avions impliqués. Les agents utilisaient la négociation pour déterminer qui était le plus apte à réaliser le plan. Cette aptitude était évaluée à partir de divers critères permettant d’identifier par exemple l’agent le mieux informé ou celui qui était le plus contraint.

Les protocoles de négociation précédents supposent que les agents sont coopératifs, et donc qu’ils poursuivent un but commun.

Cas des agents non coopératifs

Sycara [41] a étudié des situations dans lesquelles on ne peut pas supposer la coopération des agents. La résolution de conflits est mise en oeuvre soit par négociation, soit à l’aide d’un médiateur. Sycara a développé un système qui résout des conflits dans le domaine des relations de travail. Ce système comprenait trois agents : l’employeur, les employés et le médiateur. L’employeur et les employés avaient des buts conflictuels et le médiateur générait des propositions et contre-propositions pour essayer de rapprocher les deux parties adverses.

Müller de son côté [42], a indiqué que les recherches en négociation peuvent être divisées en trois catégories.
Les recherches sur les langages de négociation qui s’intéressent aux primitives de communication pour la négociation, à leur sémantique et à leur usage dans les protocoles.
Les recherches sur les décisions en négociation qui s’intéressent, autant à eux, aux algorithmes pour comparer les sujets de négociation, les fonctions d’utilité et la caractérisation des préférences des agents.
Les recherches sur le processus de négociation qui étudient des modèles généraux des comportements de négociation des agents.
Planification

Bond et Gasser [43] font remarquer que nous pouvons obtenir une plus grande coordination si on oriente les comportements des agents vers des buts communs en établissant explicitement une division du travail entre les agents. Des techniques comme la planification centralisée pour des groupes d’agents, la conciliation de plans, la planification distribuée, l’analyse organisationnelle, sont toutes des façons d’aider les agents à aligner leurs activités en assignant les tâches après avoir raisonné sur les conséquences de réaliser ces tâches dans des ordres particuliers. Dans une approche de planification multi-agents, un plan multi-agents est un plan qui est créé afin que plusieurs agents puissent l’exécuter. La création d’un tel plan peut être faite par un seul ou par plusieurs agents. En planification multi-agents centralisée un agent est responsable pour la création du plan qui spécifie les actions planifiées pour tous les agents concernés. C’est cette approche qui a été utilisée par Cammarata pour le problème de contrôle de trafic aérien.

Une autre façon d’implémenter la planification multi-agents centralisée a été proposée par Georgeff [44]. Dans cette approche, les plans des agents sont d’abord créés de façon individuelle; ensuite un agent centralisateur rassemble ces plans et les analyses pour identifier les conflits. L’agent centralisateur en question essaye de résoudre les conflits en modifiant les plans locaux des autres agents et en introduisant des commandes de communication afin que les agents se synchronisent de façon appropriée. Dans une approche de planification distribuée, les activités de planification sont réparties au sein d’un groupe d’agents. Cette approche est utilisée quand un seul agent ne peut pas avoir une vue globale des activités du groupe.

Von Martial [45] a distingué, quant à lui, deux classes de problèmes en planification distribuée : la planification dirigée par les tâches et la coordination de plans.

Dans les système s de planification dirigés par les tâches, il y a un but initial ou une tâche initiale qui est décomposée en sous-buts ou sous-tâches et qui est répartie entre plusieurs agents décomposition de problème “top-down”).

Par ailleurs, la coordination de plan s’attaque à des situations dans lesquelles il existe des plans d’agents (vision centrée sur les agents) et le problème consiste à réconcilier ces plans avant de les exécuter dans un environnement commun.

En général, la planification multi-agents nécessite une forme ou une autre de synchronisation de plans qui peut être réalisée à divers moments : pendant la décomposition de plan, pendant la construction de plan ou après celle-ci. Les plans des agents peuvent être en conflits en raison d’incompatibilités d’états des systèmes, de l’ordre des activités ou de l’usage des ressources. De tels conflits peuvent être résolus par un agent en particulier (coordonnateur ou médiateur) ou une solution peut être obtenue par négociation.

Par la suite, Von Martial [46] a proposé un modèle de coordination de plans qui s’appuie sur la résolution de conflits basée sur les divers types de relations (négatives et positives) pouvant exister entre ces plans d’une part, et sur un protocole de communication pour la synchronisation des plans d’autre part. Les relations entre plans entraînent une modification des plans des agents. Les relations négatives sont traitées pour résoudre les conflits et les relations positives sont utilisées pour tirer parti de plans convergents.

Conry et ses collègues [47], [48] ont développé un protocole de négociation appelé “multi-stage negotiation” pour résoudre de façon coopérative des conflits dans l’allocation de ressources. Le domaine d’application était celui de la surveillance et du contrôle dans un système de communication complexe. Le protocole débute par la génération d’un plan initial et consiste en plusieurs cycles permettant d’envoyer des requêtes pour des buts secondaires, l’analyse locale, la génération de plans alternatifs et l’envoi de réponses.

Durfee and Lesser [24] ont proposé une approche appelée “planification partielle globale” (PGP pour Partial Global Planning) dans laquelle les agents construisent des plans et partagent ces plans pour identifier des améliorations potentielles pour leur coordination. Au contraire de la planification multi-agents qui suppose qu’un plan est élaboré avant que les agents commencent à agir, la planification partielle globale permet aux agents d’alterner phases de planification et d’exécution : les agents commencent par planifier des interactions coordonnées au mieux de leurs connaissances et réagissent aux situations non prévues en modifiant leurs plans. Cette approche a été appliquée à une plate-forme de tests multi-agents appelée DVMT (“Distributed Vehicle Monitoring Testbed”) [25].

Dans ce contexte, Lesser [49] a utilisé le modèle FA/C “Functionally Accurate / Cooperative mode”) qu’il a en fait, développé pour répondre aux déficiences des modèles conventionnels qui supposent que les tâches sont décomposées de façon à ce que chaque agent ait suffisamment de données pour résoudre complètement et précisément les sous-problèmes qui lui sont assignés, et ce avec peu d’interaction avec les autres agents. Toutefois, dans de nombreuses applications (interprétation distribuée, planification distribuée et allocation de ressources, etc.) ce modèle de décomposition de tâches est inadéquat. Dans le modèle FA/C les agents n’ont pas besoin de disposer de toutes les informations localement pour résoudre leurs sous problèmes. Ils interagissent en échangeant des résultats partiels. Dans un SMA les agents doivent gérer des ressources distribuées qui peuvent être physiques (capacités de communication, matières premières, argent) ou informationnelles (telles que les informations au sujet de la décomposition du problème). Les agents doivent adapter leurs plans pour tenir compte de la disponibilité des ressources.

Bien entendu, la planification contribue à la coordination, dans la mesure où lorsque les agents adoptent un plan “ bien fait ”, ils agissent généralement de manière coordonnée.

Communication
La capacité de communiquer est une des caractéristiques essentielles des agents. Cette capacité est implémentée en donnant à ces agents la possibilité d’échanger des messages.

Cependant, pour qu’un échange de messages puisse se traduire en une véritable communication, un langage de communication doit être défini pour les agents (agent
communication language ou ACL). Pour cela, plusieurs conditions doivent être vérifiées.

En particulier, doivent être définis:

un vocabulaire commun permettant aux agents de faire référence de façon unifiée à un ensemble de concepts et d’actions compris de tous.
Un tel vocabulaire commun est généralement structuré, et s’appelle une ontologie (partagée); l’existence d’une ontologie partagée permet aux agents de pouvoir affecter un même sens aux unités élémentaires du langage de communication, les tokens (mots). D’une façon générale, les ontologies permettent de définir des domaines d’application en termes d’objets, d’attributs et de relations sous la forme de modèles conceptuels similaires à ceux utilisés dans le domaine des systèmes d’information.

Un mécanisme permettant de référencer de façon non ambiguë les objets de l’environnement (c’est une des raisons pour laquelle chaque agent doit être muni d’une identité propre): names mapping.

Une théorie permettant d’associer un sens aux messages échangés entre les agents: une telle théorie devra permettre d’associer des buts (objectifs) concrets aux actions exprimées dans les messages, ainsi que de déterminer l’impact de ces actions sur les états internes des agents (par exemple par des pré et post-conditions); le langage permettant de décrire les états internes des agents pour pouvoir exprimer le contenu des messages échangés est appelé langage de communication de contenu (content communication langage ou CCL)

Un langage permettant d’exprimer les messages échangés dans une forme structurée reconnue par l’ensemble des agents de l’environnement; un tel langage est appelé langage de communication entre agents (agent communication language ou ACL) ;

Un protocole permettant d’organiser les séquences de messages échangés en de véritables conversations structurées d’une façon similaire à ce que l’on peut observer chez les humains (théorie des actes de langage : requêtes, suggestions, promesses, menaces, ...)


On trouve en particulier des standards pour:

les langages de communication de contenu (KIF, FIPA-SL, FIPA-CCL, ...)

et pour les langage de communication entre agents (KQML, FIPA-ACL, ...).

Des efforts importants sont également mis en œuvre pour la création d’ontologies et de protocoles liées à des domaines spécifiques (tourismes, commerce électronique, ...).



Un travail de standardisation important est par exemple en cours dans le cadre de la FIPA (Foundation for Intelligent Physical Agents, voir  HYPERLINK "http://www.fipa.org" http://www.fipa.org). C’est notamment une des raisons pour lesquelles on a choisi la plateforme JADE puisqu’elle est compatible avec les spécifications de la FIPA

Exemple de type de messages (Communication Acts) définis dans FIPA-ACL: agree, cancel, confirm, disconfirm, failure, inform, not-understood, query-ref, refuse, request, subscribe, ...

Exemple de message au standard FIPA-ACL avec un contenu exprimé en FIPA-SL :
L’agent i confirme à l’agent j que la baleine est un mammifère :

(confirm
:sender (agent-identifier :name i)
:receiver (set (agent-identifier :name j))
:language FIPA-SL
:content (is mammal whale)
)

Autre exemple de message :

(request
:sender ( :name martinagent@liawww.epfl.ch:8080)
:receiver (:name movenpickhotel@tcp://movenpick.com:6600)
:ontology personaltravelassistant
:language FIPA-SL
:protocol fipa-request
:content
(action movenpickhotel@tcp://movenpick.com:6600
(book-hotel :arrival 25/11/2000 :departure 05/12/2000 ...
) )


Architecture de communication

Il existe 3 architectures de communications :

Réseau en anneaux dont le principal inconvénient est la lenteur des interactions : les messages échangés entre deux agents passent en pire cas par (n-1) agents.


Réseaux en étoile qui, bien que présentant l’avantage d’un accès rapide entre le superviseur et les autres agents, rend la gestion des interactions inter agents complexes par la nature bidirectionnelle des connexions.


Réseaux hybrides combinant un mixte entre un réseau en bus et un réseau en étoile.


Une communication (information, requête ou interrogation) est capable de modifier l’état interne de l’agent récepteur (remise en cause des plans, modification des croyances) d’où l’importance du contenu du message.

Il existe différents types de communication :
Communication sélective (qui est adressée à un nombre restreint d’agents selon un critère de sélection) ou diffusée,
Communication sollicitée (demandée par un autre agent) ou non,
Communication avec ou sans accusé de réception (attente par l’émetteur d’une confirmation de bonne réception),
Communication à transmission simple ou répétée (sur plusieurs envois).

Mode de communication

Les agents peuvent interagir soit en accomplissant des actions linguistiques (en communiquant entre eux), soit en accomplissant des actions non linguistiques qui modifient leur environnement. En communiquant, les agents peuvent échanger des informations et coordonner leurs activités. Dans les SMA, deux stratégies principales ont été utilisées pour supporter la communication entre agents: les agents peuvent échanger des messages directement ou ils peuvent accéder à une base de données partagées (appelée tableau noir ou “blackboard”) dans laquelle les informations sont postées.

Communication par envois de messages :
Dans ce cas, il existe une liaison directe des agents qui s’envoie directement et explicitement leurs messages aux destinataires. L’agent émetteur a donc connaissance du destinataire



Communication par partage d’information :
Dans ce cas, les agents communiquent via une structure de données partagée, où l’on trouve les connaissances relatives à la résolution (état courant du problème) qui évolue durant le processus d’exécution. (cf. les systèmes multi experts ou encore l’architecture de BB1).



Actes de langages

Quelque que soit leur mode de diffusion, les communications sont à la base des interactions et de l’organisation sociale d’un SMA. « Parler c’est agir » : lorsque l’on parle, on effectue des actes. Pour traduire cela à l’intérieur d’un message on utilise des verbes « performatifs » (promettre, ordonner, demander, etc.) où l’acte est effectué par l‘énoncé même, etc.

Il existe selon J.-L. Austin 3 types d’actes de langages existent :
Actes locutoires : activité mentale et physique de formulation et d’articulation de l’énoncé.
Actes illocutoires : actes effectués par l’interlocuteurs lors de la formulation de l’énoncé (ex. « il est 10h ? » faire comprendre une interrogation et non une affirmation)
Actes perlocutoires : conséquence indirecte des actes locutoires et illocutoires sur l’auditeur.

Les actes de langages permettent de bien illustrer la théorie des intentions (intention = un certain type d’action (actes illocutoires)). La communication sera donc reconnue à travers le type de l’action (interrogation, déclaration, requête, offre, etc.) ce qui implique une mise en correspondance entre les intentions et les modèles internes de l’émetteur et de récepteur de messages.

Cependant, insuffisance à modéliser la coordination et la négociation et donc la coopération entre les agents car la théorie des actes de langages ne permet pas de décrire les informations échangées, quand ont-elles été échangées, quel agent fait quoi, la décomposition et l’allocation des tâches, etc.

Conclusion
Les recherches dans le domaine des systèmes multi-agents poursuivent donc deux objectifs majeurs :
Le premier concerne l’analyse théorique et expérimentale des mécanismes qui ont lieu lorsque plusieurs entités autonomes interagissent,
Le seconde s’intéresse à la réalisation de programmes distribués capables d’accomplir des tâches complexes via la coopération et l’interaction.

Leur position est donc double :
d’un côté, elles se placent au sein des sciences cognitives, des sciences sociales et des sciences naturelles pour à la fois modéliser, expliquer et simuler des phénomènes naturels, et susciter des modèles d’auto-organisation,
de l’autre côté, elles se présentent comme une pratique, une technique qui vise la réalisation de systèmes informatiques complexes à partir des concepts d’agent, de communication, de coopération et de coordination d’actions.

En s’intéressant non plus a la notion d’agent en tant qu’individu isolé mais comme faisant partie d’un groupe, nous nous sommes ensuite intéressé au comportement global d'une société d'agents et aux théories sociales requises pour la résolution de problèmes dans un univers multi-agents : nous avons ainsi développé les problématiques liées à l’organisation sociale, à l’interaction, la coopération, la négociation, la coordination et encore la communication.

Nous avons ensuite dégagé les besoins nécessaires à une architecture de base pour la construction de système multi-agents au travers de l’étude des méthodologies et plate-formes existantes ; les concepteurs d’application de SMA ont besoin d’environnement de développement doté d’un langage de spécification, de protocoles de coopération et de communication ainsi que des moyens de mise en œuvre des différentes lois (organisations) sociales dans une société d’agents.

Il serait alors intéressant de voir comment concevoir les plates-formes technologiques et les méthodologies de développement pour les SMA.
METHODOLOGIES ET OUTILS DE DEVELOPPEMENT

Méthodologies

Avant de réaliser une implémentation particulière, et s’ils veulent pouvoir en tirer une leçon à portée plus générale, les informaticiens, quel que soit leur domaine de spécialité, doivent pouvoir disposer d’une méthodologie de conception. Le rôle principal de ces méthodologies est d'identifier des étapes permettant de passer du cahier des charges ou des spécifications d'un projet à son implémentation (i.e. le cycle de vie du projet). Elles fournissent les outils qui permettent de transformer une vision intuitive et subjective du système à construire (les besoins du maître d'œuvre, par exemple) en une définition formelle et objective (partageable et réutilisable) une fois qu'il a été implémenté, et offrent de ce fait une trace du processus à l’œuvre entre le brouillon originel et le code final. Cette trace est évidemment différente selon les méthodologies employées et leur degré de maturité, mais un certain consensus existe pour estimer qu’elle doit au moins fournir :

Un ensemble structuré de directives, qui incluent la définition des étapes mentionnées plus haut, des conseils de conception pour chacune des étapes, et des règles de transition entre ces étapes.

Une façon unifiée et standardisée de documenter le processus de conception. Elle est utilisée pour partager et transmettre l'expérience acquise durant ce processus, soit entre les concepteurs, soit à destination d'autres concepteurs (reprenant par exemple le projet plus tard).

L'utilisation d'une terminologie homogène, qui possède une signification à chaque étape et qui facilite les transitions entre étapes (souvent une terminologie graphique à base de diagrammes ou d'organigrammes).

L'utilisation d'abstractions conceptuelles opérationnelles, c'est-à-dire de structures suffisamment abstraites pour permettre un choix suffisant de techniques au moment de l'implémentation, mais assez concrètes pour éviter au concepteur d'utiliser des techniques dépassées ou non pertinentes.

Une histoire complète et incrémentale du projet, qui permette, à partir de n'importe quelle étape, de revenir aux étapes précédentes sans avoir à supprimer ce qui a été réalisé entre temps.


CASSIOPEE

CASSIOPEE permet une définition intentionnelle du système multi-agents depuis les comportements individuels jusqu’aux comportements collectifs, tout en autorisant l’usage de n’importe quelle technique d’implémentation, où les agents conçus selon un schéma particulier peuvent aussi bien manipuler explicitement les comportements qui leur ont été attribués lors de la conception que ne pas les « connaître » du tout (ceux-ci « émergeant » alors de leurs interactions).

Essentiellement, CASSIOPEE, est une façon d'aborder un type de résolution de problèmes où des comportements collectifs sont mis en œuvre par un ensemble d'agents. Elle n'est pas dédiée à une classe particulière d'applications et n’exige aucune architecture d'agents spécifique.

Néanmoins, il est supposé que, bien que les agents puissent avoir différents buts, l'intention du concepteur est de les faire fonctionner de façon coopérative. CASSIOPEE repose sur quelques concepts clés : ceux de rôle, d'agent, de dépendances et de groupes. Son idée principale est qu'un agent n'est rien d'autre qu'un ensemble de rôles, parmi lesquels nous distinguons trois niveaux :

1. Les rôles individuels, qui sont les comportements que les agents sont individuellement capables de mettre en œuvre, indépendamment de la façon dont ils le font.

2. Les rôles relationnels, c'est-à-dire comment ils choisissent d'interagir avec les autres (en activant/désactivant les rôles individuels), en se basant sur les dépendances mutuelles qu'entretiennent les différents rôles individuels.

3. Les rôles organisationnels, ou comment les agents peuvent gérer leurs interactions pour devenir ou rester organisés (en activant/désactivant leurs rôles relationnels).


CASSIOPEE invite à progresser depuis la définition de la tâche collective jusqu'à son implémentation en suivant cinq étapes, décrites sur la Figure 4 sous la forme de calques. L'ordre dans lequel ils sont parcourus n'est pas fixé, afin d’autoriser une approche ascendante, descendante ou mixte. Cependant, la façon usuelle de procéder consiste à définir, dans l'ordre :

1. Le calque des rôles individuels, qui contient la définition des rôles individuels requis, de façon à pouvoir établir des types d'agent.

2. Le calque des dépendances, qui contient la définition des dépendances existant entre ces rôles.

3. Le calque des rôles relationnels, qui contient la définition de la façon dont les agents gèrent ces dépendances, en jouant les rôles relationnels adéquats.

4. Le calque des groupes, qui contient la définition des groupes pouvant apparaître en cours de résolution.

5. Le calque des rôles organisationnels, qui décrit de la dynamique de ces groupes, c'est-à-dire les rôles organisationnels que les agents peuvent jouer pour les faire apparaître, évoluer ou disparaître.



CASSIOPEE a été utilisée essentiellement comme méthode d’analyse dans les différents travaux des membres de l’équipe MIRIAD et appliquée au domaine des robots-fooballers [50]


Approche AEIO

Cette approche [BER01] propose de distinguer ces deux étapes du génie logiciel et de les appeler analyse et conception orientée systèmes multi-agents.

Analyse orientée systèmes multi-agents.

L’approche va consister à décomposer le problème en une solution multi-agents. Cela veut dire identifier les quatre composantes fondamentales : Agents, Environnement, Interactions et Organisation (AEIO) pour la modélisation de SMA. Cette approche est connue sous le nom de VOYELLES [Demazeau95]. Ce travail d’analyse et de décomposition du problème peut être orienté suivant trois axes ; il est :
·ð ðorienté agent : quand le nombre, le rôle et les fonctionnalités de chaque agent sont parfaitement identifiables et que le type même des agents (cognitif, réactif, mixte) influence la résolution de problème,

·ð ðorienté environnement : quand il s agit de modéliser une représentation du monde où l environnement est primordial (exemple des robots, des couloirs aériens de navigation),

·ð ðorienté interaction-organisation : quand l accent doit être mis sur les mécanismes de coordination et de coopération entre agents pour la résolution de problèmes ou lorsque des groupes d’intérêts doivent se former et se défaire mais aussi et plus généralement lorsque les besoins en communication au sein du système sont importants.

Trois principes sont issus de l’approche AEIO.

Principe Déclaratif
SMA = Agents + Environnement + Interactions + Organisation

Cette relation exprime le fait qu’un Système Multi-Agents est toujours composé de plusieurs agents, d’un environnement, d’un ensemble d’interactions possibles et d’une structure organisationnelle.

Principe Fonctionnel
Fonction (SMA) = åð ðFonction(Agents) + Fonction Collective

Ce principe exprime le fait que la fonction globale d un système multi-agents est toujours supérieure à la simple addition des fonctionnalités individuelles de chaque agent. Cette fonction collective résulte du phénomène d’émergence engendré par les interactions des agents entre eux.

Principe Récursif
MAS = Agent | MAS

Le troisième principe stipule qu’un SMA peut être vu à un niveau supérieur d’abstraction comme un agent et en conséquence doit pouvoir être manipulé en tant que tel.

Conception orientée systèmes multi-agents.

Quelle que soit la démarche suivie au cours de la phase d’analyse, les quatre composantes A, E, I et O qui constituent les spécifications globales, doivent au cours de la phase de conception, être intégrées pour produire un SMA opérationnel. Ce sont en fait des modèles opérationnels que le concepteur aura choisis pour chaque composante qui seront intégrés.

Les modèles d’agent ou architectures d’agents vont de modèles simples comme les automates à états finis (agents réactifs) aux modèles les plus sophistiqués comme les systèmes à base de connaissances (agents cognitifs).

Les modèles d’environnement dépendent du domaine d’application, ils sont généralement spatialisés et dotés d’une métrique.

Les structures et langages d’interaction vont des modèles issus de la physique comme les modèles à base de forces, à des types d’interaction de haut niveau comme les actes de langage.

Les modèles d’organisations vont des modèles biologiques jusqu’aux modèles inspirés par les lois sociales.


Approche Agent-Groupe-Rôle

Cette approche [Gutknecht99] se base sur trois concepts : l’agent, le groupe et le rôle. L’agent est simplement décrit comme une entité autonome communicante qui joue des rôles au sein de différents groupes. Un groupe est un regroupement d’agents, un agent pouvant être membre d’un ou de plusieurs groupes, les groupes peuvent se recouper. Le rôle enfin, est une représentation abstraite d’une fonction, d’un service ou de l’identification d’un agent au sein d’un groupe particulier. Un même rôle peut être tenu par plusieurs agents comme il peut être le fait d’un seul.


Le processus méthodologique de construction d’une application se compose ici des phases d’analyse, de conception et de réalisation.

La phase d’analyse correspond à l’analyse fonctionnelle, l’analyse des dépendances, l’identification des communautés pour préparer la conception des groupes ainsi que le choix des mécanismes de coordination et d’interaction.

La phase de conception correspond à la construction du modèle organisationnel : il s’agit d’une représentation abstraite des structures de groupe, de rôles. Cette phase comprend également la définition des schémas d’interaction (protocoles, messages) et également à la définition des autres entités manipulées (actions, tâches, objectifs).

Le choix d’architectures d’agent en fonction des phases précédentes et du domaine applicatif, ainsi que les stratégies d’implémentation des protocoles d’interaction sont l’objet de la phase de réalisation. L’utilisation d’un modèle agent-groupe-rôle permet l’expression et l’analyse des systèmes multi-agents en utilisant avant tout des concepts organisationnels.

Et toutes les autres….
Par ailleurs, dans « A Multidimentional Framework for the Evaluation of Multiagent System Methodologies »[0], Arsène Sabas, Mourad Badri & Sylvain Delisle se sont intéressés plus spécifiquement à plusieurs méthodologies pour le développement de SMA :

GAIA [18];
Multiagent Systems Engineering (MaSE) [16]:
A Methodology and Modelling Technique for Systems of BDI Agents (MMTS) [6]:
An Agent-Oriented Methodology : High-Level andIntermediate Models (HLIM) [8];
The CoMoMAS Methodology and Environment for Multi-Agent System Development [12];
Multi-Agent Scenario-Based Method (MASB) [4];
Analysis and Design of Multiagent Systems Using MASCommonKADS[5];
Agent-Oriented Methodology for Enterprise Modelling(AOMEM) [9];
Agent Oriented Design of Soccer Robot Team (Cassiopeia)[3].

Pour la plupart, ces méthodologies restent incomplètes : elles sont l'une ou l'autre une extension des méthodologies orientées objet ou de l’ingénierie des connaissances. De plus, trop peu d'effort ont été fait pour une standardisation des méthodologies, plates-formes et environnements de SMA. Il semble dès lors évident que les aspects d’ingénierie logiciel pour le développement de SMA reste un domaine ouvert.

Conclusion

Il convient aussi de comprendre que disposer d’une méthodologie ne résout pas le problème essentiel de l’analyse, c’est-à-dire la manière de « trouver les agents » au moment de démarrer une activité de conception : il existe, bien entendu, des pistes, qui proviennent aussi bien de l'informatique (avec le développement des méthodes d'analyse et de conception orientées objets) que, pour le cas de la simulation, des modèles dont disposent les chercheurs du domaine considéré.

La plus grande source provient cependant encore de l’expérience accumulée lors de travaux expérimentaux, qui permettent de dégager des règles empiriques de conception. L'application de ces règles ne permet pas, à elle seule, d'obtenir l'émergence d'une fonctionnalité au sein d'une population et n'explique comment passer d'une dynamique locale à une dynamique collective. Elles sont à donc considérer comme des contraintes pesant sur les choix de conception et constituent donc, à ce titre, des conditions nécessaires plutôt que suffisantes :

la décomposition purement fonctionnelle, classique en informatique, et bien adaptée aux systèmes centralisés, n'est clairement pas le type d'analyse à adopter pour concevoir ce type de système : il convient d'abord de déterminer de quoi est composé un système (ou de quoi il peut être composé) avant d'envisager comment il va réaliser la tâche pour laquelle il a été conçu. [PAR 96 ; PAR 97a]

la redondance fonctionnelle entre individus n'est pas un handicap, mais une opportunité supplémentaire d'adaptabilité au niveau global : l'existence de redondances au niveau individuel permet à la collectivité de prendre des risques. Il faut néanmoins prévoir, et c'est ce qui existe dans les colonies d'insectes sociaux, de fournir aux agents des possibilités de se spécialiser dans une tâche particulière, afin de limiter les éventuels conflits qui pourraient nuire à la qualité de la résolution. C'est le jeu entre la redondance et la spécialisation individuelle qui détermine les qualités d'adaptation et de performance du système global.


il faut se forcer à adopter une vue minimaliste en termes de granularité des agents, à la fois dans l'espace et dans le temps :

Taille réduite : la taille (puissance de calcul ou mémoire par exemple) d'une fourmi est négligeable par rapport à celle de la colonie. Le résultat est que le comportement de l'ensemble, une fois stabilisé, n'est plus dépendant des éventuelles défaillances individuelles, et que la dynamique collective est prépondérante.

Mémoire courte : la mémoire individuelle (et collective) doit être bornée dans le temps. Par exemple, les phéromones déposées sur le sol par les fourmis pour former des pistes de fourragement ont naturellement tendance à s'évaporer

Perception et action locales : la perception (de l'environnement, des autres agents), ainsi que l'action (sur l'environnement, sur les autres agents, ce qui inclut également la communication) doivent être bornées dans l'espace. Ceci permet, d'une part, de limiter la complexité des comportements individuels, et, d'autre part, de rester cohérent avec les principes précédents : à quoi bon, en effet, prévoir des agents individuellement peu performants s'ils doivent influencer l'ensemble du système ?

la décentralisation est un des points clés qui résultent de l'ensemble des autres règles. Ni l'information ni la décision ne doivent être centralisées, c'est-à-dire confiées à un sous-ensemble de la collectivité. Elles doivent être le produit, respectivement, de l'ensemble des informations maintenues par tous les agents du système, et de l'ensemble des décisions qu'ils prennent sur la base de leur perception locale.

Ces quelques règles ne constituent en aucune manière une méthodologie permettant d’effectuer une analyse complète et objective d'un problème en termes d’agents aptes à le résoudre. Elles peuvent tout au plus, dans leur état actuel, servir de mémorandum au moment où doivent être faits des choix de conception et/ou d'implémentation.


Comme on peut le constater plusieurs méthodes d’analyse et de conception des SMA ont été proposées récemment. La plupart d’entre elles, s’appuient sur des techniques de modélisation empruntées à des méthodes connues en développement orienté objets ou en ingénierie des connaissances pour aider à la construction des modèles d’agents, de l’architecture du SMA, pour la spécification des modèles d’organisation, d’interaction, etc. Peut-on s’attendre à une normalisation des modèles comme ce fut le cas en orienté objets avec le langage UML? L’avenir nous le dira. Une telle standardisation apparaîtra certainement quand les technologies multi-agents seront adoptées effectivement par les entreprises.

Plates-formes SMA

De la même façon qu’il est nécessaire de disposer d’une méthodologie lorsqu’il s’agit de concevoir des applications complexes, il est nécessaire de disposer d’outils et de composants génériques permettant d’envisager la réutilisabilité et faciliter ainsi le développement des applications.

On rencontre donc aujourd’hui, sous l’appellation « plates-formes SMA », des environnements de développement de systèmes multi-agents. Certains sont très complets et génériques, ils supportent toutes les phases du cycle de développement, depuis l’analyse jusqu’à l’exécution en passant par la conception et l’implémentation. D’autres se contentent de fournir des outils qui vont servir aux concepteurs dans une phase bien précise du processus de réalisation de l’application.

En grande majorité, les plates-formes SMA sont issues de projets de recherche mais on trouve aussi des produits commerciaux. [AgentBuilder] présente une liste exhaustive des plates-formes aujourd’hui disponibles qu’il s’agisse de produits commerciaux ou académiques.
Nous nous intéresserons à comparer ses plateformes sous 3 points de vue différents :

L’analyse pour identifier les domaine d’application et les problèmes clés : la méthodologie d’analyse est-elle utile et bien documentée ? A quel domaines et problématiques cette méthode s’applique-t-elle ? Cette méthode d’analyse est-elle facile à appliquer ? Y a-t-il possibilité de réutiliser des analyses de problèmes précédemment rencontrés ?

La conception pour spécifier une solution principale au problème: la méthodologie de modélisation est-elle utile et bien documentée ? Existe-t-il des outils ? Quel type de SMA peuvent être modélisé ? Cette méthode de modélisation est-elle facile à appliquer ? Y a-t-il possibilité de réutiliser des modélisations de problèmes précédemment rencontrés ?


Le développement pour coder la solution avec un certain langage de programmation: Les outils disponibles sont-ils efficace ? Y a-t-il des fonctionnalités impossibles à implémenter ? Les outils et langages de développement sont-ils faciles à utiliser ? Y a-t-il possibilité de réutiliser du code ?


AGENTBUILDER

AgentBuilder est une suite d'outil intégrée pour la construction d’agents logiciels intelligents. Il est développé par Reticular Systems Inc. et est fondé sur les modèles Agent0 [2] [3] et Placa BDI [4]. Cet outil est remarquable par la haute qualité de son logiciel et par le très connu modèle académique qu’il utilise. La méthodologie générale est décrite dans le guide utilisateur d’AGENTBUILDER.


Analyse : cette phase consiste à la spécification des objets (en OMT) du domaine et des opérations qu’ils peuvent réaliser ainsi que la production d’une ontologie appropriée. Malgré le peu de conseils pour réaliser au mieux cette phase, AGENTBUILDER dispose d’outils graphique dont l’utilisation est très intuitive et propose également la réutilisation d’ontologie.

Conception : cette phase consiste en la décomposition du problème en fonctions que les agents pourront exécuter, suivi par l’identification des agents, de leurs rôles, leurs caractéristiques ainsi que des protocoles d’interaction. Là encore des outils efficaces sont disponibles (comme le Agency Manager et le Protocol Editor). La réutilisabilité de protocoles est également possible.

Développement : cette phase consiste à identifier les comportements des agents : règles comportementales, croyances initiales, engagements, intentions et capacités des agents. Cet outil se limite donc à la construction d’agent avec une architecture BDI. A l’aide d’une librairie (Project Accessory Class), les IHM des agents sont également définies. Les agents ainsi que leurs actions extérieures peuvent être réutilisées dans d’autres projets.

AGENTBUILDER est un outil commercialisé dont une version d’évaluation simplifiée est disponible sur leur site. La documentation fournie couvre assez bien les différentes phases de l’analyse au développement ; indiquant davantage le que faire plutôt que le comment faire, ce qui n’est pas pour déplaire au développeur. Seul reproche : les SMA construits à l’aide d’AGENTBUILDER sont constitué uniquement d’agents reposant sur le modèle de la plateforme et il est par ailleurs difficile d’intégrer des agents reposant sur un autre modèle. Pour finir, AGENTBUILDER propose un outil très complet au développement de SMA même si l’on peut prévoir que la maîtrise de cet outil complexe sera longue.


JACK

JACK est un environnement pour la construction, l’exécution et l’intégration de SMA commercial réalisé en JAVA utilisant une approche à base de composants. Développé par Agent Oriented Software Pty. Ltd. Une compagnie australienne, il est basé sur le modèle BDI dMARS développé au sein de l’AAII (Australian Artificial Intelligence Institute) [6].

Essentiellement axé sur la phase de développement, l’outil est composé d’un JDE (Java Development Environment), une outil graphique pour gérer le projet, un compilateur dédié à JAL (Jack Agent Langage) qui transforme du code JAL en code JAVA, et enfin le Jack Agent Kernel constitué d’un ensemble de libraire de classes.

Analyse : néant

Conception : Il est supposé que les agents reposent sur le modèle BDI. Aussi cette phase consiste-t-elle en l’indentification des perceptions, actions, structures de données spécifiques au domaine, états mentaux des agents (interactions, buts, croyances, plans). Aucune réutilisation possible.

Développement : Il s’agit du codage JAL des composants spécifiques à l’agent : ses comportements, plans, etc. Le compilateur convertit ensuite le code en pure JAVA. Un outil graphique facilite également la gestion de gros projets et la modularité de JACK lui permet d’offrir des possibilités de réutilisation du code.

Jack est fortement orienté programmation agent, ce qui lui confère une haute polyvalence. L'architecture de l'agent peut s'étendre du simple comportement réactif au plus complexe BDI, en employant l’architecture fournie ou non par JACK. On peut regretter malheureusement que la documentation soit trop technique et ne couvre pas tous les aspects comme l’analyse et la modélisation.

MADKIT

MADKIT est une plateforme multi-agents JAVA construite sur le modèle organisationnel Agent-Groupe-Rôle précédemment défini. Développé par O. Gutknacht et J. Ferber du LIRMM (Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier), C’est davantage un environnement d’exécution de SMA, utilisant un micro-noyau agent. Le modèle organisationnel sous-jacent est AALAADIN[8]. Une courte méthodologie est disponible.[9]




Analyse : Aucune méthode d’analyse particulière n’est présente dans MADKIT. Cette phase devrait néanmoins inclure une analyse fonctionnelle, de dépendance, de groupe et d’un choix de mécanismes de coordination.

Conception : MADKIT étant essentiellement orienté organisation, cette phase doit inclure la définition du modèle organisationnel (groupes, rôles), le modèle d’interaction (protocoles, messages) et autres entités spécifiques (tâches, butes, etc.). Le modèle Aalaadin sert de trame pour la modélisation mais aucun outil n’est fournit sur la plateforme. La réalisation de cette phase est facilitée par la formation intuitive de groupes et de rôles. De plus, les définitions de rôles et de groupes peuvent être réutilisés à travers des designs patterns par exemple.

Développement : cette phase inclut le choix du modèle agent, de son implémentation et de celle des stratégies de protocoles d’interaction. Aucun modèle d’agent n’est fourni (par conséquent n’importe lequel peut être utilisé même si on privilégiera les plus simples) mais il doit être implémenté en JAVA. Grâce à la possibilité de réutilisation offerte par MADKIT, la réalisation d’agent complexe peut être fait grâce aux modèles développés dans de précédents projets.

L’exécution d’agent MADKIT se fait dans la G-Box, une sorte de bac à agent, où les agents peuvent être créés, modifiés, détruits, et dont l’interface graphique est agréable. Plusieurs G-Box peuvent être connectées les unes aux autres afin d’être distribuées sur le réseau. La G-Box permet la configuration dynamique des propriétés éditables des agents, d'une façon semblable aux JavaBeans. Aucun profiling global n'est disponible. Les agents sont enregistrés dans des archives Jar et peuvent être mixé avec d'autres agents, permettant un haut niveau de la réutilisation d'agent.

On peut reprocher à MADKIT un manque de méthodologie ainsi que la construction d’agent complexe nécessite une grosse quantité de code à écrire puisqu’il n’existe pas de modèle pré-établi. Néanmoins, grâce à sa forte flexibilité et à la facilité avec laquelle n’importe quel programmeur peut développer ses propres agents, MADKIT offre un outil très intéressant dans un contexte éducatif. D’après le mail de J. Ferber que j’ai reçu, un nouvelle version devrait arriver mais sans reprendre la base des concepts.


ZEUS

Zeus est un environnement intégré pour la construction rapide d’applications d'agents collaboratifs. Il est développé par le Programme de Recherche d'Agent du British Telecom Intelligent System Research laboratory. La documentation Zeus est abondante et met l’accent sur l'importance de l'aspect méthodologique (‘The agentcreation methodology is vital to the use of the Zeus toolkit’ [10]). La méthodologie de ZEUS emploie une décomposition en quatre étapes pour le développement d'agent : analyse de domaine, conception, réalisation et appui pendant l'exécution.

Analyse : L'étape d'analyse, qui consiste au modelage de rôle, est décrite dans [11]. À Cette étape, on ne fournit aucun outil de logiciel. Comme les agents sont définis par leur rôle et par leur comportement, cette étape est spécifiquement applicable aux SMA rationnel orienté de rôle. Le modelage des rôles est fait à l’aide de diagrammes de classe UML et de patterns, évitant ainsi tous nouveaux formalismes et la rendant accessible à un large public. Sur l'aspect de réutilisation, un grand nombre de modèles de rôle sont fournit, couvrant la gestion de l'information, le trading et les processus commerciaux.

Conception : L'étape de conception qui consiste à trouver les solutions qui accomplissent les responsabilités du rôle est décomposée en trois études de cas [11] : FruitMarket (trading), PC Manufacture (supply chain) et Maze Navigator (Agent à base de règle). Il existe un outil pour cette étape. Le modèle agent sous-jacent limite la conception à des agents collaboratifs orientés par leurs tâches et leurs buts. Cette étape exige donc principalement des compétences de conception, mais n'est pas techniquement difficile. Les trois études de cas sont une base intéressante à la réutilisation.

Développement : L'étape de développement d'agent couverte par les trois études de cas fournies et le Guide de Réalisation D'application [11]. Les cinq activités impliquées pour le développement d'agents sont toutes réalisable à l’aide d’outils logiciels graphiques Ces cinq activités sont : Création d'ontologie, Création d'agent, Création d’agent utilitaire, Configuration de tâches agent et Implémentation d’agent. Toutes ces activités nécessitent une bonne connaissance des outils qui sont heureusement bien documentés. Cette phase n’est applicable qu’au modèle agent ZEUS. Les ontologies peuvent être facilement réutilisées. Il n’y a cependant par de réutilisation possible d’agent d’un projet à un autre. La modularité générale de l’outil de développement nécessite de retourner au code JAVA (par exemple pour l’ajout d’une nouvelle stratégie de coordination agent).

L’outil Visualiser permet de visualiser le SMA de différents point de vue : organisation et interaction dans la société, décomposition de tâche globale, statistiques et états internes des agents. Il est également possible de contrôle les états individuels des agents, et même de configurer les agents pendant l’exécution. Les modifications sur la composition ou la localisation d’une société agent nécessite la recompilation du code rendant ainsi impossible toute réutilisation.

L’intégralité de l’outil est disponible en téléchargement sur le site de ZEUS ; il s’agit d’un outil disponible en Open Source dès lors gratuit que son utilisation soit académique ou industrielle. Zeus intègre donc toutes les étapes de la conception à l’exécution. Il fournit des outils théoriques et pratiques, emploie des techniques d'ingénierie de logiciel telles que les design patterns, la modélisation UML et ses documents méthodologiques se concentrent sur le comment faire et pas seulement sur le que faire. Focalisé sur un seul modèle agent, ZEUS ne permet donc pas la réalisation de « toute la gamme » des SMA. Enfin, comme tout outil complexe, ZEUS est long et difficile à manipuler même si une grande productivité peut à terme être atteinte.



LA PLATEFORME JADE

JADE (Java Agent DEvelopment Framework) est un environnement de développement logiciel destiné à la création de systèmes et applications multi agents conformément aux spécification FIPA pour les agents « intelligents ». Elle est constituée de deux principaux organes : une plateforme agent compatible FIPA ainsi qu’une API de développement.

Nous présenterons dans un premier temps les spécifications imposées par les standards FIPA puis nous donnerons une description rapide de la plateforme (+ évaluation de la plateforme) et pour finir, nous présenterons le SMA de suivi du trafic aérien développé sur la plateforme JADE à l’aide d’agents réactifs.

Standards FIPA
 
Un agent est un acteur fondamental du domaine. Il combine une ou plusieurs capacités de service dans un modèle d'exécution unifié et intégré qui peut inclure l'accès au logiciel externe, des utilisateurs humains et des équipements de communication.  
Les agents résident sur une plate-forme d'agent (l'AP). Une plate-forme d'agent fournit une infrastructure dans laquelle les agents peuvent être déployés. Un agent doit être enregistré sur une plate-forme pour interagir avec d'autres agents, qu’ils soient situés sur cette même plate-forme ou sur une autre plateforme.
Les spécifications FIPA identifient 3 agents clés nécessaires à la gestion d’une plateforme agent :
Agent Management System (AMS - Système de Gestion d’Agent): L’AMS exerce un contrôle de surveillance sur l’accès et l’utilisation de la plateforme : il est responsable de l’authentification des agents et du contrôle des enregistrements des agents. Il gère en effet la création, la suppression, la suspension, la reprise, l'authentification et la migration d'agents sur la plate-forme d'agent et fournit un service de renseignement de type "pages blanches" pour tout agent résidant sur une plate-forme. Il stocke la « table d’identification» des agents qui fait correspondre au GUID des agents (Global Unique Identifier) leurs adresses locales de transport employées par la plate-forme.
Agent Communication Channel (ACC - Canal de Communication Agent) Router : L’ACC est un agent qui emploie l'information fournie par l’AMS pour acheminer des messages entre des agents situés sur une même plate-forme et ceux résidant sur d'autres plates-formes. Il fournit ainsi le chemin permettant un contact basique entre agents à l’intérieur et à l’extérieur d’une plateforme. C’est la méthode de communication par défaut qui offre un service de routage de message fiable, normé et précis. FIPA spécifie ainsi le protocole IIOP (Internet Inter-ORB Protocol) comme le protocole de transport de base pour la livraison de message entre plateformes.
Directory Facilitator (DF): Le DF est un agent qui fournit un service de renseignement de type "pages jaunes" pour les agents. Il stocke les descriptions des agents et les services qu'ils offrent.
Par ailleurs, la plateforme doit fournir :
Agent Platform Security Manager (APSM – Gestionnaire de Sécurité pour la Plateforme Agent): un APSM est responsable du maintient de la politique de sécurité de la plateforme. L'APSM est responsable de la sécurité au niveau de transport et de la création de fichiers de logs d’audit. L'APSM négocie les services de sécurité à l’intérieur et entre domaines d'autre APSM de concert avec les architectures distribuées mises en oeuvre, comme CORBA, COM, DCE. Pour l’agent du domaine le demandant
Agent Resource Broker (ARB – Courtier de ressource d’agents): un agent est nécessaire pour fournir les service d’un ARB. I doit y avoir au moins un tel agent pour chaque plateforme afin de permettre le partage de services non agent. 
Les agents doivent être enregistré auprès de la plateforme afin de pouvoir se localiser les uns les autres et de partager leurs services. Chaque agent doit donc s’enregistrer auprès de l’AMS et du DF de leur plateforme d’origine. L’enregistrement auprès de l’AMS assure aux agents d’avoir accès aux services de la plateforme. L’AMS fournit également une fonction d’authentification pour les agents qui y sont enregistrés. L’enregistrement auprès du DF L'enregistrement avec le DF permet à d'autres agents de localiser un agent à partir de critères de recherche comme les types des services qu'il offre.
Les messages sont échangés entre agents à l'aide d'un transport de message. Il y a deux types de transport de message : le transport de message, qui livre des messages dans une plate-forme d'agent et le transport de message, qui livre des messages entre des plates-formes d'agent. Le Transport de Message de Plate-forme Interne (IPMT) ne concerne pas l’interopérabilité de la plate-forme et n'est donc pas sujet à standardisation par la FIPA. A l’inverse, le transport utilisé pour livrer des messages entre des plates-formes est crucial à l’interopérabilité de la plateforme et est donc spécifié dans les spécifications de la FIPA97.

La communication agent dans FIPA97 est accomplie à l'aide de trois composants : la Langue de Communication Agent FIPA (FIPA ACL), la langue contenu FIPA (CL ou Content Language) et l'ontologie :
Une ontologie énumère les termes comprenant le domaine d'application, à ne pas confondre avec un dictionnaire de données comme dans un système d'information traditionnel.
Le CL est employé pour combiner des termes dans l'ontologie en des phrases (logique ou autre) qui sont significatives aux agents qui ont validé cette ontologie. Parfois l'ontologie et le CL sont si fermement intégrés qu'ils deviennent la même chose ; le CL est alors une liste de phrases, qui représente l’ontologie.
Finalement l'ACL agit comme un protocole, permettant le développement de dialogues entre des agents contenant des phrases du CL et la définition de quelques sémantiques pour le comportement d'agents participant dans de tels dialogues. Une composition de termes issus d'une ontologie contenue à l’intérieure d’une phrase de CL, elle-même contenue dans un acte communicatif aussi est définit (par la FIPA97) comme un message et les agents FIPA97 communiquent en échangeant de tels messages.
Quand les opérations de gestion d'agent sont effectuées sur le transport de plateforme s'enterrant (c'est-à-dire par l'ACC) ceux-ci doivent être portés comme ACL; quand ils sont portés sur l'IPMT ils peuvent être portés dans une façon de marque déposée.
Description

La plate-forme agent JADE est un environnement de développement de SMA compatible avec les spécifications FIPA2000 pour l’interopérabilité de SMA intelligents. JADE est un projet Open Source, et l’intégralité du système est disponible en téléchargement à partir de la Home Page de JADE.

La plateforme JADE peut-être décrite de 2 points de vue différents. D’un côté, JADE est un environnement d’exécution pour SMA compatible FIPA, et de l’autre côté, c’est une environnement de développement d’application agent compatible FIPA, mettant à la disposition du programmeur toutes les spécificités FIPA au travers d’abstractions orientés objet.

L’architecture de communication de Jade essaye d’offrir un routage de message flexible et efficace, en choisissant de manière totalement transparente le meilleur transport disponible et en exploitant les dernières technologies objets intégrées à le JRE. (Java Runtime Environment).

Apparaissant comme une seule entité de l’extérieur, une plateforme agent JADE est elle-même une système distribué, puisqu’elle peut être répartie sur plusieurs machines hôtes.


Figure  SEQ Figure \* ARABIC 1 : Jade, Plate-forme agent distribuée

Remarque : l’architecture interne d’un conteneur Jade est similaire au conteneur principal à la différence qu’il ne contient pas d’AMS, de DF ni de modules IIOP.

Chaque plate-forme JADE est composée par un ou plusieurs agent containers, chacun installé sur une JVM séparée. Néanmoins, chaque plate-forme ne peut contenir qu’un et seulement un conteneur principal (jade.wrapper.MainContainer) et n'importe quel nombre de conteneurs agent (jade.wrapper.AgentContainer). La seule différence notable, du point de vue du développeur, est que le conteneur principal initialise automatiquement les agents de plate-forme et ainsi, doit être référencé par d'autres conteneurs. Excepté cela, il n'a pas d'autre différence et il peut accueillir n’importe quel agent.


Figure  SEQ Figure \* ARABIC 2 : Architecture interne du conteneur principal

JADE fait la distinction entre les échanges de messages inter plate-forme (l’expéditeur et le destinataire appartiennent à deux plate-formes différentes) et les échanges intra plate-forme (les deux agents interagissant sa situant alors sur la même plate-forme). Alors que les échanges de messages inter plate-forme sont soumis aux spécifications FIPA, les échanges de messages intra plate-forme est strictement sensible à JADE et par conséquent un transport de message propriétaire plus adapté peut-être utilisé. JADE utilise alors Java RMI pour les communications intra plate-forme, mais un nouveau noyau est en train d’être développé dans le cadre du projet LEAP, qui supportera différents protocoles de transferts pour les communications intra plate-forme.

Tous les agents de JADE héritent de la classe jade.core.Agent, qui fournit des implémentations pour tout le noyau de l’agent. Lors de sa création, chaque agent obtient GUID unique, qui lui assure unicité et identification. En plus des services de communication qu’elle offre, JADE fournit également le support nécessaire à la gestion du cycle de vie de l’agent. Chaque agent a un jeu d'états (attente, activé, …), avec des transitions bien définies d'un état à un autre comme le montre le graphique ci-dessous :

Figure  SEQ Figure \* ARABIC 3 : Cycle de vie de l'agent comme défini par la FIPA

Ainsi, un agent de JADE peut être considéré comme un automate à nombre fini d'états et peut être facilement contrôlé d'un point de vue abstrait, à partir d'une application extérieure.

Compatible avec le modèle Swing, la classe agent jade.gui.GUIAgent propose une trame agent dotée d’un interface graphique personnalisable.

La logique de l'agent est mise en oeuvre à l'aide des behaviours (comportements). Les behaviours peuvent être considérés comme des threads d'exécution logiques qui peuvent être suspendus et engendrés à volonté. Ces Behaviours permettent de modéliser les tâches de l’agent : un ensemble de behaviours est planifié et exécuté pour que l’agent réalise ses tâches. Les behaviours représente les threads de l’agent. Selon le pattern design Active Object, chaque agent JADE exécute son propre thread Java , garantissant ainsi une certaine autonomie ; au lieu de cela, afin de limiter le nombre de thread d’une plate-forme agent, tous les behaviours de l’agent sont exécutés de façon coopérative avec un seul thread Java. Ainsi, JADE utilise un modèle de un-thread-par-agent avec une planification intra agent coopérative.

La figure ci-dessous propose le modèle UML présentant la hiérarchie de la classe Behaviour


Figure  SEQ Figure \* ARABIC 4 : Modèle UML de la hiérarchie de la classe Behaviour

En plus d’une librairie d’exécution et d’une librairie de programmation agent, JADE fournit quelques outils pour gérer l’exécution de la plate-forme agent et surveiller et débuger les sociétés d’agent. Tous ces outils sont eux-mêmes des agents FIPA et ne nécessite pas de support particulier pour réaliser leur tâche, ils reposent simplement sur l’AMS de JADE.

La console de gestion générale pour une plate-forme d'agent de JADE est appelée RMA (Remote Management Agent). Le RMA récupère l’information de la plateforme et exécutes les commande de l’IHM pour modifier l’état de la plateforme (création d’un nouvel agent, fermeture d’un container périphérique, etc.) via l’AMS. La figure ci –dessous montre l’IHM de la plate-forme JADE.



Figure  SEQ Figure \* ARABIC 5 : Agent RMA de la plate-forme JADE
Parmi les nombreux outils disponibles, le Dummy Agent est un outil simple, et très souvent utile, pour inspecter les échanges de messages entre agents. Le Dummy Agent facilite la validation d'un modèle d'échange de message entre agent avant son intégration dans un SMA et facilite les tests interactifs d'un agent.

Il existe également le Sniffer Agent. Comme le nom l’indique, le Sniffer Agent est un Agent compatible FIPA dotés de fonctionnalités « espionnes ». Quand l'utilisateur décide de renifler un agent ou un groupe d'agents, chaque message adressé à cet agent / groupe d’agent est suivi à la trace et montré dans l’IHM du Sniffer Agent.


Figure  SEQ Figure \* ARABIC 6 : IHM du Sniffer Agent
Evaluation

Avant d’entamer tout développement, le choix de la plate-forme s’est justifié par ses nombreux avantages :

Disponible en open source, elle permet d’être entièrement « disséquée » afin de bien comprendre son fonctionnement interne. Par ailleurs, elle dispose d’une bonne documentation : guide administrateur, guide du développeur, tutorial sur les ontologies, etc.

Très populaire auprès des grands acteurs du domaine, elle m’a été vivement recommandée par J. Ferber. Elle dispose par ailleurs d’un collectif de « JADErs » très actifs (par le biais notamment de la mailing liste) et ainsi en perpétuel évolution (correction des bugs et ajout de nouvelles fonctionnalités)

Elle couvre de nombreux aspects des systèmes multi-agents incluant les modèles d’agents, interaction (possibilité de création de protocoles d’interaction ou encore utilisation de protocoles existant comme le FIPA-Contract-Net), coordination, etc.

Compatible avec les standards FIPA, elle lui acquière des capacités accrues d’interopérabilité avec les autres plateformes partageant ce standard comme :
Agent Development Kit,
April Agent Platform,
Comtec Agent Platform,
FIPA-OS,
Grasshopper,
JACK Intelligent Agents,
JAS (Java Agent Services API),
LEAP,
ZEUS
(cf.  HYPERLINK "http://www.fipa.org/resources/livesystems.html" http://www.fipa.org/resources/livesystems.html)
Malgré la relative jeunesse de ce projet, JADE a déjà été utilisé dans de nombreux projets internationaux : En particulier, elle a été utilisée dans deux projets sponsorisés par la Commission Européenne : LEAP et CoMMA
LEAP développera une plate-forme d'agent qui est :
légère, exécutable sur petits dispositifs comme des PDAs et des téléphones mobiles;
extensible, dans la taille et les fonctionnalités;
agnostique de système d'exploitation;
permettant de réaliser des applications de gestion d'équipes mobiles, supportant les communications sans fil et TCP/IP;
compatible FIPA.
CoMMA mettra en oeuvre une structure de gestion de mémoire d'entreprise basée sur la technologie agent et s’intéressera en particulier aux questions suivantes :
Amélioration de l'insertion de nouveaux employés dans la société,
Réalisation de processus qui détectent, identifient et interprètent les évolutions technologiques afin de diffuser parmi les employés des idées innovantes liées aux activités de veille technologiques

Pendant la phase de développement, il est apparut évident qu’un grand effort a été pour alléger le processus de développement d’un agent. Ceci se vérifie notamment par la présence de la classe jade.lang.acl.ACLMessage (qui représente un message agent à agent) qui fournit des méthodes utilitaires pour la création automatique de réponse à un message.

Il est facile d'invoquer une plate-forme complète (un conteneur principal) ou n'importe quel nombre de conteneurs de l'intérieur d’une autre demande application. La construction de conteneurs est un processus direct réalisé grâce à la création de profils d'initialisation et à leur passage en paramètres

De la même façon, le processus d’initialisation d’un agent est très simple : la création de l’agent ainsi que le lancement de son exécution ne prennent que deux lignes de code. . Le processus de création de nouveaux conteneurs, compte tenu du principal est aussi simple : il suffit de passer le nom de la machine hôte du conteneur principal comme paramètre au profil.

La seule partie "traitre" dans le processus de développement d’un agent concerne le modèle d'exécution de JADE. Les créateurs de JADE ont assigné un thread d’exécution Java par agent. Le scheduler (ou planificateur) incorporé est par défaut non- préemptif c’est-à-dire qu’il fonctionne en mode multitâche coopératif. Ainsi il est très facile de créer des behaviours qui "suspendront" l'exécution de l’agent, soit en étant exécuté pendant une très longue période de temps soit en engageant le scheduler dans une boucle intensément longue. Ainsi, faut-il éviter, dans le cadre d’une programmation à l’aide de la plate-forme JADE, de créer des behaviours qui doivent être exécutés dans des intervalles très courts ou consulter la boîte d'arrivée des messages de l’agent fréquemment. Il est alors conseillé d’utiliser le mécanisme de propagation d’évènement qui réveille les behaviours bloqués à l’arrivée de certains évènements.

Il vaut la peine de noter cependant que, à condition que le raisonnement de l’agent suive les règles mentionnées précédemment, le programme résultant est tout à fait efficace en termes de consommation de mémoire et d'activité de garbage collector.


Application au suivi du trafic aérien

Problématique

En Europe, le trafic aérien double tous les dix ans. Un phénomène pour le moins préoccupant, les infrastructures du contrôle n’ayant pas réellement évoluées depuis les années 1960-1970… En effet, l’espace aérien européen est en permanence à la limite de la saturation aux heures de pointe. Saturation au voisinage des aéroports mais, particularité européenne, saturation aussi et surtout sur les routes aériennes entre aéroports. Principale manifestation de ce phénomène, le nombre croisant des retards ne cesse de croître et coûte extrêmement cher aux compagnies aériennes (jusqu’à 2,5 milliards de francs en 1996).

La congestion du ciel est en passe de devenir le facteur limitant de la croissance exponentielle du trafic aérien. Pourtant, la densité volumique d’avions reste faible en dehors des zones aéroportuaires. Comment expliquer ce paradoxe ? Vient-il – comme le pensent aujourd’hui bon nombre d’experts – des faiblesses du contrôle aérien ? Ainsi, Philippe Jaquard, ancien directeur de la navigation aérienne écrivait en 1998 : «  La véritable saturation observée n’est pas celle du ciel, c’est celle du système de contrôle ». Alors que l’automatisation à bord des avions a progressé à grands pas, force est de constater que les méthodes de travail dans le petit monde de l’ATC (Air Traffic Control) n’ont guère évolué au cours des dernières années et ce quelque soit le pays.

Pour résoudre ce problème, nous allons tenter à l’aide d’un SMA d’assurer le contrôle de la navigation aérienne en coordonner les actions des avions afin qu’ils puissent évoluer selon les spécifications de leur plan de vol sans risque de collision. Mais commençons tout d’abord par rappeler quelques notions élémentaires.
La circulation aérienne
Le transport aérien s’est développé au rythme des progrès technologiques, de la volonté d’échanges, de la communication et de l’accroissement des relations commerciales. L’aviation est passée au cours des cinquante dernières années, d’une époque de pionniers à une ère de consommation de masse. Aujourd’hui, tous les grands aéroports mondiaux sont reliés quotidiennement et un grand nombre d’avions sillonnent l’espace aérien mondial. Ils constituent un gigantesque et complexe ballet planétaire géré par les contrôleurs aériens.

Les avions évoluent d’abord dans la zone d’aérodrome, sous le contrôle de la vigie (Tour de Contrôle). Ils sont ensuite pris en compte par les contrôleurs chargés des départs, puis transférés au contrôle « En route » pour la croisière. A l’arrivée, ils sont pris en compte par le radar d’approche jusqu’à l’atterrissage et transférés ensuite à la vigie de la Tour, pour assurer l’arrivée au parking.
La programmation des vols
Les vols sont planifiés deux fois par an par les compagnies aériennes et les aéroports sous l’égide de l’Association Internationale des Transports Aériens (IATA). Les contraintes de capacité de chaque Etat définissent une planification du trafic à prendre en compte.
Elle est enregistrée par le système de prévisions, qui est communiqué aux instances de contrôle, qui connaissent à l’avance la nature et le volume du trafic qu’ils auront à traiter.
Comme il n’y a pas de feux rouges en l’air, la fluidité des vols est assurée par le contrôle aérien, qui établit chaque jour un plan d’encombrement des routes aériennes et donne une heure de décollage précise à chaque avion, appelée « Créneau de décollage », pour que les séparations en altitude soient assurées sur les routes aériennes. En Europe, ce dispositif est géré par le centre d’Eurocontrol de Maastricht.
Cette planification se double d’un contrôle en temps réel, les contrôleurs visualisent sur l’écran radar la position de l’ensemble des avions dont ils ont la charge et qui constitue un flux continu et irrégulier dans un espace à trois dimensions.
En effet, les caractéristiques de vol de chaque avion impliquent des variables, fonction du type d’appareil, de son poids, de sa motorisation. Chaque avion est identifié et traité comme un vol particulier à l’intérieur de la séquence de trafic.
Le Radar
Le radar est avec la radio l’outil par excellence du contrôle aérien. Deux types de radar permettent de situer l’avion dans l’espace :
 – Le radar primaire envoie une onde électromagnétique qui se reflète sur la carlingue des avions. En fonction du temps de retour des ondes au radar, le système permet de déterminer l’azimut et la distance à laquelle se trouve l’avion, du radar.
– Le radar secondaire interroge l’avion sur un code qui lui est affecté. L’avion répond sur une autre fréquence et communique son altitude au système de contrôle. Ce système de transmission est appelé Transpondeur.
L’ensemble de ces informations est traduit sous forme graphique sur les écrans radar. Elles permettent une connaissance parfaite en temps des positions respectives de chacun des avions.
L’écran radar présente l’image de l’espace aérien dans un espace d’environ 100 Km autour  des pistes de l’aéroport, et de 300km environ pour le contrôle des routes aériennes. Dans les espaces non couverts par le radar, désertiques ou maritimes, l’espacement entre les avions est augmenté à 10 minutes de vol et le suivi par le contrôleur est assuré par des messages des pilotes donnant leur position à intervalles réguliers (30 minutes environ)
L’écran radar permet de visualiser la position des avions dans l’espace grâce aux cercles concentriques espacés de 5 Nm, (soit ~9km.)
Le contrôleur peut, grâce à des zooms successifs, focaliser sur une partie de l’espace aérien dans laquelle circulent plusieurs avions.
Le contrôleur identifie chaque avion grâce à une étiquette qui est associée sur le scope à la trace de son écho radar. Cette étiquette permet de lire le code transpondeur (ex : 4426), le numéro de ligne de l’avion (ex : AF 031), son altitude et sa vitesse.
Les étiquettes sont générées par les informations recueillies par les radars et les données du plan de vol (imprimé où figure le type de l’avion, son immatriculation, la trajectoire de destination, l’altitude, la vitesse, les aéroports de dégagement, ainsi que les heures de départ et d’arrivée prévues) qui ont été transmises par l’équipage avant le départ de l’avion.
Toutes ces informations permettent au contrôleur d’effectuer la régulation de l'ensemble des trafics aériens.
Les espacements des avions en vol

Dans toutes les phases de vol, les avions circulent en fonction de normes minimales d’espacement destinées à rendre impossible tous risques de collision en vol.
Dans les zones terminales d’approche ou de montée, deux trajectoires doivent être séparées latéralement de 5Nm = 9km, longitudinalement de 3Nm = 5,5Km. (Nautical Milles = Nm = 1,852km.
A l’atterrissage, le minimum d’espacement longitudinal entre deux avions en approche est de 2,5Nm.
La cadence de décollage et d’atterrissage est passée en 20 ans de 20 à 40 avions/heure.
En croisière, au-dessus de 6000m, les avions circulent alors dans de larges couloirs aériens, dont les traînées blanches d’altitude émaillent le ciel de la planète. La largeur de ces couloirs aériens de croisière est de 8 soit 15km
Ce sont alors des espaces de circulation à l’intérieur desquels les avions circulent à des altitudes allant jusqu’à 12000 mètres et à des vitesses sol de 800 à 1200 Km/h, en fonction des vents souvent très forts en haute altitude.
Verticalement, le minimum d’espacement de deux avions est de 1000 pieds, soit 300m, dans les zones terminales. En haute altitude, les espacements sont portés à 2000 pieds, soit 600m, du fait de l’imprécision des altimètres. Mais devant les récents progrès techniques des mesures d’altitude, il est en étude de ramener cette séparation à 300m pour tout l’espace aérien.
La tour de contrôle
La tour de contrôle est le repère de l'aéroport. Elle le domine, elle en est le symbole, celui du rôle des contrôleurs aériens. Les contrôleurs aériens font un travail invisible mais essentiel. Ils ont pour mission le guidage des avions. La tour de contrôle est donc au cœur d'un système complexe, d'une chaîne ininterrompue de position de contrôle des avions qui couvre la planète.
La tour renferme deux salles de contrôle.
·     La vigie dans laquelle les contrôleurs gèrent l'alternance des atterrissages et des décollages.
·     La salle IFR (Instrument Flying Rules) au cœur de la tour où les contrôleurs travaillent exclusivement au radar et contrôlent les arrivées et les départs dans un rayon de 100 km.

Elle abrite également :
·     Les réseaux de communication.
·     Les systèmes de prévisions du trafic.
·     Les calculateurs qui permettent la lecture des écrans radar, qui donnent une image exacte des mouvements en vol comme au sol, des avions.
Vol « en route »
Après le décollage, le contrôleur départ communique au pilote
un cap
un niveau de vol et le transfert vers le centre de contrôle en route.
la vitesse à respecter est de 250 nœuds jusqu’à 3000m sur tous les aéroports mondiaux (460 Km/h).
L'avion va monter par paliers successifs pour atteindre une altitude voisine de 10.000 mètres. Il circule alors sous la responsabilité des centres de contrôle en route qui gèrent l'ensemble des appareils pendant leur phase de vol de croisière.
Ne nous intéressant qu’au suivi du trafic aérien (vol de croisière), nous ne présenterons pas les autres phases de vol que sont le décollage, l’approche et l’atterrissage.

Les agents, c’est-à-dire les avions, se déplacent sur un espace représenté sous la forme d’une grille. Le but de l’application est de parvenir à ce qu’aucun de ces agents ne rentrent en collision, comme le montre la figure suivante.



Sur la figure, on distingue 5 couloirs aériens (2 horizontaux, 1 vertical et 2 obliques) sur lesquels se déplacent 5 avions à 4 altitudes différentes (4 nuances de bleu). On remarque qu’il y a risque de collision entre les avions 3 et 4 (altitude et couloir identiques) contrairement avec l’avion 5 qui se trouve à deux altitudes différentes respectant le périmètre de sécurité (cf. remarque2).

On pose les hypothèses suivantes :

L’environnement est discontinu (grille dont les cases font 10km*10km) et fini : on se restreint à la gestion d’un secteur de l’espace aérien. L’altitude des avions est également discontinue : l’espace est décomposé en tranches de 1km de hauteur (altitude max = 10km).


les avions se déplacent à une vitesse constante qui est fonction des caractéristiques de l’avion (type, poids et motorisation) le long de couloirs aériens d’une largeur de 8Nm soit 15km. Contraint d’évoluer à l’intérieur de ces couloirs, ils se déplaceront selon leur plan de vol.

Un plan de vol est caractérisé par une succession balises à la verticale desquelles l’avion doit passer. On appelle couloir aérien, le tronçon de l’espace aérien situé entre deux balises successives. Pour simplifier le problème, on ne considèrera que des couloirs aériens orientés horizontalement ou verticalement.

Les avions se déplacent donc selon un cap (horizontal ou vertical) et une altitude que l’on supposera fixe tout au long de leur parcours. En effet, d’après un dossier consacré au trafic aérien issu du magazine La Recherche n°319 d’avril 1999, plus de 98% des conflits en vol sont résolus en n’utilisant que des manœuvres horizontales.

Lors de leur déplacement les avions doivent nécessairement respecter une certaine distance de sécurité dont les caractéristiques sont illustrées par la figure suivante :


Modélisation du problème

La décomposition d’un problème en termes multi-agents aborde la difficile mais essentielle question de savoir ce que représente véritablement un agent en relation avec le problème à résoudre. Que doit-on considérer comme un agent ? Les individus ? Les groupes d’individus ? Les espaces ? Etc. Doit-on avoir des représentations multiples ?

Dans l’exemple du contrôle aérien, quels doivent être les agents responsables de l’évitement et du contrôle des différentes opérations ? Les avions, les secteurs d’espaces ou la phase de vol de croisière à laquelle on se restreint ici ?

Dans le premier cas, l’approche est centrée sur l’objet : l’avion, « agentifié », est responsable de ses propres mouvements et décide des actions qu’il doit entreprendre à partir d’une interaction avec les autres appareils. Chaque avion dispose alors de toutes les fonctionnalités nécessaires à son activité et, en particulier, des compétences pour gérer la phase de vol « en route ».

Nous choisirons ce modèle, apparaissant comme étant le plus intuitif, pour la réalisation du sma réactif à la différence que les agent communiqueront par modification de l’environnement uniquement : chacune des balises (appartenant à son plan de vol) guidera l’avion dan son déplacement en émettant un signal attracteur pour les avions et les avions se repousseront les uns avec les autres en émettant un signal répulsif.

Dans le second cas, l’approche est centrée sur l’espace : chaque partie de l’espace est une portion d’environnement qui contrôle les mouvements de tous les objets qui se trouvent dans son secteur, les avions n’étant alors que des objets passifs qui ne font qu’obéir aux ordres de la tour de contrôle. Les opérations de gestion de la phase de vol « en route » ne sont plus associées aux avions (notion d’agent esclave), mais aux agents représentant les différentes portions de l’espace. Nous choisirons ce model, le moins utilisé semble-t-il, pour la réalisation du sma cognitif. Cela nous permettra par exemple de modifier les composantes de l’environnement en créant par exemple des zones de turbulences par endroit par simple ajout d’un comportement aux cellules de l’environnement concernées.

Dans le troisième cas, l’approche est fonctionnelle : la phase de pilotage représente un (ou plusieurs) expert(s) qui gère de manière centralisée les mouvements de tous les avions. Dès qu’un avion se trouve dans la phase de vol « en route », il est pris en charge par l’agent spécialiste de la question. Nous laisserons celui là de côté qui nous semble moins intéressant.

Approche cognitive et réactive

Dans l’approche cognitive, on identifie tout d’abord les différentes fonctions que doit remplir le système (détection de l’environnement, allocation de rôle : changement d’altitude, changement de cap,…) et que l’on implémentera dans les agents sous forme de comportements adaptés. Ceci nécessitera alors un système de communication permettant le dialogue et la prise de décision distribuée. On supposera alors que les agents ont des buts (suivre leur route sans interférer avec d’autres agents) et qu’il agissent rationnellement par rapport à ces buts en désignant si nécessaire un agent « leader » pour organiser la répartition / coordination des actions dans les situations de conflits. Ce rôle correspond à celui jouer par la tour de contrôle où les aiguilleurs du ciel « orchestre » les plans de vol de chacun des avions. Le but de cette modélisation révèlera alors une coopération induite intentionnelle dans la gestion de situation de conflits.

Dans l’approche réactive, on supposera que les balises des couloirs aériens émettent un signal dont l’intensité décroît proportionnellement à la distance et qui jouent le rôle d’attracteurs pour les avions (l’avion aura tendance à aller vers ce point). A l’inverse, les avions émettent un signal servant de répulsif pour les autres avions. Ainsi les avions seront à la fois attirés par leur « route » et repoussés par les autres avions. La réussite du contrôle du trafic aérien émerge ainsi de la combinaison de ces différentes réactions aux stimuli de l’environnement envoyés par les avions et les balises. On s’attend alors à une coopération réactive entre les avions qui n’apparaîtra que par simple effet de bord du comportement individualiste de chaque agent.





Développement du SMA réactif

Les approches plus actuelles (Zeghal et al. 1993), dixit Ferber en 1995, utilisent des agents réactifs et des mécanismes de champs de force. C’est pourquoi nous avons développé une première application de suivi du trafic aérien à l’aide d’agents réactifs.

La démarche de développement est inspirée de la méthode XP [Annexe VI : Méthode XP] c’est pourquoi le développement de l’application a-t-il constitué en plusieurs itérations appuyées sur les user stories suivantes, mes deux responsables de stage ayant joué le rôle de client et décomposé la phase de développement du projet en différentes itérations.

User story 1
Un avion se déplace dans un environnement à une seule dimension. Il parcourt une succession de cellule, d’une cellule de départ à une cellule d’arrivée initialement fixées par le développeur. Quand l’utilisateur lance l’application, la succession des cellules par lesquelles l’avion passe doit s’afficher sur l’écran au fur et à mesure des déplacements de l’avion.
Exemple :
L’environnement est constitué de 10 cellules appelées Cx, x ( [0 ; 9]
L’avion se déplace de cellule en cellule (Départ en C0, Arrivée en C9)
( L’écran doit afficher progressivement : C0 C1 C2 C3 C4 C5 C6 C7 C8 C9


User story 2
Idem à la user story 1, excepté la présence d’une IHM une grille 1D permettant de visualiser le déplacement de l’avion. La présence de l’avion dans une case se matérialise par la colorisation d’une case en bleu. Quand l’utilisateur démarre l’application, l’avion se trouve dans la première case qui est donc colorée en bleu. Puis, après avoir lancée l’application, l’avion se déplace régulièrement de cellule en cellule jusqu’à la cellule d’arrivée, à l’autre bout de la grille 1D.
Exemple :

Départ :
(Avion en C0)


Après premier
déplacement :
(Avion en C1)

Arrivée :
(Avion en C9)


User story 3
Un avion se déplace dans un environnement à deux dimensions représenté par une grille 2D. L’utilisateur définit le plan de vol de l’avion ; il indique les balises (x, y) par lesquelles l’avion doit successivement passer pendant son vol. Au lancement de l’application, l’avion se trouve à la verticale de la balise n°1 spécifiée dans son plan de vol. Après que l’utilisateur ait lancé l’application, l’avion se déplace en direction de la balise n°2 spécifiée dans son plan de vol. Pour cela, la balise n°2 émet un signal attracteur, dont les caractéristiques sont définies dans la classe AttractivePerimeter. Une fois la verticale de cette balise atteinte, le signal attracteur de la balise n°2 s’éteint au profit de celui de la balise n°3 qui s’active aussitôt. Le processus se poursuit jusqu’à ce que l’avion atteigne sa balise de fin.

Tout comme la User story 2, les déplacements de l’avion se matérialise par la colorisation en bleu des cellules une à une occupée par l’avion. Pendant chaque « tronçon » de son plan de vol, la cellule se situant à la verticale de la balise de départ est colorisée en jaune et celle se situant à la verticale de la balise d’arrivée d’une est colorisée en vert.


 Exemple :


Dans cet exemple, l’avion est en déplacement
de la cellule jaune (balise de départ) vers la
cellule verte (balise d’arrivée), toutes deux
spécifiées dans le plan de vol de l’avion.




 Arrivée à la balise verte, celle-ci devient jaune
et une autre balise verte se colore indiquant la
prochaine balise de destination. Etc.








User story 4

Idem que dans la User story 3, sauf que plusieurs avions peuvent désormais se déplacer dans l’espace. Ceci implique donc la mise en place d’un RepulsivePerimeter propre à chaque avion, qui signale ainsi sa présence aux autres avions. Il faudra introduire également la notion de couloir aérien dans lesquels les avions doivent impérativement rester.
Remarque : Attention à ne pas dépasser le seuil de saturation du secteur.





Résultats

Les User stories 1, 2 et 3 sont actuellement réalisée et la user story 4 en cours de réalisation. La figure suivante montre l’activation d’une balise contenue dans le plan de vol de l’avion qui le guide grâce à l’imputation d’un signal attracteur (chiffre affiché dans les cellules).



Le plan de vol est constitué de trois balises situées respectivement en B2, F2 et F7.

L’avion, après activation de la balise située en F2, s’est déplacé progressivement de la case jusqu’à cette case. Arrivé en F2, les signaux attracteurs émis par la balise F2 se sont éteints et la balise F7 a pris le relais. La figure ci-dessous montre l’arrivée de l’avion à destination.



Le prochain mois de stage sera donc consacré à la poursuite du développement en intégrant la notion de signaux répulsifs pour que plusieurs avions puissent évoluer sans risque de collision tout en suivant leur plan de vol.

Une fois la dernière user story réalisée, on pourra essayer de mesurer la qualité du SMA réactif. Pour cela il suffira de définir des paramètres quantitatifs qui prennent en compte les qualités de la solution obtenue ou l’efficacité du système. Dans le cas de l’évitement de collision entre avions, on voudra connaître le nombre de conflits (le nombre de fois où des avions se croisent à une distance inférieure à une distance limite) ou la déviation par rapport aux trajectoires nominales établies par leur plan de vol (dans notre cas un changement de direction par rapport au plan de vol initial de l’avion.).


CONCLUSION


Après ces 5 mois de stage et bien qu’il serait illusoire de croire que les SMA sont la solution à tous nos problèmes, les systèmes multi-agents offrent de nombreux avantages :

Ils fournissent des solutions aux problèmes distribués comme les réseaux de détecteurs distribués (comme pour le DVMT) ou contrôle de la navigation aérienne; les sources d’informations et d’expertise étant distribuées sur les agents qui collaborent à la résolution du problème

Ils tiennent compte des technologies existantes en permettant l’interconnexion et l’interopérabilité des divers systèmes existants comme les systèmes experts, mes outils de programmation par contraintes, etc.

Ils offrent plus de modularité (ce qui réduit la complexité du système), de vitesse d’exécution (grâce au parallélisme), de fiabilité (grâce à la redondance notamment dans le cas des systèmes réactifs), de flexibilité (la composition de nouvelles est facilité par la grande modularité des organisations) et de réutilisabilité du point de vue de la connaissance (partage des ressources).


Dans ce rapport, nous avons proposé une synthèse des travaux en Intelligence Artificielle Distribuée (IAD) et plus particulièrement les systèmes multi-agents (SMA).

L'IAD et les SMA sont des thèmes de recherche en cours d'exploration. Ils font intervenir plusieurs domaines de recherche tels que les systèmes répartis, la biologie, l’IA, la psychologie cognitive et la sociologie. De ce fait, les termes utilisés varient selon les différents chercheurs : il a été donc été nécessaire dans un premier temps de définir un vocabulaire précis afin d'éviter toute source de confusion et / ou ambiguïté sur l’utilisation de la terminologie agent.

En s’intéressant non plus à la notion d’agent en tant qu’individu isolé mais comme faisant partie d’un groupe, nous nous sommes ensuite intéressé au comportement global d'une société d'agents et aux théories sociales requises pour la résolution de problèmes dans un univers multi-agents : nous avons ainsi développé les problématiques liées à l’organisation sociale, à l’interaction, la coopération, la négociation, la coordination et encore la communication.

Nous avons ensuite dégagé les besoins nécessaires à une architecture de base pour la construction de système multi-agents au travers de l’étude des méthodologies et plate-formes existantes. En effet, les concepteurs d’application de SMA ont besoin d’environnement de développement doté d’un langage de spécification, de protocoles de coopération et de communication ainsi que des moyens de mise en œuvre des différentes lois (organisations) sociales dans une société d’agents.

Enfin, nous avons au travers de la plateforme JADE éprouvé le développement d’un SMA réactif appliqué à une problématique industrielle qu’est le suivi du trafic aérien. En réalité les avions sont aveugles et c’est le contrôleur aérien qui décide des changements d’altitude des avions : il a une connaissance « totale » sur le secteur aérien qu’il contrôle et peut ainsi donner les directives que doivent suivre les avions sur le secteur concerné. Nécessitant encore un peu de développement nous ne sommes pas en mesure de vérifier si la modélisation réalisée parvient à résoudre la problématique et d’éviter ainsi les collisions entre avions. Le mois restant sera donc nécessaire pour terminer et vérifier les propriétés d’émergence caractéristiques des systèmes à base d’agents réactifs. Toutefois, il semble qu’un système communiquant embarqué sur chaque avion et grâce auquel les avions communiqueront directement entre eux soit à l’étude chez Eurocontrol. A quand des agents dans nos avions…

BIBLIOGRAPHIE

Voici trois sites traitant des travaux en systèmes multi-agents et sur lesquels j’ai basé mes recherches pendant toute la durée de mon stage. Extrêmement riche en liens et références, c’est là que j’ai trouvé la plupart des références citées dans ce rapport:

The UMBC Agent Web :  HYPERLINK "http://www.cs.umbc.edu/agents/" \t "blank" http://www.cs.umbc.edu/aw/
The MIT Media Laboratory Agents Research group :  HYPERLINK "http://agents.www.media.mit.edu/groups/agents/" \t "blank" http://agents.www.media.mit.edu/groups/agents/
Muliagent Systems : HYPERLINK "http://www.multiagent.com/"http://www.multiagent.com/
AgentLink :  HYPERLINK "http://www.agentlink.org" http://www.agentlink.org Sur ce site sont également répertoriés les grands noms des acteurs du domaine dans la rubrique Agent People Finder
Nec Research Index :  HYPERLINK "http://citeseer.nj.nec.com/cs" http://citeseer.nj.nec.com/cs qui n’est pas exclusivement réservé aux systèmes multi-agents mais offre une collection incroyable d’articles scientifiques.

Il existe également des organismes de standardisation dont les deux principaux sont :

OMG Agent Platform Special Interest Group:  HYPERLINK "http://www.objs.com/agent/" http://www.objs.com/agent/
FIPA Foundation of Intelligent Physical Agents :  HYPERLINK "http://www.fipa.org/" http://www.fipa.org/


Les agents

[0]  HYPERLINK "http://www.agentlink.org/resources/agent-software.html" http://www.agentlink.org/resources/agent-software.html
A cette adresse sont recensés plus de 100 produits (académique / éducatifs ou industriels) : elle fournit une rapide descriptif des produits ainsi que le lien vers leurs sites respectifs.

[1]  HYPERLINK "http://www.msci.memphis.edu/~franklin/AgentProg.html" http://www.msci.memphis.edu/~franklin/AgentProg.html
“Is it an Agent, or just a Program?: A Taxonomy for Autonomous Agents” de Stan Franklin et Art Graesser - Institute for Intelligent Systems - University of Memphis - Proceedings of the Third International Workshop on Agent Theories, Architectures, and Languages, Springer-Verlag, 1996.

[2] « Les Systèmes Multi-Agents - Vers une Intelligence Collective » de Jacques Ferber – Laforia, Université Pierre et Marie Curie, InterEditions, 1995.

[3]  HYPERLINK "http://www.isrl.uiuc.edu/~gasser/papers/AgentsAndObjects-07.html" http://www.isrl.uiuc.edu/~gasser/papers/AgentsAndObjects-07.html
“ Agents and Concurrent Objects” – Interview de Les Gasser part Jean-Pierre Briot, Special Series on Actors and Agents, éditée par Dennis Kafura et Jean-Pierre
Briot, IEEE Concurrency, vol. 6, n° 4, pages 74-81, octobre-décembre 1998.

[4]  HYPERLINK "http://nrc.stanford.edu/~petrie/agents/abse/abse.html" http://nrc.stanford.edu/~petrie/agents/abse/abse.html
“On Agent-Based Software Engineering”, de JENNINGS N.R.- Artificial Intelligence, n°
117, pages 277-296, 2000.

[5] « Objets et agents : une étude des structures de représentation et de communications en Intelligence Artificielle » Jacques Ferber – Thèses d’état – Université Paris VI

[6] « Systèmes multi-agents et écosystèmes » - F. Bousquet et C. Le Page.

[7]  HYPERLINK "http://www.cs.berkeley.edu/~davidp/cs263/index.html" http://www.cs.berkeley.edu/~davidp/cs263/index.html
“Agent-Oriented Programming : A Practical Evaluation” - David Parks - University of California, Berkeley 94720

[8]  HYPERLINK "http://www710.univ-lyon1.fr/~rjcia/papiers/Fernandes.pdf" http://www710.univ-lyon1.fr/~rjcia/papiers/Fernandes.pdf
« Une approche multi-agents hybride pour la conception de systèmes complexes à raisonnement intégré » - Kelly Fernandes et Michel Occello - Laboratoire LEIBNIZ / IMAG / CNRS

[9]  HYPERLINK "http://citeseer.nj.nec.com/jung98methodological.html" http://citeseer.nj.nec.com/jung98methodological.html
“Methodological Comparison of Agents Models”, de Jong C., Fischer K. - Octobre 1998.  Propose une comparaison de l’architecture InteRRap (agent hybride) avec des architectures réactives et / ou cognitives comme l’architecture Subsumption, BDI (dMars), AOP (AGENT0) etc.
[10] HYPERLINK "http://citeseer.nj.nec.com/rao91modeling.html" http://citeseer.nj.nec.com/rao91modeling.html
“Modeling Rational Agents within a BDI-Architecture” (1991) - Anand S. Rao, Michael P. Georgeff - Proceedings of the 2nd International Conference on Principles of Knowledge Representation and Reasoning (KR'91)
[10a]  HYPERLINK "http://www.cs.umbc.edu/agents/introduction/rao.ps" http://www.cs.umbc.edu/agents/introduction/rao.ps
“BDI agents: From theory to practice,” A. S. Rao and M. P. Georgeff, Tech. Rep. 56, Australian Artificial Intelligence Institute, Melbourne, Australia, Apr 1995.

[10b]  HYPERLINK "http://www.isi.edu/teamcore/tambe/papers/99/bdi-panel.ps" http://www.isi.edu/teamcore/tambe/papers/99/bdi-panel.ps
“The Belief-Desire-Intention model of agency” - Georgeff, M., Pell, B., Pollack, M., Tambe, M. and Wooldridge, M., 1999 - Proceedings of Agents, Theories, Architectures and Languages (ATAL). 

[11]  HYPERLINK "http://www-ksl.stanford.edu/projects/BB1/bb1.html" http://www-ksl.stanford.edu/projects/BB1/bb1.html
« The BB1 Blackboard Control Architecture »

[12] « Atome: outil d’aide au développement de systèmes multi-experts. »
Lâasri H., Maître B. et Haton J.-P. - Actes 6e journées sur la reconnaissance des formes et l’intelligence artificielle (RFIA’87)

[13] HYPERLINK "http://agents.umbc.edu/introduction/ao/" http://agents.umbc.edu/introduction/ao/
“Software Agents: An Overview” de Hyacinth S. Nwana - Intelligent Systems Research -
Advanced Applications & Technology Department - BT Laboratories

[14]  HYPERLINK "http://www.rd.francetelecom.fr/fr/conseil/mento8/c4.pdf" http://www.rd.francetelecom.fr/fr/conseil/mento8/c4.pdf
« Technologie multi-agent » J. Ferber – Synthèse sur la technologie agent : les composants, les mécanismes d’interaction ainsi que des exemples pratiques d’utilisation de cette technique dans des problématiques liées aux télécommunications.

[15] Moulin B. & B. Mario (1996). A Scenario-based Design Method and an Environment for the Development of Multiagent Systems, In D. Lukose and C. Zhang, editors, First Australian Workshop on Distributed Artificial Intelligence, (LNAI volume 1087), 216-231. Springer-
Verlag: Heidelberg, Germany.

[16]  HYPERLINK "http://damas.ift.ulaval.ca/~coursMAS/" http://damas.ift.ulaval.ca/~coursMAS/
Support de cours sur les agents et les systèmes multi-agents de Brahim Chaib-draa couvrant toues les notions et indiquant des axes de lecture sur les différentes notions comme la communication, la coopération etc.

Les systèmes multi-agents

[20] “An overview of distributed artificial intelligence”. - B. Moulin and B. Chaib-draa. - In G. M. P. O'Hare and N. R. Jennings, editors, Foundations of Distributed AI, pages 3-54. John Wiley & Sons : Chichester, England, 1996.

[21] « Cooperative distributed problem solving » Durfee E. H., Lesser V. R. et Corkill D. D. – 1989 – The handbook of Artificial Intelligence – Addison-Weysley

[22] “Distributed interpretation : A model and experiment.” - V. R. Lesser and L. D. Erman. - IEEE Transactions on Computers, C-29(12), 1980.

[23] “A retrospective view of FA/C distributed problem solving.” - V. R. Lesser. - IEEE Transactions on Systems, Man, and Cybernetics, Special Issue on Distributed Artificial Intelligence, 21(6) :1347-1362, 1991.

[24]  HYPERLINK "ftp://ftp.eecs.umich.edu/people/durfee/smc-dsn91.ps.Z" ftp://ftp.eecs.umich.edu/people/durfee/smc-dsn91.ps.Z
"Partial Global Planning: A Coordination framework for Distributed Hypothesis Formation," Durfee, IEEE-SMC 21(5) 1991.

[25] "Coherent Cooperation Among Communicating Problem Solvers," E.H. Durfee, V.R. Lesser, and D.D. Corkill, IEEE TOC 1987

[26] N. R. Jennings. “Controlling cooperative problem solving in industrial multi-agent systems using joint intentions”. Artificial Intelligence, 74(2), 1995.

[27] H. J. Levesque, J. H. T. Nunes, and P. R. Cohen. « On acting together”. In William Dietterich, Tom ; Swartout, editor, Proceedings of the 8th National Conference on Artificial
Intelligence, pages 94-99, Hynes Convention Centre, 1990. MIT Press.

[28]  HYPERLINK "http://www-2.cs.cmu.edu/afs/cs/user/katia/www/persuader.html" http://www-2.cs.cmu.edu/afs/cs/user/katia/www/persuader.html
Home page du projet PERSUADER

[29] S. J. Rosenschein. “Rational Interaction : Cooperation Among Intelligent Agents”. PhD thesis, Stanford University, Computer Science Department, 1985.

[30] S. J. Rosenschein et G. Zlotkin. “Rules of Encounter : Designing Conventions for Automated Negotiation Among Computer ». MIT Press, Boston, MA, 1994.

[31] T. Sandholm and V. Lesser. “Issues in automated negotiation and electronic commerce : Extending the contract net framework”. In Proceedings of the First International
Conference on Multi-Agent Systems (ICMAS-1)1995

[32] T. W. Malone. “Organizing information processing systems : parallels between human organizations and computer systems.” In W. W. Zachary and S. P. Robertson, editors, Cognition,Computation and Cooperation, pages 56-83. Ablex, 1990.

[33] H. Mintzberg. “The Structuring of Organizations.” Englewoods Cliffs, 1979.

[34] R. Conte, M. Miceli, and C. Castelfranchi. “Limits and levels of cooperation.” In Y. Demazeau and J.-P. Mü ller, editors, Decentralized AI 2 - Proceedings of the Second EuropeanWorkshop on Modelling Autonomous Agents and Multi-AgentWorlds (MAAMAW-90) Elsevier Science

[35] F. V. Martial. “Interactions among autonomous planning agents.” In Y. Demazeau and J.-P. Mü ller, editors, Decentralized AI - Proceedings of the First European Workshop on Modelling Autonomous Agents in Multi-Agent Worlds (MAAMAW-89).

[36] E. H. Durfee and V. Lesser. “Negotiating task decomposition and allocation using partial global planning”. In L. Gasser and M. Huhns, editors, Distributed Artificial Intelligence VolumeII, 1989.

[37 R. Davis and R. Smith. “Negotiation as a metaphor for distributed problem solving.” Artificial Intelligence, January 1983.

[38] R. G. Smith.”The contract net protocol.” IEEE Transactions on Computers, 1980.

[39] S. Cammarata, D. McArthur, and R. Steeb. “Strategies of cooperation in distributed problem solving”. In Proceedings of the Eighth International Joint Conference on Artificial
Intelligence (IJCAI-83), Karlsruhe, Germany, 1983.

[40] S. Cammarata, D. McArthur, and R. Steeb. “Strategies of cooperation in distributed problem solving”. Proceedings of the8th International Joint Conference on Artificial Intelligence, 1983.

[41] K. P. Sycara. “Multi-agent compromise via negotiation”. In L.Gasser and M. Huhns, editors, Distributed ArtificialIntelligence Volume II1989.

[42] J. Müller. „Negotiation principles”. In G. M. P. O'Hare and N. R.Jennings, editors, Foundations of Distributed AI 1996.

[43] A. H. Bond and L. Gasser, editors. Readings in Distributed Artificial Intelligence. 1988.

[44] M. P. Georgeff. “Communication and interaction in multi-agent planning”. In Proceedings of the Third National Conference on Artificial Intelligence (AAAI-83), 1983.

[45] F. V. Martial. “Interactions among autonomous planning agents.” In Y. Demazeau and J.-P. Mü ller, editors, Decentralized AI - Proceedings of the First European Workshop on Modelling Autonomous Agents in Multi-Agent Worlds (MAAMAW-89).

[46] F. V. Martial, editor. “Coordinating Plans of Autonomous Agents”. Springer-Verlag : Heidelberg, Germany, 1992.

[47] S. E. Conry, R. A. Meyer, and R. P. Pope. “Mechanisms for assessing the nonlocal impact of local decisions in distributed planning”. In L. Gasser and M. Huhns, editors, Distributed Artificial Intelligence. 1989.

[48] S. E. Conry, K. Kuwabara, V. R. Lesser, and R. A. Meyer. “Multistage negotiation in distributed constraint satisfaction.”
[49] V. R. Lesser. « A retrospective view of FA/C distributed problem solving”. IEEE Transactions on Systems, Man, and Cybernetics,1991.


Voici maintenant une liste de liens plus spécifique à chacun des thèmes abordés comme l’interaction, l’organisation, la coordination, la planification, la négociation dans les systèmes multi-agents.

Interaction

“Agent Communication Languages: Rethinking the Principles”, M.P. Singh, IEEE Computer, volume 31, number 12, December 1998, pages 40-47.
 HYPERLINK "http://www.csc.ncsu.edu/faculty/mpsingh/papers/mas/computer-acl-98.pdf" http://www.csc.ncsu.edu/faculty/mpsingh/papers/mas/computer-acl-98.pdf

KQML
« KQML as an Agent Communication Language » , Finin, McKay, McEntire 1994
 HYPERLINK "http://www.cs.umbc.edu/kqml/papers/kqml-acl.ps" http://www.cs.umbc.edu/kqml/papers/kqml-acl.ps

« Communicative Actions for Artificial Agents » , Cohen & Levesque, ICMAS-95
 HYPERLINK "ftp://cse.ogi.edu/pub/chcc/pcohen/our-kqml-unix.ps" ftp://cse.ogi.edu/pub/chcc/pcohen/our-kqml-unix.ps

« FIPA Agent Communication Language draft spec » , 1999
 HYPERLINK "http://www.fipa.org/repository/bysubject.html" http://www.fipa.org/repository/bysubject.html

Organisation  
“Commitments and Conventions: The Foundation of Coordination in Multi-Agent Systems” , N. R. Jennings, The Knowledge Engineering Review, 8 (3), 1993, 223-250.
 HYPERLINK "ftp://ftp.elec.qmw.ac.uk/pub/isag/distributed-ai/publications/KE-REVIEW-8-3.ps.Z" ftp://ftp.elec.qmw.ac.uk/pub/isag/distributed-ai/publications/KE-REVIEW-8-3.ps.Z

Réseaux de dépendances
“DEPINT: Dependence-Based Coalition Formation in an Open Multi-Agent Scenario” 1998 - J.S. Sichman, in: Journal of Artificial Societies and Social Simulation, 1(2),  HYPERLINK "http://www.soc.surrey.ac.uk/JASSS/1/2/3.html" http://www.soc.surrey.ac.uk/JASSS/1/2/3.html

 Le modèle AALAADIN
« Vers une méthodologie organisationnelle pour les systèmes multi-agents », O. Gutknecht & J. Ferber, JFIADSMA'99 et RR LIRMM 99073, Juin 99 –
 HYPERLINK "http://www.lirmm.fr/~gutkneco/ecrits/rr99073.pdf,%20ps.gz" http://www.lirmm.fr/~gutkneco/ecrits/rr99073.pdf, ps.gz

Méthode Cassiopée
« Application de la méthode Cassiopée à l'organisation d'une équipe de robots » , Collinot A.,Drogoul A. and Ploix L. in Intelligence Artificielle Distribuée et Systèmes Multi-Agents, J.P. Muller et J. Quinqueton (Eds), pp. 136-152, Hermès, Paris, 1996
 HYPERLINK "http://www-poleia.lip6.fr/~drogoul/papers/jfiadsma96.ps.gz" http://www-poleia.lip6.fr/~drogoul/papers/jfiadsma96.ps.gz

“Agent Oriented Design of a Robotic Soccer Team” Collinot A.,Drogoul A. and Benhamou P. in proceedings of ICMAS'96, pp. 41-57, AAAI Press, 1996.  HYPERLINK "http://www-poleia.lip6.fr/~drogoul/papers/icmas96.ps.gz" http://www-poleia.lip6.fr/~drogoul/papers/icmas96.ps.gz


Coordination

“Coordination Techniques for Distributed Artificial Intelligence” N. R. Jennings, in Foundations of Distributed Artificial Intelligence (eds. G. M. P. O'Hare and N. R. Jennings), Wiley, 1996, 187-210.
 HYPERLINK "ftp://ftp.elec.qmw.ac.uk/pub/isag/distributed-ai/publications/FOUND-DAI-COORD.ps.Z" ftp://ftp.elec.qmw.ac.uk/pub/isag/distributed-ai/publications/FOUND-DAI-COORD.ps.Z
 HYPERLINK "http://www.labs.bt.com/projects/agents/publish/papers/report4.ps.gz" Coordination in Software Agent Systems, Hyacinth Nwana, Lyndon Lee, and Nick Jennings, BT Technology Journal, 14(4), 1996, pp 79-88.

Planification multi-agents
Partial Global Planning
“Partial Global Planning: A Coordination framework for Distributed Hypothesis Formation” Durfee, IEEE-SMC 21(5) 1991
 HYPERLINK "ftp://ftp.eecs.umich.edu/peolple/durfee/smc-dsn91.ps.Z" ftp://ftp.eecs.umich.edu/peolple/durfee/smc-dsn91.ps.Z
 Keith S. Decker and Victor R. Lesser. “Designing a Family of Coordination Algorithms”. Reprinted in M. Huhns and M. Singh, editors, Readings in Agents. Morgan Kaufmann,1997.
 HYPERLINK "ftp://ftp.cs.umass.edu/pub/lesser/decher-94-14.ps" ftp://ftp.cs.umass.edu/pub/lesser/decher-94-14.ps
Keith S. Decker. “TÆMS: A framework for analysis and design of coordination mechanisms”. In G. O'Hare and N. Jennings, editors, Foundations of Distributed Artificial Intelligence. Wiley Inter-Science, 1995 (Chapter 16, invited).  HYPERLINK "ftp://dis.cs.umass.edu/pub/decker-thesis-chapter3.ps" ftp://dis.cs.umass.edu/pub/decker-thesis-chapter3.ps
Négociation
The internet Auction List : http://www.internetauctionlist.com/
M. Beer, M. d'Inverno, M. Luck, N. R. Jennings, C. Preist and M. Schroeder (1999) "Negotiation in Multi-Agent Systems" Knowledge Engineering Review 14 (3) 285-289.  HYPERLINK "http://www.ecs.soton.ac.uk/~nrj/download-files/ker99-2.ps" http://www.ecs.soton.ac.uk/~nrj/download-files//ker99-2.ps
N. R. Jennings, P. Faratin, A. R. Lomuscio, S. Parsons, C. Sierra and M. Wooldridge (2001) "Automated negotiation: prospects, methods and challenges" Int. J. of Group Decision and Negotiation 10  HYPERLINK "http://www.ecs.soton.ac.uk/~nrj/download-files/gdn01.ps%20" http://www.ecs.soton.ac.uk/~nrj/download-files/gdn01.ps
P. Faratin, N. R. Jennings, P. Buckle, and C. Sierra (2000) "Automated negotiation for provisioning virtual private networks using FIPA-compliant agents" Proc. 5th Int. Conf. on the Practical Application of Intelligent Agents and Multi- Agent Systems (PAAM-2000), Manchester, UK, 185-202.
 HYPERLINK "http://www.ecs.soton.ac.uk/~nrj/download-files/paam2000.ps" http://www.ecs.soton.ac.uk/~nrj/download-files/paam2000.ps
Sandholm, T. and Lesser, V. 1995. “Issues in Automated Negotiation and Electronic Commerce: Extending the Contract Net Framework”. First International Conference on Multiagent Systems (ICMAS-95), San Fransisco, pp. 328-335.  HYPERLINK "ftp://ftp.cs.umass.edu/pub/lesser/sandhom-icmas95-issues.ps" ftp://ftp.cs.umass.edu/pub/lesser/sandhom-icmas95-issues.ps
Gilad Zlotkin, Jeffrey S. Rosenschein, “Mechanisms for Automated Negotiation in State Oriented Domains” (1996) , Journal of Artificial Intelligence Research,   HYPERLINK "http://citeseer.nj.nec.com/zlotkin96mechanisms.html" http://citeseer.nj.nec.com/zlotkin96mechanisms.html

Méthodologie  

[0]A. Sabas, M. Badri & S. Delisle : A Multidimentional Framework for the Evaluation of Multiagent System Methodologies  HYPERLINK "http://citeseer.nj.nec.com/cache/papers/cs/25995/http:zSzzSzwww.uqtr.uquebec.cazSz~delislezSzRecherchezSzconf-paperszSzSCI2002-134JD-MUCCMAS.pdf/a-multidimentional-framework-for.pdf" http://citeseer.nj.nec.com/cache/papers/cs/25995/http:zSzzSzwww.uqtr.uquebec.cazSz~delislezSzRecherchezSzconf-paperszSzSCI2002-134JD-MUCCMAS.pdf/a-multidimentional-framework-for.pdf

[3] Collinot A., A. Drogoul & P. Benhamou (1996). Agent Oriented Design of a Soccer Robot Team, Proceedings of the Second International Conference on Multi-Agent systems (ICMAS-96), 41-47, Japan.

[4] Moulin B. & B. Mario (1996). A Scenario-based Design Method and an Environment for the Development of Multiagent Systems, In D. Lukose and C. Zhang, editors, First Australian Workshop on Distributed Artificial Intelligence, (LNAI volume 1087), 216-231. Springer-
Verlag: Heidelberg, Germany.

[5] Iglesias C.A., M. Garjo, J.C. Gonzàlez, & J.R. Velasco (1998). Analysis and Design of Multiagent Systems Using MAS-CommonKADS, In AAA’97 Workshop on Agent Theories, Architectures and Languages, Providence, RI, July 1997. ATAL. An extended version of this paper has been published in INTELLIGENT AGENTS IV : Agent Theories, Architectures, and Languages, Springer-Verlag.

[6] Kinny D., M. Georgeff & A. Rao (1996). A Methodology and Modelling Technique for Systems of BDI Agents, In W. van der Velde and J. Perram, editors, Agents Breaking
Away : Proceedings of the Seventh European Workshop on Modelling Autonomous Agents in a Multi-Agent World - MAAMAW’96 (LNAI Volume1038), Springer-Verlag: Heidelberg, Germany.

[8] Deloach S.A. (1999). Multiagent Systems Engineering : A Methodology And Language for Designing Agent System, AOIS-1999 (Agent-Oriented Information Systems).

[9] Kendall E.A., M.T. Malkoun & C. Jiang (1996). A Methodology for Developing Agent-based Systems for Enterprise Integration, In D.Luckose and Zhang C., editors, Proceedings of the First Australian Workshop on DAI, Lecture Notes on Artificial Intelligence, Springer-Verlag: Heidelberg, Germany.

[12] Glaser N. (1996). Contribution to Knowledge Modelling in a Multi-Agent Framework (the CoMoMAS Approach), PhD thesis, Université Henri Poincaré, Nancy I, France, 1996.

[15] Schreiber G., B.J. Wielinga, J.M. Akkermans, W. Van de Velde & A. Anjewierden (1994). CML: The CommonKADS Conceptual Modelling Language, In Proc. 8th European Knowledge Acquisition Workshop, 1-25, Hoegaarden, Belgium.

[16] Scott A.D. (1999). Multiagent Systems Engineering : A Methodology And Language for Designing Agent Systems, AOIS-1999 (Agent-Oriented Information Systems).

[18] Wooldridge M., N.J. Jennings N.J. & D. Kinny (2000). The Gaia Methodology For Agent-Oriented Analysis and Design, Journal of Autonomous Agents and Multi-Agent
Systems 3 (3), 285-312.

[BER01]Vers une méthodologie d’analyse et de conception
http://www-leibniz.imag.fr/LesCahiers/2001/Cahier20/CLLeib20.pdf
A. Tveit.  HYPERLINK "http://csgsc.idi.ntnu.no/2001/pages/papers/atveit.pdf" A Survey of Agent-Oriented Software Engineering. NTNU CSGSC, 2001 Discution sur les différentes méthodologie en passant par les design partterns, UML, GAIA, les composants, etc.

Plate-formes
 HYPERLINK "http://www.agentbuilder.com/AgentTools/index.html" http://www.agentbuilder.com/AgentTools/index.html
Sur ce site d’agentbuilder sont répertoriées ensemble des plate-formes existantes sur le marché et catégorisé selon qu’elles sont commercialisées ou faisant parties d’un projet de recherche et / ou universitaire.

A titre d’exemple, voici une liste non exhaustive des plate-formes compatibles FIPA :
JADE : http://sharon.cselt.it/projects/jade/
FIPA-OS : http://fipa-os.sourceforge.net/
LEAP : http://leap.crm-paris.com/index.shtml
ZEUS : http://more.btexact.com/projects/agents.htm
Et aussi :
Madkit : http://www.madkit.org/
Agentbuilder : http://www.agentbuilder.com/
OAA : http://www.ai.sri.com/~oaa/
Java Agent Services  : http://www.java-agent.org/

Plate-formes SMA testées

AGENTBUILDER

2. Y. Shoham. AGENT-0: a simple agent language and its interpreter. In Proceedings of the Ninth National Conference on Artificial Intelligence,

3. Y. Shoham. Agent Oriented Programming. Artificial Intelligence, 60(1), pp. 51-92, North-Holland, 1993.

4. S. R. Thomas. PLACA, an Agent Oriented Programming Language. Ph.D. Thesis, Stanford University, 1993

JACK

6. Mark d’Inverno, David Kinny, Michael Luck, and Michael Wooldridge. A formal
Specification of dMARS. In Singh et al, editors, Proceedings of the 4th International
Workshop on Agent Theories, Architectures, and Languages (ATAL’97), LNAI, Vol. 1365,pp. 155-176, Springer, 1998.

7. P. Busetta, R. Rönnquist, A. Hodgson, A. Lucas. JACK Intelligent Agents – Components forIntelligent Agents in Java. Updated from AgentLink Newsletter #2, Octobre 1999 -  HYPERLINK "http://www.agent-software.com.au/" http://www.agent-software.com.au/


MADKIT
8. J. Ferber and O. Gutknecht. A meta-model for analysis and design of multi-agent systems. Proceedings of the 3rd International Conference on Multi-Agent Systems, (ICMAS'98),IEEE, pp. 155-176, August 1998.

9. O. Gutknecht and J. Ferber. Vers une méthodologie organisationnelle pour les systèmes multi-agents. In Actes des JFIADSMA’99 (Journées Francophones d’Intelligence ArtificielleDistribuée et Systèmes Multi-Agents), Saint-Denis, Reunion, 1999

ZEUS
10. J. Collis, D. Ndumu. The ZEUS Technical Manual. external documentation,
 HYPERLINK "http://www.labs.bt.com/projects/agents/zeus" http://www.labs.bt.com/projects/agents/zeus/, September 1999.

11. J. Collis, D. Ndumu, and S. Thompson. ZEUS Methodology Documentation, Role
Modelling Guide, Three case studies, Application Realisation Guide, Runtime Guide.
 HYPERLINK "http://www.labs.bt.com/projects/agents/zeus" http://www.labs.bt.com/projects/agents/zeus/, August-November 1999.

12. H. Van Dyke Parunak, Sven Brueckner, John Sauter and Robert S. Matthews.
Distinguishing Environmental and Agent Dynamics: A Case Study in Abstraction and
Alternate Modeling Technologies. In this volume.

13. Cristiano Castelfranchi. Engineering Social Order.

14. M. Occello, C. Baeijs, Y. Demazeau, and J.L. Koning. MASK : An AEIO Toolbox to Develop Multi-Agent Systems. In Cuena et al editors, Knowledge Engineering and AgentTechnology, IOS Series on Frontiers in Artificial Intelligence and Applications, 2000.

15. Y. Demazeau, M. Occello, C. Baeijs, and P.-M. Ricordel. Systems Development as
Societies of Agents. In Cuena et al editors, Knowledge Engineering and Agent Technology,IOS Series on Frontiers in Artificial Intelligence and Applications, 2000.
.

ACL

« Agent Communication Languages : The Current Landscape » - Introduit les concepts utiles pour appréhender les ACLs puis compare les deux principaux : KQML et FIPA ACL
 HYPERLINK "http://citeseer.nj.nec.com/labrou99current.html" http://citeseer.nj.nec.com/labrou99current.html

KIF – Knowledge Interchange Format - Spécification de la syntaxe et des sémantiques
 HYPERLINK "http://logic.stanford.edu/kif/dpans.html" http://logic.stanford.edu/kif/dpans.html

KQML – Knowledge Query and Manipulation Language
 HYPERLINK "http://www.cs.umbc.edu/kqml/papers/kbkshtml/kbks.html" http://www.cs.umbc.edu/kqml/papers/kbkshtml/kbks.html


Méthode XP

 HYPERLINK "http://www.extremeprogramming.org" http://www.extremeprogramming.org
Le site de référence XP, qui propose une excellente présentation de la méthode.

HYPERLINK "http://www.xprogramming.com" http://www.xprogramming.com
Un site XP écrit et maintenu par Ron Jeffries, un acteur important du mouvement XP. On y trouve des articles très intéressants sur la méthode (rubrique "XP Magazine"), ainsi qu'une liste des frameworks xUnit disponibles pour divers langages ("XP downloads").

 HYPERLINK "http://www.objectmentor.com" http://www.objectmentor.com
Object Mentor est une société de conseil dirigée par Robert Martin, un acteur important des mouvements objet et XP. De nombreux articles sur ces thèmes sont disponibles sur leur site, en particulier ceux qui ont servi de base à notre dossier "Principes avancés de conception objet".

 HYPERLINK "http://www.xp123.com" http://www.xp123.com
Ce site de William Wake propose de nombreux articles sur les pratiques concrètes de XP (les tests unitaires avec Java, le Planning Game, etc). Ces articles font l'objet du livre "Extreme Programming Explored".


 HYPERLINK "http://c2.com/cgi/wiki?ExtremeProgrammingRoadmap" http://c2.com/cgi/wiki?ExtremeProgrammingRoadmap
A mi-chemin entre le site web et la mailing list, le Wiki Wiki Web contient une grande quantité d'informations sur le développement en général, et sur XP en particulier.

 HYPERLINK "http://www.xp-france.org" http://www.xp-france.org
Ce site français propose une vue d'ensemble de la méthode ainsi que des traductions d'une sélection d'articles américains. GLOSSAIRE

Cette rubrique a pour objectif de définir des termes clefs dans le domaine des systèmes multi-agents qui ont été introduits et utilisés dans ce rapport.

ACCOINTANCES
Chaque agent est lié directement à un ensemble d’autres agents, que l’on appelle ses accointances.

ACL
Agent Communication Language – Langage de communication utilisé par les AGENTS pour communiquer (échanger de l’information et de la connaissance) avec d’autres. Les ACL les plus connus sont KQML et KIF - Knowledge Interchange Format. De nombreux dialectes et variantes existent comme notamment FIPA ACL, homologué aux standards de la FIPA - Foundation for Intelligent Physical Agents.

ACTEUR
Concept développé par Carl Hewitt au MIT, les acteurs sont des objets concurrents qui encapsulent chacun une partie de la connaissance et du contrôle répartis. Le comportement d'un acteur est composé d'une partie accointances et d'une partie opératoire. Un acteur traite en série les messages qu'il reçoit. En réponse à un message un acteur peut simultanément créer dynamiquement de nouveaux acteurs, envoyer des messages aux acteurs qu'il connaît, et remplacer son comportement courant par celui qui va traiter le prochain message. Les acteurs sont identifiés de manière unique par une adresse. Analogue à un service postal, leur communication est asynchrone, point à point, unidirectionnelle et sûre.

ADAPTATIVITE
Un agent est ''adaptatif'' s'il est capable de contrôler ses aptitudes (communicationnelles, comportementales, etc.) selon l'agent avec lequel il interagit. C'est un agent d'un haut niveau de flexibilité capable de changer de comportement en fonction de ses expériences passées.

AGENT
On appelle agent une entité réelle ou abstraite :
capable d'agir sur elle-même et son environnement,
disposant d'une représentation partielle de cet environnement,
pouvant, dans un univers multi-agents, communiquer avec d'autres agents,
et dont le comportement est la conséquence de ses observations, de sa connaissance et des interactions avec les autres agents.

Autre définition de Jacques Ferber dans « Les Systèmes multi-agents ». Vers une intelligence collective », Inter-Editions, 1995 :
« Entité physique ou virtuelle :
capable d'agir dans un (sur son) environnement,
capable de communiquer directement avec d'autres agents,
qui est mue par un ensemble de tendances,
qui possède des ressources propres,
qui est capable de percevoir de manière limitée (localement) son environnement, et qui ne dispose que d'une représentation partielle de cet environnement, (Attention ceci n’est pas le cas d'un agent réactif)
qui possède des compétences,
qui offre des services, (pour le réactif ?)
qui peut éventuellement se reproduire. »

On distingue deux principaux types d’agents : les AGENTS REACTIFS et les AGENTS COGNITIFS.

AGENT COGNITIF
Ces agents possèdent une symbolique interne, un modèle de raisonnement et ils s'engagent dans la planification et la négociation pour réaliser la coordination avec d'autres agents

AGENT REACTIF
Les agents perçoivent leur environnement, (qui peut être le monde physique, un utilisateur via une interface utilisateur graphique, une collection (ramassage) d'autres agents, l’Internet, ou peut-être une combinaison de tout ça) et répondent d'une façon opportune aux changements qui y arrivent. (Loi du stimuli/action)
Ces agents n'ont pas de modèle symbolique interne de leur environnement et ils agissent en employant un type de comportement de stimulus/action en réponse à l'état présent de leur environnement.

ANALYSE
La phase d’analyse dans le cycle de vie d’un logiciel a pour but de trouver une modélisation satisfaisante du monde réel pour déboucher sur une spécification des moyens informatiques à mettre en œuvre pour réaliser l’application visée. Elle correspond à l’écriture des spécifications fonctionnelles ou à la définition des d’objets conceptuels dans les méthodes objets.

ARCHITECTURE
Terme généralement employé pour décrire l’organisation interne d’un agent qui définit les structures de données logicielles (composants) qui les constituent ainsi que les opérations applicables sur ces dernières.

Dans son livre, Jacques Ferber en dénombre pas loin de 9. Il s’agit des architectures à base de modules horizontaux (ou architectures modulaires), de tableau noir (ou blackboard), de subsomption, de tâches compétitives, de règles de production, de classifieurs, de systèmes dynamiques, de systèmes multi-agents et les architectures connexionnistes.




AUTOMATE CELLULAIRE
http://www-ensimag.imag.fr/eleves/Franck.Vivien/maths/automates/index.html
Système simple, capable de se reproduire à la manière d'un organisme vivant et caractérisé par 4 propriétés :
La géométrie du réseau de cellules (2D en général)
La façon dont le voisinage d'une cellule modifie l'évolution de cette dernière
Le nombre d'états possibles des cellules
Les règles que l'on peut adopter pour déterminer l'état suivant en fonction de l'état des cellules de son voisinage.

AUTONOMIE
Contrairement à des programmes standards qui sont directement manipulés par l'utilisateur, un agent autonome est capable de réagir sans intervention extérieure (humaine ou non) et d'exercer un contrôle sur ses propres actions ; il décide de lui-même quand agir.

ARCHITECTURE BDI
C’est une ARCHITECTURE contenant des représentations explicites de croyances, désirs et intentions (Beliefs, Desires, Intentions). Les croyances sont généralement vues comme l’information dont un agent dispose sur son environnement (informations qui peuvent être fausses d’ailleurs) ; les désirs sont les buts que les agents aimeraient atteindre (les désirs ne sont pas nécessairement consistant et un agent peut agir tout en ne respectant pas tous ces désirs) ; et enfin, les intentions sont les choses dont l’agent peut-être commis de faire (par lui-même ou pour un autre agent).
A. S. Rao et M. P. Georgeff. An abstract architecture for rational agents. In C. Rich, W. Swartout and B. Nebel, editors, Proceedings of Knowledge Represnetation and Reasonning.

BIENVEILLANCE
Un agent bienveillant essaiera toujours de faire ce qu'on lui demande.

BLACKBOARD
Sorte d’architecture dans laquelle une collection de sources de connaissance (knowledge sources) communique au travers d’une structure de données accessibles par tous connu sous le nom de tableau noir (blackboard).

COLLABORATIF
Un agent collaboratif est capable d'interagir et de collaborer avec d'autres agents logiciels ou avec des êtres humains dans le but d'accomplir ses actions.

Un agent n'obéit pas aveuglément aux commandes, mais a la capacité de modifier les requêtes, poser des questions (pour clarifier la requête), ou même refuser de satisfaire certaines requêtes.

COMMUNICATION POINT A POINT
Lorsque le destinataire est connu de l'émetteur, ce dernier peut lui adresser des messages en particulier et ainsi instaurer une communication individuelle. On dit alors que les communications sont effectuées selon un mode point à point. C'est le type de communication qui est généralement le plus employé dans les agents cognitifs.

COMMUNICATIF
Un agent communicatif est capable d'engager une conversation complexe avec d'autres agents, incluant des personnes, afin d'obtenir des informations ou de les enrôler dans l'accomplissement de ses buts.

COOPERATIF
Un agent coopératif planifie ses actions par coordination et négociation avec les autres agents.

CONCEPTION
La phase de conception doit conduire à l’implémentation de l’application en effectuant les choix de modèles opérationnels pour la réalisation. Il s’agit des spécifications opérationnelles ou de la définition des aspects statiques, dynamiques et fonctionnels des objets.

DIFFUSION OU BROADCAST
Si le destinataire n'est pas connu de l'émetteur, le message est envoyé sous un mode appelé diffusion (ou broadcasting) à tout un ensemble d'agents, ses derniers étant liés à l'émetteur par une relation de voisinage (ACCOINTANCES).
Ce type de communication est très utilisé dans les systèmes dynamiques dans lesquels des agents peuvent apparaître ou disparaître, en particulier dans des protocoles d'allocation des tâches (ex. Contract net).

EFFICACITE
C'est l'aptitude d'un agent à résoudre le problème et atteindre ses buts.

ENGAGEMENT
Qualité essentielle des agents coopératifs : en construisant un plan pour atteindre un but, l'agent se donne les moyens d'y parvenir et donc s'engage à accomplir les actions qui satisfassent ce but.

ENVIRONNEMENT
Un environnement est un espace représentant le monde dans lequel les agents évoluent. On fait généralement une distinction entre les agents qui sont les entités actives, et les objets passifs qui se situent dans l’environnement. Lorsque ce dernier dispose d’une métrique (cas général), la capacité de perception d’un agent est sa capacité à reconnaître les objets situés (position, relations entre objets) et la capacité d’action d’un agent est celle de transformer l’état du système en modifiant les positions et relations qui existent entre les objets. Par exemple dans un univers de robots, l’environnement est l’espace géométrique euclidien dans lequel se déplacent les robots (agents) et où sont situés des objets physiques que les robots peuvent manipuler ou doivent éviter.

FLEXIBILITE
Les actions d'un agent ne sont pas entièrement prédéfinies (ce ne sont pas des scripts) : l'agent est capable de choisir et ordonnancer dynamiquement les actions à mettre en oeuvre en réponse à l'état de l'environnement extérieur.

INTELLIGENT
On appelle agent intelligent un agent cognitif, rationnel, intentionnel et adaptatif.

INTENTION
Un agent est dit intentionnel s'il ne se contente pas d'agir en fonction des conditions de / en réponse à son environnement mais en fonction de ses buts propres et s'il possède une intentionnalité, c'est-à-dire est une volonté consciente d'effectuer un acte : il est guidé par ses buts.

Une intention est la déclaration explicite des buts et des moyens d'y parvenir. Elle exprime la volonté d'un agent d'atteindre un but ou d'effectuer une action.
Autrement dit, les agents intentionnels n'agissent pas simplement en réponse à leur environnement mais sont capables de prendre l'initiative afin de satisfaire leurs buts. Ils sont donc guidés par leurs buts.

INTERLINGUA
Ce langage sert de médiateur dans la traduction d'autres langues.
Ex. KIF (Knowledge Interchange Format)

KQML
Knowledge Query and Manipulation Language - KQML est un protocole et un langage de communication orienté message de haut niveau permettant un échange d'information indépendamment de la syntaxe du contenu et de l'ONTOLOGIE appliquée.

Ainsi, KQML est indépendant du mécanisme de transport (TCP/IP, SMTP, IIOP, ou autre), indépendant du langage du contenu (KIF, SQL, STEP, Prolog ou autre), et indépendant de l'ontologie présumée pour le contenu.

Pour plus de détails, voir en Annexe.

MOBILITE
Un agent mobile est un agent capable de se déplacer dans son environnement, qui peut être physique (réel ou simulé) ou structurel (niveaux d'exécution par exemple). Un agent mobile dispose donc de dispositifs assurant sa mobilité.

Dans le cas d'un agent robotique physique ou simulé, il s'agit bien évidemment d'effecteurs lui permettant de se déplacer. Dans le cas d'un agent logiciel, la mobilité implique le déplacement dans le réseau ou dans l'architecture du système, c'est à dire la mise en place d'un mécanisme de migration de processus.

Ainsi, un agent mobile qui se rapproche d'une ressource (base de données, agent logiciel, périphérique, etc.) pourra travailler de manière plus efficace: plutôt que d'accéder à cette ressources à travers un WAN, il peut se déplacer à travers le réseau de relais en relais et accéder localement à la ressource désirée en utilisant une bande passante maximale.

ONTOLOGIE
Terme technique utilisé pour décrire la connaissance de base dont dispose un agent sur le domaine auquel il s’applique. Plus formellement, une ontologie est une conceptualisation particulière d’un ensemble d’objets, concepts et autres entités à partir desquels la connaissance est exprimée ainsi que des relations qui existent parmi eux. Une ontologie est constituée de termes, et d’axiomes relatifs à ces derniers ; ces termes ont généralement organisés en taxonomie.

Dans un contexte de partage de la connaissance, les ontologies fournissent donc un vocabulaire pour la représentation et la communication de la connaissance sur un quelconque sujet ainsi que l’ensemble des rapports qui existent entre eux pour un agent ou une communauté d'agents.

''Ontolingua'' est un langage permettant la description d'ontologies
cf  HYPERLINK "http://www.ksl.stanford.edu/software/ontolingua/" http://www.ksl.stanford.edu/software/ontolingua/

PERFORMATIF
Très utile pour les systèmes multi-agents, le performatif permettra d'indiquer le type d'acte de langage effectué par le locuteur d'un message à son destinataire associé au message. De ce fait les énoncés des messages sont exprimé sous la forme ().
Ex. : informer(« Il pleut »)

KQML a adopté le terme performatif pour caractériser chacun des types de message primitif.

PLAN
Représentation d’une succession d’actions qui, quand le plan est exécuté, conduira à l’accomplissement d’un but. Les plans peuvent impliquer un ou plusieurs agents ; on parle alors de plans joints.


PRO-ACTIF
Capable de prendre l’initiative, un agent proactif n’est pas seulement conduit par les évènements mais capable de générer des buts et d’agir rationnellement pour les atteindre.

PROGRAMMATION ORIENTEE AGENT
« AGENT-ORIENTED PROGRAMMING » - C’est une approche « orientée agent », de la même manière qu’il existe des approches « orientés objets », qui propose une programmation des agents en terme des buts, des choix, des compétences, des croyances etc. et que les types de message que les agents s’échangent se réfèrent à des mécanismes de communication de haut niveau en définissant des messages d’information, de requête, d’offre, de promesse, de refus, d’acceptation, etc.

PROTOCOLE DE COMMUNICATION
C’est un ensemble de primitives connues par chaque entité pour pouvoir échanger des informations et coopérer pour la résolution d’un problème :
Etablissement d’une connexion entre deux entités
Identification du nœud destinataire dans un réseau de communication
Envoi/Réception de données
Définition d’un type de communication : synchrone ou asynchrone


RATIONNALITE
Un agent est rationnel s'il suit le principe de rationalité :

« Si un agent sait qu'une de ses actions lui permet d'atteindre un de ses buts, il la sélectionne. »

Ainsi, l'agent rationnel dispose de critères d'évaluation de ses actions. Il agira dans le but de réaliser ses buts dans la mesure où ses croyances le permettent.

Remarque : La rationalité d'une architecture est une mesure de cohérence (consistance) ; elle consiste à savoir si les actions qu'un agent exécute sont toujours compatibles avec sa connaissance et ses buts. Généralement, si un agent exécute deux actions différentes avec la même connaissance dans deux situations (environnementales) identiques, il n’est pas rationnel.

REACTIVITE
Un agent est réactif s’il est capable de maintenir une interaction en cours avec l’environnement et de répondre aux modifications qui s’y déroulent de façon opportune. Il est à noter que ce terme est largement utilisé pour définir un système qui n’inclut aucune représentation symbolique ni raisonnement : un tel agent (réactif) ne réfléchit pas sur les effets à long terme de ses action ni ne considère la coordination d’activité avec d’autres agents. Dès lors, un AGENT REACTIF répondra toujours de façon opportune aux stimuli extérieurs.

REFLEXIF
Qui se comporte selon un mode de stimulus action. Cf. AGENT REACTIF

ROBUSTESSE
Complémentaire à l'adaptation, c'est la capacité que l'agent n'évolue pas trop vite, faute de quoi il serait influencé par de faux signaux. L'agent doit donc avoir un juste équilibre entre adaptation et robustesse.

SCRIPT
Un script est un ensemble de méthodes décrivant la manière dont une entité doit répondre aux événements venant de l'extérieur. Dans le modèle acteur, l'acteur filtre les messages reçus et active les méthodes appropriées.

SYSTEME MULTI AGENTS

Définition de Jacques Ferber dans « Les Systèmes multi-agents. Vers une intelligence collective », Inter-Editions, 1995 :
«  Système composé de:
Un environnement E (espace disposant généralement d'une métrique).
Un ensemble O d'objets situés (il est possible, à un moment donné, de leur associer une position dans E). Ils sont passifs et peuvent être perçus, créés, détruits et modifiés par les agents.
Un ensemble A d'agents, qui sont des objets particuliers représentant les entités actives du système.
Un ensemble R de relations unissant des objets (et donc des agents) entre eux.
Un ensemble Op d'opérations permettant aux agents de A de percevoir, produire, consommer, transformer et manipuler les objets de O.
Des opérateurs chargés de représenter l'application de ces opérations et la réaction du monde à cette tentative de modification (que l'on appellera les lois de l'univers). »

On peut classer les SMA selon différents critères : taille des agents, nombre d'agents en interaction, mécanismes d'interaction et types de communications, capacités de comportement de chaque agent, organisation et contrôle, représentation du problème et des autres agents, capacités d'apprentissage des agents, etc.

SOCIABILITE
Aptitude des agents à interagir avec d'autres agents (humain ou non) via un certain langage de communication agent.

TELEONOMIE
Les agents ont des buts qu’ils cherchent à satisfaire par une coopération avec d’autres agents, en utilisant des plans qui doivent être parfois remis en question et en estimant la connaissance et les plans des autres agents.
VERSATILITE
Un agent est dit versatile s'il a beaucoup de buts ou s'il s'engage dans une variété de tâches.

VERACITE
Un agent ne communiquera pas sciemment de fausses informations.




ANNEXES



Abréviations utilisées

ACL Agent Communication Language
AID Agent Identifier
AMS Agent Management Service. (cf. FIPA )
AP Agent Platform
API Application Programming Interface
DF Directory Facilitator. (cf. FIPA )
DSI Direction des systèmes d’information
FIPA Foundation for Intelligent Physical Agents
GUI Graphical User Interface
GUID Globally Unique Identifier
HAP Home Agent Platform
HTML Hyper Text Markup Language
HTTP Hypertext Transmission Protocol
IA Intelligence Artificielle
IAD Intelligence Artificielle Distribuée
IDL Interface Definition Language
IIOP Internet Inter-ORB Protocol
IOR Interoperable Object Reference
JADE Java Agent DEvelopment Framework
JDK Java Development Kit
LGPL Lesser GNU Public License
MTP Message Transport Protocol.
ORB Object Request Broker
POA Portable Object Adapter
POOC Programmation Orientée Objets Concurrents
RMA Remote Monitoring Agent.
RMI Remote Method Invocation
SC Source de Connaissance (blackboard)
SMA Systèmes Multi-Agents
TCP Transmission Control Protocol
URI Uniform Resource Identifier
URL Uniform Resource Locator
XML Extensible Markup Language
Annexe I : Mail de J. FERBER

De : Jacques FERBER [mailto:ferber@lirmm.fr] Envoyé : vendredi 25 janvier 2002 09:46 À : Patricia Guillierme Objet : Re: Etude plate-forme SMA
Bonjour, Pourquoi ne pas vous faire la main sur une plate-forme existante plutôt que de refaire une n-ieme plate-forme qui ira nécessairement (c'est très long de faire une "vraie" plate-forme, on en sait quelque chose) dans un placard à la fin de votre stage. Si vous êtes intéressée par les plate-formes, allez voir à  HYPERLINK "http://www.multiagent.com/" http://www.multiagent.com qui recense la plupart des plate-formes existantes. Dans le domaine général, vous pouvez bien entendu essayer notre plate-forme, Madkit, qui se trouve à  HYPERLINK "http://www.madkit.com/" www.madkit.com. Mais cette version va bientôt être remplacée par une version 3.0 qui va vraiment décoiffer (mais sans reprendre la base des concepts). Dans le domaine purement de la simulation, il faut essayer Swarm ou Cormas. Sinon, il y a les plate-formes FIPA, Jade et FIPA-OS. Toutes ces plate-formes sont gratuites (et la plupart en Java). Bon courage, mais surtout, ne faites pas la betise d'essayer d'en refaire une, ou alors prévoyez deux ans de travail minimum pour qu'elle puisse entrer en compétition avec les plate-formes existantes!! Adressez bien le bonjour à votre professeur que je connais bien et que j'estime beaucoup. Jacques Ferber
==============================================
Jacques Ferber                       LIRMM
Professeur                              Universite Montpellier II
                                              161, rue ADA
Tel: (33) 4 67 41 86 07           34392 Montpellier Cedex 5
Fax: (33) 4 67 41 85 00          FRANCE
Email: ferber@lirmm.fr    HYPERLINK "http://www.lirmm.fr/~ferber" http://www.lirmm.fr/~ferber
==============================================
Annexe II : Evolution des systèmes de blackboard

Annexe III : Comparatif entre
agents cognitifs et agents réactifs


Systèmes d'agents cognitifsSystèmes d'agents réactifsReprésentation explicite
soi :
• connaissances (beliefs)
• buts (intentions)
• tâches
• plans
• engagements
environnement
autres agents :
• compétences
• intentions
 Pas de représentation expliciteArchitecture complexe, souvent modèle logique (ex : BDI, Agent0)Architecture simple
stimulus / actionOrganisation explicite (social)
• allocation et dépendances tâches
• partage des ressources
• protocoles de coordination/négociation
Organisation implicite/induite (biologique)
Auto organisation
Ex. Colonies de fourmisCommunication explicite, point à point, élaborée (ex : KQML)Communication via l’environnement
Ex. perceptions/actions sur l’environnement, phéromones de fourmisPeut tenir compte de son passéPas de mémoire de son historiquePetit/moyen nombre d'agents (10/20)(Très) Grand nombre d'agents (> 100)
redondance Annexe IV : KQML
Basé sur la théorie des actes de langage, KQML est un protocole et un langage de communication orienté message de haut niveau, pour l'échange d'information indépendamment de la syntaxe du contenu et de l'ontologie appliquée.
KQML est indépendant :
du mécanisme de transport (TCP/IP, SMTP, IIOP, ou autre),
indépendant du contenu du message (KIF, SQL, STEP, Prolog ou autre)
et indépendant de l'ontologie présumée du contenu.
1. Organisation
Un message KQML se compose de trois couches :
La couche contenu porte le contenu du message exprimé dans le propre langage de représentation du programme (ASCII, notation binaire, etc.)
La couche communication code un ensemble de particularités du message caractéristiques des paramètres de communication de plus bas niveau (ex. identité de l'expéditeur et du destinataire) ainsi qu'un unique identifiant associé à la communication.
La couche message qui code le message à transmettre est le noyau de KQML. Elle permet de déterminer les sortes d'interactions qu'un autre peut avoir avec un agent parlant KQML :
identifie le protocole réseau avec lequel délivrer le message et fournit un performatif (ex. affirmer, questionner, commander, etc.) que l'expéditeur attachera au contenu
indique le langage du corps du message
spécifie l'ontologie associée
ainsi que des types de description du corps du message
Dès lors, les implémentations KQML analyse, dirige et délivre proprement les messages bien que le contenu du corps du message soit inaccessible.
2. Syntaxe et performatifs
La syntaxe d'un message KQML est basée sur les s-expressions utilisées en LISP, le premier élément de la liste étant le performatif suivi de ses arguments (paires mot-clé/valeur).
(ask-one
: sender joe
: content (PRICE IBM ?price)
: receiver stock-server
: reply-with ibm-stock
: language LPROLOG
: ontology NYSE-TICKS)




(tell
: sender stock-server
: content (PRICE IBM 14)
: receiver joe
: in-reply-to ibm-stock
: language LPROLOG
: ontology NYSE-TICKS)
Remarque : bien que KQML dispose d'un jeu de performatifs réservés, il n'est ni un ensemble minimal nécessaire ni même fixe à tout agent: c'est un ensemble extensible !

Liste des performatifs définis dans KQML :
achieveA veut que Y accomplisse une actionadvertiseA indique qu'il veut faire Pask-aboutA veut toutes les expressions sur P de la BC de Bask-allA veut toutes les réponses de B à une questionask-oneA veut une réponse de B à une questionbreakA veut supprimer une communicationbroadcastA veut B envoie une performative à toutes ses accointancesbroker-allA veut que B récupère toutes les réponses à un performatifbroker-oneA veut de l'aide pour récupérer la réponses à un performatifdenyA indique à B que le performatif ne s'applique plus à BdeleteA veut que B supprime une expression de sa BCdelete-allA veut que B supprime toutes les P correspondantes de sa BCdiscardA ne veut pas les réponses suivantes de BeosFin d'une suite de réponse à une requête préalableerrorA considère que le message de B est mal forméevaluateA veut que B simplifie l'expression associéeforwardA veut que B délègue un performatifgeneratorIndique à standby pour un stream-allinsertAveut que R insère une expression dans sa BCmonitorA veut que R mette à jour ses réponses à un stream-allnextA veut la réponse suivante à une requête préalablepipeA veut que R redirige tous les performatifs suivant à un agentreadyA est prêt à répondre à un performatif préalable de Brecommend-allA veut tous les agents qui répondent à un performatif donnérecommend-oneA veut un agent qui réponde à un performatif donnérecruit-allA veut que tous les agents capables répondent à un performatifrecruit-oneA veut qu'un agent capable réponde à un performatifregisterA indique à B qu'il peut accomplir une actionreplyA répond à une demande attenduerestA veut toutes les réponses suivantessorryA ne peut fournir une réponse plus informativestandbyA veut que B soit prêt à répondre à un performatifstream-aboutVersion à réponses multiples de ask-aboutstream-allVersion à réponses multiples de ask-allsubcribeA veut que B mette à jour ses réponses à un performatiftellIndique qu'une expression fait partie de la BC de Atransport-addressA associe un nom symbolique à une adresse de transportunregister Un deny de register untell Indique qu'une expression ne fait pas partie de la BC de A

Critique du KQML

Après avoir donné les performatifs définis dans KQML, Ferber [2] soulèves trois problèmes : ambiguïté et imprécision des performatifs, inutilité et incohérence de certains et enfin, manque des certains. Dans le même sens, il cite :
 HYPERLINK "http://citeseer.nj.nec.com/cohen95communicative.html" http://citeseer.nj.nec.com/cohen95communicative.html
Annexe V : Le free flight

De nouvelles techniques pour le contrôle aérien
Nicolas Durand   Jean-Marc Alliot
1  Introduction
Le trafic aérien a connu une progression très importante pendant les dernières décennies et toutes les prévisions tendent à montrer que cette croissance ne devrait guère se ralentir dans les prochaines années. De 1986 à 1996, le trafic a connu un accroissement de 66% et on prévoit pour 2006 un accroissement par rapport à 1996 de l'ordre de 35% à 70% [ HYPERLINK "http://www.recherche.enac.fr/opti/papers/articles/JAUNE/main.html" \l "ATMRD#ATMRD" TM+97]. Dans ces conditions, la congestion du ciel est en passe de devenir le facteur limitant de la croissance du trafic aérien, du moins en Europe, et la pression des compagnies aériennes se fait de plus en plus forte pour que la gestion du trafic soit à la fois plus souple et plus efficace. Parallèlement, les avions s'équipent de moyens sophistiqués (FMS HYPERLINK "http://www.recherche.enac.fr/opti/papers/articles/JAUNE/main.html" \l "note1#note1" 1 , GPS HYPERLINK "http://www.recherche.enac.fr/opti/papers/articles/JAUNE/main.html" \l "note2#note2" 2 , Data Link) qui devraient permettre, à plus ou moins long terme, de changer radicalement les techniques de contrôle des aéronefs. C'est dans ce cadre qu'est aujourd'hui posé par les compagnies, suivant en cela le RTCA [ HYPERLINK "http://www.recherche.enac.fr/opti/papers/articles/JAUNE/main.html" \l "RTCA#RTCA" cotRbod95], le concept du Free Flight (vol sans contrainte), un concept qui tendrait, sous certaines conditions, à affranchir les avions du contrôle aérien tel qu'il est pratiqué aujourd'hui et permettrait ainsi aux aéronefs de suivre le cheminement de leur choix dans certaines zones de l'espace aérien. Comme nous allons cependant le voir, le chemin à parcourir est encore long avant la mise en place d'un tel concept.
2  Principes généraux
Le but premier du contrôle du trafic aérien est d'assurer la sécurité des aéronefs. Le but second, d'assurer un écoulement aussi optimal que possible des flux de trafic, en particulier en terme de retards. Nous allons tout d'abord poser quelques définitions indispensables pour la compréhension du reste de notre exposé :

Route aérienne :
Le cheminement d'un avion dans l'espace est une série de segments de droite, reliant des points de report appelés balises. Historiquement, ces balises étaient bien souvent des points équipés de moyens de radionavigation.
Plan de vol :
Il contient tous les éléments indicatifs décrivant le vol prévu pour un avion (heure de départ, niveau de vol, route prévue).
Contrôle en route :
Il s'agit du contrôle à l'extérieur des zones entourant les aéroports (dans ces dernières, on parle de contrôle d'approche).
Secteurs de contrôle :
L’espace aérien est divisé en secteurs de contrôle. Chaque secteur est confié à un, ou plus souvent deux, contrôleurs, qui ont la charge d'assurer la séparation des aéronefs dans cette portion de l'espace. Le transfert d'un avion d'un secteur à un autre secteur fait l'objet d'une coordination entre les contrôleurs en charge de chacun des deux secteurs.
Séparations :
On définit une distance horizontale exprimée en milles nautiques (NM), la séparation horizontale, et une distance verticale exprimée en pieds : la séparation verticale. On dit que deux avions sont séparés quand la distance qui sépare leurs projections sur un plan horizontal est supérieure à la séparation horizontale OU quand la différence de leurs altitudes est supérieure à la séparation verticale.
Conflit élémentaire :
Deux avions sont dits en conflit lorsqu'ils ne sont plus séparés. Si l'on se fixe une durée T, deux avions seront dits en conflit potentiel pendant T, si durant le temps T, ils ont une probabilité non nulle d'être en conflit.
Cluster :
Un cluster d'avions est une fermeture transitive d'avions en conflits potentiels. Si un avion A est en conflit avec B à l'instant t ? @ Ä Å Æ s t u  ÌxÑ!sÄúúòòòòòòòòòòòêêâÝÝÝÖÖÏÏ
ÆÀf#

Æàf#
gdïP÷$a$gdïP÷$a$gdá%T$a$gdŒ1¹gdÌ&ò¯
¸
ÿ
 
}~€›œž«¬­ÆÇÈÉÊüøôéÚéÚñ¡±ƒÃuj[jJ[?[h0z]mHnHu j{hïP÷UmHnHujhïP÷UmHnHuhïP÷mHnHuh]ÕhïP÷0JmHnHu:jhïP÷hïP÷>*B*CJ(UaJ(mHnHphÿuhïP÷hïP÷CJ(aJ(mHnHu#hïP÷hïP÷0JCJ(aJ(mHnHu,jhïP÷hïP÷0JCJ(UaJ(mHnHujhïP÷hïP÷CJ(UaJ(hïP÷hïP÷CJ(aJ(h¿@hm"/hŒ1¹ÊËÌÍÎéêëìøùú6789WXYrstíàíÒÉÒ¯íÒ¤•¤„•y•íàíÒÉÒ_íÒ¤•¤N• jghïP÷UmHnHu2jìh]ÕhïP÷>*B*UmHnHphÿuh0z]mHnHu jqhïP÷UmHnHujhïP÷UmHnHuhïP÷mHnHu2jöh]ÕhïP÷>*B*UmHnHphÿuhïP÷mHnHuh]ÕhïP÷0JmHnHuhïP÷^JaJmHnHu$jh]ÕhïP÷0JUmHnHutuvwxyz•–—˜š›°±²ËÌÍÎÏÐÑÒÓîïðñóôõæÓÆÓ¸¯¸•Ó¸‡¸|æ|kæõæӇӸ¯¸QÓ¸‡¸2jØh]ÕhïP÷>*B*UmHnHphÿu j]hïP÷UmHnHuhïP÷mHnHuhïP÷5CJ\mHnHu2jâh]ÕhïP÷>*B*UmHnHphÿuhïP÷mHnHuh]ÕhïP÷0JmHnHuhïP÷^JaJmHnHu$jh]ÕhïP÷0JUmHnHujhïP÷UmHnHuh0z]mHnHu !"#>?@AEFRSTmnopqrstu‘õæõÕæÊæ·©·›’›x·›m›õæõ\æÊæ·m·›’› jIhïP÷UmHnHuhïP÷CJmHnHu2jÎh]ÕhïP÷>*B*UmHnHphÿuhïP÷mHnHuh]ÕhïP÷0JmHnHuhïP÷5CJ\mHnHu$jh]ÕhïP÷0JUmHnHuh0z]mHnHu jShïP÷UmHnHujhïP÷UmHnHuhïP÷mHnHu‘’“—˜¢£¤½¾¿ÁÂÃÄÅÆáâãäêëòóô
æÓźů ¯ „ ÓºÓÅ{ÅaÓźů ¯P „ Ó j5hïP÷UmHnHu2jºh]ÕhïP÷>*B*UmHnHphÿuhïP÷mHnHuh0z]mHnHu j?hïP÷UmHnHujhïP÷UmHnHuhïP÷mHnHuhïP÷CJmHnHuh]ÕhïP÷0JmHnHu$jh]ÕhïP÷0JUmHnHu2jÄh]ÕhïP÷>*B*UmHnHphÿuÄh¸`²þT¥ùY¤ûL¬]µ}âF¢
–åøøøñøøìåññññåññøøøñøøøøøøå
Æàf#
gdïP÷
ÆÀf#

Æ°f#
1234:;FGHabcefghij…†‡ˆŽ–—˜±ôáÓÊÓ°áÓôÓ¥–¥…–z–áôáÓÊÓ`áÓôÓ¥–¥2j¦h]ÕhïP÷>*B*UmHnHphÿuh0z]mHnHu j+hïP÷UmHnHujhïP÷UmHnHuhïP÷mHnHu2j°h]ÕhïP÷>*B*UmHnHphÿuhïP÷mHnHuh]ÕhïP÷0JmHnHu$jh]ÕhïP÷0JUmHnHuhïP÷CJmHnHu±²³µ¶·¸¹ºÕÖ×ØÜÝåæç $%&'-ïàÕà·© ©†Â©·©{à{jàÕà·© ©P©2j’
h]ÕhïP÷>*B*UmHnHphÿu j
hïP÷UmHnHuhïP÷mHnHu2jœ h]ÕhïP÷>*B*UmHnHphÿuhïP÷mHnHuh]ÕhïP÷0JmHnHuhïP÷CJmHnHu$jh]ÕhïP÷0JUmHnHuh0z]mHnHujhïP÷UmHnHu j! hïP÷UmHnHu-.>?@YZ[]^_`ab}~€†‡‘’«¬­¯°±²³´ÏÐôæÛÌۻ̰̝ôæ”æzæôæÛÌÛḭ̝ôæ”æ j hïP÷UmHnHu2jˆ h]ÕhïP÷>*B*UmHnHphÿuhïP÷mHnHu$jh]ÕhïP÷0JUmHnHuh0z]mHnHu j
hïP÷UmHnHujhïP÷UmHnHuhïP÷mHnHuh]ÕhïP÷0JmHnHuhïP÷CJmHnHu!ÐÑÒÜÝÞ÷øùûüýþÿ !234MæÓź«ºš««Ó‚ÓÅyÅ_ÓÅQź«ºhïP÷5CJ\mHnHu2jt
h]ÕhïP÷>*B*UmHnHphÿuhïP÷mHnHuhïP÷^JaJmHnHuh0z]mHnHu jù hïP÷UmHnHujhïP÷UmHnHuhïP÷mHnHuh]ÕhïP÷0JmHnHu$jh]ÕhïP÷0JUmHnHu2j~ h]ÕhïP÷>*B*UmHnHphÿuMNOQRSTUVqrstxyƒ„…žŸ ¢£¤¥¦§ÂÃïàÕà´¦¦ƒÂ¦x¦màm\àÕàÂx¦¦ jåhïP÷UmHnHuhïP÷mHnHuhïP÷CJmHnHu2jjh]ÕhïP÷>*B*UmHnHphÿuhïP÷mHnHuh]ÕhïP÷0JmHnHuhïP÷5CJ\mHnHu$jh]ÕhïP÷0JUmHnHuh0z]mHnHujhïP÷UmHnHu jï
hïP÷UmHnHuÃÄÅÉÊ×ØÙòóôö÷øùúû789RSTVWXæÓźů ¯ „ ÓºÓÅ{ÅaÓźů ¯P „ Ó jÑhïP÷UmHnHu2jVh]ÕhïP÷>*B*UmHnHphÿuhïP÷mHnHuh0z]mHnHu jÛhïP÷UmHnHujhïP÷UmHnHuhïP÷mHnHuhïP÷CJmHnHuh]ÕhïP÷0JmHnHu$jh]ÕhïP÷0JUmHnHu2j`h]ÕhïP÷>*B*UmHnHphÿuXYZ[vwxy}~‚ƒ„žŸ¡¢£¤¥¦ÁÂÃÄÆÇÙÚÛôôáÓÊÓ°áÓôÓ¥–¥…–z–áôáÓÊÓ`áÓRÓ¥–¥hïP÷5CJ\mHnHu2jBh]ÕhïP÷>*B*UmHnHphÿuh0z]mHnHu jÇhïP÷UmHnHujhïP÷UmHnHuhïP÷mHnHu2jLh]ÕhïP÷>*B*UmHnHphÿuhïP÷mHnHuh]ÕhïP÷0JmHnHu$jh]ÕhïP÷0JUmHnHuhïP÷CJmHnHuôõöøùúûüý *+,EFGIJKLMNijïàÕà´¦¦ƒÂ¦x¦màm\àÕàÂx¦¦ j³hïP÷UmHnHuhïP÷mHnHuhïP÷CJmHnHu2j8h]ÕhïP÷>*B*UmHnHphÿuhïP÷mHnHuh]ÕhïP÷0JmHnHuhïP÷5CJ\mHnHu$jh]ÕhïP÷0JUmHnHuh0z]mHnHujhïP÷UmHnHu j½hïP÷UmHnHujklpqŠ‹Œ¥¦§©ª«¬­®ÉÊËÌÒÓâãäýþÿæÓźů ¯ „ ÓºÓÅ{ÅaÓźů ¯P „ Ó jŸhïP÷UmHnHu2j$h]ÕhïP÷>*B*UmHnHphÿuhïP÷mHnHuh0z]mHnHu j©hïP÷UmHnHujhïP÷UmHnHuhïP÷mHnHuhïP÷CJmHnHuh]ÕhïP÷0JmHnHu$jh]ÕhïP÷0JUmHnHu2j.h]ÕhïP÷>*B*UmHnHphÿu!"#$*+;*B*UmHnHphÿuh0z]mHnHu j•hïP÷UmHnHujhïP÷UmHnHuhïP÷mHnHu2jh]ÕhïP÷>*B*UmHnHphÿuhïP÷mHnHuh]ÕhïP÷0JmHnHu$jh]ÕhïP÷0JUmHnHuhïP÷CJmHnHu®¯°²³´µ¶·ÒÓÔÕÙÚðñò  
/0128ïàÕà·© ©†Â©·©{à{jàÕà·© ©P©2jüh]ÕhïP÷>*B*UmHnHphÿu jhïP÷UmHnHuhïP÷mHnHu2jh]ÕhïP÷>*B*UmHnHphÿuhïP÷mHnHuh]ÕhïP÷0JmHnHuhïP÷CJmHnHu$jh]ÕhïP÷0JUmHnHuh0z]mHnHujhïP÷UmHnHu j‹hïP÷UmHnHu89[\]vwxz{|}~š›œ£¤ÀÁÂÛÜÝßàáâãäÿôæÛÌۻ̰̝ôæ”æzæôæÛÌÛḭ̝ôæ”æ jmhïP÷UmHnHu2jòh]ÕhïP÷>*B*UmHnHphÿuhïP÷mHnHu$jh]ÕhïP÷0JUmHnHuh0z]mHnHu jwhïP÷UmHnHujhïP÷UmHnHuhïP÷mHnHuh]ÕhïP÷0JmHnHuhïP÷CJmHnHu! $%&?@ACDEFGHcdeflm€‚›œŸ ¡æÓźů ¯ „ ÓºÓÅ{ÅaÓźů ¯P „ Ó jYhïP÷UmHnHu2jÞh]ÕhïP÷>*B*UmHnHphÿuhïP÷mHnHuh0z]mHnHu jchïP÷UmHnHujhïP÷UmHnHuhïP÷mHnHuhïP÷CJmHnHuh]ÕhïP÷0JmHnHu$jh]ÕhïP÷0JUmHnHu2jèh]ÕhïP÷>*B*UmHnHphÿu¡¢£¤¿ÀÁÂÈÉëìí
  
*+,-34tuvôáÓÊÓ°áÓôÓ¥–¥…–z–áôáÓÊÓ`áÓôÓ¥–¥2jÊh]ÕhïP÷>*B*UmHnHphÿuh0z]mHnHu jOhïP÷UmHnHujhïP÷UmHnHuhïP÷mHnHu2jÔh]ÕhïP÷>*B*UmHnHphÿuhïP÷mHnHuh]ÕhïP÷0JmHnHu$jh]ÕhïP÷0JUmHnHuhïP÷CJmHnHu‘“”•–—˜³´µ¶¸¹ÃÄÅÞßàâãäåæçïàÕà·© ©†Â©x©màm\àÕàÂx© © j;hïP÷UmHnHuhïP÷mHnHuhïP÷5CJ\mHnHu2jÀh]ÕhïP÷>*B*UmHnHphÿuhïP÷mHnHuh]ÕhïP÷0JmHnHuhïP÷CJmHnHu$jh]ÕhïP÷0JUmHnHuh0z]mHnHujhïP÷UmHnHu jEhïP÷UmHnHu 9:;=>?@AB]^_`bcmnoˆæÓź«ºš««Ó‚ÓÅyÅ_ÓÅQź«ºhïP÷5CJ\mHnHu2j¬ h]ÕhïP÷>*B*UmHnHphÿuhïP÷mHnHuhïP÷^JaJmHnHuh0z]mHnHu j1 hïP÷UmHnHujhïP÷UmHnHuhïP÷mHnHuh]ÕhïP÷0JmHnHu$jh]ÕhïP÷0JUmHnHu2j¶h]ÕhïP÷>*B*UmHnHphÿuå@îLªüN²fµqÁvÇ p » !S!ª!ÿ!Q"¢"#úóóóóóóìììóúóììììóììììóìììì
ÆÀf#

Æàf#
gdïP÷ˆ‰ŠŒŽ‘¬­®¯±²ÌÍÎçèéëìíîïð  
ïàÕà´¦¦ƒÂ¦´¦xàxgàÕà´¦¦MÂ2j˜"h]ÕhïP÷>*B*UmHnHphÿu j"hïP÷UmHnHuhïP÷mHnHu2j¢!h]ÕhïP÷>*B*UmHnHphÿuhïP÷mHnHuh]ÕhïP÷0JmHnHuhïP÷5CJ\mHnHu$jh]ÕhïP÷0JUmHnHuh0z]mHnHujhïP÷UmHnHu j'!hïP÷UmHnHu*+,EFGIJKLMNijklnoˆ‰Š£¤¥§¨©ª«¬ÇÈñãñØÉظɭɚãšñ‘ñwšñãñØÉØfɭɚãšñ‘ñ j $hïP÷UmHnHu2jŽ#h]ÕhïP÷>*B*UmHnHphÿuhïP÷mHnHu$jh]ÕhïP÷0JUmHnHuh0z]mHnHu j#hïP÷UmHnHujhïP÷UmHnHuhïP÷mHnHuhïP÷5CJ\mHnHuh]ÕhïP÷0JmHnHu"ÈÉÊÌÍÚÛÜõö÷ùúûüýþ,-.GHIKLæÓŷŬ¬ŒÓ·ÓÅxÅ^ÓŷŬ¬M jõ%hïP÷UmHnHu2jz%h]ÕhïP÷>*B*UmHnHphÿuhïP÷mHnHuh0z]mHnHu jÿ$hïP÷UmHnHujhïP÷UmHnHuhïP÷mHnHuhïP÷5CJ\mHnHuh]ÕhïP÷0JmHnHu$jh]ÕhïP÷0JUmHnHu2j„$h]ÕhïP÷>*B*UmHnHphÿuLMNOPklmnrs‘’«¬­¯°±²³´ÏÐÑÒÖ×ìíîíßíÑÈÑ®íѣј‰˜x‰m‰í£íÑÈÑSíѣј‰˜2jf'h]ÕhïP÷>*B*UmHnHphÿuh0z]mHnHu jë&hïP÷UmHnHujhïP÷UmHnHuhïP÷mHnHuhïP÷CJmHnHu2jp&h]ÕhïP÷>*B*UmHnHphÿuhïP÷mHnHuh]ÕhïP÷0JmHnHuhïP÷5CJ\mHnHu$jh]ÕhïP÷0JUmHnHu    
+,-.23DEF_`acdefghƒ„…†ˆïàÕà·© ©†Â©·©{à{jàÕà·© ©P©2jR)h]ÕhïP÷>*B*UmHnHphÿu j×(hïP÷UmHnHuhïP÷mHnHu2j\(h]ÕhïP÷>*B*UmHnHphÿuhïP÷mHnHuh]ÕhïP÷0JmHnHuhïP÷CJmHnHu$jh]ÕhïP÷0JUmHnHuh0z]mHnHujhïP÷UmHnHu já'hïP÷UmHnHuˆ‰“”•®¯°²³´µ¶·ÒÓÔÕýþÿ !*B*UmHnHphÿuhïP÷mHnHu$jh]ÕhïP÷0JUmHnHuh0z]mHnHu jÍ)hïP÷UmHnHujhïP÷UmHnHuhïP÷mHnHuh]ÕhïP÷0JmHnHuhïP÷5CJ\mHnHu=>?ABOPQjklnopqrsŽ‘•–Ÿ ¡ºæÓŷŬ¬ŒÓ·ÓÅxÅ^ÓÅSŬ¬hïP÷CJmHnHu2j4,h]ÕhïP÷>*B*UmHnHphÿuhïP÷mHnHuh0z]mHnHu j¹+hïP÷UmHnHujhïP÷UmHnHuhïP÷mHnHuhïP÷5CJ\mHnHuh]ÕhïP÷0JmHnHu$jh]ÕhïP÷0JUmHnHu2j>+h]ÕhïP÷>*B*UmHnHphÿuº»¼¾¿ÀÁÂÃÞßàáåæóôõ23459ïàÕà·© ©†Â©·©{à{jàÕà·© ©P©2j .h]ÕhïP÷>*B*UmHnHphÿu j¥-hïP÷UmHnHuhïP÷mHnHu2j*-h]ÕhïP÷>*B*UmHnHphÿuhïP÷mHnHuh]ÕhïP÷0JmHnHuhïP÷CJmHnHu$jh]ÕhïP÷0JUmHnHuh0z]mHnHujhïP÷UmHnHu j¯,hïP÷UmHnHu9:TUVopqstuvwx“”•–š›¥¦§ÀÁÂÄÅÆÇÈÉäåôæÛÌۻ̰̝ôæ”æzæôæÛÌÛḭ̝ôæ”æ j‘/hïP÷UmHnHu2j/h]ÕhïP÷>*B*UmHnHphÿuhïP÷mHnHu$jh]ÕhïP÷0JUmHnHuh0z]mHnHu j›.hïP÷UmHnHujhïP÷UmHnHuhïP÷mHnHuh]ÕhïP÷0JmHnHuhïP÷CJmHnHu!åæçéêûüý         : ; < = A B N O P i æÓŷŬ¬ŒÓ·ÓÅxÅ^ÓNCN¬¬hïP÷CJmHnHuh]ÕhïP÷0JmHnHsH u2j1h]ÕhïP÷>*B*UmHnHphÿuhïP÷mHnHuh0z]mHnHu j‡0hïP÷UmHnHujhïP÷UmHnHuhïP÷mHnHuhïP÷5CJ\mHnHuh]ÕhïP÷0JmHnHu$jh]ÕhïP÷0JUmHnHu2j 0h]ÕhïP÷>*B*UmHnHphÿui j k m n o p q r  Ž   ” • ™ š › ´ µ ¶ ¸ ¹ º » ¼ ½ Ø Ù ïàÕà·© ©†Âv·vkàkZàÕà·© © js2hïP÷UmHnHuhïP÷mHnHuh]ÕhïP÷0JmHnHsH u2jø1h]ÕhïP÷>*B*UmHnHphÿuhïP÷mHnHuh]ÕhïP÷0JmHnHuhïP÷CJmHnHu$jh]ÕhïP÷0JUmHnHuh0z]mHnHujhïP÷UmHnHu j}1hïP÷UmHnHuÙ Ú Û ß à æ ç è !!!!!!! !
!%!&!'!(!,!-!1!2!3!æÓø힭ž‚žÓ¸ÓtktQÓA¸A­žh]ÕhïP÷0JmHnHsHu2jä3h]ÕhïP÷>*B*UmHnHphÿuhïP÷mHnHuh]ÕhïP÷0JmHnHuh0z]mHnHu ji3hïP÷UmHnHujhïP÷UmHnHuhïP÷mHnHuhïP÷CJmHnHuh]ÕhïP÷0JmHnHsH u$jh]ÕhïP÷0JUmHnHu2jî2h]ÕhïP÷>*B*UmHnHphÿu3!L!M!N!P!Q!R!S!T!U!p!q!r!s!u!v!ˆ!‰!Š!£!¤!¥!§!¨!©!ª!«!¬!Ç!È!õäÕÊÕ·¬·ž•ž{·žmžõÕõ\ÕÊÕ·m·ž•ž jU5hïP÷UmHnHuhïP÷5CJ\mHnHu2jÚ4h]ÕhïP÷>*B*UmHnHphÿuhïP÷mHnHuh]ÕhïP÷0JmHnHuhïP÷CJmHnHu$jh]ÕhïP÷0JUmHnHuh0z]mHnHujhïP÷UmHnHu j_4hïP÷UmHnHuhïP÷mHnHuÈ!É!Ê!Î!Ï!Ý!Þ!ß!ø!ù!ú!ü!ý!þ!ÿ!""""""#"$"/"0"1"J"K"L"N"O"P"æÓźů ¯ „ ÓºÓÅ{ÅaÓźů ¯P „ Ó jA7hïP÷UmHnHu2jÆ6h]ÕhïP÷>*B*UmHnHphÿuhïP÷mHnHuh0z]mHnHu jK6hïP÷UmHnHujhïP÷UmHnHuhïP÷mHnHuhïP÷CJmHnHuh]ÕhïP÷0JmHnHu$jh]ÕhïP÷0JUmHnHu2jÐ5h]ÕhïP÷>*B*UmHnHphÿuP"Q"R"S"n"o"p"q"u"v"€""‚"›"œ""Ÿ" "¡"¢"£"¤"¿"À"Á"Â"Æ"Ç"ì"í"î"#ôáÓÊÓ°áÓôÓ¥–¥…–z–áôáÓÊÓ`áÓôÓ¥–¥2j²8h]ÕhïP÷>*B*UmHnHphÿuh0z]mHnHu j78hïP÷UmHnHujhïP÷UmHnHuhïP÷mHnHu2j¼7h]ÕhïP÷>*B*UmHnHphÿuhïP÷mHnHuh]ÕhïP÷0JmHnHu$jh]ÕhïP÷0JUmHnHuhïP÷CJmHnHu## # # #
####+#,#-#.#4#5#B#C#D#]#^#_#a#b#c#d#e#f##‚#ƒ#„#Š#ïàÕà·© ©†Â©·©{à{jàÕà·© ©P©2jž:h]ÕhïP÷>*B*UmHnHphÿu j#:hïP÷UmHnHuhïP÷mHnHu2j¨9h]ÕhïP÷>*B*UmHnHphÿuhïP÷mHnHuh]ÕhïP÷0JmHnHuhïP÷CJmHnHu$jh]ÕhïP÷0JUmHnHuh0z]mHnHujhïP÷UmHnHu j-9hïP÷UmHnHu#d#Å#*$|$È$%b%¬%&d&×&7'Š'æ'?(A(N(O(P(Q(**p+øøøøóóóóíííííííåß××ÒÆÆÆ $7$8$H$a$gdjS²gd3+:$a$gdVõ0@&gdTX$a$gdá%T
Æf#
gdïP÷
Æ f#
Š#‹#£#¤#¥#¾#¿#À#Â#Ã#Ä#Å#Æ#Ç#â#ã#ä#å#ë#ì#$ $
$#$$$%$'$($)$*$+$,$G$H$ôæÛÌۻ̰̝ôæ”æzæôæÛÌÛḭ̝ôæ”æ j*B*UmHnHphÿuhïP÷mHnHu$jh]ÕhïP÷0JUmHnHuh0z]mHnHu j;hïP÷UmHnHujhïP÷UmHnHuhïP÷mHnHuh]ÕhïP÷0JmHnHuhïP÷CJmHnHu!H$I$J$P$Q$Z$[$\$u$v$w$y$z${$|$}$~$™$š$›$œ$¦$§$¨$Á$Â$Ã$Å$Æ$Ç$æÓźů ¯ „ ÓºÓÅ{ÅaÓů ¯P „ Ó jû=hïP÷UmHnHu2j€=h]ÕhïP÷>*B*UmHnHphÿuhïP÷mHnHuh0z]mHnHu j=hïP÷UmHnHujhïP÷UmHnHuhïP÷mHnHuhïP÷CJmHnHuh]ÕhïP÷0JmHnHu$jh]ÕhïP÷0JUmHnHu2jŠ*B*UmHnHphÿuÇ$È$É$Ê$å$æ$ç$è$õ$ö$÷$%%%%%%%%%4%5%6%7%@%A%B%[%\%]%_%òßÑÈÑ®ßÑ£”£ƒ”x”ßòßÑÈÑ^ßÑ£”£M”x jç?hïP÷UmHnHu2jl?h]ÕhïP÷>*B*UmHnHphÿuh0z]mHnHu jñ>hïP÷UmHnHujhïP÷UmHnHuhïP÷mHnHu2jv>h]ÕhïP÷>*B*UmHnHphÿuhïP÷mHnHuh]ÕhïP÷0JmHnHu$jh]ÕhïP÷0JUmHnHuhïP÷^JaJmHnHu_%`%a%b%c%d%%€%%‚%‰%Š%‹%¤%¥%¦%©%ª%«%¬%­%®%É%Ê%Ë%Ì%â%ã%ä%ý%þ%ðÝÐݹŸÝ”ð”ƒðxðÝÐݹÂ^Ý”ð”M jÓAhïP÷UmHnHu2jXAh]ÕhïP÷>*B*UmHnHphÿuh0z]mHnHu jÝ@hïP÷UmHnHuhïP÷mHnHu2jb@h]ÕhïP÷>*B*UmHnHphÿuhïP÷mHnHuh]ÕhïP÷0JmHnHuhïP÷^JaJmHnHu$jh]ÕhïP÷0JUmHnHujhïP÷UmHnHuþ%ÿ%&&&&&&"&#&$&%&A&B&C&\&]&^&a&b&c&d&e&f&&‚&ƒ&„&´&µ&¶&Ï&ðåðÒÄÒ¶­¶“Ò¶ˆðˆwðåðÒÄÒ¶­¶]Ò¶ˆðˆ2jDCh]ÕhïP÷>*B*UmHnHphÿu jÉBhïP÷UmHnHuhïP÷mHnHu2jNBh]ÕhïP÷>*B*UmHnHphÿuhïP÷mHnHuh]ÕhïP÷0JmHnHuhïP÷5CJ\mHnHu$jh]ÕhïP÷0JUmHnHuh0z]mHnHujhïP÷UmHnHuÏ&Ð&Ñ&Ô&Õ&Ö&×&Ø&Ù&ô&õ&ö&÷&'''/'0'1'4'5'6'7'8'9'T'U'V'W'g'h'ïàÕà´¦¦ƒÂ¦xàxgàÕà´¦¦M¦x2j0Eh]ÕhïP÷>*B*UmHnHphÿu jµDhïP÷UmHnHuhïP÷mHnHu2j:Dh]ÕhïP÷>*B*UmHnHphÿuhïP÷mHnHuh]ÕhïP÷0JmHnHuhïP÷5CJ\mHnHu$jh]ÕhïP÷0JUmHnHuh0z]mHnHujhïP÷UmHnHu j¿ChïP÷UmHnHuh'i'‚'ƒ'„'‡'ˆ'‰'Š'‹'Œ'§'¨'©'ª'Ã'Ä'Å'Þ'ß'à'ã'ä'å'æ'ç'è'(((ðåÔðÉ𶨶š‘šw¶šåðåfðÉ𶨶š‘šL2jGh]ÕhïP÷>*B*UmHnHphÿu j¡FhïP÷UmHnHu2j&Fh]ÕhïP÷>*B*UmHnHphÿuhïP÷mHnHuh]ÕhïP÷0JmHnHuhïP÷5CJ\mHnHu$jh]ÕhïP÷0JUmHnHuh0z]mHnHu j«EhïP÷UmHnHuhïP÷mHnHujhïP÷UmHnHu(((((7(8(9((?(@(A(M(N(P(Q(÷(&)*** *!***7*o*p*íßÔÅÔ´Å©Å훓ˆ}rkd]VOVdOdVdH hÆP¡hZ¾ hÆP¡h+44 hÆP¡hƒsz hÆP¡h;[ hÆP¡h¯Uz hÆP¡hïÎhÆP¡hVõCJaJhÆP¡h}"CJaJ hÆP¡h}"hTXjhïP÷UhïP÷5CJ\mHnHuh0z]mHnHu j—GhïP÷UmHnHujhïP÷UmHnHuhïP÷mHnHuh]ÕhïP÷0JmHnHu$jh]ÕhïP÷0JUmHnHup*€*·*¹*À*Á*È*É*Ë*Î*Ñ*ð*ò*++++g+h+o+q+",',S,T,w,x,¢,£,¶,·,Ï,Ð,Ñ,Ò,--*-+-n-o--‘-ê-ë-Q.R..Ž.è.é../1/J/K/R/S/³/´/00000%0&040E0Y0Z0ùòùëùëùëùëùäÝùäÝäùÖòäÏäòäÅäÅäò¾äÖ·äòäòäòäòäòäòä°ÖòÖ·ÖòÖòÖòÖò¾·¾Ö·Ö·Öò hÆP¡hV^j hÆP¡h¿ní hÆP¡h¤+úhÆP¡h¯Uz6] hÆP¡hÚV' hÆP¡h+44 hÆP¡hƒsz hÆP¡h¯Uz hÆP¡hZ¾ hÆP¡hb¦ hÆP¡hÎG€Ep+q+È+Ð,Ñ,.Ž.0022á2â2È4É4š5›588í9î9ø>ú>û>óåóóóÝóóóÝóóóóóóóóÝóóÔÏgdb¦
ÆŸgd
#¨$a$gdjS²
$7$8$@&H$a$gdTX $7$8$H$a$gdjS²Z0½0¾0¿0æ0ò0ô0õ0J1K1¢1£1Õ1Ö122222ì3ñ37484>4Q4¡4­4®4¾4Æ4Ê4Ì4î4÷4˜5™5›5œ5»5Ã5È5Ú5þ5:6e6ž6¡6Î6Ï6Ñ6ß6ã6ä6ü6 7ùòùëùëòùòùòùäùòäùÝÖÏÖäÖËÖÄËÖÀÖëֲֹ뫤²¤Ö¤²«¹«–«‹äh hÆP¡h=4 hÆP¡h!1d hÆP¡hûuœ hÆP¡hN@ hÆP¡hä%¼ hÆP¡hØE– hÆP¡hÚV'ho hÆP¡h®¸h®¸ hÆP¡h¡aÑ hÆP¡h;M hÆP¡hV^j hÆP¡h¤+ú hÆP¡h¿ní hÆP¡hb¦ hÆP¡h+446 7F7S7˜7¹7ê7î7ù78 888888ì9î9I:J: ;;[;€;;ƒ;™;š;¥;¦;¼;½;ù>ú>û>??ùòùòëòëòäòäòùÝÖÏÈÁȺäÈÁȳ¬³¬³¬³¬³¬Á¬³¬³¬Á¬¨ä¨ä¬Á¬ÏȡϚ“ hÆP¡h hÆP¡h}" hÆP¡h!1dh ü hÆP¡hóXï hÆP¡hí© hÆP¡hKu hÆP¡hXFc hÆP¡h
#¨ hÆP¡h¤+ú hÆP¡hy&B hÆP¡húS hÆP¡hÔ hÆP¡hÚV' hÆP¡hûuœ hÆP¡h=47û>??1?@ø@
A4AGAeAùôïßßÙÑÆÆ
$$Ifa$K$$IfK$$If$¤d¤d7$8$H$a$gdÆ
K2gd[ gd0@&gdTX ?1?@ø@3A4AFAGAdAeAfAžAŸAÔAÕABBIBJB„B…B¸B¹BõBöBrCsCyC‰CŠCŒC”C•CãCäCåC%D&D'D(D¾GùòëáÚáÚáÚÓÚëÚÓÚÓÚÓáÓÚÓÚÓÚëáÚÓÚų¥³|³ngÓ hÆP¡hGmúhÆP¡hGmú6CJ]aJ'hÆP¡h‘{?0J6B*CJ]aJphÿ)j—QhÆP¡h‘{?6CJU]aJhÆP¡h‘{?6CJ]aJ#jhÆP¡h‘{?6CJU]aJhÆP¡híjº6CJ]aJ hÆP¡hâ hÆP¡hbThÆP¡hbT5\ hÆP¡h´# hÆP¡h‘{? hÆP¡hîg(eAfAA˜AžAph]]
$$Ifa$K$$IfK$ŽkdH$IfK$L$T– hÆP¡hóFÂh*âh-b hÆP¡hvK hÆP¡hô « hÆP¡h¿ 5 hÆP¡h6q hÆP¡h9°6v­®µ®T¯U¯ª¯‰°o±²m²n²ê²ë²µæææÖÖ½½©½Ö֜ƒ$
& F$?$Œ$$Ý$Þ$ó$ô$1%5%a%b%³%´%&&&& &
&R&S&n&¤&¥&ù&ú&''('C'I'J'M'N'g'i'm'o'v'w'}'~'Ç'È'((n(o(À(Á())*)4)5)6)T)öïëïëïäïäïÝïäïäïäïäïäïÝïäïäïäïÝïäïÝïäÙïäïäïÙïÝäïäïëïëïäïÝïäïäïäïäïäÏÅϸïhÆP¡h©ò56\]h?–h¡aÑ5\h?–h,5\h4u hÆP¡héY hÆP¡h©òhM$— hÆP¡h,hÆP¡h©ò6]HT)^)~))—)˜)É)Ê)**h*i*À*Á*++`+a++²+³+¶+¾+È+É+Î+æ+é+ê+,,,,L,M,u,v,w,z,‚,˜,š,»,½,Á,Ã,Ä,Å,--)-3-8-@-U-[-\-d-e-´-µ-. .[.\.¯.°.//K/L/ /¡/«/¬/ë/ì/D0E0–0—0ùòëòäòëòëòëòëòëòàòàòàòùàòàòàòäòÜòÕòÑÊòäòàòàòàòÕòÕòùòäòäëòÕòÕòÕòÕòÕòÕòÕòÕòäòÕòÕòÕ hÆP¡hczh, hÆP¡h~?UhuNhcz hÆP¡héY hÆP¡h©ò hÆP¡h, hÆP¡h¡aÑP—0ã0ä0è0/101g1h1|1~11€1á1â1E2F22€2Í2Î233_3`3h3i3n3o3·3¸3 4
464B4W4X4‹4Œ4”4–4³4´455Q5R5¤5¥5±5³5»5½5ð5ñ5D6E6—6´6è6é6>7?7’7“7ë7ì788988‘8Â8Ä8Ñ8Ò89ùòëùòùäùàÜÕùäùäùëùòùòùäùòùäùòùòùËùòùäùÇù½ùòùòùòùòùÇùòùòùòùòùòùòùòùòùòùÇùòùhÆP¡h~?U5\hczhÆP¡h,6] hÆP¡huNh~?UhuN hÆP¡héY hÆP¡h©ò hÆP¡h~?U hÆP¡h,J€1½12$2K22€2™4³4´4²5³5è6é68‘8N9O9É;ãããããÚÎÉļ¼¼¼¼¼¼·¬ $
& Fka$gduNgd~?U$a$gduNgd‰w2gdD>t $„Å^„Åa$gduN„Å^„ÅgdD>t$
& Ff
ÆЕ„•„›þ¤x¤x^„•`„›þa$gduN9 9M9N9O9Q9c9r9s9¼9½9::V:W:Ÿ: :ñ:ò:@;A;‹;Œ;Å;È;É;Ê;Í;Ø;Ù;á;(c>¶>·>??$?+?;?
 :