Un modèle pour la prise de décision multi-agent sous incertitude stricte, A model for multiagent decision making under strict uncertainty

De
Publié par

Sous la direction de Pierre Marquis
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
Publié le : jeudi 27 octobre 2011
Lecture(s) : 37
Nombre de pages : 173
Voir plus Voir moins

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 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
4.3.1 J eux bayØsiens . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
4.3.2 J eux sous incertitude stricte : jeux prØbayØsiens . . . . . . . . . . . . . . . 79
4.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
Partie II Contribution 8 5
Chapitre 5 Contribution ? la thØorie de la dØcision sous incertitude 8 7
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
5.2 Cadre formel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
5.3 PropriØtØs des cadres et des critŁres de dØcision . . . . . . . . . . . . . . . . . . . . 88
5.4 CaractØrisation des critŁres d’optimalitØ . . . . . . . . . . . . . . . . . . . . . . . . 91
5.5 Exemples de critŁres d’optimalitØ . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
5.6 Comparaison avec d’autres axiomes . . . . . . . . . . . . . . . . . . . . . . . . . . 104
5.7 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
Chapitre 6 Extension de la planication classiq ue au cadre multi-ag ent : une approche par
la thØorie des jeux 111
6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
iv6.2 PrØfØrences dichotomiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
6.2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
6.2.2 Un cadre formel pour la planication multi-agent . . . . . . . . . . . . . . 114
6.2.3 RØsolution du jeu et gØnØration de diagnostic stratØgique . . . . . . . . . . 119
6.2.4 Exemple : le pont . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
6.2.5 Relation avec des modŁles existants . . . . . . . . . . . . . . . . . . . . . . 122
6.3 PrØfØrences non dichotomiques : satisfaction graduØe . . . . . . . . . . . . . . . . . 124
6.3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124
6.3.2 Evaluation des ensembles de rØsultats . . . . . . . . . . . . . . . . . . . . . 124
6.3.3 ? valuation des opportunitØs de coordination . . . . . . . . . . . . . . . . . 127
6.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128
Chapitre 7 DØcision multi-agent sous incertitude stricte : jeux ? rØsultats multiples 131
7.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131
7.2 Jeux qualitatifs ? rØsultats multiples . . . . . . . . . . . . . . . . . . . . . . . . . . 133
7.3 RØsolution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134
7.3.1 ? valuation pour un joueur . . . . . . . . . . . . . . . . . . . . . . . . . . . 135
7.3.2 Coordination sous ignorance . . . . . . . . . . . . . . . . . . . . . . . . . 139
7.4 Finesse de l’Øchelle d’Øvaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146
7.5 Liens avec la thØorie des jeux classique . . . . . . . . . . . . . . . . . . . . . . . . 147
7.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151
Conclusion 153
B ibliographie 155
Publications 165
vTable des matiŁres
viIntroduction
Les Œtres humains se trompent. Ils tombent, ratent la cible, perdent leur argent en bourse. Ils ont
conscience que cela peut arriver. Cela ne les paralyse pourtant pas en gØnØral. Ils Øvaluent leurs chances
de rØussite, prennent une dØcision puis agissent. On dit alors communØment, quand ils se trompent,
qu’ils ont fait un mauvais calcul. La dØcision est en effet trŁs souvent prise alors qu’ils ne possŁdent
pas toute l’information nØcessaire pour dØterminer complŁtement les consØquences de leurs choix. Ils se
contentent de l’information qu’ils possŁdent. Ils s’y adaptent et la considŁrent (de maniŁre consciente ou
pas) comme un ØlØment du problŁme qui se pose ? eux.
Ce fait que l’on retrouve dans les gestes les plus anodins d’un Œtre humain est particuliŁrement
intØressant pour le domaine de l’intelligence articielle (IA). Un des objectifs de l’IA est de reproduire
sur machine des comportements considØrØs comme "intelligents". La facultØ de dØcider est sans doute
le trait le plus spØcique ? ce que l’on entend par Œtre intelligent. Un agent (humain ou articiel) met
en oeuvre un comportement "intelligent" lorsque, en fonction de ses objectifs (buts, prØfØrences, inten-
tions), il raisonne sur les informations dont il dispose (typiquement de natures variØes : connaissances et
croyances sur le "monde extØrieur", les autres agents, perceptions diverses de ce monde extØrieur, rŁgles
de dØcision, arguments, etc.) pour dØcider, agir au mieux en exploitant les actions dont il dispose. On
voit appara?tre dans cette description un certain nombre de concepts clØs (croyances, prØfØrences, ac-
tions, etc.) et de processus d’exploitation des informations correspondantes (raisonnement, dØcision). En
particulier, les connaissances sont ici vues comme synonymes d’informations, munies de mØcanismes
d’exploitation de celles-ci et pas dans le sens plus technique de croyances certaines. C’est la mŒme
acception de "connaissances" qui est ? l’oeuvre dans "reprØsentation des connaissances".
La reprØsentation des connaissances constitue le pilier de l’approche dite symbolique de l’intel-
ligence articielle, s’appuyant sur le postulat mØcaniste de Simon et Newell : un systŁme physique est
capable d’un comportement "intelligent" si et seulement si c’est un systŁme physique de symboles, i.e.,
une machine qui produit au cours du temps un assemblage Øvolutif de structures symboliques. Cette ap-
proche ne prØjuge en rien des moyens ? mettre en oeuvre pour aboutir ? un comportement vu comme
"intelligent". En fait, dans "reprØsentation des connaissances", le terme "reprØsentation" doit Œtre pris
dans un sens assez large. En effet, il s’agit tout autant de dØnir des modŁles pour les processus d’ex-
ploitation des concepts d’intØrŒt (et Øvidemment ces concepts eux-mŒmes) que des langages permettant
la reprØsentation proprement dite de ces concepts.
Cette sØparation, pas toujours claire entre modØlisation et reprØsentation, peut s’expliquer par la
prØpondØrance des approches logiques en reprØsentation des connaissances. En effet, dans toute logique,
le point de dØpart est un langage, donc un formalisme de reprØsentation ; le modŁle considØrØ pour les
concepts reprØsentØs existe mais est souvent moins apparent. Par exemple, en logique propositionnelle
ØpistØmique mono-agent, on s’intØresse ? la reprØsentation des connaissances propositionnelles d’un
agent. La logique prØpondØrante pour cela est S5. Dans cette logique, on traite en fait des connaissances
propositionnelles d’un agent idØalement rationnel (i.e. ayant des capacitØs de dØduction non limitØes),
qui ne conna?t que des propositions vraies (et a donc des connaissances cohØrentes) et a des capacitØs
parfaites d’introspection positive et nØgative (quand il sait, il sait ce qu’il sait et quand il ne sait pas, il sait
1

Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.

Diffusez cette publication

Vous aimerez aussi