Academic literature on the topic 'Processus décisionnel de Markov(MDP)'

Les processus décisionnels de Markov (MDPs) modélisent des problèmes de décisionsséquentielles dans lesquels un utilisateur interagit avec l’environnement et adapte soncomportement en prenant en compte les signaux de récompense numérique reçus. La solutiond’unMDP se ramène à formuler le comportement de l’utilisateur dans l’environnementà l’aide d’une fonction de politique qui spécifie quelle action choisir dans chaque situation.Dans de nombreux problèmes de décision du monde réel, les utilisateurs ont despréférences différentes, donc, les gains de leurs actions sur les états sont différents et devraientêtre re-décodés pour chaque utilisateur. Dans cette thèse, nous nous intéressonsà la résolution des MDPs pour les utilisateurs ayant des préférences différentes.Nous utilisons un modèle nommé MDP à Valeur vectorielle (VMDP) avec des récompensesvectorielles. Nous proposons un algorithme de recherche-propagation qui permetd’attribuer une fonction de valeur vectorielle à chaque politique et de caractériser chaqueutilisateur par un vecteur de préférences sur l’ensemble des fonctions de valeur, où levecteur de préférence satisfait les priorités de l’utilisateur. Etant donné que le vecteurde préférences d’utilisateur n’est pas connu, nous présentons plusieurs méthodes pourrésoudre des MDP tout en approximant le vecteur de préférence de l’utilisateur.Nous introduisons deux algorithmes qui réduisent le nombre de requêtes nécessairespour trouver la politique optimale d’un utilisateur: 1) Un algorithme de recherchepropagation,où nous propageons un ensemble de politiques optimales possibles pourle MDP donné sans connaître les préférences de l’utilisateur. 2) Un algorithme interactifd’itération de la valeur (IVI) sur les MDPs, nommé algorithme d’itération de la valeurbasé sur les avantages (ABVI) qui utilise le clustering et le regroupement des avantages.Nous montrons également comment l’algorithme ABVI fonctionne correctement pourdeux types d’utilisateurs différents: confiant et incertain.Nous travaillons finalement sur une méthode d’approximation par critére de regret minimaxcomme méthode pour trouver la politique optimale tenant compte des informationslimitées sur les préférences de l’utilisateur. Dans ce système, tous les objectifs possiblessont simplement bornés entre deux limites supérieure et inférieure tandis que le systèmeine connaît pas les préférences de l’utilisateur parmi ceux-ci. Nous proposons une méthodeheuristique d’approximation par critère de regret minimax pour résoudre des MDPsavec des récompenses inconnues. Cette méthode est plus rapide et moins complexe queles méthodes existantes dans la littérature
Markov decision processes (MDPs) are models for solving sequential decision problemswhere a user interacts with the environment and adapts her policy by taking numericalreward signals into account. The solution of an MDP reduces to formulate the userbehavior in the environment with a policy function that specifies which action to choose ineach situation. In many real world decision problems, the users have various preferences,and therefore, the gain of actions on states are different and should be re-decoded foreach user. In this dissertation, we are interested in solving MDPs for users with differentpreferences.We use a model named Vector-valued MDP (VMDP) with vector rewards. We propose apropagation-search algorithm that allows to assign a vector-value function to each policyand identify each user with a preference vector on the existing set of preferences wherethe preference vector satisfies the user priorities. Since the user preference vector is notknown we present several methods for solving VMDPs while approximating the user’spreference vector.We introduce two algorithms that reduce the number of queries needed to find the optimalpolicy of a user: 1) A propagation-search algorithm, where we propagate a setof possible optimal policies for the given MDP without knowing the user’s preferences.2) An interactive value iteration algorithm (IVI) on VMDPs, namely Advantage-basedValue Iteration (ABVI) algorithm that uses clustering and regrouping advantages. Wealso demonstrate how ABVI algorithm works properly for two different types of users:confident and uncertain.We finally work on a minimax regret approximation method as a method for findingthe optimal policy w.r.t the limited information about user’s preferences. All possibleobjectives in the system are just bounded between two higher and lower bounds while thesystem is not aware of user’s preferences among them. We propose an heuristic minimaxregret approximation method for solving MDPs with unknown rewards that is faster andless complex than the existing methods in the literature

Cette thèse s'intéresse à la problématique de la coordination de plusieurs agents autonomes dans un environnement réel. Cela implique la prise en compte de l'incertitude dans la réalisation des actions et du comportement des autres agents, ainsi que d'une certaine dynamicité de l'environnement. Nous avons basé notre travail sur le formalisme des processus décisionnels de Markov (MDP) qui permet d'intégrer les incertitudes dans le processus de raisonnement. Afin de prendre en compte les interactions avec les autres agents, nous avons formalisé celles-ci et intégré les interactions au sein d'un processus de décision en ligne. Ce processus est une extension des MDP où les agents cherchent à optimiser leurs gains personnels, ainsi que le bien-être du groupe. Il en découle un problème de décision multi-critères, auquel nous avons proposé une solution. Une fois ce formalisme établi, nous avons pu aborder plusieurs problèmes de coordination comme : la formation de convois, la couverture spatiale et la formation de coalitions. Ces problèmes nous ont permis d'appliquer avec succès les principes établis en début de thèse. Les extensions de ce travail traiteront l'apprentissage en ligne, et la théorie des jeux afin de permettre la détection et la résolution de cas d'inter-blocages
This thesis deals with the coordination of a group of autonomous agents in the real world. So, we have to take into account uncertainty about action's outcome, about other agent's behavior and also the changes in the environment. We are using Markov decision processes (MDP), whose allow to manage those uncertainties in a decision process. In order to manage the interactions with the other agents, we give a formalism to express them, and also we give a solution to integrate them in a on-line decision process. This is an extension of the Markov Decision Processes where the agent are trying to optimize their own reward as well as the welfare of the group. This is a mutlicriteria decision problem, and we give it a solution. Once this formalism built, we tackle some classical coordination problems : platooning, spatial coverage, coalitions formation. Those applications allow us to apply with success the principle given at the beginning of the thesis. The extensions of this work will be dealing with on-line learning, and also game theory in order to detect and to solve deadlocks

Les robots vont être de plus en plus utilisés dans les domaines civils, comme dans le domaine militaire. Ces robots, opérant en flottes, peuvent accompagner des soldats au combat, ou accomplir une mission en étant supervisés par un poste de contrôle. Du fait des exigences d'une opération militaire, il est difficile de laisser les robots décider de leurs actions sans accord d'un opérateur ou surveillance, en fonction de la situation. Dans cette thèse, nous nous attardons sur deux problématiques:D'une part, nous cherchons à exploiter l'autonomie ajustable de sorte à ce qu'un robot puisse accomplir sa mission de la manière la plus efficace possible, tout en respectant des restrictions assignées par un opérateur sur son niveau d'autonomie. Pour cela, celui-ci est en mesure de définir pour un ensemble d'états et d'actions donné un niveau de restriction. Ce niveau peut par exemple imposer au robot la télé-opération pour accéder à une zone à risque.D'autre part, comme nous envisageons la possibilité que plusieurs robots soient déployés en même temps, ces robots doivent se coordonner pour accomplir leurs objectifs. Seulement, comme les opérateurs peuvent prendre le contrôle de certains d'entre eux, la question de la coordination se pose. En effet, l'opérateur ayant ses propres préférences, perception de l'environnement, connaissances et étant sujet aux stress, hésitations, il est difficile de prévoir les actions que celui-ci va effectuer, et donc de s'y coordonner. Nous proposerons dans cette thèse une approche visant à estimer la politique exécutée par un robot télé-opéré à partir d'apprentissage basé sur les actions observés de ce robot.La notion de planification est très présente dans ces travaux. Ceux-ci se baseront sur des modèles de planifications comme les Processus Décisionnels de Markov
Robots will be more and more used in both civil and military fields. These robots, operating in fleet, can accompany soldiers in fight, or accomplish a mission while being supervised by a control center. Considering the requirement of a military operation, it is complicated to let robots decide their action without an operator agreement or watch, in function of the situation.In this thesis, we focus on two problematics:First, we try to exploit adjustable autonomy to make a robot accomplishes is mission as efficiency as possible, while he respects restrictions, assigned by an operator, on his autonomy level. For this, it is able to define for given sets of states and actions a restriction level. This restriction can force, for example, the need of being tele-operated to access a dangerous zone.Secondly, we consider that several robots can be deployed at the same time. These robots have to coordinate to accomplish their objectives. However, since operators can take the control of some robots, the coordination is harder. In fact, the operator has preferences, perception, hesitation, stress that are not modeled by the agent. It is then hard to estimate his next actions, so to coordinate with him. We propose in this thesis an approach to estimate the policy executed by a tele-operated robot from learning methods, based on observed actions from this robot.The notion of planning his important in these works. These are based on planning models, such as Markov Decision Processes

La régulation adaptative des feux de signalisation est un problème très important. Beaucoup de chercheurs travaillent continuellement afin de résoudre les problémes liés à l’embouteillage dans les intersections urbaines. Il devient par conséquent très utile d’employer des algorithmes intelligents afin d’améliorer les performances de régulation et la qualité du service. Dans cette thèse, nous essayons d'étudier ce problème d’une part à travers une modèlisation microscopique et dynamique en temps discret, et d’autre part en explorant plusieurs approches de résoltion pour une intersection isolée ainsi que pour un réseau distribué d'intersections.La première partie se concentre sur la modélisation dynamique des problèmes des feux de signalisation ainsi que de la charge du réseau d’intersections. Le mode de la “séquence de phase adaptative” (APS) dans un plan de feux est d'abord considéré. Quant à la modélisation du contrôle des feux aux intersections, elle est formulée grâce à un processus décisionnel de markov (MDP). En particulier, la notion de “l'état du système accordable” est alors proposée pour la coordination du réseau de trafic. En outre, un nouveau modèle de “véhicule-suiveur” est proposé pour l'environnement de trafic. En se basant sur la modélisation proposée, les méthodes de contrôle des feux dans cette thèse comportent des algorithmes optimaux et quasi-optimaux. Deux algorithmes exacts de résolution basées sur la programmation dynamique (DP) sont alors étudiés et les résultats montrent certaines limites de cette solution DP surtout dans quelques cas complexes où l'espace d'états est assez important. En raison de l’importance du temps d’execution de l'algorithme DP et du manque d'information du modèle (notamment l’information exacte relative à l’arrivée des véhicules à l’intersection), nous avons opté pour un algorithme de programmation dynamique approximative (ADP). Enfin, un algorithme quasi-optimal utilisant l'ADP combinée à la méthode d’amélioration RLS-TD (λ) est choisi. Dans les simulations, en particulier avec l'intégration du mode de phase APS, l'algorithme proposé montre de bons résultats notamment en terme de performance et d'efficacité de calcul
Adaptive traffic signal control is a decision making optimization problem. People address this crucial problem constantly in order to solve the traffic congestion at urban intersections. It is very popular to use intelligent algorithms to improve control performances, such as traffic delay. In the thesis, we try to study this problem comprehensively with a microscopic and dynamic model in discrete-time, and investigate the related algorithms both for isolated intersection and distributed network control. At first, we focus on dynamic modeling for adaptive traffic signal control and network loading problems. The proposed adaptive phase sequence (APS) mode is highlighted as one of the signal phase control mechanisms. As for the modeling of signal control at intersections, problems are fundamentally formulated by Markov decision process (MDP), especially the concept of tunable system state is proposed for the traffic network coordination. Moreover, a new vehicle-following model supports for the network loading environment.Based on the model, signal control methods in the thesis are studied by optimal and near-optimal algorithms in turn. Two exact DP algorithms are investigated and results show some limitations of DP solution when large state space appears in complex cases. Because of the computational burden and unknown model information in dynamic programming (DP), it is suggested to use an approximate dynamic programming (ADP). Finally, the online near-optimal algorithm using ADP with RLS-TD(λ) is confirmed. In simulation experiments, especially with the integration of APS, the proposed algorithm indicates a great advantage in performance measures and computation efficiency

Ce travail de thèse propose deux contributions: (i) la formalisation et la résolution approchée du problème d'échantillonnage adaptatif optimal dans les champs de Markov et (ii) la modélisation du problème d'échantillonnage d'une espèce adventice au sein d'une parcelle cultivée et la conception de stratégies d'échantillonnage adaptatives de cette espèce. Pour le premier point, nous avons d'abord formulé le problème du choix d'une stratégie d'échantillonnage adaptative optimale comme un Processus Décisionnel de Markov (PDM) à horizon fini. Nous avons ensuite proposé un algorithme de résolution approchée de tout PDM à horizon fini dont le modèle est connu. Cet algorithme, nommé Least Square Dynamic Programming (LSDP), combine les concepts de programmation dynamique et d'apprentissage par renforcement. Il a ensuite été adapté pour la conception de stratégies d'échantillonnage adaptatives pour tout type de champ de Markov et tout type de coût d'observation. En pratique, l'algorithme LSDP permet une résolution approchée de problèmes d'échantillonnage de plus grande taille qu'avec la plupart des algorithmes classiques d'apprentissage par renforcement. Pour le deuxième point, nous avons d'abord modélisé la répartition spatiale d'une espèce adventice à l'aide des champs de Markov. Un modèle de coût d'échantillonnage d'une espèce adventice a également été proposé. Ces deux modèles ont ensuite été utilisés pour concevoir de nouvelles stratégies d'échantillonnage adaptatives d'une espèce. Une étude sur données réelles a démontré la supériorité des stratégies adaptatives sur des stratégies statiques, classiquement utilisées en échantillonnage adventice
This work is divided into two parts: (i) the theoretical study of the problem of adaptive sampling in Markov Random Fields (MRF) and (ii) the modeling of the problem of weed sampling in a crop field and the design of adaptive sampling strategies for this problem. For the first point, we first modeled the problem of finding an optimal sampling strategy as a finite horizon Markov Decision Process (MDP). Then, we proposed a generic algorithm for computing an approximate solution to any finite horizon MDP with known model. This algorithm, called Least-Squared Dynamic Programming (LSDP), combines the concepts of dynamic programming and reinforcement learning. It was then adapted to compute adaptive sampling strategies for any type of MRF distributions and observations costs. An experimental evaluation of this algorithm was performed on simulated problems. For the second point, we first modeled the weed spatial repartition in the MRF framework. Second, we have built a cost model adapted to the weed sampling problem. Finally, both models were used together to design adaptive sampling strategies with the LSDP algorithm. Based on real world data, these strategies were compared to a simple heuristic and to static sampling strategies classically used for weed sampling

Cette thèse porte sur la résolution de problèmes de décision séquentielle sous incertitude,modélisés sous forme de processus décisionnels de Markov (PDM) dont l’espace d’étatet d’action sont tous les deux de grande dimension. La résolution de ces problèmes avecun bon compromis entre qualité de l’approximation et passage à l’échelle est encore unchallenge. Les algorithmes de résolution dédiés à ce type de problèmes sont rares quandla dimension des deux espaces excède 30, et imposent certaines limites sur la nature desproblèmes représentables.Nous avons proposé un nouveau cadre, appelé PDMF3, ainsi que des algorithmesde résolution approchée associés. Un PDMF3 est un processus décisionnel de Markov àespace d’état et d’action factorisés (PDMF-AF) dont non seulement l’espace d’état etd’action sont factorisés mais aussi dont les politiques solutions sont contraintes à unecertaine forme factorisée, et peuvent être stochastiques. Les algorithmes que nous avonsproposés appartiennent à la famille des algorithmes de type itération de la politique etexploitent des techniques d’optimisation continue et des méthodes d’inférence dans lesmodèles graphiques. Ces algorithmes de type itération de la politique ont été validés sur un grand nombre d’expériences numériques. Pour de petits PDMF3, pour lesquels la politique globale optimale est disponible, ils fournissent des politiques solutions proches de la politique globale optimale. Pour des problèmes plus grands de la sous-classe des processus décisionnels de Markov sur graphe (PDMG), ils sont compétitifs avec des algorithmes de résolution de l’état de l’art en termes de qualité. Nous montrons aussi que nos algorithmes permettent de traiter des PDMF3 de très grande taille en dehors de la sous-classe des PDMG, sur des problèmes jouets inspirés de problèmes réels en agronomie ou écologie. L’espace d’état et d’action sont alors tous les deux de dimension 100, et de taille 2100. Dans ce cas, nous comparons la qualité des politiques retournées à celle de politiques expertes. Dans la seconde partie de la thèse, nous avons appliqué le cadre et les algorithmesproposés pour déterminer des stratégies de gestion des services écosystémiques dans unpaysage agricole. Les adventices, plantes sauvages des milieux agricoles, présentent desfonctions antagonistes, étant à la fois en compétition pour les ressources avec la cultureet à la base de réseaux trophiques dans les agroécosystèmes. Nous cherchons à explorerquelles organisations du paysage (ici composé de colza, blé et prairie) dans l’espace etdans le temps permettent de fournir en même temps des services de production (rendementen céréales, fourrage et miel), des services de régulation (régulation des populationsd’espèces adventices et de pollinisateurs sauvages) et des services culturels (conservationd’espèces adventices et de pollinisateurs sauvages). Pour cela, nous avons développé unmodèle de la dynamique des adventices et des pollinisateurs et de la fonction de récompense pour différents objectifs (production, maintien de la biodiversité ou compromisentre les services). L’espace d’état de ce PDMF3 est de taille 32100, et l’espace d’actionde taille 3100, ce qui en fait un problème de taille conséquente. La résolution de ce PDMF3 a conduit à identifier différentes organisations du paysage permettant d’atteindre différents bouquets de services écosystémiques, qui diffèrent dans la magnitude de chacune des trois classes de services écosystémiques
This PhD thesis focuses on the resolution of problems of sequential decision makingunder uncertainty, modelled as Markov decision processes (MDP) whose state and actionspaces are both of high dimension. Resolution of these problems with a good compromisebetween quality of approximation and scaling is still a challenge. Algorithms for solvingthis type of problems are rare when the dimension of both spaces exceed 30, and imposecertain limits on the nature of the problems that can be represented.We proposed a new framework, called F3MDP, as well as associated approximateresolution algorithms. A F3MDP is a Markov decision process with factored state andaction spaces (FA-FMDP) whose solution policies are constrained to be in a certainfactored form, and can be stochastic. The algorithms we proposed belong to the familyof approximate policy iteration algorithms and make use of continuous optimisationtechniques, and inference methods for graphical models.These policy iteration algorithms have been validated on a large number of numericalexperiments. For small F3MDPs, for which the optimal global policy is available, theyprovide policy solutions that are close to the optimal global policy. For larger problemsfrom the graph-based Markov decision processes (GMDP) subclass, they are competitivewith state-of-the-art algorithms in terms of quality. We also show that our algorithmsallow to deal with F3MDPs of very large size outside the GMDP subclass, on toy problemsinspired by real problems in agronomy or ecology. The state and action spaces arethen both of dimension 100, and of size 2100. In this case, we compare the quality of thereturned policies with the one of expert policies. In the second part of the thesis, we applied the framework and the proposed algorithms to determine ecosystem services management strategies in an agricultural landscape.Weed species, ie wild plants of agricultural environments, have antagonistic functions,being at the same time in competition with the crop for resources and keystonespecies in trophic networks of agroecosystems. We seek to explore which organizationsof the landscape (here composed of oilseed rape, wheat and pasture) in space and timeallow to provide at the same time production services (production of cereals, fodder andhoney), regulation services (regulation of weed populations and wild pollinators) andcultural services (conservation of weed species and wild pollinators). We developed amodel for weeds and pollinators dynamics and for reward functions modelling differentobjectives (production, conservation of biodiversity or trade-off between services). Thestate space of this F3MDP is of size 32100, and the action space of size 3100, which meansthis F3MDP has substantial size. By solving this F3MDP, we identified various landscapeorganizations that allow to provide different sets of ecosystem services which differ inthe magnitude of each of the three classes of ecosystem services

Pour bien fonctionner, une application répartie nécessite de communiquer
et d'échanger des informations entre ces différentes entités. Les agents
mobiles apparaissent dans ce contexte comme une solution prometteuse
permettant la construction d'applications flexibles, adaptables aux
contraintes de l'application et de l'environnement d'exécution. Dans
cette thèse, la mobilité est étudiée sous deux angles. D'une part,
l'envoi du code sur le serveur permet d'adapter les services distants
aux exigences du client ce qui permet la réduction du trafic réseau.
D'autre part, une machine surchargée peut déléguer l'exécution de
certaines de ces tâches à une autre machine ce qui permet de gagner au
niveau du temps d'exécution. Une architecture basée sur la technologie
d'agents mobiles est proposée. Elle permet l'équilibrage de charge dans
une application répartie. L'architecture proposée est décentralisée et
l'équilibrage de charge se fait d'une façon dynamique. Un agent mobile
collecteur est utilisé afin de construire une vision globale du système.
Pour la réduction du trafic, nous proposons la communication par un
agent intelligent hybride. L'agent utilise ainsi deux modes,
client/serveur ou migration (échange locale), pour sa communication. Le
processus décisionnel de Markov est utilisé pour trouver la politique
optimale du déplacement de l'agent. Un travail d'expérimentation sur des
problèmes concrets permet de valider les algorithmes proposés.

Cette thèse traite de la conception de système multi-agents. Elle se focalise sur des approches formelles et s'est donné pour objectif à long terme de construire de manière automatique et décentralisée les comportements d'agents coopératifs devant résoudre collectivement un problème. Ce travail a cherché à proposer des méthodes pour construire les comportements d'agents sociaux, capables de prendre en compte à l'exécution la présence d'autres agents dans le système.

Les formalismes existants comme les DEC-POMDPs parviennent à représenter des problèmes multi-agents mais ne représentent pas au niveau individuel la notion d'interaction fondamentale dans les systèmes collectifs. Ceci induit une complexité algorithmique importante dans les algorithmes de résolution. Afin de donner aux agents la possibilité d'appréhender la présence d'autres agents et de structurer de manière implicite les systèmes multi-agents, cette thèse propose un formalisme original, l'interac-DEC-POMDP inspiré des DEC-POMDPs et d'Hamelin, une simulation développée au cours de cette thèse et issue d'expériences conduites en éthologie. La spécificité de ce formalisme réside dans la capacité offerte aux agents d'interagir directement et localement entre eux. Cette possibilité permet des prises de décision à un niveau intermédiaire entre des décisions globales impliquant l'ensemble des agents et des décisions purement individuelles.

Nous avons proposé en outre un algorithme décentralisé basé sur des techniques d'apprentissage par renforcement et une répartition heuristique des gains des agents au cours des interactions. Une démarche expérimentale nous a permis de valider sa capacité à produire pour des restriction du formalisme des comportements collectifs pertinents adaptatifs sans qu'aucun agent ne dispose d'une vue globale du système.

Un parcours de golf est composé de dix-huit trous. Sur chaque trou, le problème du golfeur est de déplacer la balle d'un point de départ prédéfini jusqu'au drapeau en un minimum de coups. Sous certaines hypothèses, ce problème peut se modéliser comme un problème de plus court chemin stochastique (PCCS). Le problème du PCCS est un processus de Markov particulier dans lequel un agent évolue dynamiquement dans un ensemble fini d'états. En chaque état, l'agent choisis une action, induisant un coût, qui le mène en un autre état en suivant une distribution de probabilité connue. Il existe également un état `puits' particulier dans lequel, une fois atteint, on reste avec une probabilité un et un coût de zéro. Le but de l'agent est, depuis un état initial, d'atteindre l'état puits en un coût moyen minimal. Dans un premier chapitre, nous étudions de manière théorique le problème du PCCS. Après avoir redéfini un cadre d'étude dans lequel nous avons affaibli les hypothèses d'existence d'une solution optimale, nous avons prouvé que les algorithmes classiques de résolution convergent dans ce nouveau cadre. Nous avons également défini un nouvel algorithme de résolution basé sur l'algorithme primal-dual. Dans le deuxième chapitre, nous détaillons la modélisation du problème d'optimisation de stratégies au golf en un problème de PCCS. Grâce à la base de données Shotlink, nous définissons des `clones numériques' de joueurs que nous pouvons faire jouer artificiellement sur différents parcours de golf afin de prédire les scores des joueurs. Nous avons appliqué ce modèle à deux compétitions : le master d'Augusta en 2017 et la Ryder Cup en 2018. Dans un troisième et dernier chapitre, nous étudions l'extension naturelle à deux joueurs du problème du PCCS : les jeux de plus courts chemins stochastiques. Nous étudions particulièrement les formulations programmation linéaire de ces jeux et de deux cas particuliers de ceux-ci
A golf course consists of eighteen holes. On each hole, the golfer has to move the ball from the tee to the flag in a minimum number of shots. Under some assumptions, the golfer's problem can be modeled as a stochastic shortest path problem (SSP). SSP problem is a special case of Markov Decision Processes in which an agent evolves dynamically in a finite set of states. In each state, the agent chooses an action that leads him to another state following a known probability distribution. This action induces a cost. There exists a `sink node' in which the agent, once in it, stays with probability one and a cost zero. The goal of the agent is to reach the sink node with a minimum expected cost. In the first chapter, we study the SSP problem theoretically. We define a new framework in which the assumptions needed for the existence of an optimal policy are weakened. We prove that the most famous algorithm still converge in this setting. We also define a new algorithm to solve exactly the problem based on the primal-dual algorithm. In the second chapter we detail the golfer's problem model as a SSP. Thanks to the Shotlink database, we create `numerical clones' of players and simulate theses clones on different golf course in order to predict professional golfer's scores. We apply our model on two competitions: the master of Augusta in 2017 and the Ryder Cup in 2018. In the third chapter, we study the 2-player natural extension of SSP problem: the stochastic shortest path games. We study two special cases, and in particular linear programming formulation of these games

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