Processus de décision markovien partiellement observable

En théorie de la décision et de la théorie des probabilités, un processus de décision markovien partiellement observable (POMDP pour partially observable Markov decision process) est une généralisation d'un processus de décision markoviens (MDP pour Markov decision process). Comme dans un MDP, l'effet des actions est incertain mais, contrairement à ce qui se passe pour un MDP, l'agent n'a qu'une information partielle de l'état courant. Les POMDP sont des modèles de Markov cachés (HMM pour hidden Markov model) particuliers, dans lesquels on dispose d'actions probabilistes. Le tableau suivant montre la place des POMDP dans la famille des processus de décision :

	aucun contrôle des transitions (i.e. pas de noms d'actions)	contrôle des transitions (i.e. avec des noms d'actions)
états observables	Chaînes de Markov	MDP
états partiellement observables	HMM	POMDP

Les modèles de cette famille sont, entre autres, utilisés en intelligence artificielle pour le contrôle de systèmes complexes comme des agents intelligents.

Définition formelle

Un POMDP est un tuple $\{S,A,T,R,\Omega ,O\}\,$ où :

• $S$ est un ensemble fini non vide des états possibles du système à contrôler (il s'agit des états cachés du processus) ;
• $A$ est l'ensemble fini non vide 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 \mathbb {R}$ est la fonction de récompense. Elle indique la valeur réelle obtenue lorsque l'on effectue l'action $a$ dans l'état $s$ et que l'on arrive dans l'état $s'$ ;
• $\Omega$ est un ensemble de symboles observables ;
• $O:S\times \Omega \to [0;1]$ est une fonction d'observation qui à un état donné associe la probabilité $p(\omega |s)=O(s,\omega )\,$ d'observer un symbole donné.

Note : il existe des variantes dans lesquelles les récompenses peuvent dépendre des actions ou des observations. Les observations peuvent également dépendre des actions effectuées.

Approches

Il existe deux grands types d'approches pour s'attaquer à un problème POMDP.

• On peut chercher à déterminer de la façon la plus certaine possible quel est l'état dans lequel on se trouve (en maintenant à jour une distribution de probabilité sur les états appelée belief-state).
• On peut travailler directement sur les observations [2] de $\Omega$ sans considérer l'état caché. Cela n'est pas sans poser de problèmes car des observations similaires peuvent être obtenues dans des états différents (par exemple, avec l'observation locale des carrefours dans un labyrinthe, on peut très bien tomber sur deux carrefours en forme de T). Une approche possible pour discriminer ces observations consiste à garder une mémoire des observations rencontrées par le passé (dans ce cas, on perd la propriété markovienne).

Extension

Il existe des variantes multi-agents des POMDP, appelés les Dec-POMDP (Dec pour décentralisé).

Articles connexes

• Les Processus de Décision Markoviens (MDP), dont dérivent les POMDP pour l'aspect décision,
• Modèle de Markov caché, dont dérivent les POMDP pour l'aspect observabilité partielle,
• Processus stochastique

Sources

1. Kaebling L. P., Littman M. L., Cassandra A. R., Planning and Acting in Partially Observable Stochastic Domains, Artificial Intelligence, vol. 101, num. 1–2, pp. 99-134, 1998.
2. McCallum A. K., Reinforcement learning with selective perception and hidden state, PhD thesis, University of Rochester, Computer Science Dept., 1996.

Liens externes

• Tony's POMDP Page est une page de ressources d'Anthony R. Cassandra
• POMDP information page, la page de ressources de Michael L. Littman