1

2

Interactions - Systèmes Multi - Agents

pascal.estraillier @ univ-lr.frpascal.estraillier @ univ-lr.fr

Département Informatique - Laboratoire L3i Université de La Rochelle

Master IMA - 1

3

Environnement

D’après Boissier, Demazeau, Drogoul, Ferber,

Quinqueton, Sayettat, …..

Interactions - Systèmes Multi - Agents

Master IMA

Master IMA

4

Systèmes Multi - AgentsSystèmes Multi - Agents

Dans une Dans une organisationorganisation, les agents devront , les agents devront interagir pour coopérer (contrinteragir pour coopérer (contrôôle)le) Collaborer (allocation de tCollaborer (allocation de tââches)ches) Négocier (résolution de conflits)Négocier (résolution de conflits) se coordonner (synchronisation)se coordonner (synchronisation)

Un SMA peut-Un SMA peut-êêtre :tre : Ouvert / Fermé : Ouvert / Fermé :

les agents y entrent et en sortent librement /l'ensemble d'agents les agents y entrent et en sortent librement /l'ensemble d'agents reste le mreste le mêêmeme

Homogène / Hétérogène : Homogène / Hétérogène : tous les agents sont issus du mtous les agents sont issus du mêême modèle / des agents de me modèle / des agents de

modèles différents, de granularités différentes (ex: un éco-modèles différents, de granularités différentes (ex: un éco-système)système)

Mixte (ou non) : Mixte (ou non) : les agents « humains » sont partie intégrante du systèmeles agents « humains » sont partie intégrante du système

5

Vision locale et décentraliséeVision locale et décentralisée

La conception d'un système multi-agent impose une La conception d'un système multi-agent impose une vision locale et décentralisée. vision locale et décentralisée.

• locale : locale : chaque agent devient responsable de ses connaissances chaque agent devient responsable de ses connaissances

(encapsulation) et de ses actions(autonomie), mais également de (encapsulation) et de ses actions(autonomie), mais également de l'organisation qu'il met en place avec d'autres agents. l'organisation qu'il met en place avec d'autres agents.

Aucun agent n'a de vue globale du SMA tout entier. Aucun agent n'a de vue globale du SMA tout entier.

• décentralisée : décentralisée : on s'efforce d’éliminer tout contron s'efforce d’éliminer tout contrôôle central.le central. Les tLes tââches à réaliser et les compétences pour le faire sont ches à réaliser et les compétences pour le faire sont

distribuées sur les agents. distribuées sur les agents. Permet une grande modularité Permet une grande modularité

6

MéthodologieMéthodologie

QuickTime™ et undécompresseur TIFF (LZW)

sont requis pour visionner cette image.

QuickTime™ et undécompresseur TIFF (LZW)

sont requis pour visionner cette image.

7

Architecture d’un agentArchitecture d’un agent

QuickTime™ et undécompresseur TIFF (LZW)

sont requis pour visionner cette image.

8

EnvironnementEnvironnement

‘‘‘‘Espace’’ commun aux agents du système doté d'un ensemble Espace’’ commun aux agents du système doté d'un ensemble d’objets pouvant être :d’objets pouvant être :

situés (à tout moment il est possible de déterminer la position d’un objet),situés (à tout moment il est possible de déterminer la position d’un objet), passifs (ces objets peuvent être perçus, détruits, modifiés par les agents) ou passifs (ces objets peuvent être perçus, détruits, modifiés par les agents) ou

actifs.actifs.

Environnement d’un agent :Environnement d’un agent :

environnement du SMAenvironnement du SMA + + les autres agentsles autres agents appartenant au appartenant au système.système.

ExempleExemple un médium un médium d'interactiond'interaction : signaux, traces, ... avec des lois physiques ou non, : signaux, traces, ... avec des lois physiques ou non, un un lieulieu où des actions individuelles ou collectives sont réalisées, où des où des actions individuelles ou collectives sont réalisées, où des

réactions sont perçues,réactions sont perçues, un espace de un espace de déplacementdéplacement : grilles, positions des agents, … : grilles, positions des agents, … un moyen de un moyen de structurationstructuration des agents : relations de proximité, définition de des agents : relations de proximité, définition de

topologies spatiale, temporelle, …topologies spatiale, temporelle, … une une source de donnéessource de données pour le système, pour le système, un lieu où des un lieu où des ressourcesressources sont disponibles, ... sont disponibles, ...

9

• L’environnement joue un rôle important dans le L’environnement joue un rôle important dans le comportement d’un agent :comportement d’un agent :

mémoire dans laquelle différentes traces sont laissées,mémoire dans laquelle différentes traces sont laissées, source de rétroaction envers l’agent, …source de rétroaction envers l’agent, …

• une distinction nette doit être faite entre ce qui est du une distinction nette doit être faite entre ce qui est du ressort du comportement de l’agent et ce qui est du ressort du comportement de l’agent et ce qui est du ressort de l’environnement.ressort de l’environnement.

• ses caractéristiques doivent donc être clairement ses caractéristiques doivent donc être clairement définies …définies …

10

Propriétés de l’environnementPropriétés de l’environnement

Accessible/Inaccessible.Accessible/Inaccessible. Si les capteurs d ’un agent lui donnent accès à l ’état complet de Si les capteurs d ’un agent lui donnent accès à l ’état complet de

l’environnement suffisant pour choisir une action, l ’environnement est accessible l’environnement suffisant pour choisir une action, l ’environnement est accessible à l ’agent (inutile de conserver les changements de l ’environnement).à l ’agent (inutile de conserver les changements de l ’environnement).

Déterministe/Non déterministe.Déterministe/Non déterministe. L ’environnement est déterministe pour un agent si le prochain état de L ’environnement est déterministe pour un agent si le prochain état de

l’environnement est déterminé par l ’état courant et par l ’action de l ’agent.l’environnement est déterminé par l ’état courant et par l ’action de l ’agent.

Episodique/Non épisodique.Episodique/Non épisodique. Un environnement épisodique signifie que les prochaines évolutions ne Un environnement épisodique signifie que les prochaines évolutions ne

dépendent pas des actions déjà réalisées.dépendent pas des actions déjà réalisées.

Statique/Dynamique.Statique/Dynamique. Un environnement qui ne change pas pendant que l ’agent réfléchit est statique.Un environnement qui ne change pas pendant que l ’agent réfléchit est statique.

Discret/Continu.Discret/Continu. Si le nombre de percepts distincts et d ’actions est limité, l’environnement est Si le nombre de percepts distincts et d ’actions est limité, l’environnement est

discret.discret.

Centralisé/DistribuéCentralisé/Distribué Environnement centralisé : tous les agents ont accès à la même structure;Environnement centralisé : tous les agents ont accès à la même structure; Environnement distribué : assemblage de cellules disposées en réseau ; chaque Environnement distribué : assemblage de cellules disposées en réseau ; chaque

cellule gère les influences des agents qui sont localisés sur cette cellule.cellule gère les influences des agents qui sont localisés sur cette cellule.

11

Résolution, Simulation et IntégrationRésolution, Simulation et Intégration

• En En résolution de problème résolution de problème les agents évoluent les agents évoluent par rapport à par rapport à l’environnementl’environnement, sauf dans le cas où le problème consiste à , sauf dans le cas où le problème consiste à organiser les objets dans l’environnement.organiser les objets dans l’environnement.

la donnée du problèmela donnée du problème le contexte dans lequel s’actualisent des règles codées dans les Agents, les le contexte dans lequel s’actualisent des règles codées dans les Agents, les

Interactions et les Organisations.Interactions et les Organisations.L’environnement du SMA peut être L’environnement du SMA peut être DécoupléDécouplé des agents : il ne subit aucune modification par les agents, bien qu’il des agents : il ne subit aucune modification par les agents, bien qu’il

puisse être dynamiquepuisse être dynamique CoupléCouplé avec les agents : réactions aux actions de ceux-ci avec les agents : réactions aux actions de ceux-ci

• En En simulationsimulation, l’environnement d’un SMA est constitué d’un , l’environnement d’un SMA est constitué d’un ensemble d’objets actifs et passifs que l’agent peut manipulerensemble d’objets actifs et passifs que l’agent peut manipuler

• Dans cadre de Dans cadre de l’intégrationl’intégration et des systèmes collaboratifs, et des systèmes collaboratifs, l’environnement d’un SMA est constitué des informations non l’environnement d’un SMA est constitué des informations non contrôlées par le systèmecontrôlées par le système

les agents n’ont pas d’action sur l’environnement, sauf par des canaux les agents n’ont pas d’action sur l’environnement, sauf par des canaux externes au modèle SMA via leur utilisateur.externes au modèle SMA via leur utilisateur.

12

ActionsActions

Une action est mise en oeuvre par un ensemble Une action est mise en oeuvre par un ensemble d’effecteursd’effecteurs..

Dans le cas de la Dans le cas de la simulationsimulation, un effecteur reçoit une commande de , un effecteur reçoit une commande de l’agent et en fonction de cette commande, de la situation de l’agent et en fonction de cette commande, de la situation de l’agent, de l’état de l’environnement, une action pourra être l’agent, de l’état de l’environnement, une action pourra être réalisée.réalisée.

Une action peut être définie :Une action peut être définie : par les mécanismes impliquant une modification de l’environnement par les mécanismes impliquant une modification de l’environnement

physique,physique,

ou ou comme la modification de l’environnement physique résultant de son comme la modification de l’environnement physique résultant de son

application (action) et de la réaction de l’environnement (co-action).application (action) et de la réaction de l’environnement (co-action).

Les co-actions sont gérées par l’environnement.Les co-actions sont gérées par l’environnement.

QuickTime™ et undécompresseur TIFF (LZW)

sont requis pour visionner cette image.

13

Modélisation de l’actionModélisation de l’action

• Transformation d ’un état global (fortement utilisé en Transformation d ’un état global (fortement utilisé en IA en planification)IA en planification)

• Réponse à des influences [Ferber 95]Réponse à des influences [Ferber 95]• Processus informatique (ensemble d’événements Processus informatique (ensemble d’événements

produits et consommés par des processus produits et consommés par des processus informatiques)informatiques)

• Modification locale propagée le long d’un réseau Modification locale propagée le long d’un réseau d’automatesd’automates

• Déplacement physiqueDéplacement physique• CommandeCommande

14

PerceptionPerception

• Mise en oeuvre par un ensemble de Mise en oeuvre par un ensemble de capteurscapteurs..• Dans le cas de la Dans le cas de la simulationsimulation, un capteur est une , un capteur est une

interface entre l’environnement et l’agent.interface entre l’environnement et l’agent.• Dans le cas de la Dans le cas de la résolution de problèmesrésolution de problèmes, la , la

perception est un mécanisme de sélection d’un point perception est un mécanisme de sélection d’un point de vue sur le problème.de vue sur le problème.

• Dans le cas Dans le cas d’intégration et de systèmes collaboratifsd’intégration et de systèmes collaboratifs, , la perception est une interprétation des informations la perception est une interprétation des informations externes.externes.

15

AgentAgent

Une entité réelle ou virtuelle, Une entité réelle ou virtuelle,

• • capable d’agir dans un capable d’agir dans un environnementenvironnement,, Mais avec une capacité de Mais avec une capacité de perception limitperception limitéeée de de son environnement, son environnement, qui ne dispose donc que d’une qui ne dispose donc que d’une reprrepréséseentation partiellentation partielle de cet environnement de cet environnement

(et (et évéveentuellement aucune),ntuellement aucune),

• • peut peut communiquercommuniquer directement avec d’autres agents, directement avec d’autres agents,

• • vise à atteindre un ensemble vise à atteindre un ensemble d’objectifsd’objectifs individuels ou une individuels ou une fonction de satisfaction, voire de survie, qu’elle cherche fonction de satisfaction, voire de survie, qu’elle cherche �� optimiser,optimiser,

• • qui possqui possèdeède des des ressourcesressources propres, propres,

• • qui possqui possédédee des des compcompététeencesnces et offre des et offre des servicesservices,,• qui exhibe un comportement qui exhibe un comportement autonomeautonome, ,

Autonomie : conséquence de ses connaissances, de ses interactions avec Autonomie : conséquence de ses connaissances, de ses interactions avec d'autres agents et des buts qu'il poursuit. d'autres agents et des buts qu'il poursuit.

• capable d’agir de manière capable d’agir de manière flexibleflexible dans un environnement dans un environnement Flexibilité : réactivité, pro-activité, capacités socialesFlexibilité : réactivité, pro-activité, capacités sociales

16

Vision locale et décentraliséeVision locale et décentralisée

La conception d'un système multi-agent impose une La conception d'un système multi-agent impose une vision locale et décentralisée. vision locale et décentralisée.

• locale : locale : chaque agent devient responsable de ses connaissances chaque agent devient responsable de ses connaissances

(encapsulation) et de ses actions(autonomie), mais également de (encapsulation) et de ses actions(autonomie), mais également de l'organisation qu'il met en place avec d'autres agents. l'organisation qu'il met en place avec d'autres agents.

Aucun agent n'a de vue globale du SMA tout entier. Aucun agent n'a de vue globale du SMA tout entier.

• décentralisée : décentralisée : on s'efforce d’éliminer tout contron s'efforce d’éliminer tout contrôôle central.le central. Les tLes tââches à réaliser et les compétences pour le faire sont ches à réaliser et les compétences pour le faire sont

distribuées sur les agents. distribuées sur les agents. Permet une grande modularité Permet une grande modularité

17

Agents situés vs communicantsAgents situés vs communicants

• • Agent purement Agent purement situésitué: : ––l'environnement possède une métrique,l'environnement possède une métrique, ––les agents sont situés à une position dans l'environnement qui les agents sont situés à une position dans l'environnement qui

détermine ce qu'ils perçoivent;détermine ce qu'ils perçoivent; ––ils peuvent se déplacer; ils peuvent se déplacer; ––il n'y a pas communications directes entre agents, elle se font via il n'y a pas communications directes entre agents, elle se font via

l'environnementl'environnement Société de FourmisSociété de Fourmis

––La résolution du problème s'inscrit dans l'environnement La résolution du problème s'inscrit dans l'environnement physique et dans l'organisation physique trouvée par les agents physique et dans l'organisation physique trouvée par les agents

• Agent purement Agent purement communiquantcommuniquant: : ––il n'y a pas d'environnement au sens physique du terme,il n'y a pas d'environnement au sens physique du terme, ––les agents n'ont pas d'ancrage physique, les agents n'ont pas d'ancrage physique, ––ils communiquent via des informations qui circulent entre les agents ils communiquent via des informations qui circulent entre les agents Réseau de décideursRéseau de décideurs

––la résolution du problème s'inscrit dans une structure la résolution du problème s'inscrit dans une structure conceptuelle et dans les modes de coopération entre agentsconceptuelle et dans les modes de coopération entre agents

18

Agents réactifsAgents réactifs

••Agent réactif:Agent réactif: ––pas de représentation explicite de l'environnementpas de représentation explicite de l'environnement ––pas de mémoire de son histoire, ni de but explicitepas de mémoire de son histoire, ni de but explicite ––comportement de type stimulus réponsecomportement de type stimulus réponse – – communication via l’environnementcommunication via l’environnement ––mode "biologique "d'organisation : auto-organisationmode "biologique "d'organisation : auto-organisation ––grand nombre d'agents (>100), homogènes à grain fingrand nombre d'agents (>100), homogènes à grain fin – – validation expérimentalevalidation expérimentale

La structure du système émerge des comportements et non La structure du système émerge des comportements et non d'une volonté d'organisationd'une volonté d'organisation

19

Agents cognitifsAgents cognitifs

Agent cognitif:Agent cognitif: – – représentation explicite de l'environnement et des autres agentsreprésentation explicite de l'environnement et des autres agents

– – peut tenir compte de son passé et dispose d'un but explicitepeut tenir compte de son passé et dispose d'un but explicite• connaissances (beliefs)• buts (intentions)• tâches• plans• Engagements

– – autres agentsautres agents• compétences• intentions

– – mode "social" d'organisation (planification, engagement)-organisation explicitemode "social" d'organisation (planification, engagement)-organisation explicite allocation et dépendances tâchesallocation et dépendances tâches partage des ressourcespartage des ressources protocoles de coordination/négociationprotocoles de coordination/négociation

– – petit nombre d'agents (10/20), hétérogènes à gros grainpetit nombre d'agents (10/20), hétérogènes à gros grain Les relations entre agents s'établissent en fonction des collaborations nécessaires Les relations entre agents s'établissent en fonction des collaborations nécessaires

à la résolution du problèmeà la résolution du problème – – architectures complexes, souvent modèle logique (ex : BDI, Agent0)architectures complexes, souvent modèle logique (ex : BDI, Agent0) – – communication explicite, point à point, élaborée (ex : KQML)communication explicite, point à point, élaborée (ex : KQML) – – certaines validations formelles possiblescertaines validations formelles possibles

20