A stochastic point-based algorithm for Partially Observable Markov Decision Processes

Authors: Tobin, Ludovic
Advisor: Laviolette, François
Abstract: Decision making under uncertainty is a popular topic in the field of artificial intelligence. One popular way to attack such problems is by using a sound mathematical model. Notably, Partially Observable Markov Processes (POMDPs) have been the subject of extended researches over the last ten years or so. However, solving a POMDP is a very time-consuming task and for this reason, the model has not been used extensively. Our objective was to continue the tremendous progress that has been made over the last couple of years, with the hope that our work will be a step toward applying POMDPs in large-scale problems. To do so, we combined different ideas in order to produce a new algorithm called SSVI (Stochastic Search Value Iteration). Three major accomplishments were achieved throughout this research work. Firstly, we developed a new offline POMDP algorithm which, on benchmark problems, proved to be more efficient than state of the arts algorithm. The originality of our method comes from the fact that it is a stochastic algorithm, in comparison with the usual determinist algorithms. Secondly, the algorithm we developed can also be applied in a particular type of online environments, in which this algorithm outperforms by a significant margin the competition. Finally, we also applied a basic version of our algorithm in a complex military simulation in the context of the Combat Identification project from DRDC-Valcartier.
Document Type: Mémoire de maîtrise
Issue Date: 2008
Open Access Date: 13 April 2018
Permalink: http://hdl.handle.net/20.500.11794/19764
Grantor: Université Laval
Collection:Thèses et mémoires

Files in this item:
SizeFormat 
25194.pdf864.78 kBAdobe PDFView/Open
All documents in CorpusUL are protected by Copyright Act of Canada.