Cette thèse porte sur la planification en environnement incertain, dont un modèle classique sont les Processus Décisionnels de Markov (MDP). Nous utilisons des modèles structurés de MDP, basés sur les Diagrammes de Décision Algébriques (ADD), qui permettent de modéliser symboliquement le système décisionnel sous une forme factorisée par variables d’état. Dans une première contribution, nous proposons de réduire le nombre de variables d’état en énumérant localement le MDP symbolique, puis en appliquant des techniques de décomposition de graphes sur le sous-MDP énuméré. Le nombre de variables diminuant, l'espace d’états et les ADD sont plus petits, ce qui facilite l'optimisation du MDP. D’autre part, le problème peut être difficile à modéliser lorsque le nombre de valeurs (arité) des variables d’état est important, car les arbres de décision du modèle deviennent très grands. Ainsi, notre deuxième contribution consiste à modéliser le problème sous forme de Réseau Bayésien Dynamique Générique et Hiérarchique, où certaines variables sont des abstractions de variables de grande arité. Notre modèle générique est paramétré puis automatiquement instancié par des macro-actions définies sur le sous-espace engendré par les variables de grande arité. Nous montrons l'efficacité de notre approche hiérarchique et symbolique sur des problèmes de déplacement et de prise d'information, dont la variable de navigation a une arité généralement très grande. Les macro-actions sont des macro-déplacements locaux, définis dans des régions distinctes du sous-espace de navigation. Enfin, dans une troisième contribution, nous proposons une classe d'algoritlnnes symboliques et heuristiques, qui permettent d'optimiser partiellement un MDP sur un sous-espace d’états atteignables, connaissant des états initiaux possibles du processus. Nous présentons une heuristique de plus sûr chemin stochastique, qui cible la recherche des stratégies optimales sur les buts du problème. Le MDP est ensuite optimisé en alternant une phase d’expansion du sous-espace atteignable, et une phase de programmation dynamique stochastique sur le sous-espace atteignable courant. Nous proposons également une version en ligne de notre algorithme, qui optimise MDP sur une liste de sous-buts qui augmente incrémentalement durant la mission. Nous montrons l'efficacité de notre algorithme sur des problèmes de déplacement et de prise d'information de grande taille.