[boussole] POMDP, une démo en ligne : description détaillée

Les pages sur le POMDP :

.

Description détaillée

Principe

Un robot est déposé dans un labyrinthe. Le robot doit se déplacer vers le drapeau. L'utilisateur peut prendre le robot et le déposer n'importe où, de façon à voir comment le robot se perd, puis retrouve son chemin. Le robot utilise un processus de décision markovien partiellement observable.

Ce que le robot sait

Le robot connaît la carte du labyrinthe et il sait quelle action faire en chaque case du labyrinthe.

Par ailleurs, il se connaît parfaitement : il sait qu'il dérive et que ses capteurs ne sont pas toujours fiables, et il connaît les probabilités qui régissent ses déplacements et ses capteurs.

En plus de ces connaissances a priori, le robot dispose de quatre capteurs de murs : il peut voir s'il y a un mur contre lui à sa gauche, à sa droite, devant lui ou derrière lui.

Enfin, le robot sait que le jeu est terminé lorsqu'il atteint le drapeau, donc qu'il n'a pas atteint le drapeau si le jeu n'est pas terminé : la probabilité d'être au drapeau est ainsi toujours 0 (sauf quand il y est effectivement).

Le robot n'est pas fiable

Probas après 10 déplacements

Dans un labyrinthe vide, le robot part de la croix et avance dix fois vers la droite. La position la plus probable (en jaune) correspond à un déplacement de 9 cases vers la droite. Les probabilités des autres positions sont indiquées par un niveau de gris (plus foncé = plus probable).

Lorsque le robot se déplace (ce qu'il fait à chaque tour), il a 70% de chance d'arriver dans la case prévue, mais également 10% de chance de dériver d'une case vers la gauche, 10% de chance de dériver d'une case vers la droite, et 10% de chance de déraper sur le sol et de ne pas changer de case.

Le robot ne se trompe pas de direction (prendre le haut de la grille pour la droite, par exemple).

Ce modèle est donc simpliste mais si l'on se place non plus à l'échelle d'une itération mais d'une dizaine d'itérations, on retrouve une répartition des probabilités plus réaliste.

Les capteurs de murs sont fiables en temps normal mais ne le sont plus lorsque le robot percute un mur. Il a alors 45% de chance de ne pas voir le mur qu'il a percuté et les trois autres capteurs ont eux 35% de chance de se tromper (détecter un mur alors qu'il n'y en a pas, ou inversement).

Sur la réalisation du film

L'animation est en Flash (Flash 5). Le film flash est créé par un programme C++ grace à Ming, une bibliothèque qui permet de créer des films Flash à partir de programmes PHP, C++, C, perl et python.

Le code source est disponible librement selon les termes de la licence GNU GPL.

Revenir en haut de la page.