Planifier les actions d’un agent dans un environnement dynamique et incertain, a été largement étudié et le cadre des processus décisionnels de Markov offre les outils permettant de modéliser et de résoudre de tels problèmes. Le domaine de la théorie des jeux, a permis l’étude des interactions stratégiques entre plusieurs agents pour un jeu donné. Le cadre des jeux stochastiques, est considéré comme une généralisation du domaine des processus décisionnels de Markov et du champ de la théorie des jeux et permet de modéliser des systèmes ayant plusieurs agents et plusieurs états. Cependant, planifier dans unsystème multi-agents est considéré comme difficile, car la politique d’actions de l’agent dépend non seulement de ses choix mais aussi des politiques des autres agents. Le travail que nous présentons dans cette thèse porte sur la prise de décision distribuée dans les systèmes multi-agents. Les travaux existants dans le domaine, permettent la résolution théorique des jeux stochastiques mais imposent de fortes restrictions et font abstraction de certains problèmes cruciaux du modèle. Nous proposons un algorithme de planification décentralisée pour le modèle des jeux stochastiques, d’une part basé sur l’algorithme Value-Iteration et d’autre part basé sur la notion d’équilibre issue de la résolution des jeux matriciels. Afin d’améliorer le processus de résolution et de traiter des problèmes de taille importante, nous recherchons à faciliter la prise de décision et à limiter les possibilités d’actions à chaque étape d’interaction. L’algorithme que nous avonsproposé, a été validé sur un exemple d’interaction incluant plusieurs agents et différentes expérimentations ont été menées afin d’évaluer la qualité de la solution obtenue. / Planning agent’s actions in a dynamic and uncertain environment has been extensively studied. The framework of Markov decision process provides tools to model and solve such problems. The field of game theory has allowed the study of strategic interactions between multiple agents for a given game. The framework of stochastic games is considered as a generalization of the fields of Markov decision process and game theory. It allows to model systems with multiple agents and multiple states. However, planning in a multi-agent system is considered difficult : agent’s decisions depend not only on its actions but also on actions of the other agents. The work presented in this thesis focuses on decision making in distributed multi-agent systems. Existing works in this field allow the theoretical resolution of stochastic games but place severe restrictions and ignore some crucial problems of the model. We propose a decentralized planning algorithm for the model of stochastic games. Our proposal is based on the Value-Iteration algorithm and on the concept of Nash equilibrium. To improve the resolution process and to deal with large problems, we sought to ease decision making and limit the set of joint actions at each stage. The proposed algorithm was validated on a coordination problem including several agents and various experiments were conducted to assess the quality of the resulting solution.
| Identifer | oai:union.ndltd.org:theses.fr/2012VALE0014 |
| Date | 03 April 2012 |
| Creators | Hamila, Mohammed Amine |
| Contributors | Valenciennes, Mandiau, René, Grislin, Emmanuelle, Mouaddib, Abdel-Illah |
| 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.0013 seconds