Un robot mobile évoluant dans un environnement dynamique doit faire face à de nombreuses incertitudes. Les actions qu'il exécute n'ont pas toujours l'effet escompté, et ses capteurs lui renvoient des données souvent bruitées. Les processus décisionnels de Markov (MDP), du fait de leur adaptation à la prise en compte d'incertitudes, sont étudiés depuis quelques années dans la communauté intelligence artificielle. Ceux-ci permettent le calcul d'un plan plus robuste que les méthodes de planification classiques, puisque calculé en prenant en compte les diverses conséquences probables des actions. Dans le cadre de la robotique mobile, ce modèle permet également de superviser l'exécution des missions, en utilisant des fonctions probabilistes pour aider le robot à se localiser. Mais les algorithmes classiques de résolution de MDP sont complexes, ce qui les rend difficilement adaptables à des environnements de grande taille, tels que ceux nécessités dans le cadre de la robotique. En conséquence, beaucoup de travaux s'intéressent aux techniques d'approximation, qui permettent d'obtenir des plans sous-optimaux en un temps de calcul réduit. C'est dans ce cadre que s'inscrit cette thèse. Apres avoir montré comment nous paramétrons un MDP pour l'appliquer à la robotique mobile, nous présentons deux techniques d'approximation. La première utilise l'agrégation d'états, chaque couloir de l'environnement donnant lieu à un ou plusieurs états abstraits. La seconde est fondée sur la décomposition d'environnements, lesquels sont représentés à l'aide d'un graphe value permettant d'approcher heuristiquement les valeurs des états. Ces deux méthodes permettent de réduire considérablement les temps de calcul, et donnent des plans très proches de l'optimal.