Дисертації з теми "Allocation de tâches à des senseurs"

L’évolution du contexte de défense aéronaval nécessite une modification majeure de l’architecture des systèmes de senseurs actuels afin de maitriser les futures menaces et d’intégrer les nouveaux dispositifs et senseurs à venir. Ces senseurs, hétérogènes, complémentaires et embarqués sur des plateformes navales ou aériennes, sont essentiels pour l’acquisition de données de l’environnement et l’établissement de la situation tactique. Dans ce contexte, les plateformes peuvent collaborer et partager leurs ressources senseurs pour accomplir de nouvelles fonctionnalités et établir un panorama global de la situation. Dans cette thèse, nous avons conçu et développé un système multi-agent pour l’allocation de tâches à des ressources distribuées sur des plateformes distinctes dans le but d’accomplir des capacités collaboratives. Nous présentons des scénarios illustrant les besoins opérationnels auxquels l’architecture doit répondre, établissant ainsi un cahier des charges. Ensuite, nous détaillons les étapes de la conception et de l’implémentation de cette nouvelle architecture, en décrivant chaque type d’agent et les interactions possibles entre eux. Nous proposons un algorithme d’enchère nécessitant des échanges entre les agents, soumis aux contraintes de bande passante et de latence. Enfin, nous présentons un banc d’essai intégrant des outils de capture et de visualisation de métriques du système, permettant l’évaluation des concepts d’agents et de leurs mécanismes de communication. L’objectif est de démontrer que notre architecture répond aux besoins opérationnels spécifiés, notamment le passage à l’échelle des algorithmes et des interfaces de communications des agents, la résistance aux pannes et la performance du système
The changing context of naval and aerial defense requires a major modification of current sensor system architectures to overcome future threats and to integrate next generation devices and sensors. These sensors, heterogeneous, complementary, and embedded on naval or aerial platforms, are essential for acquiring data from the environment in order to establish the tactical situation. In this context, platforms can collaborate and share their sensor resources to achieve new functionalities and set up a global overview of the situation. In this thesis, we have designed and developed a multi-agent system for allocating tasks to distributed resources on distinct platforms in order to accomplish collaborative capabilities. We present scenarios illustrating the operational needs that the architecture must meet, thus establishing a set of specifications. Then, we detail the steps involved in designing and implementing this new architecture, describing each type of agent and the possible interactions between them. We propose an auction algorithm requiring exchanges between agents, subject to bandwidth and latency constraints. Finally, we present a test bed integrating tools for capturing and display system metrics, allowing the evaluation of agent concepts and their communication mechanisms. The objective is to demonstrate that our architecture meets the specified operational requirements, in particular the scalability of the agents’ algorithms and communication interfaces, fault tolerance, and system performance

Des nombreuses applications participatives, commerciales et académiques se appuient sur des volontaires ("la foule") pour acquérir, désambiguiser et nettoyer des données. Ces applications participatives sont largement connues sous le nom de plates-formes de crowdsourcing où des amateurs peuvent participer à de véritables projets scientifiques ou commerciaux. Ainsi, des demandeurs sous-traitent des tâches en les proposant sur des plates-formes telles que Amazon MTurk ou Crowdflower. Puis, des participants en ligne sélectionnent et exécutent ces tâches, appelés microtasks, acceptant un micropaiement en retour. Ces plates-formes sont confrontées à des défis tels qu'assurer la qualité des réponses acquises, aider les participants à trouver des tâches pertinentes et intéressantes, tirer parti des compétences expertes parmi la foule, respecter les délais des tâches et promouvoir les participants qui accomplissent le plus de tâches. Cependant, la plupart des plates-formes ne modélisent pas explicitement les compétences des participants, ou se basent simplement sur une description en terme de mots-clés. Dans ce travail, nous proposons de formaliser les compétences des participants au moyen d'une structure hiérarchique, une taxonomie, qui permet naturellement de raisonner sur les compétences (détecter des compétences équivalentes, substituer des participants, ...). Nous montrons comment optimiser la sélection de tâches au moyen de cette taxonomie. Par de nombreuses expériences synthétiques et réelles, nous montrons qu'il existe une amélioration significative de la qualité lorsque l'on considère une structure hiérarchique de compétences au lieu de mots-clés purs. Dans une seconde partie, nous étudions le problème du choix des tâches par les participants. En effet, choisir parmi une interminable liste de tâches possibles peut s'avérer difficile et prend beaucoup de temps, et s’avère avoir une incidence sur la qualité des réponses. Nous proposons une méthode de réduction du nombre de propositions. L'état de l'art n'utilise ni une taxonomie ni des méthodes de classement. Nous proposons un nouveau modèle de classement qui tient compte de la diversité des compétences du participant et l'urgence de la tâche. À notre connaissance, nous sommes les premiers à combiner les échéances des tâches en une métrique d'urgence avec la proposition de tâches pour le crowdsourcing. Des expériences synthétiques et réelles montre que nous pouvons respecter les délais, obtenir des réponses de haute qualité, garder l'intérêt des participants tout en leur donnant un choix de tâches ciblé
A large number of commercial and academic participative applications rely on a crowd to acquire, disambiguate and clean data. These participative applications are widely known as crowdsourcing platforms where amateur enthusiasts are involved in real scientific or commercial projects. Requesters are outsourcing tasks by posting them on online commercial crowdsourcing platforms such as Amazon MTurk or Crowdflower. There, online participants select and perform these tasks, called microtasks, accepting a micropayment in return. These platforms face challenges such as reassuring the quality of the acquired answers, assisting participants to find relevant and interesting tasks, leveraging expert skills among the crowd, meeting tasks' deadlines and satisfying participants that will happily perform more tasks. However, related work mainly focuses on modeling skills as keywords to improve quality, in this work we formalize skills with the use a hierarchical structure, a taxonomy, that can inherently provide with a natural way to substitute tasks with similar skills. It also takes advantage of the whole crowd workforce. With extensive synthetic and real datasets, we show that there is a significant improvement in quality when someone considers a hierarchical structure of skills instead of pure keywords. On the other hand, we extend our work to study the impact of a participant’s choice given a list of tasks. While our previous solution focused on improving an overall one-to-one matching for tasks and participants we examine how participants can choose from a ranked list of tasks. Selecting from an enormous list of tasks can be challenging and time consuming and has been proved to affect the quality of answers to crowdsourcing platforms. Existing related work concerning crowdsourcing does not use either a taxonomy or ranking methods, that exist in other similar domains, to assist participants. We propose a new model that takes advantage of the diversity of the parcipant's skills and proposes him a smart list of tasks, taking into account their deadlines as well. To the best of our knowledge, we are the first to combine the deadlines of tasks into an urgency metric with the task proposition for knowledge-intensive crowdsourcing. Our extensive synthetic and real experimentation show that we can meet deadlines, get high quality answers, keep the interest of participants while giving them a choice of well selected tasks

Dans la plupart des cas, les systèmes modernes de production ont été étudiés de façon a être les plus autonomes possibles. Pour faire face aux erreurs éventuelles des automatismes, la présence de l'opérateur humain reste alors indispensable. Néanmoins, la complexite des tâches peut nécessiter l'apport d'une assistance qui peut consister en une répartition dynamique de tâches entre ces opérateurs et le système d'aide. La contribution de notre travail porte, d'une part sur les aspects théoriques de la répartition dynamique de tâches, et d'autre part sur l'application de cette forme de coopération au contrôle de trafic aérien. Cette application a été réalisée en collaboration avec le centre d'étude de la navigation aérienne. Dans une première partie, la problématique des systèmes intégrant une coopération homme-machine est abordée, et une méthodologie de conception et d'évaluation des systèmes homme-machine est présentée. Dans une deuxième partie, les objectifs et les problèmes de la répartition dynamique sont analysés. Pour résoudre ces problèmes, notamment dus à la complexité des procédés réels, la troisième partie propose une démarche pour la mise en œuvre d'une répartition dynamique de tâches. Cette démarche s'appuie tout d'abord sur une structure qui s'inspire des techniques de la commande adaptative. Ensuite, nous proposerons un ensemble de critères permettant la définition du degré d'automatisation d'un système homme-machine. La quatrième partie présente l'application des principes retenus au domaine du contrôle de trafic aérien, et la cinquième les résultats obtenus.

Les centres de données sont responsables d'une part importante de la consommation mondiale d'énergie. Cette consommation devrait augmenter dans les années à venir, en raison de la demande croissante de services pour les centres de données. Par conséquent, le besoin d'opérations de centres de données efficaces sur le plan énergétique et à faible émission de carbone augmente rapidement.Cette recherche se concentre sur la conception et la mise en œuvre d'un centre de données à faible émission de carbone et à haut rendement énergétique, alimenté par l'énergie solaire et l'hydrogène, ce qui lui confère une indépendance par rapport au réseau électrique. En conséquence, le centre de données est limité par la limite supérieure de la consommation d'énergie, qui est de 10KWh. La contrainte d'utilisation maximale de l'énergie impose plusieurs défis à la conception, à l'utilisation de l'énergie et à la durabilité du centre de données.Ce travail contribue tout d'abord à la conception d'un centre de données à faible consommation d'énergie tout en respectant la contrainte énergétique globale. Nous avons essayé d'économiser l'énergie du centre de données par un choix judicieux du matériel tout en conservant les performances du centre de données. La deuxième contribution de notre travail fournit des protocoles précieux tels que la réparation paresseuse dans le stockage distribué des données, le placement des tâches et les techniques de gestion de l'énergie pour réduire davantage la consommation d'énergie du centre de données. Grâce aux efforts combinés du bon choix de matériel, de protocoles et de techniques, nous avons réduit de manière significative la consommation d'énergie globale du centre de données
Data centers are responsible for a significant portion of global energy consumption. This consumption is expected to grow in the coming years, driven by the increasing demand for data center services. Therefore, the need for energy-efficient, low-carbon data center operations is growing rapidly.This research focuses on designing and implementing a low-carbon, energy-efficient data center powered by solar and hydrogen, granting it independence from the power grid. As a result, the data center is limited by the upper bound on the energy consumption, which is 10KWh. The maximum usage of energy-constraint imposes several challenges to the design, energy usage, and sustainability of the data center.The work first contributes to designing a low-power budget data center while respecting the overall energy constraint. We tried to save the energy usage of the data center through the right choice of hardware while keeping the performance of the data center intact. The second contribution of our work provides valuable protocols like lazy repair in distributed data storage, job placement, and power management techniques to further reduce the data center's energy usage. With the combined efforts of the right choice of hardware, protocols, and techniques, we significantly reduced the overall energy consumption of the data center

Définition de la répartition dynamique des tâches entre l'opérateur humain et le calculateur selon un critère tenant compte des performances de l'équipe homme-machine et la charge de travail de l'opérateur. Présentation d'une méthode de répartition implicite basée sur la théorie de la commande optimale de 2 stratégies d'affectation de tâches explicites.

L'allocation des tâches à plusieurs agents autonomes devant accomplir des tâches complexes a été l'un des domaines de recherche récents sur les systèmes multi-agents. Dans de nombreuses applications, les agents sont coopératifs et doivent effectuer des tâches qui nécessitent chacune une combinaison de différentes capacités dont peut se doter un sous-ensemble d'agents. Dans ce cas, nous pouvons utiliser la formation de coalitions comme paradigme pour affecter des coalitions d'agents à des tâches. Les solutions à ce problème d'allocation de tâches, pour les systèmes robotiques en particulier, trouvent plusieurs applications dans le monde réel et prennent de plus en plus de l'importance dans les domaines de la défense, de l'espace, de la gestion des catastrophes, de l'exploration sous-marine, de la logistique, de la fabrication de produits et de l'assistance dans les services de santé. De multiples mécanismes de formation de coalitions et d'allocation de tâches ont été introduits dans l'état de l'art, tenant rarement compte des tâches interdépendantes. Cependant, il est récurrent de trouver des tâches dont la qualité ne peut être évaluée sans considérer les autres tâches dans des applications réelles. Ces tâches sont appelées interdépendantes par opposition aux tâches indépendantes qui, elles, peuvent être évaluées individuellement, ce qui entraîne une évaluation globale de l'allocation des tâches qui additionne simplement toutes les évaluations des tâches. La recherche dans le passé a conduit à de nombreuses méthodes d'allocation de tâches qui traitent le cas des tâches indépendantes sous différents angles et sous différents paradigmes. D'autres travaux résolvent le cas des tâches interdépendantes, mais ils le font soit de manière centralisée avec une complexité très élevée, soit uniquement pour le cas des dépendances de précédence. Cependant, de nombreuses formes d'interdépendance peuvent exister entre les tâches dans les applications du monde réel. Ces applications nécessitent que les mécanismes d'allocation des tâches soient décentralisés et anytime, pouvant renvoyer une solution à tout moment quitte à l'améliorer s'il reste du temps, pour répondre à des problèmes de sensibilité au temps et de robustesse. Dans cette thèse, nous considérons des environnements multi-agents coopératifs où les tâches sont multi-agents et interdépendantes, et les méthodes d'allocation des tâches doivent être décentralisées et anytime. À cet égard, nous proposons une formalisation du problème qui considère les attributs qualitatifs et quantitatifs des agents et des tâches, et qui capture les dépendances des tâches que ça soit au niveau des exigences ou au niveau de l'évaluation des allocations. Nous introduisons une nouvelle approche avec un mécanisme de formation de coalition décentralisé anytime qui permet aux agents dotés de capacités complémentaires de former, de manière autonome et dynamique, des structures de coalitions faisables qui accomplissent une tâche globale et composite. Cette approche est basée sur la formation d'une structure de coalition faisable permettant aux agents de décider quelle coalition rejoindre et donc quelle tâche accomplir afin que toutes les tâches soient faisables. Ensuite, les structures formées sont progressivement améliorées via des remplacements d'agents pour optimiser l'évaluation globale de l'allocation, le but étant d'accomplir les tâches avec les meilleures performances possibles. Nous analysons la complexité de nos algorithmes et montrons que, bien que le problème général soit NP-complet, notre mécanisme fournit une solution dans un temps acceptable. Des scénarios d'application simulés sont utilisés pour démontrer la valeur ajoutée de notre approche
Task allocation among multiple autonomous agents that must accomplish complex tasks has been one of the focusing areas of recent research in multi-agent systems. In many applications, the agents are cooperative and have to perform tasks that each requires a combination of different capabilities that a subset of agents can have. In this case, we can use coalition formation as a paradigm to assign coalitions of agents to tasks. For robotic systems, in particular, solutions to this task allocation problem have several and increasingly important real-world applications in defense, space, disaster management, underwater exploration, logistics, product manufacturing, and support in healthcare facilities support. Multiple coalition formation and task allocation mechanisms were introduced in the prior art, seldom accounting for interdependent tasks. However, it is recurrent to find tasks whose quality cannot be evaluated without considering the other tasks in real-world applications. These tasks are called interdependent in contrast to independent tasks that can be individually assessed, resulting in a global evaluation of the tasks' allocation that sums all the tasks' evaluations. Research in the past has led to many task allocation algorithms that address the case of independent tasks from different angles and under different paradigms. Other works solve the case of the interdependent tasks, but they do it either centrally with very high complexity or only for the case of precedence dependencies. However, many forms of interdependence may exist between tasks in real-world applications. In addition, these applications need task allocation mechanisms to be decentralised and available at anytime to allow them to return a solution at any time and to improve it if there is time left, to respond to their time-sensitivity and robustness issues. In this dissertation, we consider cooperative multi-agent environments where tasks are multi-agent and interdependent, and task allocation methods have to be decentralized and available at anytime. In this regard, we propose a problem formalisation that considers the agents' and the tasks' qualitative and quantitative attributes and captures the tasks' dependencies on the requirements level and the allocation evaluation level. We introduce a novel approach with a token-passing anytime decentralised coalition formation mechanism. The approach enables agents with complementary capabilities to form, autonomously and dynamically, feasible coalition structures that accomplish a global, composite task. It is based on forming a feasible coalition structure that allows the agents to decide which coalition to join and thus which task to do so that all the tasks can be feasible. Then, the formed structures are incrementally improved via agent replacements to optimise the global evaluation. The purpose is to accomplish the tasks with the best possible performance. The analysis of our algorithms' complexity shows that although the general problem is NP-complete, our mechanism provides a solution within an acceptable time. Simulated application scenarios are used to demonstrate the added value of our approach

Cloud computing, the long-held dream of computing as a utility, has the potential to transform a large part of the IT industry, making software even more attractive as a service and shaping the way in which hardware is designed and purchased. In this thesis, we reviewed the new cloud computing technologies, and indicated the main challenges for their development in future, among which resource management problem stands out and attracts our attention. Combining the current scheduling theories, we proposed cloud scheduling hierarchy to deal with different requirements of cloud services. From the theoretical aspects, we have accomplished three main research issues. Firstly, we solved the resource allocation problem in the user-level of cloud scheduling. We proposed game theoretical algorithms for user bidding and auctioneer pricing. With Bayesian learning prediction, resource allocation can reach Nash equilibrium among non-cooperative users even though common knowledge is insufficient. Secondly, we addressed the task scheduling problem in the system-level of cloud scheduling. We proved a new utilization bound for on-line schedulability test, considering the sequential feature of MapReduce. We deduced the relationship between cluster utilization bound and the ratio of Map to Reduce. This new schedulable bound with segmentation uplifts classic bound which is most used in industry. Thirdly, we settled the comparison problem among on-line schedulability tests in cloud computing. We proposed a concept of test reliability to evaluate the probability that a random task set could pass a given schedulability test. The larger the probability is, the more reliable the test is. From the aspect of system, a test with high reliability can guarantee high system utilization. From the practical aspects, we have developed a simulator to model MapReduce framework. This simulator offers a simulated environment directly used by MapReduce theoretical researchers. The users of SimMapReduce only concentrate on specific research issues without getting concerned about finer implementation details for diverse service models, so that they can accelerate study progress of new cloud technologies.

Le domaine avionique a été transformé par l'apparition des architectures modulaires intégrées (IMA). Celles-ci définissent un support d'exécution et de communication standard et mutualisé afin de réduire la complexité de l'architecture physique. Cependant, du fait du partage des ressources, cette démarche introduit une plus grande complexité lors de la conception et de l'intégration des applications ce qui implique d'assister les concepteurs avec des outils dédiés. La présente thèse contribue à cet effort en se focalisant sur deux problèmes d'allocation de ressources : i) le problème de l'ordonnancement multiprocesseur de tâches strictement périodiques et ii) le problème du routage des messages échangés entre les fonctions avioniques. Le premier problème a été formalisé sous la forme d'un programme linéaire en nombres entiers afin de garantir un potentiel maximum d'évolution sur les durées d'exécutions des traitements. L'inefficacité d'une approche exacte pour des instances de grande taille, nous a conduit à développer une heuristique originale s'inspirant de la théorie des jeux couplée avec un algorithme multi-start. Le routage est formalisé sous la forme d'un problème d'optimisation sur la charge maximum des liens. Deux propositions sont faites pour le résoudre, l'une, exacte, est basée sur une formulation nœud-lien, et la seconde est une heuristique à deux niveaux basé sur une formulation lien-chemin. Mots-Clés en français : ordonnancement temps-réel, optimisation, systèmes avioniques, architectures modulaires intégrées, tâches strictement périodique, théorie de jeux, routage des liens virtuels

Le domaine avionique a été transformé par l'apparition des architectures modulaires intégrées (IMA). Celles-ci définissent un support d'exécution et de communication standard et mutualisé afin de réduire la complexité de l'architecture physique. Cependant, du fait du partage des ressources, cette démarche introduit une plus grande complexité lors de la conception et de l'intégration des applications ce qui implique d’assister les concepteurs avec des outils dédiés. La présente thèse contribue à cet effort en se focalisant sur deux problèmes d'allocation de ressources : i) le problème de l'ordonnancement multiprocesseur de tâches strictement périodiques et ii) le problème du routage des messages échangés entre les fonctions avioniques.Le premier problème a été formalisé sous la forme d’un programme linéaire en nombres entiers afin de garantir un potentiel maximum d'évolution sur les durées d'exécutions des traitements. L’inefficacité d’une approche exacte pour des instances de grande taille, nous a conduit à développer une heuristique originale s’inspirant de la théorie des jeux couplée avec un algorithme multi-start.Le routage est formalisé sous la forme d’un problème d’optimisation sur la charge maximum des liens. Deux propositions sont faites pour le résoudre, l’une, exacte, est basée sur une formulation nœud-lien, et la seconde est une heuristique à deux niveaux basé sur une formulation lien-chemin
The avionic domain has seen a profound evolution by the introduction of Integrated Modular Avionics (IMA). This defines a standardized execution and communication support in order to reduce the complexity of the physical architecture. Nevertheless, due to the sharing of resources, this reduction of complexity is opposed by an increased difficulty in application conception and integration, which necessitates dedicated tools for assisting system designers. This thesis’ contributions concern two major resource allocation problems: i) the multiprocessor scheduling of strictly periodic tasks and ii) the routing of messages exchanged between the avionic functions. The first problem was formulated using integer linear programming so as to guarantee a maximum evolution potential for the task execution durations. The inefficiency of this exact approach for large problem instances led us to develop an original heuristic, inspired from Game Theory, and further enhance it with a multi-start algorithm. The routing problem was formulated as an optimization one so as to minimize the maximum link loads. Two methods were proposed for this purpose, the first is exact based on node-link formulations, and the other is a two phase heuristic based on link-path formulations

MPSoCs (systèmes multiprocesseurs sur puces) avec des centaines de cœurs sont déjà disponibles sur le marché. Selon le ITRS, ces systèmes intégreront des milliers de cœurs à la fin de la décennie. La définition du cœur, où chaque tâche sera exécutée dans le système, est une question majeure dans la conception de MPSoCs. Dans la littérature, cette question est définie comme allocation de tâches. La croissance du nombre de cœurs augmente la complexité de l'allocation de tâches. Les principales préoccupations en matière d'allocation de tâches dans des grands MPSoCs incluent: (i) l'évolutivité; (ii) la charge de travail dynamique; et (iii) la fiabilité. Il est nécessaire de distribuer la décision d'allocation de tâches à travers le système afin d'assurer l'évolutivité. La charge de travail de grands MPSoCs peut être dynamique, à savoir, de nouvelles applications peuvent commencer à tout moment, conduisant à différents scénarios d'allocation. Par conséquent, il est nécessaire d'exécuter le processus d'allocation à l'exécution pour soutenir une charge de travail dynamique. La fiabilité est étroitement liée à la distribution de la charge de travail du système. Un déséquilibre de charge peut générer des hotspots et autres implications thermiques, ce qui peut entraîner un fonctionnement peu fiable du système. Dans de grands MPSoCs, les problèmes de fiabilité empirent puisque l'augmentation du nombre de cœurs sur la même puce augmente la densité de puissance et, par conséquent, la température du système. La littérature présente différentes techniques d'allocation de tâches pour améliorer la fiabilité du système. Cependant, ces techniques utilisent des approches d'allocation centralisées, qui ne sont pas évolutives. Pour répondre à ces trois défis, l'objectif principal de cette Thèse est de proposer et évaluer des heuristiques d'allocation de tâches distribuées et dynamiques en assurant l'évolutivité et une distribution équitable de la charge de travail. Une distribution équitable de la charge de travail et du trafic du NoC (réseau sur puce) augmente la fiabilité du système dans le long terme, en raison de la minimisation des régions de hotspot. Pour permettre l'exploration de l'espace de conception de grands MPSoCs, la première contribution de cette Thèse se situe dans le cadre d'une modélisation multi-niveaux, qui prend en compte différents modèles et de capacités de débogage qui enrichissent et facilitent la conception des MPSoCs. La simulation de modèles de niveau inférieur (par exemple RTL) génère des paramètres de performance utilisés pour calibrer des modèles abstraits (sans précision d'horloge). Les modèles abstraits permettent d'explorer des heuristiques d'allocation de tâches dans de grands systèmes. La plupart des techniques d'allocation de tâches se focalisent sur l'optimisation du volume de communication, ce qui peut compromettre la fiabilité du système, en raison d'une surcharge des processeurs. D'autre part, une heuristique qui optimise seulement la distribution de la charge de travail peut surcharger le NoC et compromettre sa fiabilité. La deuxième contribution importante de cette Thèse est la proposition d'heuristiques d'allocation de tâches dynamiques et distribuées, qui réalisent un compromis entre le volume de communication (liens du NoC) et la distribution de la charge de travail (de l'utilisation des processeurs). Des résultats liés au temps d'exécution, au volume de la communication, à la consommation d'énergie, aux traces de puissance et à la distribution de la température dans les grands MPSoCs (144 processeurs) confirment l'hypothèse de compromis. Faire un compromis entre la réduction du volume de communication et une distribution équitable de la charge de travail améliore le système de manière fiable grâce à la réduction des régions de hotspots, sans compromettre la performance du système
MPSoCs with hundreds of cores are already available in the market. According to the ITRS roadmap, such systems will integrate thousands of cores by the end of the decade. The definition of where each task will execute in the system is a major issue in the MPSoC design. In the literature, this issue is defined as task mapping. The growth in the number of cores increases the complexity of the task mapping. The main concerns in task mapping in large systems include: (i) scalability; (ii) dynamic workload; and (iii) reliability. It is necessary to distribute the mapping decision across the system to ensure scalability. The workload of emerging large MPSoCs may be dynamic, i.e., new applications may start at any moment, leading to different mapping scenarios. Therefore, it is necessary to execute the mapping process at runtime to support a dynamic workload. Reliability is tightly connected to the system workload distribution. Load imbalance may generate hotspots zones and consequently thermal implications, which may result in unreliable system operation. In large scale MPSoCs, reliability issues get worse since the growing number of cores on the same die increases power densities and, consequently, the system temperature. The literature presents different task mapping techniques to improve system reliability. However, such approaches use a centralized mapping approach, which are not scalable. To address these three challenges, the main goal of this Thesis is to propose and evaluate distributed mapping heuristics, executed at runtime, ensuring scalability and a fair workload distribution. Distributing the workload and the traffic inside the NoC increases the system reliability in long-term, due to the minimization of hotspot regions. To enable the design space exploration of large MPSoCs the first contribution of the Thesis lies in a multi-level modeling framework, which supports different models and debugging capabilities that enrich and facilitate the design of MPSoCs. The simulation of lower level models (e.g. RTL) generates performance parameters used to calibrate abstract models (e.g. untimed models). The abstract models pave the way to explore mapping heuristics in large systems. Most mapping techniques focus on optimizing communication volume in the NoC, which may compromise reliability due to overload processors. On the other hand, a heuristic optimizing only the workload distribution may overload NoC links, compromising its reliability. The second significant contribution of the Thesis is the proposition of dynamic and distributed mapping heuristics, making a tradeoff between communication volume (NoC links) and workload distribution (CPU usage). Results related to execution time, communication volume, energy consumption, power traces and temperature distribution in large MPSoCs (144 processors) confirm the tradeoff hypothesis. Trading off workload and communication volume improves system reliably through the reduction of hotspots regions, without compromising system performance

Cette thèse s'inscrit dans le cadre du projet Cart-O-Matic mis en place pour participer au défi CAROTTE (CArtographie par ROboT d'un TErritoire) organisé par l'ANR et la DGA. Le but de ce défi est de construire une carte en deux et trois dimensions et de localiser des objets dans un environnement inconnu statique de type appartement. Dans ce contexte, l'utilisation de plusieurs robots est avantageuse car elle permet d'augmenter l'efficacité en temps de la couverture. Cependant, comme nous le montrons, le gain est conditionné par le niveau de coopération entre les robots. Nous proposons une stratégie de coopération pour une cartographie multirobot efficace. Une difficulté est la construction d'une carte commune, nécessaire, afin que chaque robot puisse connaître les zones de l'environnement encore inexplorées. Pour obtenir une bonne coopération avec un algorithme simple nous proposons une technique de déploiement fondée sur le choix d'une cible par chaque robot. L'algorithme proposé cherche à distribuer les robots vers différentes directions. Il est fondé sur le calcul partiel de champs de potentiels permettant à chaque robot de calculer efficacement son prochain objectif. En complément de ces contributions théoriques, nous décrivons le système robotique complet mis en oeuvre au sein de l'équipe Cart-O-Matic ayant permis de remporter la dernière édition du défi CAROTTE
This thesis is part of Cart-O-Matic project set up to participate in the challenge CARROTE (mapping of a territory) organized by the ANR and the DGA. The purpose of this challenge is to build 2D and 3D maps of a static unknown 'apartment-like' environment. In this context, the use of several robots is advantageous because it increases the time efficiency to discover fully the environment. However, as we show, the gain is determined by the level of cooperation between robots. We propose a cooperation strategy for efficient multirobot mapping. A difficulty is the construction of a common map, necessary so that each robot can know the areas of the environment which remain unexplored.For a good cooperation with a simple algorithm we propose a deployment technique based on the choice of a target by each robot. The proposed algorithm tries to distribute the robots in different directions. It is based on calculation of the partial potential fields allowing each robot to compute efficiently its next target. In addition to these theoretical contributions, we describe the complete robotic system implemented in the Cart-O-Matic team that helped win the last edition of the CARROTE challenge

L’intérêt pour l’intégration des systèmes multi-robots (MRS) dans les applications du monde réel augmente de plus en plus, notamment pour l’exécution de tâches complexes. Pour les tâches de transport de charges, différentes stratégies de manutention de charges ont été proposées telles que : la poussée seule, la mise en cage et la préhension. Dans cette thèse, nous souhaitons utiliser une stratégie de manipulation simple : placer l’objet à transporter au sommet d’un groupe de robots mobiles. Ainsi, cela nécessite un contrôle de formation rigide. Nous proposons deux algorithmes de formation. L’algorithme de consensus est l’un d’entre eux. Nous adaptons un contrôleur de flocking dynamique pour qu’il soit utilisé dans le système à un seul intégrateur, et nous proposons un système d’évitement d’obstacles qui peut empêcher le fractionnement tout en évitant les obstacles. Le deuxième contrôle de formation est basé sur l’optimisation quadratique hiérarchique (HQP). Le problème est décomposé en plusieurs objectifs de tâches : formation, navigation,évitement d’obstacles et limites de vitesse. Ces tâches sont représentées par des contraintes d’égalité et d’inégalité avec différentsniveaux de priorité, qui sont résolues séquentiellement par le HQP. Enfin, une étude sur les algorithmes d’allocation des tâches(Contract Net Protocol et Tabu Search) est menée afin de déterminer une solution appropriée pour l’allocation des tâches dans l’environnementindustriel
The interest in integrating multirobot systems (MRS) into real-world applications is increasing more and more, especially for performing complex tasks. For loadcarrying tasks, various load-handling strategies have been proposed such as: pushingonly, caging, and grasping. In this thesis, we aim to use a simple handling strategy: placing the carrying object on top of a group of wheeled mobile robots. Thus, it requires a rigid formation control. A consensus algorithm is one of the two formation controllers we apply to the system. We adapt a dynamic flocking controller to be used in the singleintegrator system, and we propose an obstacle avoidance that can prevent splitting while evading the obstacles. The second formation control is based on hierarchical quadratic programming (HQP). The problem is decomposed into multiple task objectives: formation, navigation, obstacle avoidance, velocity limits. These tasks are represented by equality and inequality constraints with different levels of priority, which are solved sequentially by the HQP. Lastly, a study on task allocation algorithms (Contract Net Protocol and Tabu Search) is carried out in order to determine an appropriate solution for allocating tasks in the industrial environment

Cette thèse s'inscrit dans le cadre du projet Cart-O-Matic mis en place pour participer au défi CAROTTE (CArtographie par ROboT d'un TErritoire) organisé par l'ANR et la DGA. Le but de ce défi est de construire une carte en deux et trois dimensions et de localiser des objets dans un environnement inconnu statique de type appartement. Dans ce contexte, l'utilisation de plusieurs robots est avantageuse car elle permet d'augmenter l'efficacité en temps de la couverture. Cependant, comme nous le montrons, le gain est conditionné par le niveau de coopération entre les robots. Nous proposons une stratégie de coopération pour une cartographie multirobot efficace. Une difficulté est la construction d'une carte commune, nécessaire, afin que chaque robot puisse connaître les zones de l'environnement encore inexplorées. Pour obtenir une bonne coopération avec un algorithme simple nous proposons une technique de déploiement fondée sur le choix d'une cible par chaque robot. L'algorithme proposé cherche à distribuer les robots vers différentes directions. Il est fondé sur le calcul partiel de champs de potentiels permettant à chaque robot de calculer efficacement son prochain objectif. En complément de ces contributions théoriques, nous décrivons le système robotique complet mis en oeuvre au sein de l'équipe Cart-O-Matic ayant permis de remporter la dernière édition du défi CAROTTE
This thesis is part of Cart-O-Matic project set up to participate in the challenge CARROTE (mapping of a territory) organized by the ANR and the DGA. The purpose of this challenge is to build 2D and 3D maps of a static unknown 'apartment-like' environment. In this context, the use of several robots is advantageous because it increases the time efficiency to discover fully the environment. However, as we show, the gain is determined by the level of cooperation between robots. We propose a cooperation strategy for efficient multirobot mapping. A difficulty is the construction of a common map, necessary so that each robot can know the areas of the environment which remain unexplored.For a good cooperation with a simple algorithm we propose a deployment technique based on the choice of a target by each robot. The proposed algorithm tries to distribute the robots in different directions. It is based on calculation of the partial potential fields allowing each robot to compute efficiently its next target. In addition to these theoretical contributions, we describe the complete robotic system implemented in the Cart-O-Matic team that helped win the last edition of the CARROTE challenge

Lors de l'engagement d'un projet, un chef de projet doit structurer le projet de conception. Il s'agit de définir une architecture préliminaire du produit, de structurer le processus de conception et de regrouper les acteurs du projet en équipes interdépendantes (le regroupement est appelé "architecture des acteurs"). Ces trois activités sont fortement inter-reliées et critiques lors de la phase de conception préliminaire, car les décisions prises auront un impact fort sur les performances de l'ensemble du projet. Cependant, peu de méthodes formelles ont été proposées pour les considérer conjointement. Par ailleurs, lors de l'affectation des tâches du processus aux acteurs, le chef de projet doit s'assurer que les acteurs sont compétents pour réaliser une tâche. Il doit aussi prendre en compte des besoins de futurs projets qui pourraient nécessiter des apprentissages dans les projets en cours. Dans la réalité, la complexité de l'organisation d'un projet empêche d'avoir une vision globale des conséquences des choix d'affectation, qui plus est, sur plusieurs périodes et sur plusieurs projets. Peu de travaux se sont intéressés à ce type de problème. Or aujourd'hui, les tâches et les compétences nécessaires dans les projets de conception évoluent rapidement en lien avec la forte évolution des technologies et des besoins du marché. Le développement des compétences des ressources humaines devient une des priorités de l'entreprise qui ne les considère plus comme des ressources statiques (comme des machines) mais comme des ressources dynamiques auxquelles il faut attacher des objectifs de développement. Dans ce mémoire, nous proposons une méthode d'aide à la constitution d'équipes permettant de coupler la structuration du projet et le pilotage des compétences. Ce travail consiste alors à optimiser l'affectation des tâches aux acteurs et le regroupement des acteurs en équipes, en tenant compte à la fois des contraintes liés à l'architecture du produit et des objectifs de développement de compétences, sur de multiples projets et de multiples périodes. Ce problème étant complexe, ce mémoire de thèse présente des contributions à des sousproblèmes (affectation mon-période, affectation multi-périodes avec prise en compte du développement des compétences, architecture des acteurs avec prise en compte de l'architecture du produit), avant de proposer une formulation du problème global et une méthode de résolution en deux phases intégrant un algorithme de recuit simulé.

Les moyens et l'organisation de la justice sont des déterminants importants de l'efficacité de cette institution. Pourtant, ces aspects restent encore marginalement étudiés dans l'analyse économique du droit. Après avoir mis en évidence le besoin d'un cadre d'analyse économique des relations entre les résultats de l'activité judiciaire, les moyens alloués au système, la demande de justice et ses modes d'organisation, nous contribuons directement à l'exploration de ces relations. D'abord grâce à un modèle théorique, nous démontrons l'existence d'un effet multiplicateur des dépenses publiques de justice en nous appuyant sur l'analyse d'un type de conflits particulier : les conflits locatifs. Nous démontrons alors qu'une augmentation marginale des dépenses consacrées à la résolution de ce type de conflits améliore de manière significative à la fois le fonctionnement des tribunaux et le fonctionnement du marché du logement locatif. Ensuite, grâce à un test économétrique à partir de données originales – en particulier celles produites par la Commission Européenne pour l'Efficacité de la Justice – nous mettons en évidence un lien positif et robuste entre la confiance des individus dans la justice et diverses variables budgétaires. Nous développons l'idée que le budget de la justice joue un rôle de signal de la qualité de l'institution pour les agents dont la connaissance réelle du système judiciaire est limitée. Enfin, dans un modèle de double aléa moral appliqué à la production de justice, nous analysons les relations entre les moyens et l'organisation de la justice puis entre cette dernière et les résultats de son activité. Nous démontrons alors que certains équilibres du jeu stratégique entre les agents responsables de la production des services judiciaires – le gouvernement et les magistrats – correspondent à des situations inefficaces car les magistrats sont amenés à effectuer des tâches administratives à la place du gouvernement, au prix d'un niveau de production de services judiciaires relativement faible
The means and organization of justice are important determinants of the efficiency of this institution. Nevertheless, these aspects still remain marginally studied in the economic analysis of law. After we have highlighted the need for an economic analytical framework of the relationships between the results of judicial activity, the means allocated to the system, the demand of justice and its organizational features, we directly contribute to the exploration of these relationships. First, thanks to a theoretical model, we demonstrate the existence of a multiplier effect of public expenditure on justice by focusing on the analysis of a particular type of disputes: rental ones. We thus demonstrate that a marginal increase in expenditures dedicated to the resolution of rental disputes significantly improves both the functioning of courts and the functioning of the rental market. Then, thanks to an econometrical test on original data – in particular the ones produced by the European Commission for the Efficiency of Justice – we show a positive and robust link between individuals' trust in justice and different budget-related variables. We argue that the justice budget plays a role as a signal of the institution's quality for agents whose knowledge about the reality of the judicial system is limited. Finally, using a double-sided moral hazard model applied to the production of justice, we analyze the relationship between the means and the organization of justice and then, between the organization and the results of judicial activity. We thus demonstrate that some of the equilibria of the strategic game between the agents who are responsible for the production of judicial services – the government and the magistrates – correspond to inefficient situations because magistrates are led to perform administrative tasks instead of the government, at the cost of a relatively low level of production of judicial services

Les unités de production sont actuellement soumises à de fortes contraintes de productivité et de flexibilité. Les problèmes à résoudre sont relatifs au pilotage des installations avec prise en compte des perturbations, à la surveillance, au contrôle et à l'exploitation des équipements ainsi qu'au rôle des opérateurs. Il s'agit de rendre et de maintenir opérationnels les différents éléments de l'installation, de les synchroniser, de les coordonner et d'intégrer les ressources humaines et matérielles, dans une approche de gestion en flux tendus. Dans ce mémoire nous décrivons les principales fonctions des systèmes de pilotage des SAP et constatons que les structures de pilotage hiérarchisées classiques ne peuvent permettre d'atteindre pleinement les objectifs précédents. Nous montrons les avantages de la résolution distribuée de problèmes pour la spécification de systèmes de pilotage temps réel des SAP, et proposons un modèle d'organisation pour les systèmes distribués (concept de SIP) ainsi qu'un modèle de contrôle d'allocation dynamique de taches. Deux exemples d'applications nous permettent d'évaluer les modèles d'allocation dynamique de taches et de contrôle du système de pilotage distribué. Ces exemples démontrent la faisabilité et les potentialités des architectures distribuées pour le pilotage des SAP.

La collecte participative des données mobiles est un nouveau paradigme dédié aux applications de détection urbaines utilisant une foule de participants munis de téléphones intelligents. Pour mener à bien les tâches de collecte participative des données mobiles, diverses préoccupations relatives aux participants et aux organisateurs doivent être soigneusement prises en considération. Pour les participants, la principale préoccupation porte sur la consommation d'énergie, le coût des données mobiles, etc. Pour les organisateurs, la qualité des données et le budget sont les deux préoccupations essentielles. Dans cette thèse, deux mécanismes de collecte participative des données mobiles sont proposés : le téléchargement montant collaboratif des données et la collecte clairsemée des données mobiles. Pour le téléchargement montant collaboratif des données, deux procédés sont proposés 1) « effSense », qui fournit la meilleure solution permettant d’économiser la consommation d'énergie aux participants ayant un débit suffisant, et de réduire le coût des communications mobiles aux participants ayant un débit limité; 2) « ecoSense », qui permet de réduire le remboursement incitatif par les organisateurs des frais associés au coût des données mobiles des participants. Dans la collecte clairsemée des données mobiles, les corrélations spatiales et temporelles entre les données détectées sont exploitées pour réduire de manière significative le nombre de tâches allouées et, par conséquent, le budget associé aux organisateurs, tout en assurant la qualité des données. De plus, l’intimité différentielle est afin de répondre au besoin de préservation de la localisation des participants
Mobile crowdsensing is a novel paradigm for urban sensing applications using a crowd of participants' sensor-equipped smartphones. To successfully complete mobile crowdsensing tasks, various concerns of participants and organizers need to be carefully considered. For participants, primary concerns include energy consumption, mobile data cost, privacy, etc. For organizers, data quality and budget are two critical concerns. In this dissertation, to address both participants' and organizers' concerns, two mobile crowdsensing mechanisms are proposed - collaborative data uploading and sparse mobile crowdsensing. In collaborative data uploading, participants help each other through opportunistic encounters and data relays in the data uploading process of crowdsensing, in order to save energy consumption, mobile data cost, etc. Specifically, two collaborative data uploading procedures are proposed (1) effSense, which helps participants with enough data plan to save energy consumption, and participants with little data plan to save mobile data cost; (2) ecoSense, which reduces organizers' incentive refund that is paid for covering participants' mobile data cost. In sparse mobile crowdsensing, spatial and temporal correlations among sensed data are leveraged to significantly reduce the number of allocated tasks thus organizers' budget, still ensuring data quality. Specifically, a sparse crowdsensing task allocation framework, CCS-TA, is implemented with compressive sensing, active learning, and Bayesian inference techniques. Furthermore, differential privacy is introduced into sparse mobile crowdsensing to address participants' location privacy concerns

La collecte participative des données mobiles est un nouveau paradigme dédié aux applications de détection urbaines utilisant une foule de participants munis de téléphones intelligents. Pour mener à bien les tâches de collecte participative des données mobiles, diverses préoccupations relatives aux participants et aux organisateurs doivent être soigneusement prises en considération. Pour les participants, la principale préoccupation porte sur la consommation d'énergie, le coût des données mobiles, etc. Pour les organisateurs, la qualité des données et le budget sont les deux préoccupations essentielles. Dans cette thèse, deux mécanismes de collecte participative des données mobiles sont proposés : le téléchargement montant collaboratif des données et la collecte clairsemée des données mobiles. Pour le téléchargement montant collaboratif des données, deux procédés sont proposés 1) « effSense », qui fournit la meilleure solution permettant d’économiser la consommation d'énergie aux participants ayant un débit suffisant, et de réduire le coût des communications mobiles aux participants ayant un débit limité; 2) « ecoSense », qui permet de réduire le remboursement incitatif par les organisateurs des frais associés au coût des données mobiles des participants. Dans la collecte clairsemée des données mobiles, les corrélations spatiales et temporelles entre les données détectées sont exploitées pour réduire de manière significative le nombre de tâches allouées et, par conséquent, le budget associé aux organisateurs, tout en assurant la qualité des données. De plus, l’intimité différentielle est afin de répondre au besoin de préservation de la localisation des participants
Mobile crowdsensing is a novel paradigm for urban sensing applications using a crowd of participants' sensor-equipped smartphones. To successfully complete mobile crowdsensing tasks, various concerns of participants and organizers need to be carefully considered. For participants, primary concerns include energy consumption, mobile data cost, privacy, etc. For organizers, data quality and budget are two critical concerns. In this dissertation, to address both participants' and organizers' concerns, two mobile crowdsensing mechanisms are proposed - collaborative data uploading and sparse mobile crowdsensing. In collaborative data uploading, participants help each other through opportunistic encounters and data relays in the data uploading process of crowdsensing, in order to save energy consumption, mobile data cost, etc. Specifically, two collaborative data uploading procedures are proposed (1) effSense, which helps participants with enough data plan to save energy consumption, and participants with little data plan to save mobile data cost; (2) ecoSense, which reduces organizers' incentive refund that is paid for covering participants' mobile data cost. In sparse mobile crowdsensing, spatial and temporal correlations among sensed data are leveraged to significantly reduce the number of allocated tasks thus organizers' budget, still ensuring data quality. Specifically, a sparse crowdsensing task allocation framework, CCS-TA, is implemented with compressive sensing, active learning, and Bayesian inference techniques. Furthermore, differential privacy is introduced into sparse mobile crowdsensing to address participants' location privacy concerns

Large display environments (LDEs) are interactive physical workspaces featuring one or more static large displays as well as rich interaction capabilities, and are meant to visualize and manipulate very large datasets. Research about mid-air interactions in such environments has emerged over the past decade, and a number of interaction techniques are now available for most elementary tasks such as pointing, navigating and command selection. However these techniques are often designed and evaluated separately on specific platforms and for specific use-cases or operationalizations, which makes it hard to choose, compare and combine them.In this dissertation I propose a framework and a set of guidelines for analyzing and combining the input and output channels available in LDEs. I analyze the characteristics of LDEs in terms of (1) visual output and how it affects usability and collaboration and (2) input channels and how to combine them in rich sets of mid-air interaction techniques. These analyses lead to four design requirements intended to ensure that a set of interaction techniques can be used (i) at a distance, (ii) together with other interaction techniques and (iii) when collaborating with other users. In accordance with these requirements, I designed and evaluated a set of mid-air interaction techniques for panning and zooming, for invoking commands while pointing and for performing difficult pointing tasks with limited input requirements. For the latter I also developed two methods, one for calibrating high-precision techniques with two levels of precision and one for tuning velocity-based transfer functions. Finally, I introduce two higher-level design considerations for combining interaction techniques in input-constrained environments. Designers should take into account (1) the trade-off between minimizing limb usage and performing actions in parallel that affects overall performance, and (2) the decision and adaptation costs incurred by changing the resolution function of a pointing technique during a pointing task.