Cours SMA - Etudiants.pdf

1

Systmes Multi-Agents

Wided LEJOUAD-CHAARI

ENSI Laboratoire de Recherche SOIE

Cours II3 SMA

2

Introduction

Cours II3 SMA

3

Cours II3 SMA

Plan

Motivations

Dfinitions

Historique

Domaines daction

Bibliographie

4

Cours II3 SMA

Des Systmes de Plus en Plus

Rpartis

Architecture centralise

Client-Serveur

Systme Distribu

Systme Multi-Agents

5

Cours II3 SMA

MainFrame

Serveur BD Serveur Web Serveur Mail

Application

Application

Application Application

Serveur BD Serveur Mail

Serveur Web

Application

AGENT

Application

AGENT

Application

AGENT

Application

AGENT

Serveur Mail

AGENT

Serveur Web

AGENT

Serveur BD

AGENT

+ Architecture Centralise Client - Serveur Systme Distribu

Systme

Multi-Agents

6

Cours II3 SMA

Accroissement des Capacits

Informatiques

Connectivit (Internet, WWW, )

Puissance de calcul

Puissance de transmission (vitesse, bande passante, )

Interfaces (visualisation, vocal, )

Informations (taille, complexit, modalit)

Ressources (distribues, htrognes, partages)

7

Cours II3 SMA

Accroissement de lHtrognet

Interactivit (collecticiels, environnements, )

Donnes/Connaissances

BDs multimdia, scientifiques, numriques,

Syntaxe, smantique, structuration,

Interfaces multi-modales (donnes, voix, images,

gestes, )

Communications (satellite, communications mobiles,

rseaux)

8

Cours II3 SMA

Accroissement des besoins

Traitements intgrs, omniprsents, dynamiques,

Systmes dinformations htrognes, tendus,

fortement intgrs, trs complexes

De nouveaux utilisateurs

De nouveaux champs (domaines de connaissances,

applications)

9

Cours II3 SMA

Exemple dapplication

AGENCE DE VOYAGES

Web Server

(Train)

Web Server

(Hotel)

Web Server

(Flight)

Personal Travel

Agent

Travel Broker

Agent

Travel Service

Agent

Adding user preferences to user requests

Learning user profile

Negotiation

Service provision Advance notification

Service decomposition Negotiation

Planning and Scheduling

10

Cours II3 SMA

Motivations

Actuellement les systmes informatiques sont :

de plus en plus complexes,

souvent rpartis sur plusieurs sites,

constitus de logiciels en interaction entre eux ou

avec des tres humains.

Volont

dintgrer,

de faire inter-oprer,

de faire cooprer des logiciels existants.

11

Cours II3 SMA

Plan

Motivations

Dfinitions

Historique

Domaines daction

Bibliographie

12

Cours II3 SMA

AGENT (1)

Agent = Systme informatique situ dans un

environnement quil peut percevoir et sur lequel

il peut agir, de manire autonome.

Agent

Environnement

Perception Action

13

Cours II3 SMA

AGENT (2)

Agent = le monde des agents est peupl de diffrentes

varits.

Robots mobiles Assistants personnel Agents mobiles Agents ractifs Agents intelligents Agents coopratifs

Systmes multi-agents

14

Cours II3 SMA

AGENT (3)

Agent = entit relle ou virtuelle, dont le comportement

est autonome, voluant dans un environnement,

capable de le percevoir, dy agir dessus et dinteragir

avec les autres agents [Demazeau 96].

Agent = systme informatique capable dagir de manire

autonome et flexible dans un environnement

[wooldridge 98]. La flexibilit signifie :

ractivit,

pro-activit,

capacits sociales.

15

Cours II3 SMA

16

Cours II3 SMA

17

Cours II3 SMA

18

Cours II3 SMA

19

Cours II3 SMA

20

Cours II3 SMA

Plan

Motivations

Dfinitions

Historique

Domaines daction

Bibliographie

21

Cours II3 SMA

Sources (1)

Programmation par objets : un objet encapsule les

donnes et les mthodes qui les manipulent (ex. C++,

JAVA, Smalltalk),

Distribution : objets distribus, CORBA

Dveloppement des langages acteurs

Intelligence artificielle : modles de raisonnements

symboliques (systmes experts, reprsentation des

connaissances, logique),

Distribution : architectures de Blackboard

Systmes rpartis

22

Cours II3 SMA

Sources (2)

Informatique rpartie

Paralllisme,

Intelligence Artificielle

Programmation

Psychologie sociale

Sociologie,

Economie,

Systmes complexes

en physique,

Ethologie,

Ecologie,

Vie Artificielle,

Rseaux de neurones,

Modles multi-agents

23

Cours II3 SMA

Agent vs. Objet

Un agent, comme un objet, encapsule un tat et un

comportement

Lagent a le contrle sur son comportement; un objet na

le contrle que sur son tat

Lagent exerce ce contrle de diffrentes manires

(ractif, dirig par les buts, social)

24

Cours II3 SMA

Historique (1)

1980 : Les agents sont limits au domaine de lIA Intelligence Artificielle Distribue, Systmes multi-agents

1990 : La notion dagent slargit Assistants personnels, interfaces, mobiles, ractifs, recherche

dinformations,

1995 : Tout devient un agent Vie artificielle, agents conomiques,

25

Cours II3 SMA

Historique (2) Intelligence Artificielle Distribue, Syst. multi-agents

1973 1980 : Hearsay II (1973) : architecture de tableau noir pour la

reconnaissance de la parole,

Langages Acteurs (1973) : messages comme structures

de contrle,

Beings (1975), Society of Minds (1978) : interaction de

comportements simples conduit des comportements

complexes

1980 1990 : Contract Net (1980) : contrle hirarchique dcentralis,

DVMT (1984) : interprtation distribue,

Subsumption architecture (1986) : robots ractifs,

MACE (1987) : environnement multi-agents.

26

Cours II3 SMA

Plan

Motivations

Dfinitions

Historique

Domaines daction

Bibliographie

27

Cours II3 SMA

Quand utiliser un SMA ? (1)

Nature de lapplication :

Le problme est complexe et doit tre dcompos

Absence de solution globale

Modlisation de problmes naturels/sociaux

Existence de diffrents domaines de connaissances

Distribution des donnes, du contrle, des connaissances, des

ressources

28

Cours II3 SMA


Contraintes dexcution : Volont davoir des rsolutions concurrentes, simultanes,

asynchrones

Satisfaction de contraintes de fiabilit, de contraintes

physiques,

Besoin dvolutivit : Adaptation aux modifications et/ou lenvironnement

Besoin douverture : Le systme doit pouvoir sadapter dynamiquement au

retrait/ajout de nouveaux composants

29

Cours II3 SMA


Mais :

Absence de contrleur global

Absence de vision globale

Attention : un SMA nest pas obligatoirement LA solution

adquate dans toutes les situations !

30

Cours II3 SMA

Domaines daction (1)

Intgrer

Encapsulation dun sous-systme par un agent : value dynamiquement les besoins de lutilisateur, adapte le

fonctionnement du systme sous-jacent,

Aide linformation et la ngociation : contexte agents intelligents et assistants

recherche et structuration dinformations

Facilitation par apprentissage et adaptation

Partage de reprsentations : modle du point de vue dun acteur sur un projet

change de points de vue

31

Cours II3 SMA


Rsoudre des problmes

Rsolution multi-agents de problmes = dfinition dobjectif global, de critres globaux de succs,

division des connaissances, des ressources, du contrle

dfinition locale dobjectifs et/ou de contraintes,

activation dynamique avec minimisations locales

convergence globale, observation de ltat stable sous contrainte

Problmes : recherche de solution et non optimisation

32

Cours II3 SMA


Simuler

Simulation multi-agents = initialisation vue ou avec des donnes

activation parallle des agents

observations individuelles ou agrges

comparaison aux donnes

Problmes : comparaison aux dires dexperts

syndrome usine gaz

Coordination dactivits dun ensemble dagents voluant dans un univers multi-agents : abeilles, fourmis,

33

Cours II3 SMA

Domaines dapplication

Ex. Applications industrielles Supervision de processus : ARCHON [Jennings95]

Production industrielle : YAMS [Parunak87]

Contrle du trafic arien : OASIS [Kinny96]

Ex. Applications commerciales Gestion de linformation WWW : MAXIMS [Maes94]

Commerce lectronique : KASBAH [Chavez96]

Processus administratifs : ADEPT [OBrien96]

Ex. Applications mdicales Surveillance de patients : GUARDIAN [Hayes-Roth89]

34

Cours II3 SMA

Bibliographie

Rfrences gnrales

O. Boissier. Cours SMA lEcole des Mines Saint-Etienne.

J. Ferber. Les systmes multi-agents, InterEditions, 1995

G.M.P Hoare, N.R. Jennings. Foundations of Distributed Artificial

Intelligence, Wiley & Sons, 1996

G. Weiss. Multiagent systems: A Modern Approach to Distributed Artificial Intelligence, MIT Press, 1999

35

Cours II3 SMA

Bibliographie

Standardisation

OMG Agent Working Group http://www.objs.com/isig/agent.html

FIPA http://www.fipa.org

Projets europens

CLIMATE http://www.fokus.gmd.de/cc/ima/climate/

AgentLink http://www.agentlink.org

Eurescom http://www.eurescom.de/

36

Cours II3 SMA

Agent Environnement

Interaction - Organisation

37

Cours II3 SMA

Exemple : Proie Prdateurs

Mouton

Loup

Meute Chasse

Suivi Fuite

38

Cours II3 SMA

Exemple : Proie Prdateurs

Pour capturer les proies (moutons) :

Comment coordonner les actions entre les diffrents prdateurs (loups) ?

Comment coordonner les actions des proies ?

39

Cours II3 SMA

Situations dinteraction

1. Buts compatibles ou incompatibles,

2. Ressources suffisantes ou insuffisantes,

3. Comptences suffisantes ou insuffisantes.

Indiffrence, Coopration, Antagonisme.

40

Cours II3 SMA

Situations dinteraction (suite)

Buts Ress. Comp. Types de situation

Compa.

Compa.

Compa.

Compa.

Incomp.

Incomp.

Incomp.

Incomp.

Suff.

Suff.

Insuff.

Insuff.

Suff.

Suff.

Insuff.

Insuff.

Suff.

Insuff.

Suff.

Insuff.

Suff.

Insuff.

Suff.

Insuff.

Indpendance

Collaboration simple

Encombrement

Collab. coordonne

Comptition individuelle pure

Comptition collective pure

Conflits individuels pour des

ressources

Conflits collectifs pour des

ressources

41

Cours II3 SMA

Problmatique

Etant donn un ensemble dagents interagissant dans un

environnement commun :

Identifier les situations dinteraction

Reconnatre lexistence de situations dinteraction

Grer les situations dinteraction reconnues

COMMENT : Au sein de lagent, entre les agents, au travers de

lenvironnement, au travers de lorganisation, au travers

des changes, ?

42

Cours II3 SMA

43

Cours SMA II3/DEA W. Lejouad-Chaari

Mthodologies Orientes

Multi-Agents

44


Contexte

Naissance du domaine de recherche en SMA :

les annes 80

Accroissement de leur domaine dapplication : Contrle du trafic arien

Commerce lectronique

Distribution dlectricit

Dveloppement coteux en temps : Complexit

Cration de tout le systme pour chaque application

Multiples propositions de modles dagents

45


Besoin Les SMA sintressent des problmes complexes,

distribus, sans contrle centralis.

Fournir des modles, des mthodologies, des

plates-formes : prendre en compte la complexit

aider les concepteurs non spcialistes

proposer aux industriels une approche dingnierie

Deux grandes familles de travaux sur les mthodologies

orientes agent : une mthodologie oriente objet

une mthodologie dingnierie des connaissances

46


Caractristiques des SMA

Deux caractristiques les diffrencient, dans la conception,

des systmes classiques :

la complexit la prise en compte de la dynamique

Au niveau des interactions elles sont complexes, utilisant un langage de communication

de haut niveau entre agents ;

la conception, le concepteur ne sait pas quand, pourquoi et avec

qui lagent va interagir ;

Au niveau de lenvironnement les environnements des SMA sont de plus en plus ouverts (fortement

dynamiques) ; les agents nen ont quune vue partielle.

47


Extension dune mthodologie

oriente objets aux agents

Pas de conception de mthodologies spcifiques

Reprise et extension de mthodologies existantes :

un moindre effort dadaptation pour les concepteurs

choix dune mthodologie proche de celle qui a fait dj ses

preuves pour les industriels

utilisation frquente des objets de la part des concepteurs

48


Insuffisances de lapproche

oriente objet

Les mthodologies bases sur lobjet ne prennent pas

en compte les caractristiques : dautonomie, de pro-activit, de ractivit et de socialit de

lagent ;

de complexit des interactions et de dynamicit du systme ;

La mthodologie OO nest pas directement applicable

au dveloppement de SMA.

49

Objet Agent

Communication Invocation de

mthode

Typologie de messages

(richesse)

Protocoles (complexit)

Interprtation de messages

Interactions Rigidit Evolution dans le temps

Composante

sociale

- Influence sur le comportement

Autonomie - Facult de dcider

dynamiquement

Relations est-un

est-compos-de

Insuffisantes pour modliser

des relations dorganisation

approches

caractristiques

50


La phase danalyse

Fournir la description des besoins de lutilisateur en termes

lis au domaine et aux fonctions du systme

ANALYSE DES BESOINS

Permettre une description des entits relles intervenant

dans lapplication

IDENTIFICATION DES AGENTS ET

LES RELATIONS ENTRE EUX

51


Analyse des besoins

Les besoins, comme en GL, sont issus des documents

techniques, des spcifications formelles, (ex. MaSE)

Proposition de langages pour exprimer dune part la

description de larchitecture et dautre part les besoins et

les scnarios. (ex. DESIRE)

Les besoins peuvent tre exprims de manire informelle

par des scnarios textuels.

52


Identification des agents par leurs

RLES Dterminer les rles partir des buts,

crer des tches pour les accomplir,

dterminer les squences de messages [MaSE]

A partir des scnarios textuels,

crer une description fonctionnelle prcisant les rles des

agents et les activits, les interactions avec dautres agents

Pour un scnario, le concepteur cre un ensemble de

diagrammes de comportement associ un agent [MASB]

53


Identifier les rles partir de trois attributs :

les permissions (ressources)

les responsabilits (buts)

les protocoles (le modle dinteraction entre les rles)

[Wooldridge & al.]

Identifier les agents par leur rle au sein de groupes

dans le modle agent-groupe-rle [Ferber & Gutknetch].

54


La phase danalyse peut tre compose de deux modles :

Le modle des agents : il dcrit une hirarchie de classes dagents partir de leurs rles et des relations entre eux.

Le modle dinteractions : il prsente les responsabilits

de chaque classe dagents, les services fournis par chaque

agent et les interactions associes, et les liens de contrle

entre les classes dagents.

[Kinny & al.] : pour eux la phase danalyse fait partie du

point de vue externe des agents

55


Les applications dont les interactions sont trop dynamiques

disposent dun cadre mthodologique [Cassiope] :

Identification des comportements lmentaires ncessaires la ralisation de la tche collective et dfinition des types

dagents.

Spcification des comportements relationnels : tude des

dpendances comportementales, cration du graphe de

couplage puis du graphe dinfluences.

Spcification des comportements organisationnels.

56


Identification des agents en tant

quACTEURS Les agents sont identifis au cours des raffinages successifs

de lexpression informelle des besoins du SMA [DESIRE].

Un modle de participation issu de lanalyse de lactivit

conjointe dun groupe est dfini. Il est bas sur lenceinte,

les scnarios et les acteurs [ANTIGONE]. les scnarios sont des suites dactions proposes aux acteurs ;

les acteurs sont dfinis par leur rle, leur place dans la

socit, leurs caractristiques (croyances, liens, ) et leur

type (destinataire, auditeur) ;

un mdiateur gre les dialogues (vrifier leur pertinence) ;

57


Identification des agents comme des acteurs des cas

dutilisation [Kendall & al.].

Combinaison de la mthodologie OO (OOSE) et la mthodologie de modlisation dentreprise (IDEF).

3 modles sont tirs :

- modle fonctionnel,

- modle des cas dutilisation,

- modle dynamique de diagrammes de traces

dvnements.

58


Discussion

Les chercheurs napportent aucune aide un concepteur

non spcialiste des SMA pour dcider si cette technique

est plus pertinente quune autre.

La description du systme en plusieurs entits est

privilgie par rapport la description fonctionnelle :

il est difficile de dcrire comment raliser la fonction

globale dun SMA.

La notion de rle diminue la complexit des interactions

par une abstraction du comportement dun agent.

59


La phase de conception

De la phase danalyse, un modle de ce que doit faire

le systme est tabli :

ENRICHISSEMENT DU MODELE

AU COURS DE LA CONCEPTION

COMMENT CONSTRUIRE LE SYSTEME ?

60


Conception dagents

Les descriptions de lapplication obtenues en phase

danalyse sont transformes en spcifications formelles :

Architecture, Scnarios et Modle dagents [MASB]

A partir des rles, des communications et des interactions

entre ces rles, les classes dagents sont identifies [MaSE] :

une bijection entre chaque rle et les classes dagents

une composition des classes dagents en rles et

conversations est obtenue

61


Conception dagents

Le processus de conception comporte 3 modles

[Wooldridge & al.] :

le modle dagent :

types dagents et instances (arborescence)

le modle de services :

fonctions des agents

le modle daccointances :

liens de communication entre agents

62


Conception dagents

Le comportement des agents est mise en uvre selon 3

modles [Architectures Orientes BDI par Kinny] :

le modle des croyances

le modle des buts

le modle des plans

pour chaque but, un plan doit tre tabli

les croyances sont dfinies en analysant les actions et

les activits de lagent

63


Conception dagents

Le comportement de lagent est dcrit par la spcification

de ses rles [Le modle MOISE par Hannoun & al.] :

un rle est un ensemble de missions dfinies en termes

de : plans,

buts,

actions,

ressources

adapt aux agents de type BDI

64


Conception dagents

Lagent est constitu [Kendall & al.] :

de croyances, de capteurs et deffecteurs obtenus

partir du modle fonctionnel

de plans crits sous la forme de diagrammes de

squences et drivs du modle dynamique

les protocoles de coordination sont dcrits sous forme de

diagramme dtats

65


Conception dagents

Une analyse des besoins et des scnarios est faite aussi au

niveau des agents et des composants de la phase danalyse

[DESIRE].

A chaque scnario est associ un processus.

Le raffinage des processus amne prendre des dcisions

de conception et dfinir les composants et leur

comportement.

66


Conception dagents

Dans [DESIRE], la conception de lagent est base sur

un modle dagent gnrique guid par :

la notion de processus et de tche

le maintien des connaissances sur le monde et les

agents, la gestion des interactions, la coopration

et ses tches spcifiques.

les structures de connaissances

les croyances sur le monde et les autres agents, les

informations utilises pour la communication avec

les agents et lobservation du monde,

67


Conception dagents

Une mthodologie de conception rcursive de SMA

[Occello & Demazeau] :

Un systme est dcompos en agents qui eux-mmes

sont vus comme des systmes dcomposs leur tour

en agents.

Un agent est reprsent par un n-uplet comprenant

ses capacits de communication, perception, actions,

vues comme des agents.

68


Conception dorganisation

Dfinition des composants du systme, les interfaces et les

fonctions entre ces composants :

conception de la structure organisationnelle [Aalaadin]

Raffinage des modles dagents et dinteractions dcrits

dans la phase danalyse [Architectures BDI]

Description des liens organisationnels de 3 types :

communication, autorit et accointance qui structurent les

changes entre les rles (les agents) [MOISE]

69


Discussion

Dans la plupart des modles, le comportement des agents

est dfini :

soit comme un ou plusieurs rles

soit comme des buts et des plans

Des modles dagents vont jusqu

dfinir des classes dagents

fournir un modle gnrique instancier

La complexit des systmes en termes dinteractions est

prise en compte par une tude dtaille des communications,

par la mise en uvre de scnarios, de conversations.

70


Discussion

Aucune mthode ne prcise si les interactions peuvent

tre volutives.

Trs peu de mthodes prennent en compte les interactions

entre le systme global et son environnement.

Aucune mthode nenvisage de prendre en compte des

situations imprvues dans un environnement dynamique.

71


Exemple de modle Rles-Interactions-Organisation-Agents

72


Spcification de SMA

Une approche de spcification fonde sur les concepts

de rle, dinteraction, dorganisation et dagents

[V. Hilaire & al.]

Deux niveaux dabstraction :

le 1er considre le systme comme une

organisation compose de rles et de leurs

interactions

le 2me qualifi dagentification, introduit les

agents comme une encapsulation des rles

73


Spcification de SMA

Un rle est un niveau dabstraction qui reprsente un

comportement gnrique.

Un rle doit reprsenter une unit cohrente de services,

fonctionnalits, caractristiques, ...

Une organisation est un ensemble de rles et dinteractions

conus pour se comporter de manire coordonne.

74


Simulation dpidmies de fivres

aphteuses : troupeaux de bovins

ORGANISATION

Production

Maladie

RLES [ lintrieur des organisations,

connects par les interactions]

Gestion Troupeau

Suivi Sanitaire

LIENS DE MISE EN UVRE

Flches allant des rles aux agents

75


Simulation dpidmies de fivres

aphteuses : troupeaux de bovins

AGENT

Eleveur

RLE_1: Gestion Troupeau

Mois davril transfrer les animaux lherbage

Mois de septembre les rentrer ltable

Mois de novembre vendre les veaux

RLE_2 : Suivi Sanitaire

Tous les mois simuler lexamen des animaux et

les traitements ventuels

76


Organisation Production

Gestion Troupeau Production

Organisation Maladie

Suivi Sanitaire Site Contaminant

Anadmie

Eleveur Cheptel Maladie

Schma dorganisation

77


Spcification du rle

Gestion Troupeau

Classe GestionTroupeau

Lvnement aux mois davril et septembre :

dclenche une transition : changer tat troupeau

modifie lattribut localisation

Lvnement au mois doctobre :

dclenche une transition : vendre veaux

modifie lattribut veaux

78

GestionTroupeau

Rle

comportement

table herbage mois[i][i=4]/passageHerbage

mois(i)[i=9]/passageEtable

C

m

ois

[i] [4

79

troupeau : P Animal

veaux : P Veau

adultes : P Adulte

localisation : Animal Localisation

{troupeau, veaux, adultes, localisation} attributs

troupeau = veaux adultes

vendreVeaux

veaux

#veaux' #veaux

passageEtable

localisation

t : troupeau localisation' (t) = table

80

passageHerbage

localisation

t : troupeau localisation' (t) = herbage

81


Spcification du rle

Suivi Sanitaire

Classe SuiviSanitaire

Il sagit de :

Inspecter les animaux

Sil existe des animaux malades

alors appliquer un traitement

Linspection se fait tous les mois

La dure defficacit du traitement est fixe 3 mois

82

SuiviSanitaire

Rle

comportement

Attente

any(mois)/rmanence:=rmanence-3

Suivi Sanitaire

Examen

[mal

ades

!=0

]/tr

aite

men

t

Traitement

[rm

anen

ce=

0]

[malades=0]

83

malades : P Bovin

rmanence : N

traitement

rmanence

#malades 0 rmanence' = 3

84


Spcification de lagent

Eleveur

Classe Eleveur

Le comportement est le rsultat de :

la composition AND des comportements des rles

quil met en uvre

Les attributs, actions, stimulus de lagent :

attributs, actions, stimulus (Rle_1, Rle_2)

85

Eleveur

Agent

comportement

GestionTroupeau SuiviSanitaire

enOeuvre = {GestionTroupeau, SuiviSanitaire}

attributs = {troupeau, veaux, adultes, localisation, malades

rmanence}

actions = {vendreVeaux, passageEtable, passageHerbage,

traitement}

stimulus = { i 1..12 mois[i]}

a accointances a : Cheptel a : Maladie

Documents

Cours SMA - Etudiants.pdf