Scaling Up Decentralized MDPs Through Heuristic Search
Résumé
Decentralized partially observable Markov decision processes (Dec-POMDPs) are rich models for cooperative decision-making under uncertainty, but are often intractable to solve optimally (NEXP-complete). The transition and observation independent Dec-MDP is a general subclass that has been shown to have complexity in NP, but optimal algorithms for this subclass are still inefficient in practice. In this paper, we first provide an updated proof that an optimal policy does not depend on the histories of the agents, but only the local observations. We then present a new algorithm based on heuristic search that is able to expand search nodes by using constraint optimization. We show experimental results comparing our approach with the state-of-the-art DecMDP and Dec-POMDP solvers. These results show a reduction in computation time and an increase in scalability by multiple orders of magnitude in a number of benchmarks.
Les processus décisionnels de Markov répartis constituent un formalisme très riche pour la modélisation des systèmes coopératifs, mais leur complexité reste hors de portée (NEXP-complet). Le formalisme des Dec-MDPs avec transitions et observations indépendantes est une sous classe dont la complexité est NP, mais les algorithmes exacts pour cette classe restent ineficaces. Dans ce papier, nous offrons une nouvelle preuve de l'optimalité des politiques de Markov pour ce formalisme. Puis, nous présentons un nouvel algorithme de recherche heuristique capable explorer l'espace de recherche sur la base des techniques d'optimisation sous contraintes. Nous démontrons enfin que l'algorithme ainsi construit offre les meilleurs performances sur l'ensemble des instances testées.