Télécharger le fichier original (Mémoire de fin d’études)

Les Systèmes Multi-Agents (SMA)

Définition

Un agent est une entité physique (voiture, ordinateur, …) ou virtuelle (logiciel,…) [Ferber, 1995]. Un agent est autonome, est capable d’agir et communique avec d’autres agents à l’aide de messages. Il est certes autonome mais fortement dépendant des autres. Il n’a qu’une vision ou représentation partielle de tout ce qui se passe dans son environnement. L’agent peut être comparé à un « organisme vivant », car il communique, agit et se reproduit (éventuellement). Pour communiquer, les agents s’envoient des messages de plusieurs types dont les deux principaux sont :
– Un message à plusieurs autres agents, par exemple pour signaler ou demander quelque chose,
– Un message à un seul agent, par exemple pour répondre à une question.
Les agents évoluent dans un Système Multi-Agents (SMA). Qu’est ce qu’un SMA ?
Un Système Multi-Agents4 peut être défini par l’ensemble {E, O, A, R, Op} où :
E représente l’environnement,
O est l’ensemble des objets qui peuvent être créés, modifiés et détruits par les agents, A représente les agents qui sont des objets particuliers, A est inclus dans O, R indique l’ensemble des relations liant les objets, Op est l’ensemble des opérations permettant aux agents de A d’agir sur les objets de O. L’environnement fournit les moyens par lesquels les agents vont pouvoir interagir. Il est le coordinateur des interactions et le lieu de contraintes sur les dynamiques possibles des agents. Quelle est la différence entre objet et agent ?
Les objets ne sont pas des agents, ils n’ont ni but, ni recherche de satisfaction. Les agents ont une certaine autonomie que les objets ne possèdent pas. Les agents sont définis à un niveau conceptuel alors que les objets sont définis aux niveaux d’implémentation et d’exécution. Un objet encapsule les données et les méthodes pour pouvoir agir dessus, un agent a en plus la possibilité de contrôler son comportement. Un SMA peut être vu comme une organisation d’agents (par analogie avec une organisation humaine). En effet, un SMA évolue dans un environnement, a des buts à atteindre et les agents opèrent ensemble pour atteindre ces buts. Les éléments
4 Les SMA sont nés sous le nom d’Intelligence Artificielle Distribuée aux Etats-Unis et d’Intelligence Artificielle Décentralisée en Europe.
Les Systèmes Multi-Agents (SMA)
essentiels dans cette organisation sont la nature de l’environnement dans lequel est placée l’organisation, la nature des tâches effectuées par les agents, la structure de contrôle, de communication et de collaboration entre les agents. Le comportement d’un agent est déterminé par un ensemble d’états et de règles internes, qui peuvent être de simples clauses « que faire si… » ou alors des algorithmes beaucoup plus sophistiqués basés sur l’apprentissage. Les agents sont en interaction entre eux par échanges d’informations, négociation, collaboration… Au sein des SMA, la communication est l’un des moyens privilégiés utilisés pour échanger des informations entre agents (plans, résultats partiels, buts, etc.). La capacité de communiquer et de coopérer des agents s’appuie sur leurs aptitudes de perception, d’apprentissage, de planification et de raisonnement.
L’interaction, définie comme étant une mise en relation dynamique de deux ou plusieurs agents par le biais d’un ensemble d’actions réciproques [Ferber, 1995], constitue un niveau supérieur à la notion de communication et d’action. Il faut savoir combiner ces éléments (communications et actions) afin de coordonner et de contrôler les échanges entre plusieurs agents pour avoir un comportement collectif cohérent du système et arriver à cette interaction. Domaines d’application Avant de passer à l’implémentation d’une solution informatique, il faut d’abord penser à quelle méthodologie et démarche adopter. Quand faut-il utiliser les SMA pour résoudre un problème ?
– Quand le problème est trop complexe mais peut être décomposé
– Quand il n’y a pas de solution générale ou lorsque celle-ci est trop coûteuse en CPU
– A des fins de modélisation (populations, structures moléculaires, …)
– Quand on peut paralléliser le problème (gain de temps)
– Quand on veut une certaine robustesse (redondance)
– Quand l’expertise provient de différentes sources
– Quand les données, contrôles, ressources sont distribués
– Quand le système doit être adaptatif
Les domaines d’applications des SMA sont immense et peuvent être classés en cinq principales catégories :
– La résolution de problèmes décrit les situations dans lesquelles les tâches accomplies par les agents sont utiles aux êtres humains,
– La simulation multi-agent permet d’expliquer et de prévoir les phénomènes naturels, par la représentation du monde informatique sous forme informatique,
– La construction de mondes hypothétiques répond aux problèmes synthétiques, non réels, basés sur des hypothèses et des suppositions et n’utilise pas des agents physiques,
– La robotique distribuée porte sur la création de robot et utilise des agents concrets évoluant dans un monde réel,

Modélisation et simulation

Modélisation

Un modèle, en science, est une image simplifiée et abstraite d’une partie de la réalité. L’intérêt d’un modèle, est d’être plus explicite, plus simple et plus facile à manipuler que la réalité qu’il représente [Ferber, 1995]. La modélisation consiste à créer un modèle abstrait partant d’un phénomène observé. Ce modèle abstrait est manipulé grâce à des déductions, des raisonnements et des calculs pour aboutir à une prévision et une anticipation du modèle futur. La modélisation permet de transcrire un système dans un certain langage pour pouvoir l’étudier plus aisément (des équations différentielles, par exemple). La modélisation est importante dans le domaine des SMA, et s’explique pour les quatre raisons suivantes : les actions des agents, le comportement et mécanique interne d’un agent, l’interaction entre agents, et enfin l’évolution du SMA.
Les Systèmes Multi-Agents (SMA) Il n’existe pas de règles strictes et figées pour le bon déroulement d’une modélisation. Il faut malgré tout passer par les étapes suivantes, pour tendre à obtenir un modèle cohérent et réaliste :
– La définition des objectifs, c’est-à-dire le pourquoi du modèle, sa raison d’être,
– L’analyse du système pour bien délimiter le cadre expérimental ou l’environnement,
– La conception ou construction du modèle,
– L’implantation : étape de recherches d’informations, d’implémentation du modèle dans un langage de programmation et de validation du modèle,
– L’utilisation du modèle.
Contrairement aux approches classiques de résolution de problèmes, une modélisation à base d’agents permet de prendre en compte plusieurs constituants d’un système complexe (découpage en sous- systèmes simples à résoudre). La complexité émergeant des interactions entre ces constituants, il est nécessaire de les appréhender pour maîtriser le système. La modélisation part d’abord de la structure interne de l’agent, ensuite elle prend en compte la vue globale qui porte sur l’interaction entre les agents, sans se soucier des détails des mécanismes de fonctionnement de l’agent. Cette démarche va du détail vers le global.
Les SMA offrent une vue nouvelle sur la conception logicielle en général, car plaçant l’interaction au premier plan. En effet, dans un SMA, les agents ont une interaction complexe et continu, cette interaction est dynamique, elle varie rapidement dans le temps, et elle est imparfaitement prévisible. Ceci est dû à la complexité du système, aux possibilités d’interactions (nombre d’agents, d’actions) et à l’évolution du système dans le temps, entraînant ainsi l’impossibilité de prévoir la date d’arrivée d’un message même si l’on connaît sa date de départ et son destinataire. Cette interaction permet aux agents d’aboutir à une solution valide ou satisfaisante du problème. Ce n’est pas l’agent, ni le nombre d’agents, qui apporte une solution mais le fait qu’il y ait interaction dans le système Les agents sont principalement difficiles à programmer car la correction du comportement dépend des détails de la situation de l’agent dans son environnement. De même, les interactions nécessitent une formalisation, un modèle qui permette leur spécification, leur description et leur vérification. Nous avons donc besoin d’une méthode de conception, d’un formalisme, qui intègre à la fois le côté agent et le côté interaction d’un SMA. De plus, pour réaliser une modélisation d’un phénomène complexe par l’intermédiaire d’un SMA, il nous faut une description formelle et sans ambiguïté du système, une spécification claire de ses propriétés attendues et un moyen de vérification de la satisfaction de ces spécifications.
La validation du modèle est basée sur une comparaison entre les observations et la dynamique de la simulation. Après modélisation du comportement des agents et de leurs interactions, on paramètre le système et on simule des situations expérimentales connues. En fonction du décalage entre l’observation et la simulation, on applique le modèle. Une fois le calibrage effectué, on extrapole en faisant jouer de Les Systèmes Multi-Agents (SMA) nouveaux scénarii en supposant que le comportement du simulateur demeure fidèle à la réalité.
Simulation
La simulation consiste à analyser les propriétés de modèles théoriques du monde réel. L’usage de la simulation est très fréquent dans des disciplines diverses telles que la géographie pour essayer d’expliquer et de prévoir les phénomènes de la nature, l’évolution de l’environnement. La simulation multi-agent est issue de 3 idées :
– Utiliser des modèles centrés sur les entités et leurs interactions
– Considérer que la dynamique générale du système est issue des interactions entre ces entités
– Faire l’hypothèse que des processus informatiques (les agents) sont capables de décrire le comportement des entités.

Table des matières

INTRODUCTION
1. PRESENTATION DU SUJET
1.1. PROBLEMATIQUE
1.2. DOMAINE D’APPLICATION
2. LES SYSTEMES D’INFORMATIONS GEOGRAPHIQUES (SIG)
2.1. DEFINITION.
2.2. MODE DE REPRESENTATION
2.3. POURQUOI FAIRE DU SIG ET DOMAINES D’APPLICATION ?
3. LES SYSTEMES MULTI-AGENTS (SMA)
3.1. DEFINITION
3.2. DOMAINES D’APPLICATION
3.3. MODELISATION ET SIMULATION
4. INVENTAIRE ET ANALYSE DE L’EXISTANT
5. CONCEPTION DU SYSTEME
5.1. LA CONCEPTION DU SIG
5.1.1. Choix outil SIG.
5.1.2. Concepts de base
5.1.3. Démarche adoptée
5.2. LE MODELE CONCEPTUEL
5.2.1. Diagramme des cas d’utilisation
5.2.2. Principe de segmentation
5.2.3. Principe de déplacement des segments
5.3. LE MODELE STATIQUE UML
5.3.1. Dictionnaire des données
5.3.2. Diagramme de classes
5.4. LE MODELE DYNAMIQUE UML
5.4.1. Diagrammes de séquences
5.4.2. Diagrammes d’états
5.4.3. Diagrammes d’activités
5.5. L’AGENTIFICATION
6. REALISATION ET IMPLEMENTATION
6.1. CHOIX DES OUTILS
6.2. RECUPERATION DES OBJETS GRAPHIQUES
6.3. SIMULATION
6.4. RETOUR DU RESULTAT DE LA SIMULATION DANS LE SIG
6.5. DESSINS D’ECRANS
7. DISCUSSIONS
CONCLUSION ET PERSPECTIVES
BIBLIOGRAPHIE
SIGLES ET ACRONYMES
LISTE DES FIGURES
LISTE DES TABLEAUX
LISTE DES ECRANS
ANNEXES

Télécharger le rapport complet