Planifier le chemin d’un robot dans un environnement complexe est un problème crucial en robotique. Les méthodes de planification probabilistes peuvent résoudre des problèmes complexes aussi bien en robotique, qu’en animation graphique, ou en biologie structurale. En général, ces méthodes produisent un chemin évitant les collisions, sans considérer sa qualité. Récemment, de nouvelles approches ont été créées pour générer des chemins de bonne qualité : en robotique, cela peut être le chemin le plus court ou qui maximise la sécurité ; en biologie, il s’agit du mouvement minimisant la variation énergétique moléculaire. Dans cette thèse, nous proposons plusieurs extensions de ces méthodes, pour améliorer leurs performances et leur permettre de résoudre des problèmes toujours plus difficiles. Les applications que nous présentons viennent de la robotique (inspection industrielle et manipulation aérienne) et de la biologie structurale (mouvement moléculaire et conformations stables). / Planning a path for a robot in a complex environment is a crucial issue in robotics. So-called probabilistic algorithms for path planning are very successful at solving difficult problems and are applied in various domains, such as aerospace, computer animation, and structural biology. However, these methods have traditionally focused on finding paths avoiding collisions, without considering the quality of these paths. In recent years, new approaches have been developed to generate high-quality paths: in robotics, this can mean finding paths maximizing safety or control; in biology, this means finding motions minimizing the energy variation of a molecule. In this thesis, we propose several extensions of these methods to improve their performance and allow them to solve ever more difficult problems. The applications we present stem from robotics (industrial inspection and aerial manipulation) and structural biology (simulation of molecular motions and exploration of energy landscapes).

Les travaux effectués dans cette thèse industrielle concernent l'amélioration du calculateur d'itinéraire de Cityway, société spécialisée dans les technologies de l’information appliquées à la mobilité.Nous avons d'abord établi un état de l'art exhaustif, accompagné d'une mise en perspective de l'existant Cityway avec celui-ci. Cela nous a permis d'aider l'entreprise à prendre du recul sur son produit et de justifier les axes de recherche choisis pour nos travaux.Nous nous sommes ensuite intéressés à l'aspect multicritère du problème. En effet, le calculateur, basé sur l'algorithme de Dijkstra, permet de trouver des trajets minimisant une somme pondérée de critères. Nous avons développé un algorithme multilabel permettant de conserver et étendre plusieurs labels au même nœud. Malgré une légère augmentation des temps de calculs, des résultats satisfaisants ont été obtenus dans une application bicritère de ce nouvel algorithme.Nous avons également travaillé sur la génération et la sélection de trajets alternatifs. La génération s'appuie sur les algorithmes monolabel ou multilabel. La sélection s'appuie quant à elle sur la définition d'une distance entre les solutions et des méthodes de regroupement.Enfin, nous nous sommes intéressés à l'optimisation du calcul du critère lexicographique de durée minimale dans le cas bicritère. Pour qu'un trajet soit intéressant, il faut qu'il soit optimal sur les critères usuels, mais aussi qu'il dure le moins longtemps possible. L'utilisation de certaines propriétés sur ce critère permet de réduire des temps de calcul initialement trop longs. / The work carried out in this industrial PhD aims at improving the route planner of Cityway, a company specialized in information technologies applied to mobility. We first established an exhaustive state of the art, and compared it to the existing Cityway product. This allowed us to help the company take a step back from its urgent needs, and justify the research guidelines chosen for our work.We then looked at the multi-criteria aspect of the problem. Indeed, the trip planner, based on the Dijkstra algorithm, makes it possible to find paths minimizing a weighted sum of criteria. We have developed a multilabel algorithm to maintain and extend multiple labels at the same node. Despite a slight increase in computation time, satisfactory results were obtained in a bicriteria application of this new algorithm.We also worked on the generation and selection of alternative routes. The generation algorithm relies on the existing monolabel or newly developed multilabel algorithms. The selection algorithm is based on the definition of a distance between trips and adaptations of existing clustering algorithms to this specific case.Finally, we were interested in what we called the lexicographic criterion. For a trip to be interesting, it must be optimal on the usual criterion of earliest arrival, and, for trips arriving at the same time, on the latest departure criterion. The use of certain properties on this criterion makes it possible to reduce computation times on the bicriteria case.

La linguistique cognitive considère les structures langagières comme le reflet de structures conceptuelles sous-jacentes. Les schèmes-images font partie de ces structures. Ils sont construits et abstraits à partir de l’expérience incorporée et socialement située du monde, ce qui leur confère à la fois une assise culturelle et sensori-motrice. Le présent travail confirme qu’il est possible, sur les bases théoriques édifiées par Lakoff et Johnson (1987), d’en identifier les réalisations lexicales et syntaxiques, en observant les usages langagiers. La thèse que nous soumettons aborde plus spécifiquement le schème-image du CHEMIN (PATH-schema). Pour mener cette analyse, nous ancrons nos recherches dans deux corpus. Le premier fait état de tous les types de chemins répertoriés en linguistique cognitive, à partir d’une centaine d’unités verbales, incluses dans 500 occurrences. Le second s’intéresse à quatre items verbaux, come, go, rise, et fall, répartis sur un millier d’exemples. Notre objectif consiste à discerner les charges morphosyntaxiques et les variantes sémantiques du schème du chemin. Ce faisant, nous inscrivons la corporéité – ou du moins son réinvestissement symbolique - au cœur de notre étude. Par « corporéité », nous entendons la conceptualisation et la figuration du rapport incarné du sujet au monde, les traces que laissent ces représentations dans l’organisation du lexique et des constructions. Nos corpus présentent une quantité importante de verbes, qui révèlent des états de fait abstraits. Ces emplois nous conduiront à explorer le statut du schème du chemin, tant dans sa réalisation morphosyntaxique que dans son contenu sémantique, lorsque ce schème sous-tend les extensions sémantiques des verbes étudiés. Nos questionnements sur la polysémie des verbes, sur leur définition d’un point de vue prototypique et sur leur grammaticalisation éventuelle, contribueront à révéler la réalité cognitive du schème analysé. Enfin, la quantité importante d’emplois « abstraits » des verbes, nous amènera à questionner la corporéité, telle que la linguistique cognitive la définit. / Linguistic structures are considered to be underlain by conceptual structures in cognitive linguistics. Image schemas belong to these structures. Schemas are shaped on the basis of bodily and socially-anchored experience, which gives them a cultural and sensor-motor status. The present study demonstrates that syntactic and lexical characteristics of image-schemas can be identified, on the basis of Lakoff and Johnson’s theories (1987), while examining language usages. This study specifically focuses on the PATH-schema, which will be investigated through two corpus-based analyses. The first sample of occurrences, made up of 500 examples, is a corpus-illustrated analysis, which exemplifies all the types of paths that have been elaborated in cognitive linguistics. The second sample of occurrences is a corpus-driven analysis, made up of 1000 examples, which are divided into four verbs’ usages, i.e. come, go, rise, and fall. We are aiming at detecting the syntactic and semantic patterns of the PATH-schema. Our goal leads us to examine the notion of « embodiment », namely the conceptualization and the evidence of the embodied link of the individual to the environment, left in lexical constructions. Our data display several verbs involved in abstract descriptions. These usages will lead us to explore the status of the PATH-schema, and focus on its syntactic and semantic specificities, particularly when this schema underlies semantic extensions of come, go, rise, and fall. Issues concerning the verbs’ polysemy, their prototypical definition, and their potential grammaticalization, will contribute to revealing the cognitive reality of the PATH-schema. Finally, the quantity of verbs’ « abstract » usages, will lead us to investigate the notion of « embodiment », as cognitive linguistics defines it.

Plus de la moitié de la population mondiale vit aujourd’hui en zone urbaine et passe plus de 90 % de son temps à l’intérieur de bâtiments. Cette thèse propose un système, nommé BiMov, de planification automatique de chemin à l’intérieur de bâtiments, basé sur leur maquette numérique (un BIM au format IFC). Le processus consiste à exploiter les caractéristiques sémantiques, géométriques et topologiques des constituants du BIM afin de générer des graphes de navigation possible, en fonction du profil du navigant et de l’état conjoncturel d’accessibilité des espaces et transitions, dans lesquels le plus court chemin d’un point à un autre puisse être déterminé. BiMov s’appuie sur quatre modèles de données (1) un modèle de bâtiment déduit du BIM, qui représente et structure les caractéristiques essentielles du bâtiment en vue de la mobilité intérieure (2) un modèle de navigant à même de représenter ses caractéristiques d’encombrement, ses aptitudes aux déplacements horizontaux et verticaux ainsi que ses habilitations (3) un modèle de calendrier permettant de connaître l’état d’accessibilité des espaces et des transitions (4) un modèle de graphe sur trois niveaux de détails. Le niveau Macro représente un simple graphe de connectivité entre les espaces intérieurs voisins ; il permet aux architectes de vérifier leur conception architecturale en termes d’accessibilité. Le niveau Externe permet de connecter les espaces accessibles via leurs transitions horizontales ou verticales. Il est destiné aux navigants qui n’exigent pas un chemin détaillé pour se déplacer. Le niveau Interne intègre un maillage des espaces, en 2D pour la navigation au sol, en 3D pour la navigation de drones. Il est conçu pour considérer les obstacles intérieurs comme les meubles, les machines ou les équipements. Ce niveau est destiné aux navigants devant fiabiliser leur déplacement à l’intérieur des espaces, comme les manutentionnaires d’objets encombrants ou les robots mobiles. L’approche proposée a fait l’objet d’un développement informatique qui permet d’illustrer quelques scénarios de planification de chemin dans des modèles BIM d’origine externe à la thèse. / More than 50% of humans today live in urban areas and spend more than 90 % of their time indoor. This thesis suggests a system, called BiMov, dedicated to automatic path planning in complex building based on their digital mockup (a BIM in IFC format). The process consists in exploiting the semantic, geometric and topologic features of the constituents of a BIM, so as to generate navigation graphs, taking into account the profile of Navigants as well as the operational state of accessibility of spaces and transitions, for finally determining a shortest path. BiMov is based on 4 data models: (1) a building model deduced from the BIM that represents and structures the building features that are relevant for indoor mobility (2) a Navigant model capable to represent its bulk size, abilities for horizontal and vertical displacements and social habilitations (3) a calendar model representing the conjectural state of accessibility of spaces and transitions (4) a navigation graph model with three levels of detail: the Macro level represents a simple graph of connectivity between neighboring interior spaces. It is intended to help architects verify their architectural design in terms of accessibility. The Extern level is used to connect accessible spaces via their horizontal or vertical transitions. This level is intended for Navigants who do not require a detailed path. The Intern level integrates a meshing of each space: a 2D mesh for planar mobility or a 3D mesh for drones. This level is intended for Navigants like bulky objects handlers of mobile robots, needing to validate a reliable path within spaces containing furniture, machinery or equipment. The proposed approach was implemented in a prototype software that allows to illustrate different path planning scenarios in BIM models that were generated externally.

De nos jours, les interactions ont une part prépondérante dans notre vie. Ces interactions peuvent représenter la diffusion de rumeurs, de maladies, etc. Comprendre comment ces interactions affectent notre vie est important. Une façon naturelle de faire est d'utiliser la théorie des graphes. Néanmoins, comme le montrent certaines études, l'aspect temporel ne doit pas être négligé. Dans ce travail, nous nous sommes concentrés sur la détection d'individus importants dans ces graphes en utilisant des métriques de centralité qui prennent en compte l'aspect temporel. Nous avons proposé un protocole de comparaison qui compare les différentes mesures de centralité existantes. Nous l'avons appliqué sur plusieurs graphes, ce qui nous a donné un aperçu de la façon dont les différentes métriques agissent. Ensuite, nous avons observé le besoin de calcul élevé de ces métriques de centralité. Dès lors, nous avons introduit une méthode qui réduit ce besoin. Finalement, nous avons introduit une nouvelle mesure de centralité, appelée ego-betweenness centrality. / Nowadays, interactions are a huge part of our daily life. These interactions can represent the diffusion of rumors, diseases, etc. Understanding how these interactions affect our life is quite important. A natural way to do so is using graph theory. However, this is not straightforward as studies show the temporal aspect, in other words, the order of interactions, should be taken into account. In this work, we concentrated on detecting the important individuals in these graphs using centrality metrics that take into account the temporal aspect. We proposed a comparison protocol that compares the different centrality metrics that exist. We applied it on several networks, which gave us insight on how the different metrics react. Secondly, we observed the high computational need of these centrality metrics. Therefore, we introduced a method to reduce this need. And finally, we introduced a novel centrality metric that we call ego-betweenness centrality.

Le but de cette thèse est de tenté de donner une meilleure compréhension des nouveaux paradigmes de l'informatique en Nuage. En ce qui concerne l'Ingénierie du Trafic, l'économie d'énergie, de l'équité dans le partage du débit.Dans la première partie de note thèse, nous étudions l'impact de ces nouvelles techniques dans les réseaux de Data Center, nous avons formulé notre problème en un modèle d'optimisation, et nous le résolvons en utilisons un algorithme glouton. Nous avons étudié l'impact des ponts virtuels et du multi chemin sur différentes architectures de Data Centers. Nous avons en particulier étudié l’impact de la virtualisation des switches et l’utilisation du multi-chemin sur les différents objectifs d'optimisation tels que l'Ingénierie du Trafic, l'économie d'énergie.Dans notre seconde partie, nous avons essayé d’avoir une meilleure compréhension de l'impact des nouvelles architectures sur le contrôle de congestion, et vice versa. En effet, l'une des préoccupations majeures du contrôle de congestion est l'équité en terme de débit, l'impact apporté par le multi-chemin, les nouvelles architectures Data Center et les nouveaux protocoles, sur le débit des points terminaux et des points d'agrégations reste vague.Enfin, dans la troisième partie nous avons fait un travail préliminaire sur le nouveau paradigme introduit par la possibilité de virtualisé les Fonctions Réseaux. Dans cette partie, nous avons formulé le problème en un modèle linéaire, dans le but est de trouver le meilleur itinéraire à travers le réseau où les demandes des clients doivent passer par un certain nombre de NFV. / This dissertation tries to give a deep understanding of the impact of the new Cloud paradigms regarding to the Traffic Engineering goal, to the Energy Efficiency goal, to the fairness in the endpoints offered throughput, and of the new opportunities given by virtualized network functions.In the first part of our dissertation we investigate the impact of these novel features in Data Center Network optimization, providing a formal comprehensive mathematical formulation on virtual machine placement and a metaheuristic for its resolution. We show in particular how virtual bridging and multipath forwarding impact common DCN optimization goals, Traffic Engineering and Energy Efficiency, assess their utility in the various cases in four different DCN topologies.In the second part of the dissertation our interest move into better understand the impact of novel attened and modular DCN architectures on congestion control protocols, and vice-versa. In fact, one of the major concerns in congestion control being the fairness in the offered throughput, the impact of the additional path diversity, brought by the novel DCN architectures and protocols, on the throughput of individual endpoints and aggregation points is unclear.Finally, in the third part we did a preliminary work on the new Network Function Virtualization paradigm. In this part we provide a linear programming formulation of the problem based on virtual network function chain routing problem in a carrier network. The goal of our formulation is to find the best route in a carrier network where customer demands have to pass through a number of NFV node, taking into consideration the unique constraints set by NFV.

Les réseaux Telecom sont désormais en charge du transport d’une large variété de trafic de types donnés, voix, vidéo et autres protocoles industriels réclamant des garantie de qualité de service strictes. L’ingénierie de trafic permet non seulement d’optimiser les ressources réseaux mais aussi de parvenir à garantir ces qualités de service exprimées en termes de délais dans le réseau, de gigue mais aussi de taux de disponibilité en présence de pannes de liens ou de nœuds. La technologie MPLS TE, basée sur la commutation de labels le long de chemins contraints a permis d’atteindre ces objectifs et fut déployée dans de nombreux réseaux. L’objectif de cette thèse est de proposer un nouveau modèle architectural nommé PCE, ainsi que des protocoles et algorithmes novateurs afin de résoudre plusieurs problèmes d’envergure liés à l’ingénierie de trafic et disponibilité du réseau. L’architecture PCE est tout d’abord décrite ainsi que le protocole de signalisation PCEP utilisé entre clients et serveurs, puis les protocoles de découvertes de PCE et algorithmes de partage de charge. Ensuite un nouvel algorithme récursif est spécifié permettant grâce à un calcul collaboratif et récursif distribué impliquant une suite de PCEs de calculer le chemin optimal pour des tunnels inter-domaines. Un nouveau paradigme pour le calcul des chemin de secours est spécifié qui permet à chaque nœud d’agir en tant que PCE pour le calcul des tunnels de secours de chacun de ses voisins dans l’hypothèse que sa propre panne, permettant une utilisation partagée des ressources réseau dédiées au secours pour des tunnels protégeant des ressources indépendantes... / Modern data networks carry a wide variety of traffic such as voice, video, data and other industrial protocols that require guaranteed quality of service. Traffic Engineering (TE) allows for network resource optimization while meeting service level agreement for these sensitive traffics in terms of delays, jitter but also network reliability in case of network element failure. To that end a technology making use of constrained paths using label switching (called MPLS TE) has been developed and widely used in a number of networks. The objective of this thesis is to propose a new architecture model referred to as the Path Computation Element (PCE) along with a number of protocols and algorithms in order to tackle a number of technical challenges. First the PCE architecture is described in terms of functional blocks with its protocols: the signalization protocol called PCEP used between client and servers in charge of computing label switched path in the network, the process of PCE discovery and load balancing. Then a new backward recursive algorithm is specified allowing for the computation of optimal inter-domain tunnels, which involves a series of stateless PCEs. We then introduce a paradigm shift consisting distributing the computation of backup tunnels in the network used by the well-known technology called Fast Reroute. Thanks to this new paradigm, each node independently acts as a PCE computing the back tunnels of all of its neighbors, thus maximizing the degree of sharing of the backup capacity among tunnels that protect independent resources. We conclude this thesis by showing how the PCE architecture can be applied (with adaptations specified in the last two chapt...

Les graphes de données sont naturellement utilisés dans de nombreux contextes incluant par exemple les réseaux sociaux ou le Web sémantique. L'information contenue dans la base de données se trouve alors aussi bien dans les données mêmes que dans la topologie du graphe, c'est-à-dire dans la manière dont les données sont connectées. Cela implique donc de considérer les questions traditionnelles en théorie des bases de données pour des langages de requêtes capables de parler des chemins connectant les nœuds du graphe. Nous nous intéressons en particulier aux problèmes de la déterminabilité et de la réécriture d'une requête à l'aide de vues. Il s'agit alors de décider si une vue de la base de données contient suffisamment d'information pour répondre entièrement à une requête sans consulter la base de données directement, et dans ce cas, d'exprimer explicitement la réponse à la requête à partir de la vue. Ce cadre rencontre de nombreuses applications, notamment pour l'intégration de données et l'optimisation de requêtes. Nous commençons par comparer ces deux questions aux autres problèmes de décision classiques dans ce contexte : calcul des réponses certaines, test de cohérence et mise à jour d'une instance de vue. Nous améliorons ensuite ces résultats dans deux cas spécifiques. Tout d'abord, nous montrons que pour les requêtes régulières de chemin, l'existence d'une réécriture monotone coïncide avec l'existence d'une réécriture dans Datalog. Puis, nous montrons que pour des vues s'intéressant uniquement aux longueurs des chemins du graphe, une notion plus faible de déterminabilité, appelée déterminabilité asymptotique, est décidable et résulte en des réécritures du premier ordre. / Graph databases appear naturally in various scenarios, such as social networks and the semantic Web. In these cases, the information contained in the database lies as much in the data itself as in the topology of the graph, that is, in how the data points are linked together. This leads to considering traditional database theory questions for query languages that return data nodes based on the paths of the graph connecting them. We focus our attention on the view-based query determinacy and rewriting problems. They ask the question whether a view of the database contains enough information to fully answer a query without accessing the database directly. If so, we then want to express the answer to the query directly with regards to the view. This setting occurs in many applications, such as data integration and query optimization. We start by comparing these two tasks to other common task in this setting: computing certain answers, checking consistency of a view instance and updating it. We then build on these results in two specific cases. First, we show that for regular path queries, the existence of a monotone rewriting coincides with the existence of a rewriting expressible in Datalog. Then, we show that for views that only consider the lengths of the path in the graph, we can decide a weaker form of determinacy, called asymptotic determinacy, and produce first-order rewritings for the queries that are asymptotically determined.

No description available.

Cette thèse propose une extension des méthodes classiques de chemins de «scan». On utilise des opérateurs combinatoires plus généraux à la place des multiplexeurs à une seule sortie. Ils peuvent comporter des entrées et des sorties multiples. Ils peuvent boucler sur eux-mêmes par l'intermédiaire d'une ou plusieurs bascules. Lorsqu'ils vérifient certaines propriétés de bijectivité et qu'ils forment une structure propageant de l'information, alors cette structure est aussi utile que les chaînes du «scan» complet et s'utilise de manière semblable. Elle permet aussi une approche hiérarchique du test des circuits. On montre comment tirer profit de cette méthode plus générale pour réduire l'impact de la méthode de «scan» complet sur les performances de circuits complexes implantant des fonctions mathématiques courantes ou des séquenceurs. Des résultats sont donnés pour le cas réel d'un circuit CMOS, très rapide, spécifique pour le réseau numérique large bande et pour lequel les contraintes en vitesse étaient primordiales