Implantation d'imagerie temps réel par ondes guidées pour écran tactile

Les techniques d'imagerie développées pour la surveillance embarquée des structures ont maintenant des applications dans d'autres domaines. Par exemple, le domaine de l'écran tactile est en pleine expansion et de nouvelles technologies commencent à apparaître pour des applications spécifiques. Au niveau médical, des surfaces tactiles pouvant fournir des données sur la répartition du poids et la posture seraient une avancée pour le diagnostique des patients et la recherche. L'écran tactile est une technologie utilisée dans un nombre croissant d'appareils. Les écrans tactiles capacitifs et résistifs dominent le marché, mais ils sont connus pour être difficiles à fabriquer, facilement cassables et coûteux pour les grandes dimensions. Par conséquent, de nouvelles technologies sont encore explorées pour les écrans tactiles de grandes tailles et robustes. Les technologies candidates comprennent des approches basées sur les ondes. Parmi eux, des ondes guidées sont de plus en plus utilisés dans la surveillance des structures (SHM) pour de nombreuses applications liées à la caractérisation des propriétés des matériaux. Les techniques d'imagerie utilisées en SHM telles que Embedded Ultrasonic Structural Radar (EUSR) et Excitelet sont fiables, mais elles ont souvent besoin d'être couplées avec du traitement d'image pour donner de bons résultats. Dans le domaine du NDT (essais non destructifs), les ondes guidées permettent d'analyser les structures sans les détériorer. Dans ces applications, les algorithmes d'imagerie doivent pouvoir fonctionner en temps réel. Pour l'écran tactile, une technique d'imagerie de la pression en temps réel doit être développée afin d'être efficace et performante. Il faut obtenir la position et l'amplitude de la pression appliquée en un ou plusieurs points sur une surface. C'est ici que les algorithmes et l'expertise par rapport aux ondes guidées seront mises de l'avant tout pensant à l'optimisation des calculs afin d'obtenir une image en temps réel. Pour la méthodologie, différents algorithmes d'imagerie sont utilisés pour obtenir des images de déformation d'un matériau et leurs performances sont comparées en termes de temps de calcul et de précision. Ensuite, plusieurs techniques de traitement d'images ont été implantées pour comparer le temps de calcul en regard de la précision dans les images. Pour l'écran tactile, un prototype est conçu avec un programme optimisé et les algorithmes offrant les meilleures performances pour un temps de calcul réduit. Pour la sélection des composantes électroniques, ce sont la vitesse d'exécution et la définition d'image voulues qui permettent d'établir le nombre d'opérations par seconde nécessaire.

Dynamic Programming Approaches for Estimating and Applying Large-scale Discrete Choice Models

People go through their life making all kinds of decisions, and some of these decisions affect their demand for transportation, for example, their choices of where to live and where to work, how and when to travel and which route to take. Transport related choices are typically time dependent and characterized by large number of alternatives that can be spatially correlated. This thesis deals with models that can be used to analyze and predict discrete choices in large-scale networks. The proposed models and methods are highly relevant for, but not limited to, transport applications. We model decisions as sequences of choices within the dynamic discrete choice framework, also known as parametric Markov decision processes. Such models are known to be difficult to estimate and to apply to make predictions because dynamic programming problems need to be solved in order to compute choice probabilities. In this thesis we show that it is possible to explore the network structure and the flexibility of dynamic programming so that the dynamic discrete choice modeling approach is not only useful to model time dependent choices, but also makes it easier to model large-scale static choices. The thesis consists of seven articles containing a number of models and methods for estimating, applying and testing large-scale discrete choice models. In the following we group the contributions under three themes: route choice modeling, large-scale multivariate extreme value (MEV) model estimation and nonlinear optimization algorithms. Five articles are related to route choice modeling. We propose different dynamic discrete choice models that allow paths to be correlated based on the MEV and mixed logit models. The resulting route choice models become expensive to estimate and we deal with this challenge by proposing innovative methods that allow to reduce the estimation cost. For example, we propose a decomposition method that not only opens up for possibility of mixing, but also speeds up the estimation for simple logit models, which has implications also for traffic simulation. Moreover, we compare the utility maximization and regret minimization decision rules, and we propose a misspecification test for logit-based route choice models. The second theme is related to the estimation of static discrete choice models with large choice sets. We establish that a class of MEV models can be reformulated as dynamic discrete choice models on the networks of correlation structures. These dynamic models can then be estimated quickly using dynamic programming techniques and an efficient nonlinear optimization algorithm. Finally, the third theme focuses on structured quasi-Newton techniques for estimating discrete choice models by maximum likelihood. We examine and adapt switching methods that can be easily integrated into usual optimization algorithms (line search and trust region) to accelerate the estimation process. The proposed dynamic discrete choice models and estimation methods can be used in various discrete choice applications. In the area of big data analytics, models that can deal with large choice sets and sequential choices are important. Our research can therefore be of interest in various demand analysis applications (predictive analytics) or can be integrated with optimization models (prescriptive analytics). Furthermore, our studies indicate the potential of dynamic programming techniques in this context, even for static models, which opens up a variety of future research directions.

Étude de la médiane de permutations sous la distance de Kendall-Tau

La distance de Kendall-τ compte le nombre de paires en désaccord entre deux permuta- tions. La distance d’une permutation à un ensemble est simplement la somme des dis- tances entre cette permutation et les permutations de l’ensemble. À partir d’un ensemble donné de permutations, notre but est de trouver la permutation, appelée médiane, qui minimise cette distance à l’ensemble. Le problème de la médiane de permutations sous la distance de Kendall-τ, trouve son application en bio-informatique, en science politique, en télécommunication et en optimisation. Ce problème d’apparence simple est prouvé difficile à résoudre. Dans ce mémoire, nous présentons plusieurs approches pour résoudre le problème, pour trouver une bonne solution approximative, pour le séparer en classes caractéristiques, pour mieux com- prendre sa compléxité, pour réduire l’espace de recheche et pour accélérer les calculs. Nous présentons aussi, vers la fin du mémoire, une généralisation de ce problème et nous l’étudions avec ces mêmes approches. La majorité du travail de ce mémoire se situe dans les trois articles qui le composent et est complémenté par deux chapitres servant à les lier.

Étude de la médiane de permutations sous la distance de Kendall-Tau

La distance de Kendall-τ compte le nombre de paires en désaccord entre deux permuta- tions. La distance d’une permutation à un ensemble est simplement la somme des dis- tances entre cette permutation et les permutations de l’ensemble. À partir d’un ensemble donné de permutations, notre but est de trouver la permutation, appelée médiane, qui minimise cette distance à l’ensemble. Le problème de la médiane de permutations sous la distance de Kendall-τ, trouve son application en bio-informatique, en science politique, en télécommunication et en optimisation. Ce problème d’apparence simple est prouvé difficile à résoudre. Dans ce mémoire, nous présentons plusieurs approches pour résoudre le problème, pour trouver une bonne solution approximative, pour le séparer en classes caractéristiques, pour mieux com- prendre sa compléxité, pour réduire l’espace de recheche et pour accélérer les calculs. Nous présentons aussi, vers la fin du mémoire, une généralisation de ce problème et nous l’étudions avec ces mêmes approches. La majorité du travail de ce mémoire se situe dans les trois articles qui le composent et est complémenté par deux chapitres servant à les lier.

Ordonnancement des opérations dans une unité d’extrusion

Les travaux de ce mémoire traitent du problème d’ordonnancement et d’optimisation de la production dans un environnement de plusieurs machines en présence de contraintes sur les ressources matérielles dans une usine d’extrusion plastique. La minimisation de la somme pondérée des retards est le critère économique autour duquel s’articule cette étude car il représente un critère très important pour le respect des délais. Dans ce mémoire, nous proposons une approche exacte via une formulation mathématique capable des donner des solutions optimales et une approche heuristique qui repose sur deux méthodes de construction de solution sérielle et parallèle et un ensemble de méthodes de recherche dans le voisinage (recuit-simulé, recherche avec tabous, GRASP et algorithme génétique) avec cinq variantes de voisinages. Pour être en totale conformité avec la réalité de l’industrie du plastique, nous avons pris en considération certaines caractéristiques très fréquentes telles que les temps de changement d’outils sur les machines lorsqu’un ordre de fabrication succède à un autre sur une machine donnée. La disponibilité des extrudeuses et des matrices d’extrusion représente le goulot d’étranglement dans ce problème d’ordonnancement. Des séries d’expérimentations basées sur des problèmes tests ont été effectuées pour évaluer la qualité de la solution obtenue avec les différents algorithmes proposés. L’analyse des résultats a démontré que les méthodes de construction de solution ne sont pas suffisantes pour assurer de bons résultats et que les méthodes de recherche dans le voisinage donnent des solutions de très bonne qualité. Le choix du voisinage est important pour raffiner la qualité de la solution obtenue. Mots-clés : ordonnancement, optimisation, extrusion, formulation mathématique, heuristique, recuit-simulé, recherche avec tabous, GRASP, algorithme génétique

Transport coopératif d'un objet par deux robots humanoïdes dans un environnement encombré

Il y a présentement de la demande dans plusieurs milieux cherchant à utiliser des robots afin d'accomplir des tâches complexes, par exemple l'industrie de la construction désire des travailleurs pouvant travailler 24/7 ou encore effectuer des operation de sauvetage dans des zones compromises et dangereuses pour l'humain. Dans ces situations, il devient très important de pouvoir transporter des charges dans des environnements encombrés. Bien que ces dernières années il y a eu quelques études destinées à la navigation de robots dans ce type d'environnements, seulement quelques-unes d'entre elles ont abordé le problème de robots pouvant naviguer en déplaçant un objet volumineux ou lourd. Ceci est particulièrement utile pour transporter des charges ayant de poids et de formes variables, sans avoir à modifier physiquement le robot. Un robot humanoïde est une des plateformes disponibles afin d'effectuer efficacement ce type de transport. Celui-ci a, entre autres, l'avantage d'avoir des bras et ils peuvent donc les utiliser afin de manipuler précisément les objets à transporter. Dans ce mémoire de maîtrise, deux différentes techniques sont présentées. Dans la première partie, nous présentons un système inspiré par l'utilisation répandue de chariots de fortune par les humains. Celle-ci répond au problème d'un robot humanoïde naviguant dans un environnement encombré tout en déplaçant une charge lourde qui se trouve sur un chariot de fortune. Nous présentons un système de navigation complet, de la construction incrémentale d'une carte de l'environnement et du calcul des trajectoires sans collision à la commande pour exécuter ces trajectoires. Les principaux points présentés sont : 1) le contrôle de tout le corps permettant au robot humanoïde d'utiliser ses mains et ses bras pour contrôler les mouvements du système à chariot (par exemple, lors de virages serrés) ; 2) une approche sans capteur pour automatiquement sélectionner le jeu approprié de primitives en fonction du poids de la charge ; 3) un algorithme de planification de mouvement qui génère une trajectoire sans collisions en utilisant le jeu de primitive approprié et la carte construite de l'environnement ; 4) une technique de filtrage efficace permettant d'ignorer le chariot et le poids situés dans le champ de vue du robot tout en améliorant les performances générales des algorithmes de SLAM (Simultaneous Localization and Mapping) défini ; et 5) un processus continu et cohérent d'odométrie formés en fusionnant les informations visuelles et celles de l'odométrie du robot. Finalement, nous présentons des expériences menées sur un robot Nao, équipé d'un capteur RGB-D monté sur sa tête, poussant un chariot avec différentes masses. Nos expériences montrent que la charge utile peut être significativement augmentée sans changer physiquement le robot, et donc qu'il est possible d'augmenter la capacité du robot humanoïde dans des situations réelles. Dans la seconde partie, nous abordons le problème de faire naviguer deux robots humanoïdes dans un environnement encombré tout en transportant un très grand objet qui ne peut tout simplement pas être déplacé par un seul robot. Dans cette partie, plusieurs algorithmes et concepts présentés dans la partie précédente sont réutilisés et modifiés afin de convenir à un système comportant deux robot humanoides. Entre autres, nous avons un algorithme de planification de mouvement multi-robots utilisant un espace d'états à faible dimension afin de trouver une trajectoire sans obstacle en utilisant la carte construite de l'environnement, ainsi qu'un contrôle en temps réel efficace de tout le corps pour contrôler les mouvements du système robot-objet-robot en boucle fermée. Aussi, plusieurs systèmes ont été ajoutés, tels que la synchronisation utilisant le décalage relatif des robots, la projection des robots sur la base de leur position des mains ainsi que l'erreur de rétroaction visuelle calculée à partir de la caméra frontale du robot. Encore une fois, nous présentons des expériences faites sur des robots Nao équipés de capteurs RGB-D montés sur leurs têtes, se déplaçant avec un objet tout en contournant d'obstacles. Nos expériences montrent qu'un objet de taille non négligeable peut être transporté sans changer physiquement le robot.