Un modèle pour la prise de décision multi-agent sous incertitude stricte, A model for multiagent decision making under strict uncertainty
173
pages
Français
Documents
Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus
Découvre YouScribe en t'inscrivant gratuitement
Découvre YouScribe en t'inscrivant gratuitement
173
pages
Français
Documents
Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus
Thèse soutenue le 14 décembre 2009: Artois
Le contexte informationnel dans lequel évolue un agent possède une importance extrême quandcelui-ci élabore son comportement futur. Un agent rationnel doit en effet baser ses choix sur les informationsqu’il possède pour choisir ses actions. Or, dans les applications réelles, l’information disponible àl’agent est souvent rare et peu précise. De multiples modèles ont été élaborés dans les différents cadresd’application de l’intelligence artificielle afin de caractériser une décision rationnelle dans chacun descontextes informationnels possibles. Les travaux présentés dans cette thèse concernent l’élaboration d’unmodèle permettant à un agent de prendre des décisions rationnelles dans un contexte informationnel trèspauvre. La seule information dont dispose un agent à propos du résultat de ses actions est la donnée del’ensemble de résultats de chacune d’entre elles. En particulier, aucune information sur la conséquence laplus susceptible de se produire n’est disponible. L’agent est supposé égoïste (au sens où seul compte pourlui son propre intérêt) et autonome. Il évolue de plus dans un environnement où il coexiste avec d’autresagents (qui sont aussi égoïstes et autonomes). Les actions d’un agent influent sur les autres agents. Ladémarche entreprise pour élaborer le modèle est la suivante. D’abord, nous caractérisons les critères dedécision rationnels d’un agent seul dans le contexte informatif étudié. Ensuite, nous étendons ces critèresde décision individuelle au cas multi-agent en nous appuyant sur la théorie des jeux qui est le meilleurcadre pour exprimer les interactions entre agents rationnels et en particulier les possibilités de coordinationentre les agents. Enfin, le domaine de la planification est un excellent cadre pour représenter etexprimer les concepts du modèle.
-Incertitude stricte
-Théorie des jeux
-Multi-agent
-Décision
The informative context in which an agent evolves is extremely important when she elaborates her futurebehaviour. A rational agent must base her choices on the available information. In realistic applications,the information is often rare and imprecise. Many models have been introduced to caracterize rationaldecision in each possible informative context. This thesis is about the elaboration of a model that allowsan agent to make rational decisions in an extremely poor informative context. The only informationthat is available to an agent about her actions’ consequences is the result set of each of her actions. Noinformation about which consequence of any action will eventually happen is available. The agent issupposed to be selfish (which means that her own interest is her only concern) and autonomous. Sheevolves in an environment in which she coexists with other agents (that are as selfish and autonomous asher). An agent action may inflence those of other agents. We used the following approach to build ourmodel. First, we caracterized the rational decision criteria for an agent to use in the context of completeignorance. Then we extended these criteria, by using game theory concepts, to a multiagent environment.Finally, the planning framework is an excellent framework to represent the introduced concepts.
Source: http://www.theses.fr/2009ARTO0407/document
Un Modele pour la Prise de Decision
Multi-agent sous Incertitude Stricte
T H ESE
soutenue publiquement le 14 12 2009
pourl’obtention du
Doctorat de l’Universite d’A rtois
Specialite Informatique
par
Ramzi BEN LARBI
C omposition du jury
Rapporteurs : D idierD ubois,D irecteurde Recherche CNRS a l’IRIT Toulouse
Abel-Illah M ouaddib,Professeura l’Universite de Caen-Basse Normandie
Exam inateurs : Bruno Beauls,ma^tre de conferences a l’Universite des Sciences et Technologies de Lille
Salem Benferhat,Professeura l’Universite d’Artois
Sebastien K onieczny,Charge de Recherche CNRS au CRIL Lens (co-directeurde these)
Rene M andiau,Professeura l’Universite de Valenciennes et du Hainaut-Cambresis
Pierre M arquis,Professeura l’Universite d’Artois (co-directeurde these)
Nicolas M audet,ma^tre de conferences a l’Universite Paris-D auphine
CENTRE DE REC H ERC H E EN INF O RM A TI Q U E DE LENS ? C NRS U M R 8 1 8 8
U niversite d’A rtois,rue Jean Souvraz,S.P.18 F-62307,Lens C edex France
Secretariat :T el.:+ 33 (0)3 21 79 17 23 { Fax :+ 33 (0)3 21 79 17 70
http://www.cril.frRØsumØ
L e c o n te x te in fo rma tio n n e l d a n s le q ue l Øv o lue un a g e n t p o ssŁ d e un e imp o rta n c e e x trŒ me q ua n d
c e lui-c i Øla b o re so n c o mp o rte me n t futur. Un a g e n t ra tio n n e l d o it e n e ffe t b a se r se s c h o ix sur le s in fo rma -
tio n s q u’il p o ssŁ d e p o ur c h o isir se s a c tio n s. Or, d a n s le s a p p lic a tio n s rØe lle s, l’in fo rma tio n d isp o n ib le ?
l’a g e n t e st so uv e n t ra re e t p e u p rØc ise . De multip le s mo d Ł le s o n t ØtØ Øla b o rØs d a n s le s d iffØre n ts c a d re s
d ’a p p lic a tio n d e l’in te llig e n c e a rti c ie lle a n d e c a ra c tØrise r un e d Øc isio n ra tio n n e lle d a n s c h a c un d e s
c o n te x te s in fo rma tio n n e ls p o ssib le s. L e s tra v a ux p rØse n tØs d a n s c e tte th Ł se c o n c e rn e n t l’Øla b o ra tio n d ’un
mo d Ł le p e rme tta n t ? un a g e n t d e p re n d re d e s d Øc isio n s ra tio n n e lle s d a n s un c o n te x te in fo rma tio n n e l trŁ s
p a uv re . L a se ule in fo rma tio n d o n t d isp o se un a g e n t ? p ro p o s d u rØsulta t d e se s a c tio n s e st la d o n n Øe d e
l’e n se mb le d e rØsulta ts d e c h a c un e d ’e n tre e lle s. En p a rtic ulie r, a uc un e in fo rma tio n sur la c o n sØq ue n c e la
p lus susc e p tib le d e se p ro d uire n ’e st d isp o n ib le . L ’a g e n t e st sup p o sØ Øg o ?ste (a u se n s o ø se ul c o mp te p o ur
lui so n p ro p re in tØrŒ t) e t a uto n o me . Il Øv o lue d e p lus d a n s un e n v iro n n e me n t o ø il c o e x iste a v e c d ’a utre s
a g e n ts (q ui so n t a ussi Øg o ?ste s e t a uto n o me s). L e s a c tio n s d ’un a g e n t in ue n t sur le s a utre s a g e n ts. L a
d Øma rc h e e n tre p rise p o ur Øla b o re r le mo d Ł le e st la suiv a n te . D’a b o rd , n o us c a ra c tØriso n s le s c ritŁ re s d e
d Øc isio n ra tio n n e ls d ’un a g e n t se ul d a n s le c o n te x te in fo rma tif Øtud iØ. En suite , n o us Øte n d o n s c e s c ritŁ re s
d e d Øc isio n in d iv id ue lle a u c a s multi-a g e n t e n n o us a p p uy a n t sur la th Øo rie d e s je ux q ui e st le me ille ur
c a d re p o ur e x p rime r le s in te ra c tio n s e n tre a g e n ts ra tio n n e ls e t e n p a rtic ulie r le s p o ssib ilitØs d e c o o rd i-
n a tio n e n tre le s a g e n ts. En n , le d o ma in e d e la p la n i c a tio n e st un e x c e lle n t c a d re p o ur re p rØse n te r e t
e x p rime r le s c o n c e p ts d u mo d Ł le .
Ab stra c t
Th e in fo rma tiv e c o n te x t in w h ic h a n a g e n t e v o lv e s is e x tre me ly imp o rta n t w h e n sh e e la b o ra te s h e r future
b e h a v io ur. A ra tio n a l a g e n t must b a se h e r c h o ic e s o n th e a v a ila b le in fo rma tio n . In re a listic a p p lic a tio n s,
th e in fo rma tio n is o fte n ra re a n d imp re c ise . Ma n y mo d e ls h a v e b e e n in tro d uc e d to c a ra c te riz e ra tio n a l
d e c isio n in e a c h p o ssib le in fo rma tiv e c o n te x t. Th is th e sis is a b o ut th e e la b o ra tio n o f a mo d e l th a t a llo w s
a n a g e n t to ma k e ra tio n a l d e c isio n s in a n e x tre me ly p o o r in fo rma tiv e c o n te x t. Th e o n ly in fo rma tio n
th a t is a v a ila b le to a n a g e n t a b o ut h e r a c tio n s’ c o n se q ue n c e s is th e re sult se t o f e a c h o f h e r a c tio n s. No
in fo rma tio n a b o ut w h ic h c o n se q ue n c e o f a n y a c tio n w ill e v e n tua lly h a p p e n is a v a ila b le . Th e a g e n t is
sup p o se d to b e se l sh (w h ic h me a n s th a t h e r o w n in te re st is h e r o n ly c o n c e rn ) a n d a uto n o mo us. Sh e
e v o lv e s in a n e n v iro n me n t in w h ic h sh e c o e x ists w ith o th e r a g e n ts (th a t a re a s se l sh a n d a uto n o mo us a s
h e r). An a g e n t a c tio n ma y in e n c e th o se o f o th e r a g e n ts. W e use d th e fo llo w in g a p p ro a c h to b uild o ur
mo d e l. First, w e c a ra c te riz e d th e ra tio n a l d e c isio n c rite ria fo r a n a g e n t to use in th e c o n te x t o f c o mp le te
ig n o ra n c e . Th e n w e e x te n d e d th e se c rite ria , b y usin g g a me th e o ry c o n c e p ts, to a multia g e n t e n v iro n me n t.
Fin a lly , th e p la n n in g fra me w o rk is a n e x c e lle n t fra me w o rk to re p re se n t th e in tro d uc e d c o n c e p ts.
iiiTable des matiŁres
In tro du c tio n 1
P artie I E tat de l’art 7
Ch ap itre 1 P rØ limin aires 9
Ch ap itre 2 Th Ø o rie de la dØ c isio n so u s in c ertitu de 11
2.1 ThØorie de la dØcision . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.1.1 Attentes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.1.2 QualitØ de l’information . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.2 DØcision face au risque . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.2.1 P robabilitØs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.2.2 UtilitØ espØrØe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.3 DØcision face ? l’incertitude : cadre subjectif . . . . . . . . . . . . . . . . . . . . . 23
2.3 .1 Cadre formel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.3 .2 Axiomes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.4 Cadre de l’incertitude qualitative . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.5 Cadre de l’incertitude stricte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.5 .1 Cadre formel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.5 .2 Axiomes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.6 Cadre de l’ignorance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 3
2.6 .1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 3
2.6 .2 Cadre formel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 5
2.6 .3 Axiomes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 6
2.7 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 7
Ch ap itre 3 P lan i c atio n so u s in c ertitu de 4 9
3 .1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 9
3 .2 P lanication classique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1
iiiTable des matiŁres
3.2.1 ModŁle : concepts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
3.2.2 G ØnØralisations du cadre . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
3.3 ModŁles pour la planication sous incertitude . . . . . . . . . . . . . . . . . . . . . 53
3.4 Planication multi-agent . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
3.4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
3.4.2 Coordination . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
3.4.3 Planication distribuØe . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
3.4.4 Agents " Øgo?stes" dans un contexte multi-agent . . . . . . . . . . . . . . . 60
3.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
Chapitre 4 ThØorie des jeux sous information incomplŁte 63
4.1 Introduction ? la thØorie des jeux . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
4.1.1 Un point historique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
4.1.2 CaractØristiques d’un jeu . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
4.1.3 ReprØsentation d’un jeu . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
4.2 Propension ? la coopØration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
4.2.1 J eux non coopØratifs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
4.2.2 J eux coopØratifs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
4.3 J eux sous incertitude . . . . . . . . . . . . . . . . . . .
