Proposition d'une approche auto-organisationnelle pour le partage de ressources critiques

For this work, we study situated agent systems to address the resource sharing problem. We show that multi-agent systems manifest good characteristics for dynamic and open industrial applications. The resource sharing problems are complex systems : the sub-parts of these problems are interrelated. Also, they are combinatorial optimization problems, i.e., the solution space of these instances of problem is unusually-large. In this context, we propose a generic approach to benefit from the complexity of decentralized relations between agents to fit the complex relations of this class of problem. Moreover, it is necessary to efficiently conduct the system state toward a satisfying configuration standing for a solution to the sharing problem, among a large space of possibilities. The multi-agent systems address the resource sharing problems as a decentralized negotiation prob- lem. While decentralizing the problem, we meet a correlation need between the local behaviours of agents with respect to the global characteristics for the problems. For the resource sharing problems, a defective coordination of the global agent activity leads to a dysfunction qualified as hyperactivity of agents, which one prohibits to reach the solution : the agents form and propagate disturbances through the resolution process. We propose an indirect communication mediated by the environment (stigmergy) as a mean to coordinate the global activity of agents. This one allows to express the influence of past behaviours of agents, remaining in the environnement, on futur behaviours. Thus, a part of the study consists in finding a model to decentralize the resource sharing problem, and get an efficient support for social interactions between negotiating agents, providing a mean to broadcast complex informations for the global coordination. The next step consists in exhibiting an emergent perception for the system in order to cover appro- priately the set of configurations to estimate. The system moves along the configurations while explor- ing and exploiting in order to build a solution for the sharing problem. While exploring, it attempts to elaborate new possible patterns, while exploiting, the system autocatalyticly reinforces the elaborated combinations it perceives as relevant (i.e. the more a pattern is relevant, the more it is exploited). We underline some resolving difficulties through three agent models. For the first model, the agents participate to a spatial negotiation of available machine locations which constitute the critical resources. We meet an hyperactivity phenomena for agents which prevent to abord efficiently the problem. We propose an other model to control the agent activity with a hierarchical relation between too heterarchical resolution groups of agents. Our conclusion on the two models leads us to improve the capacity for the system to perceive the complexe relations for the sharing problems, and to innovate with a new approach : CESNA (Complex Exchange between Stigmergic Negotiating Agents). In order to represent the complex characteristics of the problem, the negotiation takes place through a negotiating network. The network contains contracts to validate/invalidate which represent the possible assignments of agents to resources and the constraints between agents allocations. In this context, agents negotiate to validate/invalidate contracts fitting their needs with respect to the needs of other agents. We measure some performances that can be confronted with some of specific optimisation methods for the graph coloring problem. These good results underline the emergent perception and sef-organizing capacities resulting from complex interaction between agents, which encourage to establish a new way to address the complex resource sharing problems with multi-agents systems.Le travail présenté dans cette thèse s'intéresse à la modélisation de systèmes à base d'agents (situés) pour la résolution de problèmes de partage de ressources critiques. Nous voyons que les systèmes multi-agents manifestent des caractéristiques qui les rendent appropriés à l'implantation industrielle en environnement ouvert et dynamique. Le problème de partage de ressources critiques exhibe les caractéristiques des systèmes complexes (interactions rétroactives entre les sous-parties du problème), et peut s'exprimer d'un point de vue algorithmique comme un problème d'optimisation combinatoire (accroissement exponentiel du nombre de combinaisons à évaluer pour les résoudre lorsque la taille des problèmes augmente). Dans le cadre de la modélisation générique que nous proposons pour ce problème, nous devons donc corréler la complexité des relations héritées du problème avec la complexité des relations liées à la décentralisation des agents en interaction. Nous devons aussi permettre une convergence rapide du système modélisé vers une configuration satisfaisante qui matérialise une solution pour le problème traité, parmi un grand ensemble de configurations disponibles. Les systèmes multi-agents abordent le problème de partage de ressources critiques comme un problème de négociation décentralisée. En décentralisant le processus de résolution, on se confronte à la difficulté de corrélation de comportements locaux par rapport aux propriétés globales du système. Nous contribuons par cette étude à identifier des limitations des approches multi-agents, et proposons deux modèles qui illustrent ces difficultés : une mauvaise coordination de l'ensemble de l'activité des agents entraîne un dysfonctionnement qualifié de `suractivité agent' qui enraille la convergence vers une solution recherchée. Ceci nous amène à envisager le défaut de 'suractivité' comme un problème de perception décentralisée, et à proposer une approche innovante : CESNA (Complex Exchanges between Stigmergic Negotiating Agents). Des agents négocient à travers un réseau la validation de contrats qui leur conviennent. Lorsque tous les agents sont satisfaits, on obtient une solution pour le problème. Certaines mesures montrent la diffusion d'informations de coordination complexes du niveau local (des agents) au niveau global (du système) et vice versa à travers le réseau de négociation. Nous mesurons par ailleurs des performances de résolution comparables à celles que l'on connaît pour les approches spécifiques de coloration de graphe. Ces résultats prometteurs soulignent les capacités de perception émergente et d'auto-organisation résultats d'interactions complexes entre les agents, ils mettent à jour la pertinence de cette nouvelle façon d'envisager les relations complexes entre agents pour le partage de ressources critiques. Il nous semble intéressant d'envisager l'expression des relations complexes que nous proposons pour d'autres domaines applicatifs