1

Un algorithme glouton de résolution de PDMTOs agrégés

Stéphane Cardon

cardon@cril.univ-artois.fr

2

Plan

Rappels sur les PDMsProblèmeRestriction à des PDMTOs agrégés muni d ’un

pré-ordre total et vérifiant certaines conditionsAlgorithme gloutonRésultats expérimentauxConclusion et perspectives

3

Processus Décisionnel de Markov (1/2)

• Un PDM est un 6-uplet : <S,A,O,Pr,G,C>• S est l ’ensemble des états, s est un état

• A est l ’ensemble des actions, a est une action

• O est l ’ensemble des observations, o est une observation

• Pr est la description des transitions du système, Pr(ot|s1t,at-1,

s2t-1) est la probabilité d ’observer o à l ’étape t, sachant que le système

est passé de l ’état s2 à l ’état s1 par l ’action a durant l ’étape t-1

• G est la fonction de gain, G(s) est le gain pour être dans l ’état s

• C est la fonction de coût, C(s,a) est le coût de l ’action a lorsqu ’on est dans l ’état s

4

Processus Décisionnel de Markov (2/2)

• Une trajectoire observable est une suite de couples (observation, action)

• Une trajectoire du système est une suite de couples (état, action)

• L ’horizon du PDM est l ’ensemble des trajectoires possibles du système

• Une politique est une trajectoire observable

5

Résolution de PDM

Résoudre un PDM revient à chercher la politique ayant une valeur espérée

maximale, politique appelée politique optimale (*)

6

PDM Totalement Observable

• Nous nous restreignons à des PDMTOs :• O = A

• Pr(s1t|at-1,s2

t-1) est la probabilité d ’arriver dans l ’état s1 depuis s2 par l ’action a durant l ’étape t-1

est une fonction de SxT dans A

• La valeur espérée de est (Bellman) :

Vt(s) = G(s) + C(s,(s,t))+ Pr(s’|s, (s,t)) . Vt-1

(s’)

• Nous supposons aussi que l ’horizon est fini, T est le nombre d ’étapes

7

Plan

Rappels sur les PDMsProblèmeRestriction à des PDMTOs agrégés muni d ’un

pré-ordre total et vérifiant certaines conditionsAlgorithme gloutonRésultats expérimentauxConclusion et perspectives

8

Problème

• Techniques usuelles inefficaces lorsque S est grand

• Notre problème est de résoudre ce type de PDMs

• PDMs courants lorsque :Agent ayant des ressources limitées, évoluant dans un environnement dynamique, temps-réel et incertain

9

Plan

Rappels sur les PDMsProblèmeRestriction à des PDMTOs agrégés muni d ’un

pré-ordre total et vérifiant certaines conditionsAlgorithme gloutonRésultats expérimentauxConclusion et perspectives

10

Agrégation de PDMs

• Une première solution, basée sur une approche « divide and conquer », est d ’agréger les PDMs

• PDM Agrégé : état = sous-PDM

• Réaliste pour nos applications : groupement d ’états en fonction de certains critères (proximité géographique)

11

Conditions supplémentaires

• Pré-ordre total pour le PDM agrégé

• Existence d ’un état de départ pour chaque sous-PDM

• Accessibilité : Si il existe une action permettant d ’aller d ’un sous-PDM P2 à un autre P1, alors la même action permet d ’aller de n ’importe quel état de P2 à l ’état de départ de P1

12

Plan

Rappels sur les PDMsProblèmeRestriction à des PDMTOs agrégés muni d ’un

pré-ordre total et vérifiant certaines conditionsAlgorithme gloutonRésultats expérimentauxConclusion et perspectives

13

Définitions

• Restriction d ’une politique :/S’(s) = (s) si s S’ S, non défini sinon

• Composition de politiques : = 1 2, 1 défini sur S1, 2 sur S2

– S1 S2 = (s) = 1(s) si s S1

(s) = 2(s) si s S2

14

Propriété de la composition

• Soit le sous-PDM P2 accessible par P1

• Soit 1 une politique de P1

• Soit 2 une politique de P2

• Soit := 1 2

V() = V(1) + V(2)

• Idée preuve : récurrence sur le nombre d ’étapes et utilisation de la valeur espérée de Bellman.

15

Décomposition optimale

• Soit P un PDM agrégé muni d ’un pré-ordre total et vérifiant les conditions d ’existence et d ’accessibilité

• Soit Pi les sous-PDMs de P

• Soit * la politique optimale de P

i, si */Pi est définie,

alors */Pi est optimale dans Pi

• Idée preuve : Raisonnement par l ’absurde, il ne peut exister une

politique optimale dans Pi différente de */Pi

16

Composition linéaire optimale

• Soit P un PDM agrégé muni d ’un pré-ordre total et vérifiant les conditions d ’existence et d ’accessibilité

• Soit Pi une suite de sous-PDMs de P

• Soit := i i*

est optimale dans le PDM engendré par Pi

• Idée preuve : conséquence du théorème précédent

17

Algorithme - détermination de la politique optimale

• Pour chaque sous-PDM P du PDM agrégé muni du pré-ordre total, en commençant par les derniers et en remontant jusqu ’aux premiers, faire :– Pour chaque sous-PDM successeur Ps faire :

• calculer la composée de la politique optimale de P avec la politique composée de Ps

• la politique composée de P devient cette composée si cette dernière a une valeur espérée plus grande

• O(N) - N est le nombre de sous-PDM

18

Algorithme - problème d ’allocation des étapes (1/2)

• Un sous-PDM a une politique optimale différente en fonction du nombre d ’étapes dont il dispose

• Combien d ’étapes allouer à chaque sous-PDM ?

• Définitions :• Variation : rapport de la valeur espérée de la politique

optimale par le nombre d ’étapes de cette politique

19

Algorithme - problème d ’allocation des étapes (2/2)

• Variation instantanée : pente de la valeur espérée entre une étape de départ inférieure strictement à une étape d ’arrivée (0 sinon)

• Perte : pente de la valeur espérée entre une étape de départ supérieure strictement à une étape d ’arrivée (0 sinon)

20

Algorithme• Allocation, pour chaque sous-PDM, de l ’étape

correspondant à une variation maximale

• Répéter– Détermination de * - O(N)

– Si * a un nombre d ’étapes consommées supérieur aux étapes maximales,chercher le sous-PDM, intervenant dans *, ayant une perte minimale et lui allouer les étapes correspondantes - O(N)

– Sinon, si c ’est inférieur,chercher le sous-PDM, intervenant dans *, ayant une variation instantanée maximale et lui allouer les étapes correspondantes (si possible, sinon arrêt) - O(N)

• Jusqu ’à égalité entre le nombre d ’étapes max. et de *

O(N²)

21

Plan

Rappels sur les PDMsProblèmeRestriction à des PDMTOs agrégés muni d ’un

pré-ordre total et vérifiant certaines conditionsAlgorithme gloutonRésultats expérimentauxConclusion et perspectives

22

Variation du nombre d ’états

Erreurs (en %)

0

5

10

15Glouton

RTDP

Glouton (+et)

RTDP (+et)

Temps (en sec.)

0

2

4

6

8

10

12

14

Glouton

RTDP

Référence

23

Variation du nombre de sous-PDMs

Erreurs (en %)

0

5

10

15Glouton

RTDP

Glouton (+et)

RTDP (+et)

Temps (en sec.)

0

2

4

6

8

10

Glouton

RTDP

Référence

24

Erreurs (en %)

0

5

10

15

20Glouton

RTDP

Glouton (+et)

RTDP (+et)

Temps (en sec.)

0

2

4

6

8

10

12

14

Glouton

RTDP

Référence

Variation du nombre d ’étapes pour chaque sous-PDM

25

Plan

Rappels sur les PDMsProblèmeRestriction à des PDMTOs agrégés muni d ’un

pré-ordre total et vérifiant certaines conditionsAlgorithme gloutonRésultats expérimentauxConclusion et perspectives

26

Conclusion et Perspectives

• Résultats satisfaisants en moyenne mais fort écart-type mais pour des PDMs agrégés générés aléatoirement

• Plus d ’expérimentations (PDMs générés puis agrégés)

• Améliorer l ’allocation des étapes• Étude pour des sous-PDMs réduits à un état• Affaiblissement des conditions, travailler avec des

PDMPOs