In computational complexity theory, a reduction is an approach to solving one problemby transforming it into another reference problem in which a solution already exists,thus providing the solution to the original problem in an efficient manner especiallywhen compared with solving the problem directly, which can be costly or even infeasible.The concept of reduction is not only limited to theory; in practice, humansuse past experience to solve problems by \emph{conforming} them, based on analogical reasoning, to known ones that are contained in references or memories.However, because the information retained in references is not always accurate and sometimes filled with redundancies or missing details, the conformation must somehow be robust enough to tolerate these uncertainties.In this thesis, we construct a framework for problem solving by reduction, and we present it in the robotics domain where contexts of problems can be represented using graphical spaces. The process has to match an input problem space to another one in a reference in order to retrieve a solution; we call this process spatial conformation. The content of this thesis can be divided into two parts.First, we develop a general approach and mathematical framework for a range of problem solving challenges to be addressed by reduction. Then we shift our attention to a class of constraint satisfaction problems formulated within the spatial conformation framework. An implementation for each part in robotics applications has been demonstrated to serve as empirical evaluation. / Selon la théorie de la complexité des algorithmes, une réduction est une approche pour résoudre unproblème en le transformant en un autre problème de référence qui a déjà été résolu. Ceci permet de trouver une solution à ce problème initial d'une manière efficace, comparemment à essayer de le résoudre directement, ce qui pourrait être coûteux ou même infaisable. Le concept de réduction n'est pas seulement constrainte à la théorie, en pratique,les humains utilisent leurs expériences pour résoudre de nouveaux problèmes en se basant surleurs raisonnements analogiques et en les conformant aux problémes qui se trouvent dans leurs références ou leurs souvenirs. Cependant, parce que les informations conservées dans les références ne sont pas toujours exactes etparfois manquent des détails, la conformation doit en quelque sorte être suffisamment robuste pour tolérer ces incertitudes. Dans cette thèse, nous construisons un systéme de résolution de problèmes basé sur la méthode de réduction, et nous le présentons dans le domaine de la robotique dans lequel les contextes des problèmes peuvent être représentés dans une espace geométrique. Nous définissons la conformation spatiale par le processus de correspondence entre un probléme d'origine et un autre probléme de référence. Tout d'abord, nous développons une approche générale pour résoudre une série de problèmes devant être traités par réduction. Par la suite, nous mettons l'accent sur une catégorie de problèmes de satisfaction de constraintesformulé dans le système de conformation spatiale. Une implémentation de chaque partie dans les applications de la robotique a été démontrée pour servir d'évaluation empirique.
| Identifer | oai:union.ndltd.org:LACETR/oai:collectionscanada.gc.ca:QMM.107862 |
| Date | January 2012 |
| Creators | Viriyasuthee, Chatavut |
| Contributors | Gregory L Dudek (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.0017 seconds