LOGIN TO YOUR ACCOUNT

Username
Password
Remember Me
Or use your Academic/Social account:

CREATE AN ACCOUNT

Or use your Academic/Social account:

Congratulations!

You have just completed your registration at OpenAire.

Before you can login to the site, you will need to activate your account. An e-mail will be sent to you with the proper instructions.

Important!

Please note that this site is currently undergoing Beta testing.
Any new content you create is not guaranteed to be present to the final version of the site upon release.

Thank you for your patience,
OpenAire Dev Team.

Close This Message

CREATE AN ACCOUNT

Name:
Username:
Password:
Verify Password:
E-mail:
Verify E-mail:
*All Fields Are Required.
Please Verify You Are Human:
fbtwitterlinkedinvimeoflicker grey 14rssslideshare1
Languages: French
Types: Article
Subjects: Planification stochastique, Algorithmes symboliques et heuristiques, Robotique autonome, 629.8
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. This PhD deals with planning under uncertainty for which Markov Decision Processes (MDPs) are a classical model. We study structured models of MDPs based on Algebraic Decision Diagrams (ADDs) which allow to symbolically model the decision system in a factored fashion using state variables. Our first contribution aims at reducing the number of state variables by locally enumerating the symbolic MDP, then by applying graph decomposition techniques over the enumerated sub-MDP. The more the number of variables decreases, the smaller state space and ADDs are, and the easier the MDP optimization is made. Moreover, the problem modelling may be difficult if some state variables have a lot of possible values (arity) because the size of decision trees used in the model noticeably increases. Also, our second contribution consists in modelling the problem with a Generic Hierarchical Dynamic Bayesian Network where some variables are abstractions of large arity variables. Our generic model is parametrized and automatically instantiated by macro-actions defined on the subspace that is generated by large arity variables. \/Ve demonstrate the efficiency of our hierarchical and symbolic approach with moving and data acquisition problems whose navigation variable arity is typically very large. The macro-actions are local movings defined in distinct regions of the navigation subspace. Finally, in our third contribution, we propose a class of symbolic and heuristic algorithms shaped to partially optimize a MDP over a reachable state subspace if some possible initial states of the process are known prior to the optimization. We present a safest stochastic path heuristics which focuses the search of optimal strategies on the problem’s goals. Then, the MDP is optimized by alternating a reachable subspace expansion step and a stochastic dynamic programming step over the current reachable subspace. We also propose an on-line version of our algorithm which optimizes the MDP with a list of sub-goals which gradually increases during the mission. The algorithm efficiency is shown on the basis of large moving and data acquisition problems.
  • No references.
  • No related research data.
  • No similar publications.

Share - Bookmark

Cite this article