Les travaux présentés dans cette thèse portent sur la planification de tâches pour des systèmes robotiques qui prennent en compte des contraintes géométriques, cinématiques et symboliques. Nous souhaitons notamment traiter des problèmes nécessitant la manipulation et l'assemblage d'objets par plusieurs robots mobiles manipulateurs dans un environnement contraint. Dans le cadre de cette thèse nous avons développé un planificateur nommé "aSyMov" qui offre un cadre innovant pour combiner les techniques issues de la planification de mouvements et de la planification de tâches. Dans un premier temps nous faisons un état de l'art des techniques de la planification de mouvements. Puis une nouvelle représentation de l'espace de recherche et de nouvelles techniques de planifications seront développées afin de généraliser et de combiner les algorithmes décrits dans l'état de l'art. Dans un second temps nous abordons les techniques de la planification de tâches et définissons une manière originale de lier le domaine géométrique au domaine symbolique. Puis nous présentons l'architecture et les algorithmes de notre planificateur. ASyMov effectue une recherche en avant dans l'espace d'état. L'état d'aSyMov a la particularité de représenter l'ensemble des instanciations géométriques possibles pour un état symbolique donné. La procédure de validation des actions va essayer de minimiser les instances géométriques à vérifier. Ce ne sera que quand les actions vont contraindre la géométrie qu'une propagation arrière de ces contraintes sera faite pour trouver de nouvelles instances valides. Nous décrivons aussi comment il est possible de combiner à la fois l'apprentissage de la topologie de l'environnement et la recherche d'une solution avec les connaissances déjà acquises. Pour finir nous présentons plusieurs problèmes complexes qui ont été résolus par aSyMov.

La répartition des calculs et des données est le problème majeur à résoudre pour réaliser une application parallèle, son efficacité dépendant de la date et du lieu d'exécution des calculs sur l'ensemble des ressources, processeurs et mémoire, de la machine. Nous nous attachons à résoudre ce "problème d'ordonnancement". Nous utilisons pour cela un modèle proposé récemment : les tâches malléables. Après une introduction au domaine du parallélisme, nous présentons les principaux défauts d'autres modèles d'exécution, notamment leur modélisation fine du comportement des échanges de données, ce qui rend leur manipulation complexe. Les problèmes d'ordonnancement qui en résultent nous semblent difficiles à résoudre efficacement. Le modèle des tâches malléables considère une application comme un ensemble de tâches parallèles, chacune étant exécutée simultanément par plusieurs processeurs. La modélisation d'une application reste classique, en graphe de tâches, mais les communications ne sont prises en compte que de manière implicite, dans le temps d'exécution de chaque tâche malléable. Nous pensons que cette approche simplifie le problème d'ordonnancement à la fois théorique et pratique. Dans ce mémoire, nous abordons d'abord l'ordonnancement de tâches malléables indépendantes. Nous présentons quelques travaux déjà connus dont nous analysons les déficiences. Nous proposons un algorithme en deux étagères avec une meilleure garantie de performance de 3/2. Une comparaison en moyenne des différents algorithmes est également présentée. Pour les problèmes incluant des contraintes de précédences, nous présentons d'abord les résultats existants dans des modèles proches avant de proposer une première étude du problème des chaînes de tâches malléables. Enfin, après une introduction au domaine de la simulation adaptative de courants océaniques, l'utilisation pratique du modèle pour l'ordonnancement d'une simulation est également présentée.

Nos travaux portent sur la supervision d'un robot autonome en environnement humain et plus particulièrement sur la prise en compte de l'interaction homme-robot au niveau décisionnel. Dans ce cadre, l'homme et le robot constituent un système dans lequel ils partagent un espace commun et échangent des informations à travers différentes modalités. L'interaction peut intervenir soit sur une requête explicite de l'homme, soit parce que le robot l'a estimée utile et en a pris l'initiative. Dans les deux cas le robot doit agir afin de satisfaire un but en prenant en compte de manière explicite la présence et les préferences de son partenaire humain. Pour cela, nous avons conçu et développé un système de supervision nommé Shary qui permet de gérer des tâches individuelles (où seul le robot est impliqué) et des tâches jointes (où le robot et un autre agent sont impliqués). Ce système se compose d'une mécanique d'exécution de tâches gérant d'une part la communication nécessaire au sein d'une tâche et d'autre part l'affinement de la tâche en sous-tâches. Pour cela chaque tâche est définie par un plan de communication et un plan de réalisation auxquels sont associés des moniteurs de suivi. Nous avons développé ce système sur le robot Rackham dans le cadre d'une tâche de "Guide de musée". Nous avons également utilisé ce système dans le cadre d'une tâche du type : "apporter quelque chose à quelqu'un" sur le robot Jido pour montrer la généricité du système.

Cette étude relève du domaine de la didactique des langues et de l'usage des TIC. Elle s'appuie sur une recherche-action portant sur un projet collectif de création d'une ressource numérique par des stagiaires professeurs des écoles de l'IUFM de Paris et des étudiants du King's College de Londres. Nous avons émis l'hypothèse que cette tâche est susceptible d'opérer comme levier d'apprentissage de l'anglais pour les stagiaires, et nous avons posé les questions de recherche suivantes.<br />- Comment le scénario de formation proposé interroge-t-il le schéma d'acquisition d'une L2 ?<br />- Un tel scénario contribue-t-il au développement de la production orale des stagiaires, compétence dont ils ont le plus besoin dans l'exercice de leur profession ?<br />Afin de cerner l'impact de la formation sur les processus d'acquisition linguistique et plus particulièrement sur le développement de l'output oral des apprenants, nous analysons les différentes tâches inhérentes au projet à la lumière des théories d'acquisition et de l'approche socioculturelle, ainsi que le contexte interactionnel instauré par les participants. Nous prenons également en compte le fait que les échanges avec les partenaires anglophones se font à distance, au moyen du courriel, et examinons les effets qu'un input authentique exclusivement écrit engendre sur la production orale des stagiaires, le risque encouru étant d'accentuer le phénomène de nativisation.<br />Mesurer la portée et les limites du dispositif en regard de l'objectif fixé permet de déboucher sur de nouvelles propositions de formation, conformément au cycle de la recherche-action.

Mémoire numérisé par la Division de la gestion de documents et des archives de l'Université de Montréal

La découverte de contingences sensorimotrices et leur structuration en compétences sont des enjeux importants en robotique. En particulier, on souhaite pouvoir apprendre ainsi des compétences qui soient à la fois riches sémantiquement et aussi générales que possible.Cette thèse s’est intéressée à la question du regroupement de compétences robotiques en compétences plus générales. Après avoir posé formellement les notions que l’on peut trouver dans la littérature de compétence et de compétence paramétrée, nous avons relié les compétences paramétrées aux modèles inverses et nous nous sommes inspirés du dualisme entre modèles directs et inverses pour proposer un formalisme dual, les compétences paramétrées directes.Nous avons ensuite entrepris de déterminer quand il était ou non pertinent de réunir des compétences au sein d’une même compétence paramétrée directe.Le problème est alors ramené à un problème de régression, et des algorithmes s’inspirant du principe du rasoir d’Ockham sont proposés pour y chercher une solution sous la forme d’un mélange d’experts de complexité minimale. Ces algorithmes sont ensuite appliqués à des données de manipulation d’objets en simulation / The discovery of sensorimotor contingencies and their structurationinto skills are both important topics in the field of robotics. In particular,robots need the ability to learn skills which are both semantically rich and as general as possible. During this thesis, we studied the question of merging robotic skills into more general skills. After formally defining the notions that can be found in the litterature of skills and parameterized skills, we established a link between paramaterized skills and inverse models, then mirrored the dualism between forward and inverse models to propose a dual type of parameterized skills:forward-parameterized skills. We went on to determine when merging skills into a forward-parameterized skill is relevant and when it’s not. The problem is then formulated as a regression problem, and algorithms inspired by the Occam Razor principle are proposed to find a mixture of experts that solves it with minimal complexity. Those algorithms are then applied to simulated object-manipulation data.

Cette thèse vise à définir et à valider un modèle de programmation intégrant la description d'architectures logicielles et un ordonnancement dynamique de tâches dans un contexte de haute performance. Par exemple, il s'agit de combiner les avantages de modèles tels que L²C et StarPU. L'objectif final est de proposer un modèle capable de supporter des applications telles que Gysela5D sur les architectures parallèles actuelles et futures (tel que des clusters très variés et supercalculateurs comportant des accélérateurs). / This thesis aims to define and validate a programing model that combines the description of software architecture with dynamic task scheduling in a high performance context. For example by integrating the advantages of the L²C and StarPU models. The final goal is to propose a model that enables the description of applications such as Gysela5D on current and future parallel architectures (such as various clusters and supercomputers including accelerators).

Le problème Rm||Cmax consiste à allouer un ensemble de tâches à m agents de sorte à minimiser le makespan de l’allocation, c’est-à-dire le temps d’exécution de l’ensemble des tâches. Ce problème est connu pour être NP-dur dès que les tâches sont allouées à deux agents ou plus (m ≥ 2). De plus, il est souvent admis que le coût d’une tâche est précisément estimé pour un agent et que ce coût ne varie pas au cours de l’exécution des tâches. Dans cette thèse, je propose une approche décentralisée et dynamique pour l’amélioration d’une allocation de tâches. Ainsi, à partir d’une allocation initiale et pendant qu’ils exécutent les tâches, les agents collaboratifs initient de multiples enchères pour réallouer les tâches qui restent à exécuter. Ces réallocations sont socialement rationnelles, c’est-à-dire qu’un agent accepte de prendre en charge une tâche initialement allouée à un autre agent si la délégation de cette tâche bénéficie à l’ensemble du système en faisant décroître le makespan. De plus, le dynamisme du procédé permet d’améliorer une allocation malgré une fonction de coût peu précise et malgré les variations de performances qui peuvent survenir lors de l’exécution des tâches. Cette thèse offre un cadre formel pour la modélisation et la résolution multi-agents d’un problème de réallocation de tâches situées. Dans un tel problème, la localité des ressources nécessaires à l’exécution d’une tâche influe sur son coût pour chaque agent du système. À partir de ce cadre, je présente le protocole d’interaction des agents et je propose plusieurs stratégies pour que les choix des agents aient le plus d’impact sur le makespan de l’allocation courante. Dans le cadre applicatif de cette thèse, je propose d’utiliser ce processus de réallocation de tâches pour améliorer le patron de conception MapReduce. Très utilisé pour le traitement distribué de données massives, MapReduce possède néanmoins des biais que la réallocation dynamique des tâches peut aider à contrer. J’ai donc implémenté un prototype distribué qui s’inscrit dans le cadre formel et implémente le patron de conception MapReduce. Grâce à ce prototype, je suis en mesure d’évaluer l’apport du processus de réallocation et l’impact des différentes stratégies d’agent. / The Rm||Cmax problem consists in allocating a set of tasks to m agents in order to minimize the makespan of the allocation, i.e. the execution time of all the tasks. This problem is known to be NP-hard as soon as the tasks are allocated to two or more agents (m ≥ 2). In addition, it is often assumed that the cost of a task is accurately estimated for an agent and that this cost does not change during the execution of tasks. In this thesis, I propose a decentralized and dynamic approach to improve the allocation of tasks. Thus, from an initial allocation and while they are executing tasks, collaborative agents initiate multiple auctions to reallocate the remaining tasks to be performed. These reallocations are socially rational, i.e. an agent agrees to take on a task initially allocated to another agent if the delegation of this task benefits to the entire system by decreasing the makespan. In addition, the dynamism of the process makes it possible to improve an allocation despite an inaccurate cost function and despite the variations of performance that can occur during the execution of tasks. This thesis provides a formal framework for multi-agent modeling and multi-agent resolution of a located tasks reallocation problem. In such a problem, the locality of the resources required to perform a task affects its cost for each agent of the system. From this framework, I present the interaction protocol used by the agents and I propose several strategies to ensure that the choices of agents have the greatest impact on the makespan of the current allocation. In the applicative context of this thesis, I propose to use this tasks reallocation process to improve the MapReduce design pattern. Widely used for the distributed processing of massive data, MapReduce has biases that the dynamic tasks reallocation process can help to counter. I implemented a distributed prototype that fits into the formal framework and implements the MapReduce design pattern. Thanks to this prototype, I am able to evaluate the effectiveness of the reallocation process and the impact of the different agent strategies.

Des méthodes efficaces s'appuyant sur des outils statistiques pour réaliser dela reconnaissance de mouvement ont été développé. Ces méthodes reposent surl'apprentissage de primitives situé dans des espaces approprié, par exemplel'espace latent de l'espace articulaire et/ou d'espace de tâches adéquat. Lesprimitives apprises sont souvent séquentielle: un mouvement est segmenté selonl'axe des temps. Dans le cas d'un robot humanoïde, le mouvement peut êtredécomposé en plusieurs sous-tâches simultanées. Par exemple dans un scénario deserveur, le robot doit placer une assiette sur la table avec une main tout enmaintenant son plateau horizontal avec son autre main. La reconnaissance nepeut donc pas se limiter à une seule et unique tâche par segment de tempsconsécutif. La méthode présenté dans ces travaux utilise la connaissance destâches que le robot est capable d'accomplir, ainsi que des contrôleurs quigénèreront les mouvements pour réaliser une rétro ingénierie sur un mouvementobservé. Cette analyse est destinée à reconnaître des tâches qui ont été exécutéde manière simultanées. La méthode repose sur la fonction de tâche et lesprojections dans l'espace nul des tâches afin de découpler les contrôleurs.L'approche a été appliqué avec succès sur un vrai robot pour distinguer desmouvements visuellement très proches, mais sémantiquement différents / Efficient methods to perform motion recognition have been developed usingstatistical tools. Those methods rely on primitives learning in a suitablespace, for example the latent space of the joint angle and/or adequate taskspaces. The learned primitives are often sequential : a motion is segmentedaccording to the time axis. When working with a humanoid robot, a motion can bedecomposed into simultaneous sub-tasks. For example in a waiter scenario, therobot has to keep some plates horizontal with one of his arms, while placing aplate on the table with its free hand. Recognition can thus not be limited toone task per consecutive segment of time. The method presented in this worktakes advantage of the knowledge of what tasks the robot is able to do and howthe motion is generated from this set of known controllers to perform a reverseengineering of an observed motion. This analysis is intended to recognizesimultaneous tasks that have been used to generate a motion. The method relieson the task-function formalism and the projection operation into the null spaceof a task to decouple the controllers. The approach is successfully applied ona real robot to disambiguate motion in different scenarios where two motionslook similar but have different purposes

Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.