Régis Sabbadin - Journée PDMIA, 28 juin 2002

Décomposition de PDM à l’aide de techniques de décomposition de graphes

Régis SabbadinINRA-BIA Toulouse

31326 Castanet-Tolosan Cedexsabbadin@toulouse.inra.fr

Régis Sabbadin - Journée PDMIA, 28 juin 2002

Processus Décisionnels Markoviens : Complexité de la résolution itérative

• Itération de la politique : O(|S|2+|A|.|S|2) – Evaluation :

Vt(s) = s’S p(s’|s,(s)).[ r(s,(s),s’)+. V

t(s’) ]– Amélioration :

’(s) = argmaxaA s’S p(s’|s,a).[ r(s,a,s’)+ .Vt(s’) ]

• Itération de la valeur : O(|A|.|S|2) – Itération : Vt+1(s) = maxaA s’S p(s’|s,a).[ r(s,a,s’)+.Vt(s’) ]

Explosion combinatoire !

Régis Sabbadin - Journée PDMIA, 28 juin 2002

Techniques de décomposition de PDMs

• Agrégation d’états / actions– réduction de la taille de l’espace d’états– utilisation de macro-actions

• Apprentissage par renforcement multi-agents– simulation / apprentissage de politiques partielles

• Décomposition de l’espace d’états / d’actions– décomposition parallèle– décomposition sérielle

Régis Sabbadin - Journée PDMIA, 28 juin 2002

Décomposition sérielle des PDMs- Généralités -

• Décomposer l’espace d’états – S=S1...Sk SiSj=, les Si étants « peu connectés »

• Topologie « en étoile »– Sommets : « noyaux » des Si (états non communiquants) – Centre (U) : ensemble « d’états communiquants »

• Programmation Dynamique Asynchrone :– Alterner des itérations de VI ou PI sur les Si avec des

évaluations de Vt (Vt ) sur U

Régis Sabbadin - Journée PDMIA, 28 juin 2002

Topologie en étoile

• Périphérie : Per(Si)={s’S\Si, sSi, aA, p(s’|s,a)0}

• Composant central, noyaux :– Composant central : U=i Per(Si)– Noyaux : Ki=Si\U

S1 S2

S3 S4

S1

Per(S1)

K1 K2

K3 K4

U

K1 K2

K3 K4

U

Régis Sabbadin - Journée PDMIA, 28 juin 2002

PDM locaux

Soit fonction réelle sur U, arbitraire• PDMi

= (SiPer(Si), A, pi, ri

)

Si-Ki

Ki

Per(Si)

Si- (s, s’) SiSi pi

(s,a,s’) = p(s,a,s’) ri

(s,a,s’) = r(s,a,s’)- (s, s’) Si-KiPer(Si) pi

(s,a,s’) = p(s,a,s’) ri

(s,a,s’) = (s’)

- s Per(Si) pi (s,a,s) = 1

ri(s,a,s’) = 0

Proposition : si = V*|U alors Vi* = V*|SiPer(Si)

Régis Sabbadin - Journée PDMIA, 28 juin 2002

Résolution « décomposée » itérative(Dean & Lin, 95)

Initialisation de V’= {, V1,..., Vk

};

Faire V V’; { Vi

, i } sol_partielle(PDMi

);

V’ {, V1,..., Vn

};

Mise à jour (s) maxaA s’S p(s’|s,a).[ r(s,a,s’)+.V’(s’) ]Tant que ||V’-V|| ;

Retourner V’.

K2K1

K3 K4

U

V1 V2

V3 V4

Régis Sabbadin - Journée PDMIA, 28 juin 2002

Décomposition automatique de l’espace d’états

• La résolution « décomposée » itérative est d’autant meilleure que :– La partition {S1,...,Sk} est « équilibrée »– |U| est faible

• Question : Comment générer une telle partition automatiquement et efficacement ?

• Réponse : Bipartition spectrale + Raffinement local

Régis Sabbadin - Journée PDMIA, 28 juin 2002

Graphe associé à un PDM

s s’maxa p(s,a,s’)0

Graphe G = (V, E)

Régis Sabbadin - Journée PDMIA, 28 juin 2002

Bipartition de graphe (nombre de coupures)

|S1| = 16, |S2| = 16, Cut = 10

Régis Sabbadin - Journée PDMIA, 28 juin 2002

Bipartition de graphe (nombre de coupures)

|S1| = 16, |S2| = 16, Cut = 2

Régis Sabbadin - Journée PDMIA, 28 juin 2002

Bipartition de graphe(nombre de coupures)

• Laplacien Q du graphe G = (V, E) :– Q(s,s’) = -1 ssi (s,s’) E– Q(s,s’) = 0 si s s’ et (s,s’) E – Q(s,s) = - ( s’ Q(s,s’) )

• Nombre de coupures d’une bipartition (S1,S2) :X = {xi} où xi=1 si xiS1 et xi=-1 si xiS2

Cut = 1/4 (XtQX)

Ce résultat est valable pour un graphe valué!

Régis Sabbadin - Journée PDMIA, 28 juin 2002

Bipartition minimale de graphe (Bipartition spectrale)

• Partition minimale :Trouver X = {xi} tel que xi{-1,1}, (| xi|) ,

minimisant Cut = 1/4 (XtQX)– Problème NP-complet

• Bipartition spectrale :Trouver Z, vecteur propre de Q associé à la valeur propre minimale Projeter Z sur {-1,1}n, en respectant la contrainte d’équilibre

Inefficace pour de grands graphes Réduction de graphe

Régis Sabbadin - Journée PDMIA, 28 juin 2002

Réduction de graphe valué(appariement maximal)

Cut = 4

Régis Sabbadin - Journée PDMIA, 28 juin 2002

Raffinement local de partition • La partition obtenue n’est pas minimale :

– On minimise le nombre de coupures, pas la taille de U– Bipartition spectrale approximative– Effet de la réduction du graphe

• Séquences successives d’échanges gloutons  de sommets, afin de minimiser P=|Per(S1) Per(S2)|

P=5P=6P=5P=3

Régis Sabbadin - Journée PDMIA, 28 juin 2002

Exemple de navigation

CPU résolution (MATLAB,biproc. PIII 600, Linux):

Itération de la valeur : 46.14s

I. V. Décomposée (fig. gauche) :

- Bipartition spectrale : 3.17s- Raffinement local : 2.37s- I.V. Décomp. : 20.27s

Total : 25.81 s

Régis Sabbadin - Journée PDMIA, 28 juin 2002

Validation expérimentale

• Paramètres :– Taille du problème |S| (200, 400, 800, 1600 états)– Nombre moyen de liens aléatoires (0, 5, 10, 20, ..., 160)

• Résultats :– Ratio |U|/|S|– Ratio CPU(Pol. It. Décomposée)/CPU(Pol. It.)

PDM 1 PDM 2Transitionsliens

Régis Sabbadin - Journée PDMIA, 28 juin 2002

Effet de la taille de U

0

0,2

0,4

0,6

0,8

1

1,2

1,4

1,6

0 0,05 0,1 0,15 0,2 0,25

ratio |U|/|S|

ratio

CPU

2004008001600

Validation expérimentale

Effet de la taille du PDM

0

0,2

0,4

0,6

0,8

1

1,2

1,4

1,6

200 400 800 1600

taille du PDM

ratio

CPU

0,020,050,1

Régis Sabbadin - Journée PDMIA, 28 juin 2002

Conclusions

• Décomposition automatique de PDMs– inspirée de méthodes de décomposition de graphes– complémentaire avec la résolution de PDMs décomposés

• Efficacité– utile pour des PDMs « faiblement couplés » de grande taille– plus intéressant si la décomposition peut être réutilisée

• Perspectivesdécomposition « par variable » dans les PDMs à représentation

factorisée