Communication complexity studies how many bits a certain number of parties need to communicate with each other in order to compute a function whose input is distributed among those parties. Although it is a natural area of investigation based on practical considerations, the main motivation comes from the myriad of applications in theoretical computer science.This thesis has three main parts, studying three different aspects of communication complexity.1. The first part is concerned with the k-party communication complexity of functions F:({0,1}^n)^k -> {0,1} in the 'number on the forehead' (NOF) model. This is a fundamental model with many applications. In this model we study composed functions f of g. These functions include most of the well-known and studied functions in communication complexity literature. A major goal is to understand which combinations of f and g lead to hard communication functions. In particular, due to important circuit applications, it is of great interest to understand how powerful the NOF model becomes when k is log n or more. Motivated by these goals, we show that there is an efficient O(log^3 n) cost simultaneous protocol for sym of g when k > 1+log n, sym is any symmetric function and g is any function. This class of functions includes some functions that were previously conjectured to be hard and our result rules this class out for possible very important circuit complexity applications. We also give Ramsey theoretic applications of our efficient protocol. In the setting of k < log n, we study more closely functions of the form majority of g, mod_m of g, and nor of g, where the latter two are generalizations of the well-known functions Inner Product and Disjointness respectively. We characterize the communication complexity of these functions with respect to the choice of g. As the main application, we answer a question posed by Babai et al. (SIAM Journal on Computing, 33:137--166, 2004) and determine the communication complexity of majority of qcsb, where qcsb is the "quadratic character of the sum of the bits" function. 2. The second part is about Fourier analysis of symmetric boolean functions and its applications in communication complexity and other areas. The spectral norm of a boolean function f:{0,1}^n -> {0,1} is the sum of the absolute values of its Fourier coefficients. This quantity provides useful upper and lower bounds on the complexity of a function in areas such as communication complexity, learning theory and circuit complexity. We give a combinatorial characterization for the spectral norm of symmetric functions. We show that the logarithm of the spectral norm is of the same order of magnitude as r(f)log(n/r(f)) where r(f) = max(r_0,r_1), and r_0 and r_1 are the smallest integers less than n/2 such that f(x) or f(x)parity(x) is constant for all x with x_1 + ... + x_n in [r_0, n-r_1]. We present some applications to the decision tree and communication complexity of symmetric functions. 3. The third part studies privacy in the context of communication complexity: how much information do the players reveal about their input when following a communication protocol? The unattainability of perfect privacy for many functions motivates the study of approximate privacy. Feigenbaum et al. (Proceedings of the 11th Conference on Electronic Commerce, 167--178, 2010) defined notions of worst-case as well as average-case approximate privacy, and presented several interesting upper bounds, and some open problems for further study. In this thesis, we obtain asymptotically tight bounds on the trade-offs between both the worst-case and average-case approximate privacy of protocols and their communication cost for Vickrey Auction, which is the canonical example of a truthful auction. We also prove exponential lower bounds on the approximate privacy of protocols computing the Intersection function, independent of its communication cost. This proves a conjecture of Feigenbaum et al. / La complexité de communication étudie combien de bits un groupe de joueurs donné doivent échanger entre eux pour calculer une function dont l'input est distribué parmi les joueurs. Bien que ce soit un domaine de recherche naturel basé sur des considérations pratiques, la motivation principale vient des nombreuses applications théoriques.Cette thèse comporte trois parties principales, étudiant trois aspects de la complexité de communication.1. La première partie discute le modèle 'number on the forehead' (NOF) dans la complexité de communication à plusieurs joueurs. Il s'agit d'un modèle fondamental en complexité de communication, avec des applications à la complexité des circuits, la complexité des preuves, les programmes de branchement et la théorie de Ramsey. Dans ce modèle, nous étudions les fonctions composeés f de g. Ces fonctions comprennent la plupart des fonctions bien connues qui sont étudiées dans la littérature de la complexité de communication. Un objectif majeur est de comprendre quelles combinaisons de f et g produisent des compositions qui sont difficiles du point de vue de la communication. En particulier, à cause de l'importance des applications aux circuits, il est intéressant de comprendre la puissance du modèle NOF quand le nombre de joueurs atteint ou dépasse log n. Motivé par ces objectifs nous montrons l'existence d'un protocole simultané efficace à k joueurs de coût O(log^3 n) pour sym de g lorsque k > 1 + log n, sym est une function symmétrique quelconque et g est une fonction arbitraire. Nous donnons aussi des applications de notre protocole efficace à la théorie de Ramsey.Dans le contexte où k < log n, nous étudions de plus près des fonctions de la forme majority de g, mod_m de g et nor de g, où les deux derniers cas sont des généralisations des fonctions bien connues et très étudiées Inner Product et Disjointness respectivement. Nous caractérisons la complexité de communication de ces fonctions par rapport au choix de g.2. La deuxième partie considère les applications de l'analyse de Fourier des fonctions symmétriques à la complexité de communication et autres domaines. La norme spectrale d'une function booléenne f:{0,1}^n -> {0,1} est la somme des valeurs absolues de ses coefficients de Fourier. Nous donnons une caractérisation combinatoire pour la norme spectrale des fonctions symmétriques. Nous montrons que le logarithme de la norme spectrale est du même ordre de grandeur que r(f)log(n/r(f)), avec r(f) = max(r_0,r_1) où r_0 et r_1 sont les entiers minimaux plus petits que n/2 pour lesquels f(x) ou f(x)parity(x) est constant pour tout x tel que x_1 + ... + x_n à [r_0,n-r_1]. Nous présentons quelques applications aux arbres de décision et à la complexité de communication des fonctions symmétriques.3. La troisième partie étudie la confidentialité dans le contexte de la complexité de communication: quelle quantité d'information est-ce que les joueurs révèlent sur leur input en suivant un protocole donné? L'inatteignabilité de la confidentialité parfaite pour plusieurs fonctions motivent l'étude de la confidentialité approximative. Feigenbaum et al. (Proceedings of the 11th Conference on Electronic Commerce, 167--178, 2010) ont défini des notions de confidentialité approximative dans le pire cas et dans le cas moyen, et ont présenté plusieurs bornes supérieures intéressantes ainsi que quelques questions ouvertes. Dans cette thèse, nous obtenons des bornes asymptotiques précises, pour le pire cas aussi bien que pour le cas moyen, sur l'échange entre la confidentialité approximative de protocoles et le coût de communication pour les enchères Vickrey Auction, qui constituent l'exemple canonique d'une enchère honnête. Nous démontrons aussi des bornes inférieures exponentielles sur la confidentialité approximative de protocoles calculant la function Intersection, indépendamment du coût de communication. Ceci résout une conjecture de Feigenbaum et al.

Protein-protein interactions represent a crucial source of information for the understanding of the biological mechanisms of the cell. In order to be useful, high quality protein-protein interactions must be computationally extracted from the noisy datasets produced by high-throughput experiments such as affinity purification. Even when filtered protein-protein interaction datasets are obtained, the task of analyzing the network formed by these numerous interactions remains tremendous. Protein-protein interaction networks are large, intricate, and require computational approaches to provide meaningful biological insights. The overall objective of this thesis is to explore algorithms assessing the quality of protein-protein interactions and facilitating the analysis of their networks. This work is divided into four results: 1) a novel Bayesian approach to model contaminants originating from affinity purifications, 2) a new method to identify and evaluate the quality of protein-protein interactions independently in different cell compartments, 3) an algorithm computing the statistical significance of clusterings of proteins sharing the same functional annotation in protein-protein interaction networks, and 4) a computational tool performing sequence motif discovery in 5' untranslated regions as well as evaluating the clustering of such motifs in protein-protein interaction networks. / Les interactions protéine-protéine représentent une source d'information essentielle à la compréhension des divers méchanismes biologiques de la cellule. Cependant, les expériences à haut débit qui identifient ces interactions, comme la purification par affinité, produisent un très grand nombre de faux-positifs. Des méthodes computationelles sont donc requises afin d'extraire de ces ensembles de données les interactions protéine-protéine de grande qualité. Toutefois, même lorsque filtrés, ces ensembles de données forment des réseaux très complexes à analyser. Ces réseaux d'interactions protéine-protéine sont d'une taille importante, d'une grande complexité et requièrent des approches computationelles sophistiquées afin d'en retirer des informations possédant une réelle portée biologique. L'objectif de cette thèse est d'explorer des algorithmes évaluant la qualité d'interactions protéine-protéine et de faciliter l'analyse des réseaux qu'elles composent. Ce travail de recherche est divisé en quatre principaux résultats: 1) une nouvelle approche bayésienne permettant la modélisation des contaminants provenant de la purification par affinité, 2) une nouvelle méthode servant à la découverte et l'évaluation de la qualité d'interactions protéine-protéine à l'intérieur de différents compartiments de la cellule, 3) un algorithme détectant les regroupements statistiquement significatifs de protéines partageant une même annotation fonctionnelle dans un réseau d'interactions protéine-protéine et 4) un outil computationel qui a pour but la découverte de motifs de séquences dans les régions 5' non traduites tout en évaluant le regroupement de ces motifs dans les réseaux d'interactions protéine-protéine.

The human visual system has a remarkable ability to perceive complex 3D shape from a variety of surface types. These surfaces can include ones shaded using the standard Phong model or mirror surfaces which can be rendered using a variety of surrounding environments. This thesis presents four visual perception experiments that examine the perception of local qualitative shape under various conditions. Surfaces were rendered using standard computer graphics models of matte, glossy, and mirror reflectance. For each experiment, the subjects' task was to judge whether a marked point on each surface lay on a local hill or valley. A variety of novel findings were made in these experiments which touch on various aspects of perceptual capabilities of the visual system. In Experiment 1 it was found, contrary to previously known results, that under some circumstances it is more difficult to perceive shape from a glossy rather than a matte surface. In Experiment 3 this finding is re-examined and it's found that glossy surfaces are more easily perceived than matte ones when the highlight falls on local extrema such as hills and valleys, but can be more difficult to perceive when the highlight falls on frontally-oriented portions of the local geometry. A perceptual model is proposed to explain this effect. Experiment 3 expands on this finding by investigating the perception of surfaces when lit from a variety of different angles as well as comparing these lighting types to the ones used in commercial visualization software such as MATLAB and Mathematica. The results of Experiment 1 also indicate that when rendering mirror surfaces an inhomogeneity in the environment map may be exploitable by the visual system as an additional cue to aid in the perception of qualitative local surface shape. Experiment 4 expands on this finding by finding that the orientation of this environmental inhomogeneity has an additional effect on performance. The Appendix generalizes the well-known depth reversal ambiguity to mirrors and highlights. Experiment 2 utilizes this finding to producing the first tests examining how the visual system resolves this ambiguity when viewing mirrors. The findings indicate that the visual system tends to resolve this ambiguity by utilizing a prior for upward-facing surface orientation in the case of surfaces rendered as mirrors, similarly to the known upward-facing surface prior for Phong surfaces. The upward-facing surface prior is found to be weaker for mirror than for Phong surfaces, however, as subjects tended to rely more heavily on perspective cues in the former rendering condition rather than the latter. / Le système visuel humain a une capacité remarquable à percevoir les formes complexes en 3D à partir d'une variété de types de surfaces. Ces surfaces peuvent inclure celles ombragées en utilisant le modèle standard Phong ou bien des surfaces miroir qui peuvent être rendues à l'aide d'une variété de milieux environnants. Cette thèse présente quatre expériences de perception visuelle qui examinent la perception de la forme qualitative locale dans diverses conditions. Les surfaces furent rendues en utilisant des modèles standards informatiques graphiques de mat, de brillant et de réflexion de miroir. Pour chaque expérience, les participants de l'étude devaient juger si un point marqué sur chaque surface se trouvait sur une colline ou sur une vallée. Une variété de nouvelles découvertes ont été faites grâce à ces expériences qui touchent à différents aspects des capacités perceptives du système visuel. Dans l'expérience 1 il a été constaté, contrairement aux résultats déjà connus, que dans certaines circonstances il est plus difficile de percevoir la forme d'une surface brillante que celle d'une surface matte. Dans l'expérience 3 cette constatation est réexaminée et il se trouve que les surfaces brillantes sont plus facilement perçues que celles qui sont mattes lorsque le reflet spéculaire tombe sur les extrema locaux tels que les collines et les vallées, mais peuvent être plus difficiles à percevoir quand le reflet spéculaire est situé sur les portions de la géométrie locale qui sont orientées frontalement. Un modèle perceptif est proposé pour expliquer cet effet. L'expérience 3 élabore sur cette conclusion en étudiant la perception des surfaces lorsqu'elles sont allumées à partir d'une variété d'angles différents ainsi qu'en comparant ces types d'éclairage à ceux utilisés dans les logiciels de visualisation commerciaux tels que MATLAB et Mathematica. Les résultats de l'expérience 1 indiquent également que, lors du rendu des surfaces, miroir un manque d'homogénéité dans le plan de l'environnement peut être exploitable par le système visuel comme un repère supplémentaire pour aider à la perception de la forme de la surface locale qualitative. L'expérience 4 développe cette constatation en remarquant que l'orientation de cette hétérogénéité de l'environnement a un effet supplémentaire sur la performance. L'annexe généralise l'ambiguïté bien connue sur l'inversion de la profondeur à des miroirs et des reflets spéculaire. L'expérience 2 utilise ce résultat pour produire les premières expérimentations sur la manière selon laquelle le système visuel résout cette ambiguïté lorsqu'il perçoit des miroirs. Les résultats indiquent que le système visuel essaye souvent de résoudre cette ambiguïté en utilisant une hypothèse que la surface est orientée vers le haut dans le cas de surfaces miroir, ressemblant à l'hypothèse connue des surfaces orientées vers le haut pour les surfaces Phong. Pourtant, l'hypothèse de la surface orientée vers le haut est jugée plus faible pour les surfaces miroir que pour les surfaces Phong, puisque les participants avaient tendance à s'appuyer d'avantage sur des indices de perspective dans le cas des surfaces miroir que des surfaces Phong.

The bottleneck concept in reinforcement learning has played a prominent role in automatically finding temporal abstractions from experience. Lacking significant theory, it has however been regarded by some as being merely a trick. This thesis attempts to gain better intuition about this approach using spectral graph theory. A connection to the theory of Nearly Completely Decomposable Markov Chains (NCD) is also drawn and shows great promise. An options discovery algorithm is proposed and is the first of its kind to be applicable in continuous state spaces. As opposed to other similar approaches, this one can have running time O(n^2 log n) rather than O(n^3) making it suitable to much larger domains than the typical grid worlds. / L'identification automatique de goulots d'étranglement dans la structure de solution a joué un rôle important en apprentissage par renforcement hiérarchique au cours des dernières années. Bien que populaire, cette approche manque toujours de fondements théoriques adaptés. Ce mémoire tente de pallier ces lacunes en établissant des liens en théorie spectrale des graphes, espérant ainsi obtenir une meilleure compréhension des conditions garantissant son applicabilité. Une revue des efforts réalisés concernant les chaines de Markov presque complètement décomposable (NCD) permet de croire qu'elles pourraient être utiles au problème ici considéré. Un algorithme de découverte d'options motivé par la théorie spectrale des graphes est proposé et semble être le premier du genre à pouvoir être aussi appliqué dans un espace d'états continu. Contraire- ment à d'autres approches similaires, la complexité algorithmique en temps peut être de l'ordre de O(n^2 log n) plutôt que O(n^3), rendant possible la résolution de problèmes de plus grande envergure.

Prometheus aims to explore artificial intelligence in a controlled but flexible environment by mimicking the properties of the real world using a swarm intelligence implementation. Swarm Intelligence has been used for solving problems in the domain of self organization, complexity and collective intelligence for a group of agents. The collective behavior of the entity considered here - ants, are modeled as a decentralized and self-organized system in which the ants communicate indirectly and thrive by modifying the environment. This novel approach combines the widely established stigmergy theory with real-time fluid dynamics by using Pheromones and the Navier-Stokes equations respectively to subject the environment to natural conditions like wind, and spread and decay of smell thus making the environment more suitable to real time conditions. The chosen real-time fluid dynamics method proves to be computationally fast, robust and far more realistic than traditional approaches. Also, for evaporation, instead of choosing a random fixed value for every timestep, we take into consideration the effect of temperature, vapor pressure, wind and humidity on evaporation and consequences of that. It is hoped that this model will be a step closer to achieving results substantially closer to the real world and also, observing the changes that the aforementioned natural properties might impose on the experimental world. / Le projet d'intelligence artificielle Prometheus vise à explorer, dans un environnement contrôlé mais flexible, les propriétés du monde réel sur une intelligence en essaim. L'intelligence distribuée a été utilisée afin de résoudre les problèmes dans le domaine de l'auto-organisation, la complexité et l'intelligence collective d'un groupe d'agents. Le comportement collectif de l'entité considérée, ici la fourmi, est modélisé comme un système décentralisé et auto-organisé dans lequel les fourmis communiquent indirectement et prospèrent en modifiant l'environnement. Celle nouvelle approche combine la théorie de stigmergie avec la mécanique des fluides, utilisant respectivement les phéromones et les équations de Navier-Stokes, afin de soumettre à l'environnement des conditions naturelles comme le vent ou encore la propagation et la désintégration de l'odeur. Ainsi l'environnement correspond mieux à des conditions réelles. La méthode de mécanique des fluides en temps réel choisie, s'avère être rapidement calculable, robuste et beaucoup plus réaliste que les approches traditionnelles. De plus, pour modéliser l'évaporation, au lieu de choisir une valeur aléatoire fixée pour chaque itération, nous prenons en compte l'effet de la température, de la pression de la vapeur, du vent, de l'humidité de l'évaporation et leurs conséquences. Nous pensons que ce modèle contribuera à l'obtention de résultats nettement plus proches du monde réel et à l'observation des changements que les propriétés naturelles susmentionnées pourraient imposer à l'environnement expérimental.

In this thesis, we investigate the question of how a legged robot can walk efficiently, and take advantage of its ability to alter its gait. This work targets the issue of increasing the efficiency of legged vehicles on different challenging terrains. We decompose the problem into three sub-problems: walking gait problem, physical adaptation problem, and terrain identification and gait adaptation problem. In the walking gait sub-problem, we investigate the effects of gait parameters on the performance of the robot. In particular, we assess the ground speed, power efficiency and terrain sensibility of the robot at varying leg cycle frequencies. In the physical adaptation sub-problem, we investigate the effects of different kinds of legs on the robot's performance. We also look at the influence of leg-compliance on walking behavior. In the terrain identification and gait adaptation sub-problem, we design a gait adaptation algorithm to identify the terrain by initially classifying the proprioceptive information collected over different terrains and then adapt its gait accordingly. Identifying the terrain in real-time helps the robot plan its gait on that terrain and effectively increase the walking efficiency in real-time. We use a cost-based unsupervised learning algorithm to classify the terrain data. In our experiments, we use proprioceptive sensor data collected by running the robot on four different terrains. We also use synthetic data for verifying our algorithm. We conclude with an analysis of the data and validate the performance of our algorithm. / Dans cette thèse, nous étudions les problèmes liés à l'efficacité de marche des robots à pattes et construisons des solutions algorithmiques et physiques pour les régler. Ce travail vise à accroître l'efficacité, en termes de mobilité, des véhicules à pattes sur différents terrains difficiles. Cette problématique est décomposée en trois sous-problèmes: la façon de marcher, l'adaptation physique, et l'identification de terrains associée à l'adaptation de la démarche des robots. Dans le premier cas (la façon de marcher), nous étudions les effets des paramètres de la démarche sur la performance du robot. Nous évaluons plus particulièrement la vitesse au sol, le rendement énergétique et la sensibilité du robot vis-à-vis du terrain et ce, en fonction de la vitesse de déplacement des jambes. Dans le cas du deuxième sous-problème, soit l'adaptation physique, nous étudions les effets de différents types de jambes sur la performance du robot. Nous examinons également l'influence de la flexibilité des jambes sur la marche du robot. Troisièmement, le sous-problème d'identification de terrains et d'adaptation de la démarche des robots est l'un des problèmes les plus importants pour les véhicules capables de marcher. Identifier le terrain en temps réel permet au robot de planifier sa démarche sur ce terrain et d'augmenter efficacement son rendement de marche. Nous concevons un algorithme permettant d'identifier le terrain en classant d'abord les informations proprioceptives recueillies sur différents terrains pour ensuite adapter la démarche en conséquence. Dans nos expériences, nous utilisons un algorithme d'apprentissage non supervisé pour classer les données de terrain, de même que les données issues de capteurs proprioceptifs collectées en employant le robot sur quatre types de terrains différents. Nous utilisons également des données synthétiques afin de vérifier notre algorithme d'identification. Dans les résultats, nous présentons une analyse des données et validons les performances de notre algorithme.

Since the introduction of non-negative matrix factorization (NMF) as a tool for single-channel musical source separation (SC-MSS) in the early part of the 21st century, it has steadily increased both in practicality and popularity, and continues to be a major area of focus within the signal processing community. It is acknowledged in the literature, however, that the fundamental assumption of the mixture model for the spectral representation of the acoustic sources, to which NMF is applied, violates the true nature of the superposition of acoustic signals by disregarding the phase relationship between overlapping sources. It is also recognized that NMF-based source separation procedures require additional post-processing, in order to reincorporate the phase information back into the spectral representation of the sources, once the factorization is complete. This thesis explores Complex Matrix Factorization (CMF), a recently proposed variant of NMF, which incorporates the phase information of the acoustic sources into the matrix factorization framework, allowing for the development of source separation procedures founded on a mixture model rooted in the complex-spectrum domain (in which the superposition of overlapping sources is preserved). CMF has the additional benefit of integrating the estimation of the phase of the constituent sources directly into the factorization algorithm, eliminating the need for post-factorization phase estimation. Three experiments were conducted, investigating the behaviour of CMF, as it compares to NMF, when applied to simple test mixtures constructed from overlapping acoustic instruments. The main contribution of this thesis is the development of a physically motivated phase-based constraint, which restricts the relation between the phase parameter estimates over time. The CMF-based separation procedure, armed with this novel phase constraint, is demonstrated to offer promising results when employed as a tool for SC-MSS on the simple acoustic test case considered. / Depuis l'introduction de la factorisation en matrices non-négatives (NMF) en tant qu'outil pour la séparation de sources musicales monophoniques (SC-MSS) au début du 21e siècle, son utilité et sa popularité ont augmenté de façon régulière et elle continue d'être un grand domaine d'intérêt au sein de la communauté de traitement du signal. Cependant, il est reconnu dans la littérature sur le sujet que l'hypothèse fondamentale du modèle de mélange pour la représentation spectrale de la source acoustique, à laquelle la NMF est appliquée, enfreint la véritable nature de la superposition des signaux acoustiques en ignorant la combinaison de phase entre sources superposées. Il est aussi reconnu que les procédures de type NMF pour la séparation de sources nécessitent des procédures de post-traitement additionnelles pour réintégrer l'information de phase à la représentation spectrale des sources une fois la factorisation complétée. Cette thèse explore la factorisation de matrices complexes (CMF), une variante de la NMF récemment proposée qui intègre l'information de phase des sources acoustiques dans le cadre de la factorisation de matrices. Ceci permet le développement de procédures de séparation de sources fondées sur un modèle de mixage ancré dans le domaine des spectres complexes (dans lequel le mélange de sources qui se superposent est préservée). La CMF apporte aussi l'avantage d'intégrer l'estimation de la phase des sources constituantes directement à l'algorithme de factorisation, ce qui élimine le besoin d'estimation de phase a posteriori. Trois expériences ont été réalisées afin d'étudier le comportement de la CMF comparé à la NMF lorsqu'appliqué à des mélanges simples fait à partir d'instruments acoustiques qui se superposent. La principale contribution de cette thèse est la formalisation d'une contrainte de phase, fondée sur des propriétés physiques, qui impose des liens entre ses estimations au court du temps. Nous montrons que l'algorithme de la CMF, armée de cette nouvelle contrainte de phase, donne des résultats prometteurs lorsqu'il est utilisé sur des signaux acoustiques simples dans le cadre de la SC-MSS.

Most digital musical instruments (DMIs) gather gestural input from musicians by way of electronic sensors and transform these data into sound through separate synthesis engines. The mapping of control inputs to synthesis parameters is arbitrary, multi-faceted and extremely important for the effectiveness of DMIs. Software tools exist to aid in this process and attempt to render the task of musical mapping more transparent, swift and configurable. This thesis presents MapperGUI, a cross-platform graphical tool for the manipulation of musical mapping networks. The libmapper software library, developed at the Input Devices and Music Interaction Laboratory, creates a standard framework for DMIs to communicate data on a distributed network and map their signals collaboratively in real-time. MapperGUI presents a graphical user interface for libmapper networks, allowing non-expert users to manipulate the text-based system. The interface aims to be flexible, such that it can accommodate the vast array of musical networks and tasks that must be performed when mapping. To this end, it provides multiple independent visualizations and interaction modes within a single framework. This document explores some of the issues challenging the field of musical mapping and describes the motivations behind the MapperGUI project in this context. Relevant research in the fields of data visualization and interface design is summarized and applied to the task of creating a graphical user interface for libmapper networks. Prior graphical interfaces for libmapper are examined for successful features that can be incorporated into MapperGUI. Specific implementation challenges and features of the final program are described. Insight gained from interviews with users of MapperGUI is presented, along with future work and possible extensions for the interface.MapperGUI is available for free download as a standalone application at www.libmapper.org/downloads. All code is open-source and can be accessed at https://github.com/mysteryDate/webmapper. / La plupart des instruments de musique numériques (IMN) assemble les données gestuelles des musiciens par des capteurs électroniques et transforme ces données en son à travers de programmes de synthèse séparés. Le mappage d'entrées de commandes aux paramètres de synthèse est arbitraire, à multiples facettes et extrêmement important pour l'efficacité des IMN. Les outils logiciels existent pour aider ce processus et tentent de rendre la tâche du mappage musical plus transparente, rapide et configurable. Cette thése présente MapperGUI, un outil graphique multiplateforme pour la manipulation des réseaux de mappage musicaux.La bibliothèque logiciel libmapper, développée au Input Devices and Music Interaction Laboratory, crée un cadre standard pour que les IMN communiquent les données sur un réseau réparti et map leurs signaux en collaboration en temps réel. MapperGUI présente une interface utilisateur pour les réseaux libmapper, ce qui permet aux utilisateurs non-experts de manipuler ce système textuel. L'interface a pour but d'être flexible, en sorte qu'elle puisse accommoder la vaste gamme de réseaux et de tâches musicales qui doivent être complétées en mappant. À cette fin, elle offre plusieurs visualisations et modes d'interactions indépendantes à l'intérieur d'un seul cadre. Ce document porte sur quelques un des enjeux qui affrontent le domaine du mappage musical et décrit les motivations qui sous-tendent le projet MapperGUI dans ce contexte. De la recherche pertinente dans les domaines de la visualisation des données et la conception d'interface sont résumées et appliquées à la tâche de créer une interface d'utilisateur graphique pour les réseaux de libmapper. Des interfaces graphiques précédentes pour libmapper sont examinées pour leurs caractéristiques réussies qui peuvent être incorporées à MapperGUI. Des difficultés de mise en oeuvre précises et des caractéristiques du programme final sont décrites. Les connaissances tirées d'entrevues avec des utilisateurs de MapperGUI sont présentées, ainsi que des travaux futurs et des extensions possibles pour l'interface.MapperGUI est disponible pour téléchargement gratuit en tant qu'application autonome à www.libmapper.org/downloads. Tout le code est code source libre et peut être accédé à https://github.com/mysteryDate/webmapper.

A key skill for mobile robots is the ability to navigate efficiently through their environment. In the case of social or assistive robots, this involves navigating through human crowds. Typical performance criteria, such as reaching the goal using the shortest path, are not appropriate in such environments, where it is more important for the robot to move in a socially adaptive manner such as respecting comfort zones of the pedestrians. This thesis investigates the Learning from Demonstration framework to address the socially adaptive path planning problem. Learning from Demonstration is a practical framework for learning complex policies using demonstration trajectories produced by an expert. We propose two approaches based on Learning from Demonstrations. First approach is based on Inverse Reinforcement Learning, in which we compactly represent the socially adaptive path planning behaviours as a cost function that we learn. The second approach is based on imitation learning, in which we use supervised learning to learn such behaviours, and then provide theoretical guarantees on its performance. We evaluate our approach by deploying it on a real robotic wheelchair platform in various scenarios, and comparing the robot trajectories to human trajectories. / Une compétence essentielle au bon fonctionnement des robots mobiles est la capacité à naviguer efficacement dans leur environnement. Ainsi, pour les robots sociaux ou d'assistance, il est essentiel de pouvoir naviguer parmi des foules humaines. Les critres de performance typiques, tels qu'atteindre un endroit ciblé par le chemin le plus court, ne sont pas appropriés dans de tels environnements, où il est plutôt important de se déplacer d'une manire socialement adaptée en respectant, par exemple, les zones de confort des piétons. Cette thèse examine un système d'apprentissage par démonstration ayant pour but de résoudre le problème de planification de trajectoire adaptée à un environment humain. L'apprentissage par démonstration est un cadre pratique permettant l'acquisition de controlleurs complexes en utilisant des trajectoires de démonstration provenant d'un expert. Nous proposons deux approches basées sur l'apprentissage par démonstration. La première approche est basée sur l'apprentissage par renforcement inverse, dans lequel nous représentons de façon compacte les comportements de planification de trajectoire socialement adaptative en fonction des cots appris. La deuxième approche est fondée sur l'apprentissage par imitation, où nous utilisons l'apprentissage supervisé pour aquérir ces comportements, et fournissons subséquemment des garanties théoriques sur sa performance. Nous évaluons notre approche en la déployant sur un véritable fauteuil roulant robotisé dans différents scénarios et la comparons à des trajectoires humaines.

While great efforts have been made in the electrical utility industry to engineer various stranded conductors with enhanced strength and vibrational characteristics, research devoted to understanding the complex mechanical behavior of complete conductors has been scarce, especially from a computational mechanics perspective. In the meanwhile, the long-lasting problem of conductor fretting fatigue becomes increasingly critical for overhead line design and maintenance, especially with the world-wide aging of electrical transmission grids. Aging of conductors contributes to significant degradation of their local fatigue strength, leading to drastic reduction of their service life. However, the complex mechanical response of stranded conductors cannot be well predicted by either experimental testing or simplified theoretical models, owing to the physical complexity introduced by their multi-layer stranded geometry, nonlinear material properties, substantial frictions among the wires and between the wires and hardware clamping systems, as well as the comprehensive contact interactions amongst their components. Simplified beam models and coarse 3-D models of earlier computational studies also fail to calculate the accurate stress variations inside a conductor strand and capture the stress gradients near the contact interfaces. Moreover, the estimations of fretting fatigue life are very dependent on the high accuracy of the stress predictions in the conductor wires. Therefore, reliable high-fidelity computational models have been long expected for a better understanding of the contact damage of transmission line conductors under both design and fretting fatigue conditions. The main objective of this thesis is to study the complex stress states and relevant influencing factors of stranded electrical conductors, using finite element analysis approaches. The research was carried out in three stages. First of all, a study focused on the finite element (FE) modeling of an optical ground wire (OPGW) cable strand for its detailed stress analysis. A refined 3-D FE model including all essential nonlinear characteristics was successfully constructed. As a result, a high-fidelity physics-based macroscopic modeling methodology was developed for detailed and accurate computational stress analysis of stranded conductors. A 795 kcmil Drake ACSR conductor was then selected as a benchmark conductor to investigate the tensile strength and critical stress states of a complete conductor under extreme design conditions. Furthermore, a sensitivity study explored the relative importance of friction effects among conductor wires on the mechanical response.A large scale 3-D FE stress analysis model with comprehensive nonlinearities was developed and implemented to simulate an actual ACSR fretting fatigue test. The computational results showed good agreement with some experimental measurements and field observations reported in the open literature. Based on the accurate stress analysis, a practical multi-axial fatigue lifing methodology was developed to estimate local fretting fatigue strength of electrical conductors. Subsequently, a parametric study was performed to examine the influence of fretting amplitudes on the mechanical response of the conductor-clamp system.In conclusion, this research shows the reliability and significance of using reliable FE modeling in predicting the complex response of stranded conductors, which has contributed to fill some of the current knowledge gaps. Furthermore, the computational modeling and lifing approaches developed in this thesis provide a different perspective from existing practices and may become a starting block of further exploration of the mechanisms of conductor fretting fatigue and future development of improved fatigue lifing methods for the increasingly aging overhead transmission line conductors. / Malgré les efforts déployés par l'industrie des lignes de transport d'électricité pour la conception de conducteurs toronnés de haute résistance mécanique, la recherche dédiée à la compréhension physique du comportement mécanique des conducteurs s'est faite plus rare, surtout du point de vue de la mécanique computationnelle. Le problème du vieillissement des conducteurs de lignes aériennes à haute tension, en particulier celui de l'usure en fatigue des brins et torons, n'est toujours pas complètement compris ni donc résolu. Le vieillissement des conducteurs se manifeste par une dégradation importante de leur résistance locale à l'usure en fatigue, réduisant par le fait même leur vie utile et la robustesse mécanique de l'ensemble de la ligne. Il faut reconnaître que les études expérimentales et les modèles théoriques simplifiés ne peuvent pas prédire le comportement mécanique détaillé des conducteurs toronnés à cause de la complexité physique de ces câbles: torons et brins multicouches, matériaux inélastiques non-linéaires, effets des frictions substantielles entre les brins, torons et les surfaces des accessoires d'attache, ainsi que les interactions de contact entre ces éléments.Les travaux rapportés dans la thèse procèdent en trois étapes principales, décrites ci-après. La première partie consiste à préparer un modèle de section de câble de garde à fibre optique (CGFO) de construction complexe et d'en faire l'analyse détaillée sous déplacement axial contrôlé. Cette étape a servi à établir les bases de la méthodologie proposée, lesquelles sont discutées de manière exhaustive. La deuxième partie de la recherche porte sur la modélisation raffinée du conducteur de ligne ACSR 795 kcmil qui porte le nom de code « Drake », sélectionné comme cas de référence pour étudier la résistance en traction et les états de contraintes complexes du conducteur sous des conditions de conception extrêmes de conception. sensibilité a également exploré l'importance relative des effets frictionnels entre les brins du câble sur les contraintes calculées par le modèle. Finalement, un modèle détaillé 3-D est créé pour simuler les conditions précises d'un essai typique de fatigue en flexion pour le conducteur « Drake » jumelé à une pince de suspension. Le modèle retient toutes les non-linéarités du problème d'un point de vue mécanique. l'auteur suggère une méthode pratique pour évaluer la résistance locale en fatigue multiaxiale des conducteurs du type ACSR au droit des points de contact des pinces de suspension. Cette méthode est relativement simple d'application (une fois les analyses de contraintes disponibles) et donne des résultats en accord avec les valeurs recommandées par les manufacturiers pour le câble « Drake ». Par la suite, une étude paramétrique est faite pour vérifier l'influence de l'amplitude des mouvements de glissement sur les états de contraintes déterminés dans le conducteur dans la région de contact avec la pince sous l'effet d'un cycle complet de chargement flexionnel. En conclusion, cette recherche démontre la faisabilité et la pertinence de l'usage des méthodes computationnelles avancées pour l'analyse des contraintes d'un problème complexe comme celui des conducteurs toronnés multicouches. La méthodologie de construction des modèles est une contribution scientifique importante qui permet d'améliorer notre compréhension du comportement mécanique des conducteurs sous charges extrêmes ou dans des conditions de fatigue flexionnelle. La méthode proposée pour l'estimation de la résistance à l'usure en fatigue est également utile pour l'industrie des lignes de transport et pour les manufacturiers de câbles et il est envisageable que cette recherche servira de tremplins à plusieurs autres études computationnelles pertinentes sur les conducteurs de lignes afin d'améliorer leur fiabilité et leur robustesse mécanique.