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

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

La planification est un domaine de l'intelligence artificielle qui a pour but de proposer des méthodes permettant d'automatiser la recherche et l'ordonnancement d'ensembles d'actions afin d'atteindre un objectif donné. Un ensemble ordonné d'actions solution d'un problème de planification est appelé un plan. Parfois, les actions disponibles peuvent avoir un coût - on souhaite alors trouver des plans minimisant la somme des coûts des actions les constituant. Ceci correspond en fait à la recherche d'un chemin de coût minimal dans un graphe, et est donc traditionnellement résolu en utilisant des algorithmes tels que A*. Dans cette thèse, nous nous intéressons à une approche particulière de la planification, dite factorisée ou modulaire. Il s'agit de décomposer un problème en plusieurs sous-problèmes (généralement appelés composants) le plus indépendants possibles, et d'assembler des plans pour ces sous-problèmes en un plan pour le problème d'origine. L'intérêt de cette approche est que, pour certaines classes de problèmes de planification, les composants peuvent être bien plus simples à résoudre que le problème initial. Dans un premier temps, nous présentons une méthode de planification factorisée basée sur l'utilisation d'algorithmes dits à passage de messages. Une représentation des composants sous forme d'automates à poids nous permet de capturer l'ensemble des plans d'un sous-problème, et donc de trouver des plans de coût minimal, ce que ne permettaient pas les approches précédentes de la planification factorisée. Cette première méthode est ensuite étendue~: en utilisant des algorithmes dits « turbos », permettant une résolution approchée des problèmes considérés, puis en proposant une représentation différente des sous-problèmes, afin de prendre en compte le fait que certaines actions ne font que lire dans un composant. Ensuite, nous proposons une autre approche de la planification factorisée, basée sur une version distribuée de l'algorithme A*. Dans chaque composant, un agent réalise la recherche d'un plan local en utilisant sa connaissance du sous-problème qu'il traite, ainsi que des informations transmises par les autres agents. La principale différence entre cette méthode et la précédente est qu'il s'agit d'une approche distribuée de la planification modulaire. / Automated planning is a field of artificial intelligence that aims at proposing methods to chose and order sets of actions with the objective of reaching a given goal. A sequence of actions solving a planning problem is usually called a plan. In many cases, one does not only have to find a plan but an optimal one. This notion of optimality can be defined by assigning costs to actions. An optimal plan is then a plan minimizing the sum of the costs of its actions. Planning problems are standardly solved using algorithms such as A* that search for minimum cost paths in graphs. In this thesis we focus on a particular approach to planning called factored planning or modular planning. The idea is to consider a decomposition of a planning problem into almost independent sub-problems (or components). One then searches for plans into each component and try to assemble these local plans into a global plan for the original planning problem. The main interest of this approach is that, for some classes of planning problems, the components considered can be planning problems much simpler to solve than the original one. First, we present a study of the use of some message passing algorithms for factored planning. In this case the components of a problem are represented by weighted automata. This allows to handle all plans of a sub-problems, and permits to perform factored cost-optimal planning. Achieving cost-optimality of plans was not possible with previous factored planning methods. This approach is then extended by using approximate resolution techniques ("turbo" algorithms) and by proposing another representation of components for handling actions which read-only in some components. Then we describe another approach to factored planning: a distributed version of the famous A* algorithm. Each component is managed by an agent which is responsible for finding a local plan in it. For that, she uses information about her own component, but also information about the rest of the problem, transmitted by the other agents. The main difference between this approach and the previous one is that it is not only modular but also distributed.

Outre la contrainte de sa situation géopolitique liée à l'occupation, la Palestine est confrontée aux mêmes problèmes écologiques que ceux qui se posent aux autres pays de la planète et qui pèsent notamment sur la population, la structure des villes et l'avenir du territoire. Plusieurs facteurs peuvent être cités : instabilité politique, non-reconnaissance en tant qu’État souverain, fragmentation géographique, pression démographique, rareté des ressources, manque de traitement des déchets et eaux usées, urbanisation anarchique, défaillance législative locale et internationale. L'ensemble de ces facteurs engendrent des conséquences graves sur l'Homme et son milieu de vie. Les territoires sont ainsi frappés par la crise économique et écologique : insécurité alimentaire, pollution, déforestation, disparition des terrains agricoles, atteinte au patrimoine bâti et naturel. Face à ces handicaps et ces défis, toute projection dans l'avenir devient difficile, voire désespérée. La forte dégradation de l'environnement en Cisjordanie ne permet pas de maintenir des conditions de vie digne pour la population existante ni pour les futures générations. La politique menée aujourd'hui relève de l'écocide progressif qui menace fortement la survie sur ce territoire. Améliorer la situation ne peut aboutir sans une réflexion globale et locale, sans une volonté d'adhésion et de coopération de l'ensemble des décideurs politiques ou technique, ni sans une participation active des associations et des habitants. Si l'on considère les enjeux environnementaux (eau, ressources, sol) comme étant au coeur du conflit israélo-palestinien, la planification environnementale devient alors primordiale tant pour les Israéliens que pour les Palestiniens. Il n'y a pas d'un côté la Palestine et de l'autre Israël, d'un côté l'homme et de l'autre l'environnement. Ces éléments sont liés et interconnectés. Chaque élément affecte la viabilité de l'autre. Ce sont les conclusions qui sont formulées dans la présente thèse autour de quatre axes. La mise en perspective des constats et des enjeux géopolitiques, environnementaux et urbains sont déclinés dans les trois premières parties de la thèse. La quatrième partie est consacrée à la nécessité d'agir en concevant une planification environnementale. Passer de l'écocide à l'écocité requiert le respect de l'Homme et de son milieu de vie, la mobilisation primordiale de tous les acteurs à tous les niveaux, que ce soient les responsables politiques, le les secteurs publics et privés, les habitants... Alors que la concrétisation peut paraître utopique, elle est le seul moyen de corriger la réalité. Même si cela exige du temps et de la patience, il faut semer dès à présent pour récolter plus tard. Ainsi, construire un meilleur avenir progressivement peut poindre et une politique démocratique et planifiée peut émerger à la condition de s'appuyer sur les volontés des associations, des universitaires, des techniciens et des citoyens... Il est alors nécessaire de travailler à l'échelle locale, de protéger le patrimoine et les richesses du territoire mais aussi d'éduquer les jeunes à l'environnement et de faire naître leur prise de conscience aux problèmes actuels. Seule une planification environnementale englobant toutes ces dimensions peut cimenter les fondations d'un État palestinien viable et durable dans une optique fondée sur une confiance mutuelle. / Palestine faces geopolitical problems on both local and global levels affecting the population, the cities and its future. In other words, it is threatening the existence of the territory. Indeed, several factors can be cited: political instability, non-recognition of the sovereign state, geographical fragmentation, population density, scarcity of resources, uncontrolled urbanization, the lack of waste and wastewater management, of local and international legislatures. All these factors have seriously impinged on the country and resulted to an economic and ecological crisis, food insecurity, pollution, deforestation, agricultural lands' loss and damage to the built and natural heritage. Therefore, any planning into the future becomes difficult and with no essence. The environmental degradation in the West Bank cannot maintain decent and hygiene living conditions for the existing population or future generations. The ecocide is progressive; it threatens the survival of the territory. A remedy for the situation cannot be established without thinking on the local and international scope of cooperation and without the willingness to join and work together on all levels hand in hand with policy makers through full participation of associations and residents. If we consider environmental issues (water, resources, land) as fundamental issues in the Israeli-Palestinian conflict: the environmental planning challenges become paramount for both Israelis and Palestinians. Facts on the ground show that we do not have the West Bank on one hand and Israel on the other, just as you do not have man on the one hand and the environment on the other. These elements are interconnected to the roots. Both States are deemed to a common destiny. Here are the conclusions that have been treated throughout this thesis divided into four parts. The first three ones put into perspective the geopolitical, environmental and urban findings. Then, the last one asserts the need to urge the environmental planning. Under such complex and unstable conditions, passing from ecocide to ecological city requires the respect for man and his environment, the mobilization of all primary stakeholders at all levels, whether they are politicians, public-private sectors, habitants, etc. Thus, it is necessary to start working at local level to protect the heritage and the wealth of the country, to educate the young generation to the environment and bring out their awareness of the current problems. Only environmental planning encompassing all these dimensions can cement a strong base to ensure a better quality of life, it will contribute to establishing a viable Palestinian State and setting the foundations to the pillars of peace

La pratique de la planification urbaine reste un défi dans les villes d'Afrique sub-saharienne et l'occupation de l'espace urbain se fait en grande partie en déphasage avec les normes urbanistiques. L'analyse du contexte de production et d'occupation de l'espace urbain ainsi que des conséquences qui découlent d'une planification urbaine inconséquente permet de faire un lien entre les problèmes de développement et les risques d'aggravation des inondations.A Cotonou, le phénomène est plus qu'inquiétant. Les problèmes de planification se posent en termes d'occupation des zones impropres à l'habitat, de fragilité des surfaces bâties et de qualité des ouvrages d'assainissement. Les conditions d'insalubrité de l'habitat et la situation sanitaire des zones potentiellement inondables ainsi que la gestion de l'environnement sont autant de défis pour les autorités locales ; l'occupation anarchique de l'espace, la perte progressive de contrôle et de régulation de l'action publique étant des causes de cette situation.Les propositions formulées dans cette recherche sont relatives aux contraintes physiques, pluviométriques, climatologiques et aux stratégies d’adaptation des populations face aux inondations. Elles intègrent également l'amélioration de la gouvernance urbaine, l'assainissement urbain et la gestion de l'environnement construit. / The practice of urban planning remains a key challenge in Sub-Saharan Africa cities since the urban land use is out of phase with the urbanistic standards. The analysis of the context of urban space production and occupation as well as of the consequences that result from an inconsistent urban planning allows us to draw a link between development problems and the risks of aggravating flood situations. The phenomenon is more than worrisome in Cotonou. The planning problems can be presented in terms of occupation of land that are unsuitable for habitat, of vulnerability of inhabited areas and of quality of wastewater facilities. The unhygienic conditions of the habitat and the sanitary situation of potentially flood-prone areas as well as the environment management are among the numerous challenges for cities councils, which are caused by the anarchic occupation of land, the gradual loss of control and regulation by the public hands.The proposals made by this research are related to the physical and climatological constraints and to the strategies for adaptation of the communities to floods. They include besides urban governance improving, urban sanitation and built environment management.

Le confort et la sécurité de conduite sont les principaux critères de vente de l’industrie automobile actuelle. De nombreux projets de recherche sont mis en place afin de les améliorer et pour faire face aux mesures de législation et de contrôle mises en place pour réduire le nombre d’accidents routiers. Les mesures semblent efficaces : en France,par exemple, le nombre des accidents mortels diminue de 11% en moyenne chaque année.D’après de récentes études, 90% de ces accidents ont pour cause le facteur humain et il devient nécessaire de prendre en compte le conducteur pendant la phase de conception des systèmes de sécurité et d’aide à la conduite. Une assistance à la conduite basée sur le partage du contrôle du véhicule entre le conducteur et l’automate est un des axes de recherche privilégiés de l’industrie, notamment pour améliorer la sécurité.Il est maintenant devenu possible de récupérer une très grande quantité d’information sur l’environnement et de réaliser une interaction intelligente entre les différents acteurs du trafic. Les techniques existantes permettent même la conduite partagée entre le véhicule et le conducteur et, dans un horizon plus lointain, d’envisager un véhicule complètement autonome. Dans les situations de conduite automatisée, un algorithme adéquat est nécessaire pour remplacer le conducteur.L’intérêt principal de cette recherche se situe au niveau de l’interaction entre le conducteur et l’algorithme d’assistance ou de conduite automatisée. Il est indispensable de connaître et de comprendre le comportement du conducteur dans sa façon de conduire,de contrôler le véhicule et de prendre une décision. Par conséquent, un modèle adapté aux besoins est nécessaire. En plus de la nécessité de disposer d’un modèle suffisamment riche pour décrire le comportement de différents conducteurs dans les situations routières les plus fréquentes, il est indispensable de disposer d’une méthode de synthèse des systèmes d’assistance sur la base de ces modèles. / Driving comfort and safety are the main points of interest for the automotive industry. Many research projects were realized in order to improve them and to reduce the number of road accidents. The measures seem to be effective : in France, for example, the number of fatal accidents decreases by 11% on average each year. According to recent studies, 90% of these accidents are caused by the human factor. As a consequence, it becomes necessary to take the driver into account during the design of driving assistance systems. An assistance based on the control sharing between the driver and the automatic pilot is one of the main topics of research and a way to improve safety. It has now become possible to recover a very large amount of information on the environment and to achieve intelligent interaction between the various actors in the traffic. Existing technologies even allow imagining a completely autonomous driving in a more distant horizon. In such a situation, an adequate algorithm is required to replace the human driver.The main interest of this research is the interaction between the driver and the driver assistance algorithm. It is essential to know and to understand the behavior of the humanin his / her way to control the vehicle and to make a decision. Therefore, his model is necessary. Moreover, it is essential to develop a design method for such assistance systems on the basis of these driver models.

Durant la dernière décennie, de nouveaux concepts ont émergé dans le domaine de l'électricité, notamment les Smart Grids, la génération distribuée et les Microgrids (MGs). Dans cette thèse, nous nous concentrons principalement sur l'étude des MGs. Selon les prévisions des spécialistes du domaine, les MGs devraient prendre une place de plus en plus importante dans les futurs systèmes électriques. Mais pour cela, ils devront être mieux gérés, et il faudra donc d’abord résoudre plusieurs problèmes importants : l’identification, la mobilité, l’aspect multi-rôles, l’interopérabilité, la non-coopération et la planification de l’offre et la demande de l’électricité. Afin de résoudre tous ces problèmes, nous proposons un Framework dédié composé de 3 couches : physique, de connaissance et de gestion. Trois principales contributions sont présentées dans ce travail ciblant la résolution des problèmes déjà cités : OntoMG : un modèle d'information ontologique pour les Microgrids, DECF : un modèle coopératif pour l’optimisation de l’échange d’électricité dans le MG, et MOCSF : une planification coopérative multi-objectifs de l’électricité dans le MG. OntoMG est un modèle ontologique de données, basé sur les standards IEC 61970 et IEC 61580, complété par un nombre de paramètres additionnels permettant au MG d’atteindre l’ensemble de ses objectifs. Notre approche présente plusieurs avantages par rapport aux approches existantes dans la littérature scientifique, notamment : elle permet une planification de la consommation, la production et le stockage de l’électricité dans le MG, elle considère plusieurs sources d'énergie contrairement aux approches existantes qui ne prennent en compte que l'interaction des consommateurs avec une seule source d'énergie, et elle prend en compte l’ensemble des préférences des composants du MG à la différence des approches existantes qui ne considèrent ces préférences qu’en partie. / Over the past decade, new concepts have emerged in the electricity field, including the Smart Grids, the Distributed Generation and the Micro- grids (MGs). In this thesis, we will be mainly focusing on the study of the MGs. An MG is a small-scale power system, consisting of local power generation, local loads and energy storage systems. Thanks to their numerous economical, ecological and operational benefits, the MGs are expected to hold the promise of becoming a major ingredient in the implementation of the future power systems. However, there are several significant challenges to overcome in order to achieve its expected bene- fits, namely: the cyber-attacks, the mobility aspect, the interoperability, the non-cooperation, and the demand-side management. Three main contributions are developed. First, we present OntoMG, an ontology-based data model, capable of representing the heterogeneous components of the MG and their properties, while being compliant with existing models and information standards (i.e., IEC 61970 and IEC 61850) and coping with the interoperability issues and the multi-objective aspect of MG. Secondly, we introduce DECF, a cooperative model for the optimization of the electricity exchange in the MG, offering several advantages over existing approaches, in particular: 1) its generic in that it considers all heterogeneous components of MG, 2) it is a cooperative model that reduces the technical, ecological and economic costs and encourages the local power exchange, and 3) it is user-oriented in that it gives the user the possibility to fine-tune the weight of each objective aspect . Finally, we introduce MOCSF, a ‘Multi-objective Cooperative Scheduling Framework’ designed for scheduling the production, consumption and storage in the MG. MOCSF 1) provides a multi-type scheduling in that it allows the scheduling of all the power consumption, production and storage of the MG, 2) considers multiple energy sources and 3) considers the MG components’ preferences. After detailing the existing power scheduling techniques and their drawbacks regarding our challenges, we presented our ‘MOCSF’ modules: The Preference-based compromise builder, designed to generate the best balance between the sellers and buyers desired schedules and the Multi-Objective Scheduler, aiming at scheduling the seller-to-buyer associations resulting from the DECF, while reducing the operational, economic and ecological costs of the MG. An illustrative example is provided after each step to ease the understanding of each module. Finally, a set of experiments showed the performance and efficiency of our approach. Illustrative examples are provided after each step to facilitate understanding of each module. Then, a number of simulations are made to show the effectiveness of our approaches to solve our challenges in relation to the existing approaches.

Une nouvelle modalité de radiothérapie, la micro-curiethérapie, est en cours de développement. Cette thérapie cible des tumeurs solides inopérables en effectuant des injections de liquide contenant des microsphères radioactives en suspension. Plusieurs injections sont nécessaires pour suffisamment irradier la zone tumorale et donc, afin d'optimiser le positionnement de ces injections, une méthode de planification de traitement nécessaire a été développée et validée au cours de cette thèse. Tout au long de ce travail, trois thèmes principaux seront discutés : • Comment réaliser la dosimétrie particulière de cette micro-curiethérapie ? • Comment effectuer la planification de traitement pour cette modalité ? • Comment optimiser le plan de traitement afin qu'il soit le plus efficace possible ? La dosimétrie en micro-curiethérapie a été réalisée en calculant la distribution de dose absorbée pour une injection. Cette distribution a été convoluée à la position des autres injections dans la tumeur pour calculer la distribution de dose absorbée dans le patient. Pour effectuer la dosimétrie spécifique dans la tumeur et les organes à risque, les histogrammes dose-volume (HDV) ont été extraits et analysés. Une fois la méthode de dosimétrie établie, nous avons développé une méthodologie de planification de traitement pour développer et optimiser le plan pour chaque patient. Pour cela, nous avons testé et comparé trois algorithmes : la méthode de Nelder-Mead, l'algorithme des abeilles et l'algorithme "Non-Dominated Sorting Genetic Algorithm II" (NSGA II). Nous avons montré que, grâce à l'optimisation multiobjectif, le NSGA II donne plus de liberté à l'utilisateur ; c'est pourquoi il a été utilisé par la suite. Enfin, nous avons effectué une comparaison entre les paramètres d'injection. Nous avons mis en évidence qu'entre les radio-isotopes 90Y, 166Ho, 131I and 177Lu, les injections de 90Y sont optimales. Nous avons testé des injections de 5, 10 et 20 µL et des activités initiales de 5, 10 et 20 MBq. Nous avons trouvé que des injections de 20 µL avec 20 MBq sont optimales car celles-ci permettent de minimiser le nombre d'injections requis. Cette nouvelle technologie associée aux développements réalisés dans ses travaux démontre la faisabilité, qui a pu être validée sur animal, de pouvoir injecter un liquide contenant des microsphères radioactives en suspension afin de pouvoir traiter efficacement, tout en préservant les tissus sains environnants, des tumeurs inopérables encore de mauvais pronostic aujourd'hui, mais surement mieux prises en charge dans un proche avenir. / An innovative form of radiotherapy, microbrachytherapy, is under development. This therapy targets solid, inoperable tumours by performing injections of liquid containing radioactive microspheres in suspension. Many injections are required to sufficiently cover the tumoural volume, and so to be able to deliver the position of these injections, a method of treatment planning has been developed and validated throughout this research. Throughout this work, three main questions are addressed: • How to perform the dosimetry for microbrachytherapy? • How to perform treatment planning for this modality? • What are the optimal injection properties to deliver the most efficient treatment? Microbrachytherapy dosimetry was performed by calculating the absorbed dose distribution for an injection. This distribution was then convolved at each injection position within the tumour to calculate the patient's absorbed dose distribution. Dosimetry of the tumour and the organs at risk was performed by extracting and analysing dose-volume histograms (DVHs). Once a method of dosimetry was put in place, optimisation algorithms were developed to generate patient-specific treatment plans. For this, three algorithms were tested and compared: Nelder-Mead Simplex, the Bees algorithm and the non-dominated sorting genetic algorithm II. It was found that, thanks to its MO optimisation, the non-dominated sorting algorithm II was the most flexible, and was used preferentially. Lastly, a comparison of injection parameters was performed. It was found that between 90Y, 166Ho, 131I and 177Lu, optimal injections consisted of microspheres of 90Y. Injection volumes of 5, 10 and 20 µL and initial activities of 5, 10 and 20 MBq were tested. It was found that 20 µL injections with 20 MBq were optimal because they minimise the number of injections required. This new technology combined with developments shown in this work demonstrate the feasibility - that was validated on animals - the ability to inject liquid containing radioactive microspheres in suspension to efficiently treat inoperable tumours whilst protecting surrounding healthy tissue. Such tumours, despite still having a poor prognosis, will surely have better support in the near future.

De nos jours, les utilisateurs de services interactifs comme le e-commerce, ou les moteurs de recherche, ont de grandes attentes sur la performance et la réactivité de ces services. En effet, les études ont montré que des lenteurs (même pendant une courte durée) impacte directement le chiffre d'affaire. Avoir des performances prédictives est donc devenu une priorité pour ces fournisseurs de services depuis une dizaine d'années.Mais empêcher la variabilité dans les systèmes de stockage distribué est un challenge car les requêtes des utilisateurs finaux transitent par des centaines de servers et les problèmes de performances engendrés par chacun de ces serveurs peuvent influencer sur la latence observée. Même dans les environnements correctement dimensionnés, des problèmes comme de la contention sur les ressources partagés ou un déséquilibre de charge entre les serveurs influent sur les latences des requêtes et en particulier sur la queue de leur distribution (95ème et 99ème centile).L’objectif de cette thèse est de développer des mécanises permettant de réduire les latences et d’obtenir des performances prédictives dans les environnements de stockage de données dans les nuages. Une contre-mesure efficace pour réduire la latence de queue dans les environnements de stockage de données dans les nuages est de fournir des algorithmes efficaces pour la sélection de réplique. Dans la sélection de réplique, une requête tentant d’accéder à une information donnée (aussi appelé valeur) identifiée par une clé unique est dirigée vers la meilleure réplique présumée. Cependant, sous des charges de travail hétérogènes, ces algorithmes entraînent des latences accrues pour les requêtes ayant un court temps d'exécution et qui sont planifiées à la suite de requêtes ayant des long temps d’exécution. Nous proposons Héron, un algorithme de sélection de répliques qui gère des charges de travail avec des requêtes ayant un temps d’exécution hétérogène. Nous évaluons Héron dans un cluster de machines en utilisant un jeu de données synthétique inspiré du jeu de données de Facebook ainsi que deux jeux de données réels provenant de Flickr et WikiMedia. Nos résultats montrent que Héron surpasse les algorithmes de l’état de l’art en réduisant jusqu’à 41% la latence médiane et la latence de queue.Dans la deuxième contribution de cette thèse, nous nous sommes concentrés sur les charges de travail multi-GET afin de réduire la latence dans les environnements de stockage de données dans les nuages Le défi consiste à estimer les opérations limitantes et à les planifier sur des serveurs non-coordonnés avec un minimum de surcoût. Pour atteindre cet objectif, nous présentons TailX, un algorithme d’ordonnancement de tâches multi-GET qui réduit les temps de latence de queue sous des charges de travail hétérogènes. Nous implémentons TailX dans Cassandra, une base de données clé-valeur largement utilisée. Il en résulte une amélioration des performances globales des environnements de stockage de données dans les nuages pour une grande variété de charges de travail hétérogènes. / Today, users of interactive services such as e-commerce, web search have increasingly high expectations on the performance and responsiveness of these services. Indeed, studies have shown that a slow service (even for short periods of time) directly impacts the revenue. Enforcing predictable performance has thus been a priority of major service providers in the last decade. But avoiding latency variability in distributed storage systems is challenging since end user requests go through hundreds of servers and performance hiccups at any of these servers may inflate the observed latency. Even in well-provisioned systems, factors such as the contention on shared resources or the unbalanced load between servers affect the latencies of requests and in particular the tail (95th and 99th percentile) of their distribution.The goal of this thesis to develop mechanisms for reducing latencies and achieve performance predictability in cloud data stores. One effective countermeasure for reducing tail latency in cloud data stores is to provide efficient replica selection algorithms. In replica selection, a request attempting to access a given piece of data (also called value) identified by a unique key is directed to the presumably best replica. However, under heterogeneous workloads, these algorithms lead to increased latencies for requests with a short execution time that get scheduled behind requests with large execution times. We propose Héron, a replica selection algorithm that supports workloads of heterogeneous request execution times. We evaluate Héron in a cluster of machines using a synthetic dataset inspired from the Facebook dataset as well as two real datasets from Flickr and WikiMedia. Our results show that Héron outperforms state-of-the-art algorithms by reducing both median and tail latency by up to 41%.In the second contribution of the thesis, we focus on multiget workloads to reduce the latency in cloud data stores. The challenge is to estimate the bottleneck operations and schedule them on uncoordinated backend servers with minimal overhead. To reach this objective, we present TailX, a task aware multiget scheduling algorithm that reduces tail latencies under heterogeneous workloads. We implement TailX in Cassandra, a widely used key-value store. The result is an improved overall performance of the cloud data stores for a wide variety of heterogeneous workloads.

Planifier un chemin géométrique pour un robot d'une configuration initiale à une configuration initiale est aujourd'hui un problème quasiment résolu moyennant une représentation géométrique de l'environnement statique du robot, une modélisation de la chaîne cinématique du robot et de ses contraintes cinématiques. L'exécution de tels chemins en environnement réel est en revanche un problème qui est loin d'être résolu malgré une littérature fournie sur le sujet. De nombreuses raisons expliquent cette difficulté parmi lesquelles l'inexactitude des modèles d'environnement utilisés et des moyens de localisation. L'objectif de notre travail est de proposer une approche générique de planification de mouvements référencés sur des amers. Le principe de notre approche consiste à associer à une trajectoire géométrique sans collision des couples amers-capteurs qui pendant l'exécution sont utilisés pour asservir localement le mouvement du robot. Cette approche nous permet de produire des mouvements sûrs en donnant plus d'importance aux amers qui ont de bonnes propriétés de localisation ou bien à ceux qui représentent un danger de collision. Des résultats expérimentaux réalisés sur un robot mobile non holonome de type Hilare avec remorque valident notre approche.