Problèmes de coordination d’agents réactifs dans un environnement incertain

De l’Intelligence Artificielle à l’Intelligence Artificielle Distribuée

     L’Intelligence Artificielle (IA) est définie comme l’élaboration des programmes informatiques imitant le comportement intelligent humain pour la résolution des problèmes donnés par intégration de capacités mentales de haut niveau tels que : l’apprentissage, l’organisation de la mémoire et le raisonnement [91]. Le but est de donner des notions de rationalité à travers des fonctions de décision autonomes et de perception pour commander un robot dans un milieu qui lui est inconnu. Elle trouve ses origines dans les travaux d’Alan Turing [136], où il propose une expérience connue sous le nom de test de Turing permettant de qualifier une machine de consciente. A la différence de l’IA qui modélise le comportement intelligent d’un seul agent, l’intelligence artificielle distribuée (IAD) s’intéresse à des comportements intelligents qui résultent de l’activité coopérative de plusieurs entités (agents), elle partage la résolution du problème entre différents agents autonomes, dotés de capacités de perception et d’action sur l’environnement [47]. Le but de l’IAD est de concevoir des approches de développement de communautés d’agents intelligents qui puissent interagir de façon coopérative mais aussi conflictuelle ou concurrente afin de résoudre des problèmes complexes. Le partage de la résolution crée, par sa nature, plusieurs problèmes parmi lesquels les plus importants sont ceux du contrôle, de la coordination, de la communication et de l’organisation des agents. Au même moment, une autre révolution a envahi l’IAD, où l’intelligence n’est pas uniquement individuelle mais également collective, provoquant l’établissement du domaine des Systèmes Multi Agents [125].

Agents Cognitifs

       Les agents cognitifs, peuvent résoudre des problèmes compliqués de manière relativement individuelle, du fait qu’ils disposent de capacités cognitives importantes. Leur représentation interne et les mécanismes d’inférence dont ils disposent leur permettent de fonctionner indépendamment des autres agents et leur offrent une grande souplesse dans l’expression de leur comportement [68]. Leur aptitude délibérative s’appuie sur la représentation symbolique de l’univers, des raisonnements à l’aide de systèmes formels et des communications de haut niveau. Ils offrent des temps d’exécution lentes, complexité croissante, fragilité et coût élevé par rapport aux agents réactifs [123]. L’architecture cognitive repose sur le traitement d’informations symboliques et suppose donc l’existence d’un langage sur lequel pourront raisonner les agents [57]. L’une des architectures cognitives les plus connues est l’architecture BDI (Beliefs Desires-Intentions) [111] qui permet aux agents de raisonner sur une base de croyances (Beliefs) pour répondre au but qu’ils se sont fixés (Desires). Ils produisent ensuite des intentions, c’est à dire des actions qu’ils souhaitent effectuer et qui pourront ou non se réaliser

Des agents aux Systèmes Multi-Agents (SMA)

        Depuis les années 80, les systèmes multi-agents ne cessent de se développer et d’étendre leur domaine d’application. Malgré toutes ces années d’existence, aucune définition, que ce soit aussi bien pour le terme d’agent que de système multi-agent, n’a encore fait l’unanimité au sein de la communauté. Le thème des systèmes multi-agents (SMA), s’il n’est pas récent, est actuellement un champ de recherche très actif. Cette discipline est à la connexion de plusieurs domaines en particulier de l’intelligence artificielle, des systèmes informatiques distribués. C’est une discipline qui s’intéresse aux comportements collectifs produits par les interactions de plusieurs entités autonomes et flexibles appelées agents, que ces interactions tournent autour de la coopération, de la concurrence ou de la coexistence entre ces agents [28]. Dans la partie précédente nous avons présenté le concept d’agent isolé comme une entité située dans un environnement qu’elle perçoit et sur lequel elle peut agir. Cette partie se concentre sur des systèmes composés de plusieurs agents. Elle met l’accent sur le concept d’interaction, élément central pour ces systèmes puisqu’il représente ce qui permet de construire une réponse collective à partir de réponses individuelles [135].

Incertitude dans les Systèmes multi-agents

       Des conditions parfaites sont définies lorsque le système est parfaitement modélisé : les capteurs et les effecteurs des agents soit d’une précision irréprochable et que la portée soit illimitée et que l’agent connaisse exactement les états et les comportements des autres agents et qu’il peut communiquer avec eux à tout moment. Ces conditions ne sont souvent pas respectées dans un environnement réel ce qui conduit à un certain nombre d’incertitudes lors de décision d’un agent (voir robot mobile). Ces incertitudes dans un système multi-agents ou même dans un agent sont dues à certaines raisons qui dépendent des systèmes mis en place et de l’environnement dans lequel évolue les agents :
– Imprécision et limitation des capteurs– la perception à travers des capteurs permet à un agent de maintenir une connaissance de sa position ainsi qu’une connaissance sur les éléments composant le système. Les capteurs permet donc de détecter l’espace navigable sous la forme d’un nuage de points délimitant ce qui est obstacle de ce qui ne l’est pas avec une certaine précision. L’imprécision des capteurs causée par leurs capacités limitées ou par le bruit entraine des incertitudes sur l’information perçue. En plus, quelque soit le type de capteur, il ne permet généralement pas de percevoir tout l’environnement mais un champs de vision de celui ci. Tout ce qui hors champs de vision du capteur est considéré comme non-observable et donc incertain.
– Imprécision des effecteurs et manque de connaissance sur l’environnement– des incertitudes sur les résultats des actions des agents surviennent à cause de la modélisation incomplète de l’environnement. La modélisation incomplète de l’environnement est due principalement au concepteur pour lequel il été impossible de dégager toutes les cas ou les paramètres intervenant dans l’évolution du système. Cette incomplétude entrainera une perte de précision des données modélisées.
– Interaction entre agents et le non contrôle d’événements extérieurs aux agents– L’agent n’a généralement qu’une observabilité partielle des états des autres agents et leur comportement. Le fait que les agent entrent en interaction avec d’autres agents, leurs actions conduisent donc à des effets non envisagés. Le fait que l’agent n’a pas de connaissance des actions des autres agents, cela ajoute un certain degré d’incertitude sur ses actions.

Intelligence en essaim et auto-organisation

       L’intelligence en essaim (intelligence collective ou swarm intelligence en anglais) a été introduit pour la première fois par Gerardo Beni et Jing Wang en 1989 [11]. Le mot “essaim” évoque l’image d’un grand nombre de petits insectes où chaque individu effectue une tâche simple, mais dont l’action produit un comportement complexe dans son ensemble [74]. Les essaims sont définis comme des collections de nombreuses individus simples qui interagissent avec les autres individus et l’environnement en utilisant des formes de contrôle décentralisé et auto-organisée pour atteindre leurs objectifs [90]. La combinaison de leurs comportements simples ou microscopiques provoque des actions beaucoup plus complexes et macroscopiques, qui permettent à l’ensemble du système d’obtenir des résultats remarquables dans son ensemble. Par conséquent, l’intelligence en essaim fournit un nouveau cadre de travail pour la conception et l’implémentation de systèmes comprenant de nombreux agents qui sont capables de coopérer afin de résoudre des problèmes très complexes. Les agents disposent de capacités très limitées. Ils ne peuvent percevoir et agir que sur leur environnement immédiat, ne sont capables de communiquer que de manière indirecte en déposant de l’information dans l’environnement, ne possèdent généralement aucune mémoire et ne réalisent leurs décisions qu’en réagissant à leur perceptions. Les avantages d’une telle approche sont multiples :
– robustesse : la défaillance d’éléments individuels ne dégrade pas significativement les performances de l’ensemble du système.
– simplicité : le comportement individuel est simple, mais encore il permet de réduire la complexité des individus.
– évolutivité : les mécanismes de contrôle utilisés ne dépendent pas du nombre des agents au sein d’un essaim.
Dans la nature, l’intelligence en essaim peut être observée dans les variétés de systèmes (voir Figure 2.1). Le mouvement coordonné de troupeaux d’oiseaux ou des groupes de poissons sont des exemples emblématiques du domaine. Chaque individus oiseau ou poisson actes de sa façon et surtout n’as aucun contrôle sur les autres, ni est conscient de ce que le groupe dans son ensemble est en train de faire. En résultat, le mouvement du groupe et sa cohésion paraissent comme une seule entité contrôlée par un cerveau unique. Les insectes sociaux, tels que les fourmis, les termites, les abeilles et les guêpes forment les exemples les plus étonnants de l’intelligence en essaim. Les foules peuvent aussi présenter des comportements d’intelligent en essaim. Des exemples peuvent êtres observés dans les mouvements des piétons. Normalement, chaque individus se déplace librement vers sa destination, mais dans des conditions de haute densité, les mouvements sont limités et des modèles émergent souvent [49]. Les actions des individus qui interagissent localement conduit à des comportements collectifs qui semblent être guidé par une volonté unique et contrôlé par une seule entité. Cette forme de comportements collectifs est appelée comportements auto-organisés. Bounabeau [15] définie l’autoorganisation comme l’ensemble de mécanismes dynamiques à partir desquels les structures apparaissent au niveau globale du système via des interactions entre ses composants de niveau locale . Ces interactions sont exécutés sur la base des informations purement locales, sans référence au modèle globale, qui est une propriété émergente du système plutôt qu’une propriété imposée sur le système. Typiquement, les approches relevant de l’intelligence en essaim s’inspirent principalement de deux disciplines, la physique et la biologie. De la physique s’est inspiré les champs de potentiels qui reposent sur l’utilisation de champs vectoriels. Ainsi chaque point de l’espace est associé à un vecteur [5] [17] [75]. Ce type d’approches s’est utilisé pour des problèmes de navigation [68], de foraging [123] et d’optimisation pour le positionnement d’usines [93]. Un principal problème de cette approche est les maxima et les minima locaux qui peuvent piéger les agents. De la biologie s’est inspiré les approches à base de phéromones, connus aussi sous le nom stigmergie, un mode de communication indirecte entre agents . En effet, les insectes sociaux (termites, fourmis, araignées sociales…) utilisent l’environnement comme moyen de communication indirecte via le dépôt des phéromones. Ces dernières ont été la source d’inspiration des phéromones digitales, l’équivalent artificiel des phéromones naturels que les agents inscrivent sur une matrice modélisant l’environnement. Ainsi plusieurs algorithmes basés sur le dépôt de phéromones ont été développés : algorithmes de foraging [15], ACO [43] , coordination entre drones [103]. Les phéromones digitales font l’avantage d’adaptabilité au changement de l’environnement grâce aux propriétés de diffusion et d’évaporation.

Le rapport de stage ou le pfe est un document d’analyse, de synthèse et d’évaluation de votre apprentissage, c’est pour cela rapport-gratuit.com propose le téléchargement des modèles complet de projet de fin d’étude, rapport de stage, mémoire, pfe, thèse, pour connaître la méthodologie à avoir et savoir comment construire les parties d’un projet de fin d’étude.

Table des matières

1 Positionnement scientifique
2 Problématique de la recherche
3 Objectifs de la recherche et contributions
4 Plan de la thèse
1 Les Systèmes Multi-Agents 
1 Introduction 
2 Agent : Concepts Fondamentaux 
2.1 La Diversité des Définitions
2.2 Classification
2.2.1 Réactifs
2.2.2 Agents Cognitifs
2.2.3 Agents Hybrides
2.3 La notion d’agent dans le cadre de notre travail
3 Des agents aux Systèmes Multi-Agents (SMA) 
3.1 Définitions
3.2 Environnement
3.3 Interaction
3.4 Organisation
3.5 SMA dans le cadre de notre travail
4 Mécanismes de coordination multi-agents 
4.1 Définitions
4.2 Pourquoi coordonner ?
4.3 Mise en œuvre des mécanismes de coordination
4.3.1 Structuration Organisationnelle
4.3.2 Allocation
4.3.3 Planification
4.3.4 Négociation
4.3.5 Coordination réactive
5 Incertitude dans les Systèmes multi-agents 
6 Application des Systèmes Multi-Agents 
7 Conclusion 
2 Contexte applicatif et travaux reliés 
1 Introduction 
2 Intelligence en essaim et robotique en essaim 
2.1 Intelligence en essaim et auto-organisation
2.2 Robotique en essaim
2.2.1 Qu’est ce que la Robotique en essaim ?
2.2.2 Propriétés souhaitables des systèmes de robotique en essaim
3 Exploration multi-agents 
3.1 Définition
3.2 Approches existantes
4 Foraging Multi-Agents
4.1 Définitions
4.2 Modèle de référence
4.3 Approches existantes
4.4 Nouvelle taxonomie de foraging
4.5 Comparaison qualitative des approches de Foraging
5 Conclusion 
3 Algorithmes proposés pour les problèmes d’exploration et de foraging multi-agents 
1 Introduction 
2 Contributions majeures de notre recherche
2.1 Stigmergic Multi-Ant Search Area (S-MASA)
2.2 C-CMFA : Algorithme de foraging Multi-Agents
2.2.1 Algorithme de la vague
2.2.2 Ré-examen de l’algorithme de la vague
2.2.3 Ré-examen de l’algorithme de la vague et de l’algorithme cmarking
2.2.4 Algorithme C-CMFA
2.3 Algorithme C-SAF
2.4 EC-SAF : algorithme de foraging multi-agents avec gestion d’énergie
2.4.1 Algorithme Ec-marking
2.5 Framework pour le foraging Multi-Agents
3 Conclusion 
4 Mise en Œuvre et Expérimentations 
1 Introduction
2 Résultats de simulation
2.1 Résultats obtenus par S-MASA
2.1.1 Pour le problème de recherche des échantillons
2.1.2 Pour le problème de couverture Multi-Agents
2.2 Résultats obtenus par C-CMFA
2.2.1 Indices de performances, paramètres et scénarios de simulation
2.2.2 Résultats de simulations et comparaisons
2.3 Résultats obtenus par C-SAF
2.3.1 Indices de performance et scénarios de simulation
2.3.2 Résultats de simulation
2.4 Résultats Obtenus par EC-SAF
2.4.1 Indices de performance et paramètres de simulation
2.4.2 Scénarios de simulation
2.4.3 Résultats de simulation
3 Conclusion 
Conclusion générale et perspectives
1 Bilan des travaux et apports de la thèse
2 Perspectives
1 Revues internationales (avec comité de lecture)
2 Conférences internationales (avec comité de lecture)
3 Conférences nationales (avec comité de lecture)
Bibliographie

Télécharger le rapport complet

Télécharger aussi :

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée. Les champs obligatoires sont indiqués avec *