Utilisation de croyances heuristiques pour la planification multi-agent dans le cadre des Dec-POMDP, Using heuristic belief points for Dec-POMDP planning

Gabriel Corona

Description

Sous la direction de François Charpillet
Thèse soutenue le 11 avril 2011: Nancy 1
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.
-Intelligence artificielle
-Systèmes multi-agent
-Modèles de Markov
-Planification
In this thesis, we focus on planning in decentralised sequentialdecision taking in uncertainty. In the centralised case, the MDP andPOMDP frameworks leads to efficient planning algorithms. The Dec-POMDPframework is used to model decentralised problems. This kind ofproblems is in a higher class of complexity than the centralisedproblem. 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.
-Artificial intelligence
-Multi-agent systems
-Markov models
-Planning
Source: http://www.theses.fr/2011NAN10026/document

Sujets

• Intelligence artificielle
• Planification
• Artificial Intelligence

Informations

• Publié par: Thesee
• Nombre de lectures: 60
• Langue: Français
• Poids de l'ouvrage: 2 Mo

Extrait

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.

D’autre part, toute contrefaçon, plagiat, reproduction
illicite encourt une poursuite pénale.


➢ Contact SCD Nancy 1 : [e-mail]




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 Departement de formation doctorale en informatique Ecole doctorale IAEM Lorraine
Sciences et Technologies
Utilisation de croyances heuristiques
pour la plani cation multi-agent dans
le cadre des Dec-POMDP
THESE
presentee et soutenue publiquement le 11 avril 2011
pour l’obtention du
Doctorat de l’universite Henri Poincare { Nancy 1
(specialite informatique)
par
Gabriel Corona
Composition du jury
Rapporteurs : Abdel-Illah Mouaddib, Professeur a l’Universite de Caen Basse-Normandie
Brahim Chaib-Draa, Professeur a l’Universite de Laval
Examinateurs : Shlomo Zilberstein, Professeur a l’Universite du Massachusetts Amherst
Nadine Piat, Professeur a l’ENSMM
Rene Mandiau,ur de l’Universite de Valenciennes
Rene Schott, Professeur a l’Universite Henri-Poincarre
Directeur de these : Fran cois Charpillet, Directeur de recherche INRIA
Laboratoire Lorrain de Recherche en Informatique et ses Applications | UMR 7503Mis
classe
la
en
thloria.
page
avec):[^:]*:[^:]*$/\1,/'
i
u
Remerciemen
's/^[^
ts
et
Merci
les
à
sed
$(
:]*:[^:]*:[^:]*:[^:]*:\([^:]*\
ypcat
)
passwd
to
|
s
grep
autres.
maia
|ii.
.
12
able
.
des
.
matières
.
T
.
able
.
des
.
gures
tributions
ix
1.2.4.2
Liste
1.2.5
des
.
tablea
.
ux
.
xi
.
Liste
.
des
.
Algori
.
thmes
.
xiii
.
1
le
In
.
tro
.
duction
.
1
tralisée
1.1
.
In
de
telligence
.
articielle
t
.
.
.
réactif
.
.
.
la
.
.
.
10
.
.
.
.
.
.
.
.
.
.
.
.
.
a
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
7
.
.
.
.
.
.
.
8
.
.
.
.
.
.
.
.
.
.
.
.
2
.
1.2
9
Agen
.
t
.
.
.
.
9
.
.
.
.
.
.
.
.
.
l'art
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
T
.
.
.
.
.
.
.
abilité
.
e
.
.
.
.
.
.
.
.
.
.
.
.
.
in
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Décision
.
.
.
.
.
.
2
.
1.2.1
.
Prise
.
de
.
décision
Arc
séq
t
u
.
en
.
tielle
.
.
.
.
.
.
.
.
1.2.7.1
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Agen
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Organisation
.
.
.
.
.
.
3
.
1.2.2
.
Ob
.
jectif
.
d
.
u
État
problème
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
1.3.2
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
13
.
.
.
.
.
.
.
.
.
.
.
.
.
5
.
Observ
.
p
.
rti
4
l
1.2.2.1
.
Critère
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
6
.
État
.
terne
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
1.2.6
.
décen
4
.
1.2.2.2
.
Récomp
.
enses
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
1.2.7
.
hitecture
.
l'agen
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
9
4
Agen
1.2.3
cognitif
Problème
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
1.2.7.2
.
t
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
1.3
.
de
.
thèse
.
.
.
.
.
.
5
.
1.2.4
.
Observ
.
ations
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
1.3.1
.
de
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
11
.
Con
.
.
.
.
.
.
.
.
5
.
1.2.4.1
.
Observ
.
abilité
.
totale
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Notations
.
iii
.
..
.
de
T
.
able
Witness
des
.
matières
v
I
.
État
.
de
.
l'art
olitiques
17
.
2
.
MDP
.
19
.
2.1
.
F
.
ormalisme
.
.
.
.
.
.
.
.
.
.
.
.
p
.
.
.
.
.
.
.
.
.
.
.
aleur
.
.
.
.
.
.
.
44
.
.
.
.
.
.
.
Mo
.
.
.
.
.
.
.
.
.
.
.
.
.
3.2.1
.
.
.
.
.
.
.
.
.
.
.
.
.
3.3
.
.
.
.
.
une
20
.
2.1.1
V
Présen
.
tation
.
.
u
.
3.3.4
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
L
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
20
.
2.1.2
.
Dénition
36
.
e
.
.
.
.
.
.
.
Belief
.
.
.
.
.
.
.
.
.
ti
.
.
.
.
.
.
.
.
.
3.3.1
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
onctions
.
re
.
exes
.
.
.
.
.
.
.
.
.
.
.
Programmation
.
.
.
.
21
.
2.1.3
Mise
Critère
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
ad
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
47
.
34
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
3.1.2
.
erformance
.
.
.
.
.
.
.
.
.
.
24
.
2.1.4
3.2
P
.
olitique
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
in
.
.
.
.
.<