Processus de décision markovien

Résumé du document

Dossier sur le processus de décision markovien (MDP) aussi appelé problème de décision markovien, qui est un modèle stochastique issu de la théorie de la décision et de la théorie des probabilités. Le modèle MDP peut être vu comme une chaîne de Markov à laquelle on ajoute une composante décisionnelle. Comme les autres modèles de sa famille, il est entre autres, utilisé en intelligence artificielle pour le contrôle de systèmes complexes comme des agents intelligents.

Extraits

[...] Bien entendu, le nouveau fichier que l'utilisateur pourra proposer devra suivre cette syntaxe. La balise representation englobe toutes les données de notre fichier XML. A l'intérieur, nous déterminons différentes valeurs qui pourront par la suite être interprété comme des constantes au sein de notre programme. La balise capacite contient le champ max qui correspond au nombre de passager maximum qu'il peut y avoir dans l'avion. La balise cout contient deux champs qui sont alphac et alphag. Ces valeurs correspondent au cout unitaire des carences, et au cout unitaire des gaspillages. [...]

[...] La valuation d'une action se calcule de la façon suivante : Pour tout les fils de l'action i : Résultat = proba du fils * valuation du fils Fin pour Valuation de l'action = coût de l'action + résultat Puis la valuation finale sera le minimum de toutes les valuations. Action optimale Lors du calcul de nos valuations, nous déterminons la valuation minimum des différentes actions possibles. De même, lors du calcul, nous stockons dans le nœud père la meilleure action qu'il aura à réaliser par le biais de l'attribut : bestAction. [...]

[...] Le second champ correspond au nombre de passagers qui aura été défini aléatoirement. Et afin d'alléger le programme, le premier champ correspondant au nombre de repas prévus pour le vol sera identique au nombre de passager déterminer au préalable. (Nous aurions du faire la totalité des commandes, c'est-à-dire commande commande commande capacitéMax mais nous avons décidé d'alléger) De cette façon notre arbre est 22 fois moins grand pour un résultat identique. Le troisième champ p correspond à la probabilité de la racine de l'arbre. [...]

[...] C'est-à-dire affichage de la racine, puis de son premier fils puis affichage du premier fils de Pour chaque nœud de l'arbre, nous avons stockés le nombre de repas, le nombre de passager, le temps (entre 0 et la probabilité pour arriver au nœud, l'action réaliser pour y arriver, le coût, et la valuation. La valuation est calculé après avoir généré l'arbre. Formules utilisées 1 Coût Afin de calculer le coût, voici la formule que nous avons utilisée. La formule coût prend un paramètre qui est le temps. En effet plus on avance dans le temps, c'est-à-dire vers le décollage de l'avion, plus les frais engendrés pour se fournir de nouveaux repas sont élevés. [...]

[...] Elle prend en paramètre les enfants d'un nœud de l'action optimale précédemment trouvé. Chargement du fichier OK Mon Random 0.21327957481378168 N choisi 50 Fils 5 nbRepas: 0 nbPassager: 50 temps: 5 proba: 0.26 action: 0 cout: 0.0 valuation: 759.88983381 Random tiré pour determiné l'état au temps Temps Proba de l'état 0.1 Temps Proba de l'état 0.63 Temps Proba de l'état 0.27 Fils 4 nbRepas: 50 nbPassager: 40 temps: 4 proba: 0.1 action: 50 cout: 500.0 valuation: 258.6279655 Random tiré pour determiné l'état au temps Temps Proba de l'état 0.05 Temps Proba de l'état 0.85 Temps Proba de l'état 0.1 Fils 3 nbRepas: 30 nbPassager: 40 temps: 3 proba: 0.85 action: -20 cout: 300.0 valuation: - 41.53665 Random tiré pour determiné l'état au temps Temps Proba de l'état 0.01 Temps Proba de l'état 0.85 Temps Proba de l'état 0.14 Fils 2 nbRepas: 45 nbPassager: 40 temps: 2 proba: 0.85 action: 15 cout: - 50.0 valuation: 8.5655 Random tiré pour determiné l'état au temps Temps Proba de l'état 0.03 Temps Proba de l'état 0.85 Temps Proba de l'état 0.11 Fils 1 nbRepas: 30 nbPassager: 50 temps: 1 proba: 0.11 action: -15 cout: 15.0 valuation: - 8.15 Random tiré pour determiné l'état au temps Temps Proba de l'état 0.67 Temps Proba de l'état 0.29 Temps Proba de l'état 0.04 Fils 0 nbRepas: 40 nbPassager: 40 temps: 0 proba: 0.67 action: 10 cout: - 10.0 valuation: 0.0 Au lancement du programme comme expliqué en nous tirons un nombre compris entre 0 et 1. [...]