Prise de décision dans l’incertain
et durée explicite

Auteur : Vincent Thomas et Olivier Buffet

Informations générales

Encadrants	Vincent Thomas	Olivier Buffet
Adresse
Téléphone	03 54 95 85 08	03 54 95 86 15
Email	vincent.thomas@loria.fr	olivier.buffet@loria.fr
Bureau	C125	C124

Motivation

De nombreux travaux cherchent à contrôler l’état d’un système dynamique pour maximiser une fonction de performance, par exemple pour qu’un robot atteigne une situation en minimisant ses coûts de déplacement. Cependant, la durée des actions executées ou la durée des processus mis en œuvre dans l’environnement n’est souvent pas modélisée finement. Ceci peut devenir un obstacle lorsqu’on souhaite, par exemple, planifier les actions d’un robot qui doit agir avec un être humain. En effet, dans ce cas, le robot doit être capable d’estimer les durées (variables) des tâches effectuées par l’humain et de ses propres actions pour pouvoir agir correctement et au bon moment. Ce stage cherchera ainsi à voir comment représenter explicitement la notion de durée et en tirer parti pour proposer des algorithmes capables de résoudre des problèmes de prise de décision dans l’incertain (en particulier dans un cadre de collaboration homme-robot).

Sujet

Le cadre des MDP (Markov Decision Process) permet de représenter des problèmes de prise de décision séquentielle lorsque l’agent connaît l’état du monde mais que les actions qu’il effectue ont des résultats incertains. On souhaite dans un premier temps explorer ce cadre lorsque les actions effectuées ont des durées variables (par exemple des macro-actions constituées d’un certain nombre de sous-actions) ou lorsque certains processus ont des durées incertaines (mais que l’on peut quantifier). On abordera ensuite des problèmes plus complexes quand par exemple l’agent n’a plus accés à l’état du monde mais uniquement à des observations qui en dépendent (cadre des POMDP – Partially Observable Markov Decision Process).

L’objectif du stage consistera (i) à étudier les modèles de prise de décision markoviens intégrant explicitement la notion de durée et les algorithmes existants; (ii) à proposer et valider de nouveaux algorithmes permettant d’aborder ces problèmes tout en évitant une explosion du temps de calcul.

Cadre du travail

Dans un premier temps, il faudra se familiariser avec les formalismes MDP et POMDP et les formalismes intégrant explicitement la notion du durée (SMDP et POSMDP). Dans un second temps, on proposera et on cherchera à modéliser des problèmes de prise de décision en observabilité partielle pour lesquels raisonner sur la dimension temporelle est nécessaire pour agir optimalement. Dans un troisième temps, on proposera des algorithmes pour aborder ces problèmes. Ceux-ci seront ensuite implémentés et évalués expérimentalement et théoriquement.

References

Sutton, R. S., Precup, D. and Singh S. 1999. Between MDPs and semi-MDPs: A framework for temporal abstraction in reinforcement learning. In Artificial intelligence, 112, 181–211, 1999.

Younes, H. L. S. and Simmons, R. G. 2004. Solving generalized semi-Markov decision processes using continuous phase-type distributions. In Proceedings of the 19th National Conference on Artifical Intelligence (AAAI’04).

Lim, Z. L., Sun, L. and Hsu, D. 2011. Monte Carlo value iteration with macro-actions. In Advances in Neural Information Processing Systems 24 (NIPS-2011).