Using heuristic belief points for Dec-POMDP planning

Utilisation de croyances heuristiques pour la planification multi-agent dans le cadre des Dec-POMDP

Gabriel Corona (1)

1 MAIA - Autonomous intelligent machine

In this thesis, we focus on planning in decentralised sequential decision taking in uncertainty. In the centralised case, the MDP and POMDP frameworks leads to efficient planning algorithms. The Dec-POMDP framework is used to model decentralised problems. This kind of problems is in a higher class of complexity than the centralised problem. For this reason, until recently, only very small problem could be solved and only for very small horizons. Recently, some heuristic algorithms have been proposed to handle problem of higher size but there is no theoretic proof of the solution quality. In this thesis, we show how to use a heuristic information in the problem, modelled as a probability distribution on the centralised beliefs, to guide the search for a good approximate policy. Using this heuristic information, we formulate each time step of the planning procedure as a combinatorial optimisation problem. This formulation leads to policies of better quality than previously existing approaches.

Nous nous intéressons dans cette thèse à la planification pour les problèmes de prise de décision décentralisée séquentielle dans l'incertain. Dans le cadre centralisé, l'utilisation des formalismes MDP et POMDP a permis d'élaborer des techniques de planification efficaces. Le cadre Dec-POMDP permet de formaliser les problèmes décentralisés. Ce type de problèmes appartient à une autre classe de complexité que les problèmes centralisés. Pour cette raison, jusqu'à récemment, seuls de très petits problèmes pouvaient être résolus et uniquement pour des horizons très faibles. Des algorithmes heuristiques ont récemment été proposés pour traiter des problèmes de taille plus conséquente mais n'ont pas de preuve théorique de qualité de solution. Nous montrons comment une information heuristique sur le problème à résoudre représentée par une distribution de probabilité sur les croyances centralisées permet de guider la recherche approchée de politique. Cette information heuristique permet de formuler chaque étape de la planification comme un problème d'optimisation combinatoire. Cette formulation conduit à des politiques de meilleure qualité que les approches existantes.

Mots clés: artificial intelligence; multi-agent systems; Markov models; planning

Mots clés: intelligence artificielle; systèmes multi-agent; modèles de Markov; planification

Domaines: Informatique [cs]

Gabriel Corona. Utilisation de croyances heuristiques pour la planification multi-agent dans le cadre des Dec-POMDP. Informatique [cs]. Université Henri Poincaré - Nancy 1, 2011. Français. ⟨NNT : 2011NAN10026⟩. ⟨tel-01746167v2⟩