2001
Fondements des systèmes multi-agents : modèles, spécifications formelles et vérification

Montréal
Nombre d'articles : 20
Vérification automatique de logiques orientées agent
Pierre-Yves Schobbens
Mots-clefs : : logique multi-agents, vérification
Résumé : : La vérification automatique connaît aujourd'hui des dévelop- pements qui la rendent applicable pour des problèmes intéressants. L'appli- cation la plus connue est la vérification de formules temporelles dans des systèmes distribués finis, souvent connue sous le nom de "model checking". Elle est aussi applicable à certains systèmes infinis, comme les systèmes temps réel, et à des logiques plus riches, comme la logique du temps alternant, qui représente les choix et les stratégies qui s'offrent à des sociétés d'agent.

Mobilité, personnalisation et Information géo-référencée
Sylvain Giroux Bernard Moulin Gavino Paddeu Davide Carboni Roberto Demontis Stefano Sanna Enrico Stara
Mots-clefs : Personnalisation, information géo-référencée, multi-modalité, applications mobiles, réseaux sans fil, systèmes répartis, Jini, XML
Résumé : Les individus sont par nature mobiles. De plus en plus, ils recherchent desservices mobiles, personnalisés et géo-référencés (SMPGR). De tels services identifient lesinformations pertinentes en fonction du contexte immédiat de l'usager, pour ensuite lesrecomposer et les lui présenter tout au long de ses déplacements. Techniquement latechnologie matérielle fournit une partie de la solution aux besoins créés par la mobilité desgens. Cependant la construction de services mobiles requiert plus qu'une infrastructurematérielle habilitante. Le projet E-mate s'intéresse au design et à l'implémentation d'anmiddleware et de frameworks pour la livraison multi-modale de services géo-référencéspersonnalisés. Dans cet article, nous présentons l'ensemble du projet E-mate Nous montronsd'abord comment les SMPGR peuvent supporter la mobilité de l'usager et la mobilité desservices.. Ensuite, nous esquissons le middleware et les services mis en place pour déployeret utiliser des SMPGR sur ordinateurs personnels et portables, assistants personnels,téléphones cellulaires et téléviseurs digitaux.

MODELES FORMELS POUR LA COOPERATION DANS LES SMA Coopération dans les systèmes multi-agents une analyse et un point de vue
Larbi Esmahi
Mots-clefs : : Systèmes multiagent, Coopération, Négociation, Commerce électronique,Marchés virtuels.
Résumé : Dans la plus pan des nouvelles structures d'organisation (entreprises virtuelles,marchés virtuels et communautés virtuelles), le problème de la coopération a été traité enétudiant des aspects isolés du processus, comme l'implantation de mécanismes decommunication ou la définition d'intentions conjointes pour les agents. Cependant, dans cesnouvelles structures plusieurs autres facteurs influencent l'interaction des agents : relationsde dépendances, confiance et capacité de persuasion.Dans celle présentation nous discuterons du problème de négociation dans sa forme généralepour les systèmes multiagent, nous ferons une présentation sommaire de l'état de l'art et nousprésenterons une analyse processus de coopération mettant en relief les différents facteursqui influencent une telle interaction. En conclusion, un ensemble de remarques pertinentpour la conception et l'implantation des mécanismes de coopérations sera élaboré.

Méthode de formation et de restructuration dynamique de coalitions d'agents fondée sur l'optimum de Pareto
Philippe Cailloux Samir Aknine Suzanne Pinson
Mots-clefs : système multi-agents, coalitions, agrégation, preférences, restructuration
Résumé : Cet article présente un protocole de formation de coalitions pour des systèmes mufti- agents qui permet d'obtenir dans tous les cas une solution optimale au sens de Pareto, et ce sans nécessiter d'agrégation de préférences entre les agents. Il propose également une extension de ce protocole permettant une restructuration dynamique des coalitions déjà formées en fonction de changements dans l'état du monde. Il donne enfin des modèles de comportement d'agents bien adaptés à ce protocole. Une application fondée sur la formation d'emplois du temps a été réalisée pour le tester. Les résultats sont présentés et montrent le bon fonctionnement du protocole. Une analyse des protocoles existants permet enfin de positionner ce travail et de montrer son apport par rapport aux travaux existants.

Enchères multi-objets pour la négociation automatique
Houssein Ben-Ameur Brahim Chaib-Draa
Mots-clefs : systèmes multiagents, Négociation, Enchères multi-objets
Résumé : Plusieurs approches ont été étudiées pour la modélisation des interactions entre agents. Nous avons retenu les enchères comme mécanisme de négociation automatique mis en oeuvre dans un réseau d'agents intelligents. Des agents vendeurs et des agents acheteurs interagissent dans un environnement assimilable à un marché électronique afin de vendre et acheter des objets. Ce mécanisme d'enchères est basé sur les lois du marché qui fixent les prix et déterminent les gagnants. Nous nous intéressons au cas des enchères multi-objets basées sur l'enchère anglaise, avec possibilité pour les agents acheteurs de diminuer leurs quantités de- mandées lors de l'enchère. Nous présentons un modèle mathématique de ce type d'enchères et des stratégies d'enchérissement des agents acheteurs. Nous simulons ce modèle à l'aide d'un système multiagents afin de vérifier sa validité et de l'évaluer empiriquement.

Révision des croyances dans un environnement multiagent : Une approche basée sur la crédibilité et les arguments
Imed Jarras Brahim Chaib-Draa
Mots-clefs : : Révision des croyances, LDS, crédibilité, arguments.
Résumé : Peu de recherches se sont penchées sur la problématique de la révision des croyancesdans un cadre multiagent. En tout cas, à notre connaissance, aucune ne s'est penchée sur larévision des croyances tenant compte de la crédibilité des informateurs, tout en gardant tracedes arguments en faveur de la révision, une fois celle-ci effectuée. C'est ce problème qui nous amotivé et pour lequel, nous proposons ici, une approche formelle basée sur la logique étiquetée.

MODELES FORMELS POUR LA CONCEPTION DES SMA La spécification de protocoles d'interaction par réseaux de Petri
Christophe Sibertin-Blanc Henrique Lopes Cardoso Chihab Hanachi
Mots-clefs : Protocoles d'interaction, Spécification, Validation, Architecture des SMA, réseau de Petri.
Résumé : Les protocoles d'interaction jouent un rôle essentiel pour la coordination et la coo- pération des agents d'un Système Multi-Agent ; la spécification, validation et mise en oeuvre de façon sûre et efficace de ces protocoles est donc un enjeu important de l'approche Mufti- Agent. Dans cet article, nous proposons une méthode basée sur les réseaux de Petri pour la spécification formelle des protocoles d'interaction elle convient notamment pour les proto- coles qui, étant concurrents et ouverts, nécessitent de recourir à un formalisme ayant un large pouvoir d'expression. Après une présentation des possibilités de validation offertes par cette forme de spécification, on montre qu'elle ouvre la voie à une architecture des Système Alulti- Agent qui présente de nombreux avantages.

Composition et substitution d'agents : sémantique et préservation de propriétés
Nabil Hameurlain
Mots-clefs : composants agent, sémantique formelle, réseaux de Petri, substituabilité,préservation de propriétés.
Résumé : Ce travail se focalise sur la composition et la substituabilité de composants dans lessystèmes muitisagents (S.M.A), et montre que les approches traditionnelles déjà utilisées pourdévelopper les S.M.A sont limitées et parfois même non rigoureuses. Sur cette base, ce papierprésente une sémantique formelle pour la composition et la substituabilité comportementalede composants. Il propose une architecture formelle basée sur les relations de préordre quisont considérées dans l'étude des systèmes concurrents. Nous définissons diverses relationsde substitution comportementale, et nous étudions la préservation de propriétés de sûreté etde vivacité par ces relations. Nous montrons que les résultats obtenus sont compatibles avecla conception incrémentale des S.M.A. Des exemples de protocoles d'interaction comme le"Contract-Net Protocol" sont donnés pour illustrer notre approche.

OUVERTURE, DISTRIBUTION ET MOBILITÉ DANS LES SMA Utilisation d'agents stationnaires et d'agents mobiles pour la planification d'itinéraires dans un environnement dynamique
Bernard Moulin Nabil Sahli Zakaria Maamar
Mots-clefs : planification dans un environnement dynamique, agents mobile et agents stationnaires, méthode de conception de SMA.
Résumé : Nousprésentons les résultats de nos travaux exploratoires sur l'utilisation d'agents stationnaires et d'agents mobiles pour la conception de systèmes de planification dans des environnements distribués et en constante évolution. Nous montrons que cette approche permet d'apporter des solutions pratiques à des problèmes que les techniques de planification classique n'ont pas pu résoudre efficacement. Nous présentons le domaine d'application, l'évacuation aéromédicale, et évoquons les limitations des approches classiques dans ce domaine. Dans ce contexte nous proposons une démarche pour l'analyse et la conception de systèmes multi-agents composés d'agents stationnaires et mobiles. Enfin, nous présentons la solution proposée pour la réalisation du système de planification composé d'agents stationnaires et d'agents mobiles dans le domaine de l'évacuationaéromédicale.

Une gestion distribuée de l'ouverture dans un système multi-agent
Laurent Vercouter
Mots-clefs : Systèmes multi-agent ouvert, Représentation des autres, Gestion de l'ouverture
Résumé : Un système multi-agent ouvert doit permettre l'ajout et le retrait d'agent après sa conception mais aussi l'ajout et le retrait de services au sein d'un agent (une modification in-terne d'un agent). Des mécanismes de gestion de ces modffications doivent être mis en placepour conserver la cohérence du SAM. Une approche couramment utilisée consiste à intro-duire un agent (appelé courtier ou faciliteur) centralisant la prise en charge de cette gestion.Néanmoins ce mode de gestion présente des inconvénients liés â la centralisation et nous noussommes intéressés au problème de l'ouverture pour proposer une nouvelle approche, complète-ment distribuée, de gestion d'un SMA ouvert. Notre proposition a été concrétisée sous la formed'un modèle d'agent, que nous appelons agent accueillant, pouvant gérer l'ouverture d'un SMAcoopérativement avec d'autres agents accueillants.

Les processus décisionnels de Markov pour l'allocation-exécution entrelacées des tâches dans les systèmes multi-agents
Hosam HANNA Abdel-Illah MOUADDIB
Mots-clefs : coordination, agents distribués, décision sous incertitude, processus décisionnel deMarkov, agents coopératifs.
Résumé : Dans les systèmes multi-agents et distribués, le problème de l'allocation des tâchessuscite un intérêt de plus en plus important. En général, les techniques proposées ignorent lecoût de l'allocation et le comportement incertain de l'agent. Pour le premier problème, nousavons distribué l'allocation à travers les agents (afin de réduire le coût), ensuite nous avonscoordonné les décisions locales des agents. Pour le deuxième problème, nous avons formalisél'allocation et l'exécution des tâches par un processus décisionnel de Markov (MDP). En effet,le MDP permet aux agents de tenir compte de deux sources d'incertitude : (1) l'incertitude surl'allocation des tâches, et (2) l'incertitude sur la consommation des ressources nécessaires à laréalisation de chaque tâche. L'autre point que nous avons abordé est de coordonner les déci-sions locales (choix locaux des tâches à réaliser) des agents. Pour cela, nous introduisons dansce papier deux stratégies de coordination fondées sur la distribution séquentielle de tâches.

AGENTS SITUÉS REACTIFS Le principe de la Coopération Située À chaque type d'agent son modèle de coopération
Angélica Munoz-Meléndez Alexis Drogoul
Mots-clefs : agent situé, variables essentielles, zone de viabilité, coopération située.
Résumé : Nous nous intéressons à la conception et l'implantation de systèmes autonomes et co-opératifs dans un cadre mufti-agent. Un système autonome coopératif est pour nous un systèmecapable de maintenir certaines variables dites essentielles, dans les limites déterminées parsa zone de viabilité, c'est-à-dire un ensemble d'états dans lesquels le système est capablede continuer à opérer normalement. Le système est dit coopératif; car tous les agents qui lecomposent effectuent des actions ayant pour conséquence sa propre préservation, ainsi que lemaintien des autres agents du système dans leur zone de viabilité. Ces actions sont entreprisesgrâce à un mécanisme d'adoption et contribution à la réalisation de buts entre les agents. Dansce papier nous introduisons le principe de la coopération située pour concevoir des sys-tèmes coopératifs. Ce principe convient à la modélisation de systèmes multi-agents situés, pourlesquels les modèles de coopération développés à l'heure actuelle ne s'avèrent pas très adaptés.Deux exemples d'application de ce principe sont discutés : la simulation d'un système de piècesauto-assemblables et le sauvetage de robots mobiles. Nous présentons aussi des résultats de cesexpériences.

Modélisation des satisfactions personnelle et interactive d'agents situés coopératifs
Olivier Simonin Jacques Ferber
Mots-clefs : agents situés, coopération/coordination réactive, sélection d'actions, modèle dessatisfactions
Résumé : Cet article aborde le problème de l'évaluation, par l'agent, de ses actions et interac- tions. Nous proposons un modèle des satisfactions différenciant actions individuelles et inter- actions avec les agents voisins. La satisfaction personnelle est calculée incrémentalement dans le temps suivant la perception de la progression de la tâche en cours. La satisfaction interactive est une évaluation de la présence des agents voisins et de leurs actions: gêne, coopération, in- difference. Cette évaluation est transformée en signaux d'intentions (attractions ou répulsions) agissant comme des champs de potentiels dynamiques. Nous proposons alors un module de sélection d'actions basé sur la compétition continue entre la satisfaction personnelle de l'agent et les signaux qu'il perçoit. Nous montrons comment l'application de cette architecture permetde resoudre des conflits spatiaux entre agents mobiles autonomes.

Intelligence diffuse : vers un monde fait d'agents ?
Alexis Drogoul David Servat
Mots-clefs : : informatique diffuse, informatique amorphe, émergence, auto-organisation
Résumé : Cet article n'expose ni techniques novatrices, ni résultats expérimentaux, ni modèlesformels ou logiciels de SMA. Il s'agit d'une réflexion, raisonnablement prospective, sur lebouleversement que va représenter, dans les années à venir, l'avènement de nouveaux systèmesinformatiques basés sur l'informatique diffuse. Nous exposons, après une introduction à ceconcept, en quoi les règles traditionnelles de conception, de validation, de contrôle et dedéploiement actuellement utilisées dans l'industrie informatique ne sont plus adaptées à cesnouveaux systèmes. Nous montrons ensuite que le domaine des systèmes multi-agents semble, parun certain nombre d'aspects, pouvoir apporter des réponses aux problèmes qu'ils soulèvent, àcondition que les paradigmes dominants soient capables d'évoluer vers une plus grandesouplesse. Nous montrons en particulier comment la convergence des recherches menées dans ledomaine des systèmes multi-agents réactifs et dans celui de l'informatique amorphe sembleprometteuse pour appréhender le développement de ce type de systèmes et aboutir à ce que nousappelons des systèmes à intelligence diffuse.

APPROCHES PLURIDISCIPLINAIRES POUR LES SMA Apport de la modélisation cognitive aux langages de communication entre agents
Nathalie Chaignaud Amal El Fallah-Seghrouchni
Mots-clefs : Systèmes multisagents (SMA), modélisation cognitive, résolution coopérative deProblèmes, planification, langages d'interactions.
Résumé : Cet article montre la nécessité de réaliser une étude cognitive des interactionshumaines pour concevoir des systèmes informatiques capables d'interagir avec l'humain.Notre travail a pour objectif d'analyser, modéliser et simuler le raisonnement de l'êtrehumain dans un contexte coopératif de résolution de problèmes incomplètement décrits (enparticulier, pour une tâche de planification). La méthode proposée est double : d'une part,Construire un modèle complet de planification « humaine » prenant en compte lacoordination entre les sujets ; d'autre part, élaborer un langage d'interactions permettant àdes agents artificiels et humains de communication entre eux dans le cadre des systèmeshomme-machine. C'est sur ce dernier point que se focalise cet article.

De la simulation de construction collective à la détection de régions dans des images à niveaux de gris L'inspiration des araignées sociales
Christine Bourjot Vincent Chevrier
Mots-clefs : système multi-agent réactif, inspiration biologique, détection de régions
Résumé : Les phénomènes collectifs en biologie sont une source d'inspiration pour proposerdes méthodes mulli-agents de résolution de problèmes. Ils permettent l'élaboration decomportements individuels simples produisant collectivement des phénomènes complexes. Cetarticle expose la démarche de transposition que nous avons suivie pour passer d'un modèlede simulation à un modèle de résolution. Le cadre biologique initial concerne un processusde construction collective de toile chez les araignées sociales. Sa transposition concerne ladéfection de régions dans des images à niveau de gris.

Les réseaux de contraintes distribuées et le backtracking
Mustapha Belaïssaoui El Houssine Bouyakhf
Mots-clefs : Problèmes de Satisfaction de Contraintes Distribués, Backtracking Distribué.
Résumé : L'expression et le traitement de la distribution ou de partage de Problèmes deSatisfaction de Contraintes (CSP) a fait l'objet de diverses extensions du cadre CSPclassiques à des CSP Distribués (DCSP). Malheureusement, de tels problèmes sont en généralNP-complets. Dans ce cadre nous avons développé une extension de l'algorithmed'Ordonnancement Distribué des Agents [HAM 98]. A partir de l'algorithme IntelligentBackTracking Distribué (DIBT) [HAM 98], nous avons proposé une Généralisation Optimaleen envoi de messages (OGDIBT).

APPLICATIONS MULTI-AGENTS Modèle de contrôle par émergence de coordinations dans un réseau de contrats multi-agents
Carine Bournez Olivier Gutknecht
Mots-clefs : Marchés d'agents, réseau de contrats, émergence, raisonnement à base de cas
Résumé : Le contrôle des systèmes de production distribués et dynamiques tels que les entre- prises virtuelles et les chaînes logistiques soulève des problèmes spécifiques, mal résolus par les systèmes de pilotage classiques. En effet, les contraintes d'hétérogénéité, de variabilité de l'échelle, de reconfigurabilité, de performance, de sécurité, d'accessibilité, etc. ne sont pas prises en considération. Nous proposons un système de pilotage émergent, construit sur une architecture multi-agent ouverte, réflexive et adaptative. Hétérarchique et décentralisée, elle est basée sur un marché économique autour d'un protocole de réseau de contrats. Les agents coopèrent implicitement et se coordonnent par le principe du marché compétinf. Leur dyna- mique de raisonnement est basée à la fois sur l'acquisition de comportements lors de 1' exploi- talion du système et sur des raisonnements partiellement pré—câblés. Un simulateur conçu sur la plateforme MadKit permet d'appliquer l'architecture proposée sur divers cas d'étude sans réimplémentations lourdes.

modèle de contrôle par émergence de coordinations dans un réseau de Contrats multi-agents
Carine liournez
Mots-clefs :
Résumé : let, t fourbir des rystèmes de prtniu£ lion distribues et d>rtarniques tels que les entre- prises virtuelles et les chalnes logistiques souleve des pmblemes spét tiques, mal résolus par ies systèmes de pilotage c lassiques b let, les t ontramtes d'hétérogeneité, de variabilité dede reconfigurabilite, de performant r, de sécurité, d'accessibilité, etc. ne sont pas prises en considération. Nous proposons un systerne de pilotage émergera, construit sur une atrhitecture multi-agent ouverte, rejleAetve et adaptative. liétérarchique et décentralisée, elle est basée sur un marché ét atomique autour d'un protocole de réseau de contrats. Les agents coopèrent implicitement et se coordonnent par le principe du marché compétitif Leur dyna- ►ique de raisonnement est basée à la fois sur l'acquisition de comportements lors de l'exploi- tation du système et sur des raisonnements partiellement pré câblés. Un simulateur conçu sur la platelorme MadiCit permet d'appliquer l'architecture proposée sur divers cas d'étude sansréirraplémentations lourdes.

SATIR : une approche multi-agent pour la gestion des réseaux de transport. Application à la gestion des réseaux de bus
Flavien Balbo
Mots-clefs : système d'aide à la décision, transport, temps réel.
Résumé : Dans cet article, nous présentons un Système Automatique de Traitement des Incidents en Réseau (SATIR). Notre proposition est un système d'aide à la décision multi- agent adapté au domaine de la gestion des réseaux d'autobus. Nous abordons le domaine de la régulation des réseaux de bus dans toute leur complexité. Le système gère les incohérences des données, les perturbations du trafic et propose des solutions aux opérateurs. Notre proposition a été testée sur le réseau de la Société de Transport intercommunal de Bruxelles et nous présentons nos premiers résultats.