Ces travaux abordent la problématique du contrôle endogène dans les Systèmes Multi-Agents (SMA) pour la résolution de problèmes complexes, que nous explorons grâce au problème de partage de ressources critiques. Les problèmes dits complexes que nous abordons se caractérisent par une explosion combinatoire du nombre de solutions avec la taille des problèmes, une forte dynamique des données du problème induite par un environnement ouvert dans lequel de nombreux événements peuvent avoir lieu, une grande complexité systémique issue des interdépendances entre les nombreuses variables du problèmes et enfin une décentralisation du processus de résolution imposée par une distribution physique et fonctionnelle des variables incompatible avec une vision centralisée du problème. Un parcours complet des espaces de recherche associés à de tels problèmes est irréaliste en un temps acceptable, il est alors nécessaire d'employer des méthodes de résolution dite incomplètes. Quelque soit l'approche incomplète considérée, le parcours incomplet de l'espace de recherche requiert un contrôle afin de maximiser la probabilité de converger vers une solution satisfaisante. Nous identifions trois niveaux de contrôle du parcours de l'espace de recherche indépendamment de l'approche utilisée : un contrôle statique (définition a priori du comportement du système), un contrôle dynamique (évoluant en cours de résolution selon des mécanismes préétablis) et un contrôle adaptatif (évoluant dynamiquement en cours de résolution). Nous montrons qu'un contrôle endogène de l'activité du système, c.-à-d. un contrôle adaptatif issu de l'activité même des agents, est nécessaire au guidage du parcours de l'espace de recherche dans le contexte de résolution de problèmes complexes. Ces travaux ayant été réalisés dans un contexte de collaboration industrielle, ils s'appuient sur une approche développée au cours de précédents travaux : CESNA (Complex Exchanges between Stigmergic Negotiating Agents). CESNA est une approche multi-agents auto-organisationnelle exploitant des agents situés dans un environnement matérialisant le problème et exploité par un processus de résolution basé sur une négociation stigmergique entre les agents. Le cas applicatif utilisé par l'approche CESNA et permettant d'illustrer ces travaux est le problème de partage de ressources critiques, caractérisé par un ensemble restreint de ressources exploitées par un grand nombre de consommateurs. Nos contributions sont de deux types : nous avons dans un premier temps proposé des évolutions de la représentation du problème exploitée par l'approche initiale (CESNA) afin d'en supprimer les limitations interdisant un passage à l'échelle, et dans un second temps, nous avons défini un nouveau modèle (MANA : Multi-level bAlancing Negotiating Agents) exploitant cette nouvelle représentation à l'aide d'un nouveau processus de résolution basé sur des mécanismes endogènes de contrôle de l'activité du système. Ces mécanismes reposent sur la matérialisation des effets microscopiques du phénomène macroscopique à orienter (le parcours de l'espace de recherche) afin de le rendre perceptible localement par les agents. Nos mesures montrent que ce nouveau modèle permet le passage à l'échelle (la résolution de problèmes industriels de grande taille) et une amélioration significative des performances de résolution par rapport à l'approche initiale montrant ainsi l'efficacité du guidage permis par les mécanismes utilisés. / This work addresses the issue of the endogenous control of Multi-Agents Systems (MAS) for solving complex problems, which we explore through the critical resources sharing problem. The complex problems we address are characterized by a combinatorial explosion of number of solutions with the size of the problems, a strong dynamic of the problem's data caused by an open environment in which many events can take place, a huge systemic complexity caused by the interdependencies between the many variables of the problem and a decentralization of the resolution process imposed by a physical and functional distribution of the variables incompatible with a centralized view of the problem. A complete course of the search space associated with such problems is unrealistic in an acceptable time, it is necessary to employ resolution methods known as incomplete. Whatever the incomplete approach considered, the incomplete course of the search space requires a control to maximize the probability of converging to a satisfactory solution. We identify three levels of control of the course of the search space regardless of the used approach : a static control (textit a priori definition of the behavior of the system), a dynamic control (evolving during the resolution according to pre-established mechanisms) and adaptive control (dynamically evolving during resolution). We show that an endogenous control of the system activity, ie. an adaptive control from the agents activity, is necessary to guide the course of the search space in the context of solving complex problems. This work was made in a context of industrial collaboration, they rely on an approach developed in previous work : CESNA (Complex Exchanges Between Stigmergic Negotiating Agents). CESNA is a multi-agent self-organizational approach using agents situated in an environment embodying the problem and used by a resolution process based on a stigmergic negotiation between agents. The application used by the CESNA approach allowing to illustrate this work is the critical resources sharing problem, characterized by a limited set of resources exploited by many consumers. Our contributions are of two kinds : we initially proposed changes in the representation of the problem used by the initial approach (CESNA) to remove restrictions prohibiting scalability, and in a second time we defined a new model (MANA : Multi-level balancing Negotiating Agents) using this new representation with a new resolution process based on endogenous control mechanisms of the system activity. These mechanisms are based on the materialization of the microscopic effects of the macroscopic phenomenon to direct (the path in the search space) to make it noticeable by agents. Our measurements show that this new model allows the scaling (the resolution of industrial problems) and a significant performances improvement of the resolution showing the effectiveness of the control allowed by the mechanisms used.
| Identifer | oai:union.ndltd.org:theses.fr/2010LYO10138 |
| Date | 05 October 2010 |
| Creators | Lefevre, Olivier |
| Contributors | Lyon 1, Hassas, Salima, Armetta, Frédéric |
| Source Sets | Dépôt national des thèses électroniques françaises |
| Language | French |
| Detected Language | French |
| Type | Electronic Thesis or Dissertation, Text |
Page generated in 0.0024 seconds