Finding optimal paths on dynamic road networks

Authors: Bergeron Guyard, Alexandre
Advisor: Laviolette, François
Abstract: 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.
Document Type: Mémoire de maîtrise
Issue Date: 2008
Open Access Date: 13 April 2018
Permalink: http://hdl.handle.net/20.500.11794/20548
Grantor: Université Laval
Collection:Thèses et mémoires

Files in this item:
SizeFormat 
25830.pdf1.8 MBAdobe PDFView/Open
All documents in CorpusUL are protected by Copyright Act of Canada.