//img.uscri.be/pth/67c4579e2aa792c93b9712fdc87ebffd608456c8
Cet ouvrage fait partie de la bibliothèque YouScribe
Obtenez un accès à la bibliothèque pour le lire en ligne
En savoir plus

Des programmes mathématiques pour les processus décisionnels de Markoff décentralisés et partiellement observés, Mathematical programming methods for decentralized POMDPs

De
215 pages
Sous la direction de François Charpillet, Alain Dutech
Thèse soutenue le 23 octobre 2008: Nancy 1
Nous étudions le problème du contrôle optimale décentralisé d'un processus de Markoff partiellement observé sur un horizon fini. Mathématiquement, ce problème se défini comme un DEC-POMDP. Plusieurs problèmes des domaines de l'intélligence artificielles et recherche opérationelles se formalisent comme des DEC-POMDPs. Résoudre un DEC-POMDP dans une mannière exacte est un problème difficile (NEXP-dur). Pourtant, des algorithmes exactes sont importants du point de vue des algorithmes approximés pour résoudre des problèmes pratiques. Les algorithmes existants sont nettement inefficace même pour des DEC-POMDP d'une très petite taille. Dans cette thèse, nous proposons une nouvelle approche basée sur la programmation mathématique. En utilisant la forme séquentielle d'une politique, nous montrons que ce problème peut être formalisé comme un programme non-linéaire. De plus, nous montrons comment transformer ce programme nonl-linéaire un des programmes linéaire avec des variables bivalents et continus (0-1 MIPs). L'éxpérience computationelle sur quatres problèmes DEC-POMDP standards montrent que notre approche trouve une politique optimale beaucoup plus rapidement que des approches existantes. Le temps réduit des heures aux seconds ou minutes.
-Planification sur l'incertitude multi-agents processus décisionnels de Markoffs observabilité partielle décentalisation
In this thesis, we study the problem of the optimal decentralized control of a partially observed Markov process over a finite horizon. The mathematical model corresponding to the problem is a decentralized POMDP (DEC-POMDP). Many problems in practice from the domains of artificial intelligence and operations research can be modeled as DEC-POMDPs. However, solving a DEC-POMDP exactly is intractable (NEXP-hard). The development of exact algorithms is necessary in order to guide the development of approximate algorithms that can scale to practical sized problems. Existing algorithms are mainly inspired from POMDP research (dynamic programming and forward search) and require an inordinate amount of time for even very small DEC-POMDPs. In this thesis, we develop a new mathematical programming based approach for exactly solving a finite horizon DEC-POMDP. We use the sequence form of a control policy in this approach. Using the sequence form, we show how the problem can be formulated as a mathematical progam with a nonlinear object and linear constraints. We thereby show how this nonlinear program can be linearized to a 0-1 mixed integer linear program (MIP). We present two different 0-1 MIPs based on two different properties of a DEC-POMDP. The computational experience of the mathematical programs presented in the thesis on four benchmark problems (MABC, MA-Tiger, Grid Meeting, Fire Fighting) shows that the time taken to find an optimal joint policy is one or two orders or magnitude lesser than the exact existing algorithms. In the problems tested, the time taken drops from several hours to a few seconds or minutes.
Source: http://www.theses.fr/2008NAN10092/document
Voir plus Voir moins




AVERTISSEMENT

Ce document est le fruit d'un long travail approuvé par le
jury de soutenance et mis à disposition de l'ensemble de la
communauté universitaire élargie.

Il est soumis à la propriété intellectuelle de l'auteur. Ceci
implique une obligation de citation et de référencement lors
de l’utilisation de ce document.

Toute contrefaçon, plagiat, reproduction illicite encourt une
poursuite pénale.


➢ Contact SCD Nancy 1 : theses.sciences@scd.uhp-nancy.fr




LIENS


Code de la Propriété Intellectuelle. articles L 122. 4
Code de la Propriété Intellectuelle. articles L 335.2- L 335.10
http://www.cfcopies.com/V2/leg/leg_droi.php
http://www.culture.gouv.fr/culture/infos-pratiques/droits/protection.htm ´D´epartement de formation doctorale en informatique Ecole doctorale IAEM Lorraine
UFR STMIA
Mathematical Programming Methods
For Decentralized POMDPs
`THESE
pr´esent´ee et soutenue publiquement le le 23 octobre, 2008
pour l’obtention du
Doctorat de l’universit´e Henri Poincar´e – Nancy 1
(sp´ecialit´e informatique)
par
Raghav Aras
Composition du jury
Rapporteurs : Nadine Piat, Professeur, Universit´e De Franche-Comt´e, Besan¸con
Shlomo Zilberstein, Professeur, University Of Massachussetts, Amherst
Examinateurs : Ren´e Schott, Professeur, Universit´e Henri-Poincar´e, Nancy
Philippe Mathieu, Professeur, Universit´e De Lille
Franc¸ois Charpillet, Directeur De Recherche, INRIA
Alain Dutech, Charg´e De Recherche, INRIA
Laboratoire Lorrain de Recherche en Informatique et ses Applications — UMR 7503Mis en page avec la classe thloria.iiiTable of Contents
Liste des tableaux xi
I Manuscrit Français 1
1 Planifier dans les problèmes décentralisés 3
1.1 Les problèmes décentralisés . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Exemples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.3 Modéliser les problèmes décentralisés . . . . . . . . . . . . . . . . . . . . . . . 6
1.4 Contributions de la thèse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.5 Plan de la thèse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2 Contrôle décentralisé d’un processus de Markov 11
2.1 Le modèle DEC-POMDP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.2 Politique et politique jointe . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.2.1 Valeur d’une politique jointe . . . . . . . . . . . . . . . . . . . . . . . 13
2.2.2 Politique optimale jointe . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.3 Algorithmes existants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.4 Bilan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
3 Politique en formulation séquentielle 17
3.1 Historique et ensemble d’information . . . . . . . . . . . . . . . . . . . . . . . 17
3.1.1 Politique sous forme séquentielle . . . . . . . . . . . . . . . . . . . . . 18
3.2 Contraintes de politique et programmation linéaire . . . . . . . . . . . . . . . 19
3.3 Formulation séquentielle d’un DEC-POMDP . . . . . . . . . . . . . . . . . . 20
3.4 Programmation mathématique et DEC-POMDP . . . . . . . . . . . . . . . . 22
4 Une approche d’optimisation combinatoriale 23
4.1 Linéarisation du problème . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
4.2 Une linéarisation améliorée . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
iiiiv Table of Contents
4.3 Vers des programmes linéaire mixtes entiers . . . . . . . . . . . . . . . . . . . 26
4.4 Bilan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
5 Approche à base d’équilibre de Nash optimal 29
5.1 Définitions préliminaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
5.1.1 Meilleure réponse et équilibre de Nash . . . . . . . . . . . . . . . . . . 29
5.1.2 Regret d’un historique . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
5.1.3 Des contraintes complémentaires comme conditions nécessaires . . . . 31
5.2 Séparer les contraintes linéaires . . . . . . . . . . . . . . . . . . . . . . . . . . 33
5.3 Un programme mixte entier pour 2 agents . . . . . . . . . . . . . . . . . . . . 34
5.4 Un programme mixte entier pour 3 agents et plus . . . . . . . . . . . . . . . 34
5.5 Bilan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
6 Heuristiques et Programmation Dynamique 37
6.1 Historiques localement superflus . . . . . . . . . . . . . . . . . . . . . . . . . 37
6.2 identifer et éliminer les historiques localement superflus . . . . . . . . . . . . 38
6.3 Historiques globalement superflus . . . . . . . . . . . . . . . . . . . . . . . . 39
6.4 Identifier et éliminer les historiques globalement superflus . . . . . . . . . . . 39
6.5 Modification des Programmes Linéaires Mixtes Entiers . . . . . . . . . . . . . 40
6.6 Coupures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
6.7 Bilan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
7 Expériences 43
7.1 Les différents programmes mathématiques . . . . . . . . . . . . . . . . . . . . 43
7.2 Expérimentations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
7.3 Problème du Tigre Multi-Agents . . . . . . . . . . . . . . . . . . . . . . . . . 45
7.4 Allocation de canal de communication . . . . . . . . . . . . . . . . . . . . . . 46
7.5 Problèmes aléatoires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
7.6 Bilan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
8 Conclusions et perspectives 49
8.1 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
8.2 Quelques directions pour des travaux futurs . . . . . . . . . . . . . . . . . . . 51
8.2.1 Problème avec un grand horizon . . . . . . . . . . . . . . . . . . . . . 51
8.2.2 Problèmes à horizon infini . . . . . . . . . . . . . . . . . . . . . . . . 52v
II English Manuscript 53
1 Planning For Decentralized Problems 55
1.1 Decentralized Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
1.1.1 The Team Decision Problem . . . . . . . . . . . . . . . . . . . . . . . 56
1.1.2 The Multi-Access Broadcast Channel Problem . . . . . . . . . . . . . 58
1.1.3 Queue Load Balancing Problem . . . . . . . . . . . . . . . . . . . . . 58
1.1.4 Two-Machine Maintenance Problem . . . . . . . . . . . . . . . . . . . 59
1.2 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
1.3 Complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
1.4 Contributions Of The Thesis . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
1.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
2 Decentralized POMDPs 67
2.1 The DEC-POMDP Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
2.1.1 The Finite Horizon Problem . . . . . . . . . . . . . . . . . . . . . . . 68
2.1.2 Special Cases . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
2.1.3 Formulating Practical Problems . . . . . . . . . . . . . . . . . . . . . 70
2.2 Exact Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
2.2.1 The DP Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
2.2.2 The MAA* Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
2.2.3 Point Based Dynamic Programming (PBDP) . . . . . . . . . . . . . . 77
2.3 Inexact Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
2.3.1 Approximate Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . 79
2.4 Computational Experience . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
2.5 Mathematical Programming Basics . . . . . . . . . . . . . . . . . . . . . . . . 80
2.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
3 The Sequence Form Of A Policy 83
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
3.2 Informal Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
3.3 Formal Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
3.4 Policy Constraints . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
3.4.1 Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
3.5 Value Of A Joint Policy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
3.5.1 Value Of A Joint History . . . . . . . . . . . . . . . . . . . . . . . . . 92
3.6 Nonlinear Program . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
3.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95vi Table of Contents
4 A Combinatorial Optimization Approach 97
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
4.1.1 The Quadratic Assignment Problem . . . . . . . . . . . . . . . . . . . 98
4.2 A 0-1 Integer Linear Program . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
4.2.1 Validity Of The Program . . . . . . . . . . . . . . . . . . . . . . . . . 101
4.3 An Improved 0-1 Integer Linear Program . . . . . . . . . . . . . . . . . . . . 103
4.3.1 Validity Of The Program . . . . . . . . . . . . . . . . . . . . . . . . . 104
4.4 Equivalent Relaxations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
4.4.1 Equivalence Of The Relaxations . . . . . . . . . . . . . . . . . . . . . 107
4.4.2 The Branch And Bound Method . . . . . . . . . . . . . . . . . . . . . 108
4.4.3 Virtues Of Relaxation . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
4.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
5 An Optimal Nash Equilibrium Search Approach 113
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
5.2 Definitions And Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
5.2.1 Linear Programming Duality . . . . . . . . . . . . . . . . . . . . . . . 116
5.3 Necessary Conditions For A Best Response Policy . . . . . . . . . . . . . . . 118
5.4 Necessary Conditions For A Nash Equilibrium . . . . . . . . . . . . . . . . . 121
5.4.1 Nonlinear Program To Find Optimal Joint Policy . . . . . . . . . . . 122
5.5 Linearization Of Complementarity Constraints . . . . . . . . . . . . . . . . . 123
5.5.1 Upper Bounds On Regrets . . . . . . . . . . . . . . . . . . . . . . . . 124
5.6 0-1 Mixed Integer Linear Program: Two Agent Case . . . . . . . . . . . . . . 125
5.7 0-1 Mixed Integer Linear Program: Three Or More Agents Case . . . . . . . 126
5.7.1 An Alternative 0-1 MILP . . . . . . . . . . . . . . . . . . . . . . . . . 129
5.8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131
6 Heuristics And Dynamic Programming 133
6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133
6.2 Locally Extraneous Histories . . . . . . . . . . . . . . . . . . . . . . . . . . . 134
6.3 Identifying Locally Extraneous Histories . . . . . . . . . . . . . . . . . . . . . 135
6.3.1 Pruning Locally Extraneous Terminal Histories . . . . . . . . . . . . . 137
6.3.2 Pruning All Locally Extraneous Histories . . . . . . . . . . . . . . . . 138
6.4 Globally Extraneous Histories . . . . . . . . . . . . . . . . . . . . . . . . . . 138
6.5 Identifying Globally Extraneous Histories . . . . . . . . . . . . . . . . . . . . 140
6.5.1 Pruning All Globally Extraneous Histories . . . . . . . . . . . . . . . 141
6.6 Changes To The Programs . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142vii
6.7 Adding Cuts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144
6.7.1 Upper Bound On Value . . . . . . . . . . . . . . . . . . . . . . . . . . 144
6.7.2 Lower Bound On Value . . . . . . . . . . . . . . . . . . . . . . . . . . 146
6.7.3 Impact Of The Cuts . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146
6.8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147
7 Computational Experience 149
7.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149
7.2 Comparison Of The Sizes Of Programs . . . . . . . . . . . . . . . . . . . . . 149
7.2.1 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151
7.2.2 Summary Of The Comparison . . . . . . . . . . . . . . . . . . . . . . 151
7.3 Experimental Set-Up . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152
7.3.1 Measurement Of Time Taken . . . . . . . . . . . . . . . . . . . . . . . 153
7.4 The MA-Tiger Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154
7.5 The MABC Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157
7.6 Random Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160
7.7 Experience of the NLP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160
7.7.1 MABC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161
7.7.2 MA-Tiger . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162
7.7.3 Grid Meeting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162
7.7.4 Fire Fighting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163
7.8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163
8 Conclusions And Future Work 165
8.1 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165
8.2 Directions For Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167
8.2.1 Long Horizon Problems . . . . . . . . . . . . . . . . . . . . . . . . . . 167
8.2.2 Infinite Horizon Problems . . . . . . . . . . . . . . . . . . . . . . . . . 169
III Appendices / Annexes 171
A An Algorithm For POSGs 173
A.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173
A.2 A Linear Complementarity Problem . . . . . . . . . . . . . . . . . . . . . . . 174
A.3 An 0-1 Mixed Integer Linear Program . . . . . . . . . . . . . . . . . . . . . . 176
A.3.1 The 3-Or-More Agents Case . . . . . . . . . . . . . . . . . . . . . . . 177