Contribution à la résolution des processus de décision markoviens décentralisés

Abstract : The subject of this thesis is the optimal resolution of decentralized Markov decision processes (DEC-POMDPs). The DEC-POMDP model has been introduced in 2000 and constitutes a formal framework for describing cooperative distributed decision problems under uncertainty. We present a first generalized overview for solving DEC-POMDPs optimally, including game theory, multi-agent planning and reinforcement learning. Our contributions constitute a theoretical approach for building optimal multi-agent systems. Solving DEC-POMDPs can be separated into two categories. If the underlying model of the system is known in advance, the optimal solution can be planned prior execution in a centralized way. We introduce two new planning algorithms. The first one is a point-based multi-agent dynamic programming approach, which constitutes a synthesis of classical multi-agent dynamic programming, and point-based dynamic programming for single-agent POMDPs. Our approach is hence able to concentrate the computational effort on the relevant regions of the policy space. The second approach is an entirely new way of applying heuristic search techniques, such as A*, to decentralized decision problems. We introduce multi-agent A* (MAA*), the first heuristic search algorithm for solving DEC-POMDPs, both over finite and infinite horizons. If the underlying model is not known, an optimal policy can be obtained by a trial-and-error approach based on reinforcement learning methods. We analyse the additional constraints in multi-agent learning vs. planning, before introducing a new multi-agent reinforcement learning algorithm based on mutual notifications of changes in the value function.
Document type :
Theses
Complete list of metadatas

https://hal.univ-lorraine.fr/tel-01754296
Contributor : Thèses Ul <>
Submitted on : Friday, March 30, 2018 - 9:43:59 AM
Last modification on : Tuesday, April 24, 2018 - 1:30:04 PM

File

SCD_T_2006_0146_SZER.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : tel-01754296, version 1

Collections

Citation

Daniel Szer. Contribution à la résolution des processus de décision markoviens décentralisés. Autre [cs.OH]. Université Henri Poincaré - Nancy 1, 2006. Français. ⟨NNT : 2006NAN10146⟩. ⟨tel-01754296⟩

Share

Metrics

Record views

22

Files downloads

41