Planning under uncertainty is an increasingly important research field, and it is clear that the design of robust and scalable algorithms which consider uncertainty is key to the development of effective autonomous and semi-autonomous systems. Partially Observable Markov Decision Processes (POMDPs) offer a powerful mathematical framework for making optimal action choices in noisy and/or uncertain environments. However, integration of the POMDP model with real world applications has been slow due to the high computation cost of exact approaches to POMDP planning. / In recent years, point-based POMDP solvers have emerged as efficient methods for providing approximate solutions by planning over a small subset of the belief space. This thesis first provides a survey on many of the proposed point-based POMDP solvers. We then conduct an empirical analysis on the key components of point-based methods, the belief collection and belief updating processes. This is an important contribution, as previous publications on point-based methods have only compared full algorithms, without comparing the underlying processes. As well, we verify the effect of a variety of parameters and optimizations that could be used within a point-based solver. Experiments are conducted on a variety of POMDP environments. / L'importance grandissante de la recherche dans le domaine de la planification sous incertitude est signe que l'élaboration d'algorithmes robustes et extensibles qui gèrent l'incertitude est un élément clé dans le développement de systèmes autonomes et semi-autonomes efficaces. Les processus de décision markoviens partiellement observables (POMDP) constituent une puissante fondation mathématique pour le choix d'actions optimales dans un environnement incertain. Il a cependant été difficile d'incorporer les POMDPs à des applications réelles, à cause de leur coût de calcul élevé lorsqu'une solution exacte est requise. / Récemment, les approches de résolution de POMDPs dites par points, qui planifient sur un petit sous-ensemble de l'état des croyance, se sont révélées être efficaces pour obtenir des solutions approximatives. Le présent m´emoire propose tout d'abord une revue de plusieurs approches par points. Par la suite, une analyse empirique des composantes primordiales des approches par points, de la collecte d'observations, ainsi que du processus de mise à jour de l'état des croyance, est proposée. De plus, les effets de différents paramètres et optimisations liés aux approches par points sont vérifiés. Des expériences sont conduites avec une variété d'environnements de type POMDP.
| Identifer | oai:union.ndltd.org:LACETR/oai:collectionscanada.gc.ca:QMM.92275 |
| Date | January 2010 |
| Creators | Kaplow, Robert |
| Contributors | Joelle Pineau (Internal/Supervisor) |
| Publisher | McGill University |
| Source Sets | Library and Archives Canada ETDs Repository / Centre d'archives des thèses électroniques de Bibliothèque et Archives Canada |
| Language | English |
| Detected Language | French |
| Type | Electronic Thesis or Dissertation |
| Format | application/pdf |
| Coverage | Master of Science (School of Computer Science) |
| Rights | All items in eScholarship@McGill are protected by copyright with all rights reserved unless otherwise indicated. |
| Relation | Electronically-submitted theses. |
Page generated in 0.0022 seconds