Processus de decision markovien

Processus de decision markovien

Processus de décision markovien

Un processus de décision markovien (MDP) aussi appelé problème de décision markovien 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.

Un MDP permet de prendre des décisions dans un environnement

  • lorsque l'on a une certitude sur l'état dans lequel on se trouve
  • en présence d'incertitude sur l'effet des actions.

Sommaire

Définition

Cycle de contrôle d'un processus de décision markovien

Définition intuitive

Afin de comprendre ce qu'est un MDP, supposons que l'on ait un système évoluant dans le temps comme un automate probabiliste. À chaque instant le système est dans un état donné et il existe une certaine probabilité pour que le système évolue vers tel ou tel autre état à l'instant suivant en effectuant une transition.

Supposons maintenant que l'on doive contrôler ce système boite noire de la meilleure façon possible. L'objectif est de l'amener dans un état considéré comme bénéfique, en évitant de lui faire traverser des états néfastes. Pour cela, on dispose d'un ensemble d'actions possibles sur le système. Pour compliquer la chose, on supposera que l'effet de ces actions sur le système est probabiliste : l'action entreprise peut avoir l'effet escompté ou un tout autre effet. L'efficacité du contrôle est mesurée relativement au gain ou à la pénalité reçue au long de l'expérience.

Ainsi, un raisonnement à base de MDP peut se ramener au discours suivant : étant dans tel cas et choisissant telle action, il y a tant de chance que je me retrouve dans tel nouveau cas avec tel gain.

Pour illustrer les MDP, on prend souvent des exemples issus de la robotique mobile (avec les positions pour états, les commandes comme actions, les mouvements comme transitions et l'accomplissement/échec de tâches comme gains/pénalités).

Hypothèse de Markov

Dans les MDP, l'évolution du système est supposée correspondre à un processus markovien. Autrement dit, le système suit une succession d'états distincts dans le temps et ceci en fonction de probabilités de transitions. L'hypothèse de Markov consiste à dire que les probabilités de transitions ne dépendent que des n états précédents. En général, on se place à l'ordre n = 1, ce qui permet de ne considérer que l'état courant et l'état suivant.

Définition formelle

Un MDP est un quadruplet \{ S, A, T, R \}\, où :

  • S = \{ s_0, \cdots , s_{ |S| } \} \, est l'ensemble fini discret des états possibles du système à contrôler
  • A = \{ a_0, \cdots , a_ {|A| } \} \, est l'ensemble fini discret des actions que l'on peut effectuer pour contrôler le système
  • T : S \times A \times S \to [ 0 ; 1 ]\, est la fonction de transition du système en réaction aux actions de contrôle.

Dans le cas général, la fonction T est probabiliste et donne la probabilité p (s' | s, a) = T (s, a, s') \, que le système passe de l'état s à l'état s' lorsque l'on choisit d'effectuer l'action a.

  • R : S \times A \times S \to \Re est la fonction de récompense. Elle indique la valeur réelle obtenue lorsque l'on effectue l'action a dans l'état s pour arriver dans l'état s'.

Exemple de MDP

Exemple simple de Processus de Décision Markovien à trois états et à deux actions.

L'exemple donné ci-contre représente un Processus de Décision Markovien à trois états distincts {S0,S1,S2} représentés en vert. Depuis chacun des états, on peut effectuer une action de l'ensemble {a0,a1}. Les nœuds rouges représentent donc une décision possible (le choix d'une action dans un état donné). Les nombres indiqués sur les flèches sont les probabilités d'effectuer la transition à partir du nœud de décision. Enfin, les transitions peuvent générer des récompenses (dessinées ici en jaune).

  • La matrice de transition associée à l'action a0 est la suivante :

\begin{pmatrix} 0.50 & 0 & 0.50 \\ 0.70 & 0.10 & 0.20 \\ 0.40 & 0 & 0.60 \end{pmatrix}

  • La matrice de transition associée à l'action a1 est la suivante :

\begin{pmatrix} 0 & 0 & 1.0 \\ 0 & 0.95 & 0.05 \\ 0.30 & 0.30 & 0.40 \end{pmatrix}

En ce qui concerne les récompenses,

  • on perçoit une récompense de +5 lorsque l'on passe de l'état S1 à l'état S0 en accomplissant l'action a0
  • on perçoit une récompense de -1 (aussi appelée pénalité) lorsque l'on passe de l'état S2 à l'état S0 en accomplissant l'action a1

Remarques

Le modèle MDP présenté ici est supposé stable dans le temps, c'est-à-dire que les composants du quadruplet sont supposés invariants. Il n'est donc pas applicable en l'état pour un système qui évolue, par exemple pour modéliser un système qui apprend contre un autre agent.

Notion de politique

Dans le cadre des MDP, la politique \pi : S \to A est une suite qui indique pour chaque état quelle est l'action à effectuer. Il s'agit là d'une politique déterministe, dans laquelle il n'y a pas d'ambiguïté sur l'action à effectuer. On note Π l'ensemble des politiques déterministes.

Note : Il est possible d'introduire du hasard dans le choix de l'action, comme si on tirait aléatoirement l'action à effectuer. Dans ce cas, on parlera de politique stochastique \pi : S \times A \to [ 0 ; 1 ]

Problèmes possibles

  • Planification : Il s'agit, étant donné un MDP {S,A,T,R} de trouver quelle est la politique π qui maximise la récompense,
  • Améliorer une politique connue : Soit une politique π0, on souhaite trouver une meilleure politique,
  • Apprentissage d'une politique sans connaitre le modèle
    • à partir de traces d'exécution
    • au cours d'expériences sur le modèle

Articles connexes

Voir aussi :

Références

Ce document provient de « Processus de d%C3%A9cision markovien ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Processus de decision markovien de Wikipédia en français (auteurs)

Игры ⚽ Поможем сделать НИР

Regardez d'autres dictionnaires:

  • Processus de Décision Markovien — Un processus de décision markovien (MDP) aussi appelé problème de décision markovien 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… …   Wikipédia en Français

  • Processus de décision markovien — Un processus de décision markovien (MDP) 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.… …   Wikipédia en Français

  • Processus de decision markovien partiellement observable — Processus de décision markovien partiellement observable Un Processus de décision markovien partiellement observable (POMDP) est un modèle stochastique issu de la théorie de la décision et de la théorie des probabilités. Les modèles de cette… …   Wikipédia en Français

  • Processus de décision markovien partiellement observable — Un Processus de décision markovien partiellement observable (POMDP) est un modèle stochastique issu de la théorie de la décision et de la théorie des probabilités. Les modèles de cette famille sont, entre autres, utilisés en intelligence… …   Wikipédia en Français

  • Processus de Markov — En mathématiques, un processus de Markov est un processus stochastique possédant la propriété de Markov. Dans un tel processus, la prédiction du futur à partir du présent n est pas rendue plus précise par des éléments d information concernant le… …   Wikipédia en Français

  • POMDP — Processus de décision markovien partiellement observable Un Processus de décision markovien partiellement observable (POMDP) est un modèle stochastique issu de la théorie de la décision et de la théorie des probabilités. Les modèles de cette… …   Wikipédia en Français

  • Planification (intelligence artificielle) — La planification (Automated planning) est une discipline de l intelligence artificielle qui vise le développement d algorithmes pour produire des plans (en d autre termes, une planification), typiquement pour l exécution par un robot ou tout… …   Wikipédia en Français

  • Planification en intelligence artificielle — Planification (intelligence artificielle) La planification (Automated planning) est une discipline de l intelligence artificielle qui vise le développement d algorithmes pour produire des plans (en d autre termes, une planification), typiquement… …   Wikipédia en Français

  • Automate de Markov à états cachés — Modèle de Markov caché Pour les articles homonymes, voir MMC. Un modèle de Markov caché (MMC) en anglais Hidden Markov Models (HMM) (ou plus correctement, mais moins employé automate de Markov à états cachés) est un modèle statistique dans lequel …   Wikipédia en Français

  • HMM — Modèle de Markov caché Pour les articles homonymes, voir MMC. Un modèle de Markov caché (MMC) en anglais Hidden Markov Models (HMM) (ou plus correctement, mais moins employé automate de Markov à états cachés) est un modèle statistique dans lequel …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”