Ce document examine différentes méthodes pour calculer des chemins optimaux sur des
graphes dynamiques. Deux grandes approches sont comparées: l’approche déterministe et
l’approche probabiliste. L’approche déterministe prend pour acquise une certaine connaissance
préalable des changements à venir dans l’environnement. L’approche probabiliste tente
de modéliser et traiter l’incertitude. Une variante dynamique de l’algorithme de Dijkstra
est détaillée dans le contexte déterministe. Les paradigmes des Markov Decision Processes
(MDP) et Partially Observable Markov Decision Processes sont explorés dans le cadre du
problème probabiliste. Des applications et mesures sont présentées pour chaque approche.
On constate une relation inverse entre la calculabilité des approches proposées et leur potentiel
d’application pratique. L’approche déterministe représente une solution très efficace
à une version simplifiée du problème. Les POMDP s’avèrent un moyen théorique puissant
dont l’implantation est impossible pour des problèmes de grande taille. Une alternative est
proposée dans ce mémoire à l’aide des MDP. / This document examines different methods to compute optimal paths on dynamic graphs.
Two general approaches are compared: deterministic and probabilistic. The deterministic approach
takes for granted knowledge of the environment’s future behaviour. The probabilistic
approach attempts to model and manage uncertainty. A dynamic version of Dijkstra’s algorithm
is presented for the deterministic solution. Markov Decision Processes and Partially
Observable Markov Decision Processes are analysed for the probabilistic context. Applications
and measures of performance are given for each approach. We observe a reverse relationship
between computability and applicability of the different approaches. Deterministic
approaches prove a fast and efficient way to solve simpler versions of the problem. POMDPs
are a powerful theoretical model that offers little potential of application. An alternative is
described through the use of MDPs.
| Identifer | oai:union.ndltd.org:LACETR/oai:collectionscanada.gc.ca:QQLA.2008/25830 |
| Date | 12 1900 |
| Creators | Bergeron Guyard, Alexandre |
| Contributors | Laviolette, François |
| Publisher | Université Laval |
| Source Sets | Library and Archives Canada ETDs Repository / Centre d'archives des thèses électroniques de Bibliothèque et Archives Canada |
| Language | French |
| Detected Language | French |
| Type | Electronic Thesis or Dissertation |
| Format | text/html, application/pdf |
| Rights | © Alexandre Bergeron Guyard, 2008 |
Page generated in 0.0107 seconds