Une méthode de programmation linéaire mixte pour les POMDP décentralisé à horizon fini

Raghav Aras; Alain Dutech; François Charpillet

inria-00162469, version 1

Une méthode de programmation linéaire mixte pour les POMDP décentralisé à horizon fini

Raghav Aras () ¹, Alain Dutech ()^a^, 1, François Charpillet ()^a^, 1

2e Journées Francophones Planification, Décision, Apprentissage pour la conduite de systèmes - JFPDA 2007 (2007)

a – INRIA
1 : MAIA (INRIA Lorraine - LORIA)
INRIA – CNRS : UMR7503 – Université Henri Poincaré - Nancy I – Université Nancy II – Institut National Polytechnique de Lorraine (INPL) France

Références bibliographiques

Liste des fichiers attachés à ce document :

PDF

aras_milp_JFPDA07.pdf

(146.8 KB)

inria-00162469, version 1
http://hal.inria.fr/inria-00162469
oai:hal.inria.fr:inria-00162469
Contributeur : Alain Dutech <>
Soumis le : Vendredi 13 Juillet 2007, 15:13:14
Dernière modification le : Lundi 20 Juin 2011, 11:38:37

Voir la fiche concise

Documents associés

PDF :

Exporter

Bibtex EndNote TEI RefWorks

%% inria-00162469, version 1
%% http://hal.inria.fr/inria-00162469
@inproceedings{aras:inria-00162469,
    hal_id = {inria-00162469},
    url = {http://hal.inria.fr/inria-00162469},
    title = {{Une m{\'e}thode de programmation lin{\'e}aire mixte pour les POMDP d{\'e}centralis{\'e} {\`a} horizon fini}},
    author = {Aras, Raghav and Dutech, Alain and Charpillet, Fran{\c c}ois},
    abstract = {{Nous nous int{\'e}ressons au probl{\`e}me consistant {\`a} trouver une politique jointe optimale pour $n$ agents dans le cadre du contr{\^o}le optimal d'un processus d{\'e}cisionnel de Markov d{\'e}centralis{\'e} partiellement observ{\'e} (Dec-POMDP). Le principe de notre approche est le suivant\~: la politique jointe optimale d'un Dec-POMDP est {\'e}quivalente {\`a} une politique \emph{sous-optimale} du POMDP li{\'e}, politique qui devrait en outre respecter des contraintes structurelles afin qu'elle puisse {\^e}tre d{\'e}centralis{\'e}e. En s'appuyant sur ce principe, nous pr{\'e}sentons un algorithme exact qui utilise la programmation lin{\'e}aire mixte (PLM) pour trouver un vecteur de poids de r{\'e}alisation de s{\'e}quences jointes (suite d'actions et d'observations jointes) qui repr{\'e}sente ainsi une politique jointe. La politique jointe (d{\'e}centralisable) optimale pour le Dec-POMDP d{\'e}rive directement de la solution de ce PLM. Des exp{\'e}rimentation de notre algorithme sur des probl{\`e}mes de Dec-POMDP standards montrent qu'il est plus efficace (rapide) que les algorithmes exacts actuels de programmation dynamique.}},
    keywords = {Dec-POMDP; Programmation lin{\'e}aire ; Syst. multi-agents},
    language = {Fran{\c c}ais},
    affiliation = {MAIA - INRIA Lorraine - LORIA},
    booktitle = {{2e Journ{\'e}es Francophones Planification, D{\'e}cision, Apprentissage pour la conduite de syst{\`e}mes - JFPDA 2007}},
    address = {Grenoble, France},
    audience = {nationale },
    year = {2007},
    month = Jul,
    pdf = {http://hal.inria.fr/inria-00162469/PDF/aras\_milp\_JFPDA07.pdf},
}

%F inria-00162469, version 1
%0 Conference Proceedings
%U http://hal.inria.fr/inria-00162469
%2 INFO:INFO_AI
%T Une méthode de programmation linéaire mixte pour les POMDP décentralisé à horizon fini
%A Aras, Raghav
%A Dutech, Alain
%A Charpillet, François
%+ MAIA - INRIA Lorraine - LORIA
%X Nous nous intéressons au problème consistant à trouver une politique jointe optimale pour $n$ agents dans le cadre du contrôle optimal d'un processus décisionnel de Markov décentralisé partiellement observé (Dec-POMDP). Le principe de notre approche est le suivant~: la politique jointe optimale d'un Dec-POMDP est équivalente à une politique \emph{sous-optimale} du POMDP lié, politique qui devrait en outre respecter des contraintes structurelles afin qu'elle puisse être décentralisée. En s'appuyant sur ce principe, nous présentons un algorithme exact qui utilise la programmation linéaire mixte (PLM) pour trouver un vecteur de poids de réalisation de séquences jointes (suite d'actions et d'observations jointes) qui représente ainsi une politique jointe. La politique jointe (décentralisable) optimale pour le Dec-POMDP dérive directement de la solution de ce PLM. Des expérimentation de notre algorithme sur des problèmes de Dec-POMDP standards montrent qu'il est plus efficace (rapide) que les algorithmes exacts actuels de programmation dynamique.
%2 I.2.11.3: Multiagent systems, I.: Computing Methodologies/I.2: ARTIFICIAL INTELLIGENCE/I.2.8: Problem Solving, Control Methods, and Search/I.2.8.2: Dynamic programming, G.: Mathematics of Computing/G.1: NUMERICAL ANALYSIS/G.1.6: Optimization/G.1.6.6: Linear programming, G.3.15: Stochastic processes
%Z Dec-POMDP, Programmation linéaire, Syst. multi-agents
%G Français
%8 2007-07-04
%2 nationale
%B 2e Journées Francophones Planification, Décision, Apprentissage pour la conduite de systèmes - JFPDA 2007
%2 Grenoble
%2 France
%8 2007-07-02
%8 2007-07-06
%2 JFPDA 2007
%K Dec-POMDP; Programmation linéaire ; Syst. multi-agents
%2 2007

<?xml version="1.0" encoding="UTF-8"?>
<listBibl xmlns="http://www.tei-c.org/ns/1.0" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:mml="http://www.w3.org/1998/Math/MathML">
<listBibl type="inproceedings"><head>Communications avec actes</head>
<biblStruct type="inproceedings" xml:id="inria-00162469"><analytic>
<author><persName><forename>Raghav</forename><surname>Aras</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA Lorraine - LORIA</orgName>
<orgName type="team">MAIA</orgName>
<country>FR</country>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">CNRS : UMR7503</orgName>
<orgName type="institution">Université Henri Poincaré - Nancy I</orgName>
<orgName type="institution">Université Nancy II</orgName>
<orgName type="institution">Institut National Polytechnique de Lorraine (INPL)</orgName>
</affiliation>
</author>
<author><persName><forename>Alain</forename><surname>Dutech</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA Lorraine - LORIA</orgName>
<orgName type="team">MAIA</orgName>
<country>FR</country>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">CNRS : UMR7503</orgName>
<orgName type="institution">Université Henri Poincaré - Nancy I</orgName>
<orgName type="institution">Université Nancy II</orgName>
<orgName type="institution">Institut National Polytechnique de Lorraine (INPL)</orgName>
</affiliation>
</author>
<author><persName><forename>François</forename><surname>Charpillet</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA Lorraine - LORIA</orgName>
<orgName type="team">MAIA</orgName>
<country>FR</country>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">CNRS : UMR7503</orgName>
<orgName type="institution">Université Henri Poincaré - Nancy I</orgName>
<orgName type="institution">Université Nancy II</orgName>
<orgName type="institution">Institut National Polytechnique de Lorraine (INPL)</orgName>
</affiliation>
</author>
<title type="main" level="a">Une méthode de programmation linéaire mixte pour les POMDP décentralisé à horizon fini</title></analytic><monogr><meeting>2e Journées Francophones Planification, Décision, Apprentissage pour la conduite de systèmes - JFPDA 2007</meeting><imprint><pubPlace><settlement>Grenoble</settlement><country>France</country></pubPlace><biblScope type="publicationDate">2007-07-04</biblScope></imprint></monogr><idno type="HALid">http://hal.inria.fr/inria-00162469</idno><idno type="HALFile">http://hal.inria.fr/inria-00162469/PDF/aras_milp_JFPDA07.pdf</idno></biblStruct>
</listBibl>
</listBibl>