Dissertations / Theses on the topic 'Chemins temporels'

Les données structurelles et les données temporelles ont, pendant longtemps, été analysées séparément. De nombreux réseaux complexes contiennent une dimension temporelle, comme les contacts entre individus ou les transactions financières. La théorie des graphes fournit un large ensemble d'outils pour modéliser et analyser les connexions entre entités. Malheureusement, cette approche ne prend pas compte la nature temporelle des interactions. La théorie des stream graphs est un formalisme permettant de modéliser les réseaux dynamiques dans lesquels les nœuds et/ou les liens arrivent et/ou partent au fil du temps. Plusieurs concepts théoriques tels que les composantes connexes dans les stream graphs ont été définis récemment, mais aucun algorithme n'a été proposé pour les calculer. De plus, la complexité algorithmique de ces problèmes est inconnue, ainsi que les connaissances qu'ils peuvent apporter sur les stream graphs de terrain. Dans cette thèse, nous proposons plusieurs solutions pour le calcul de notions de connectivité et de chemins dans les stream graphs. Nous présentons également des représentations alternatives - des structures de données conçues pour faciliter certains calculs - stream graphs. Nous fournissons également des implémentations et comparons expérimentalement nos méthodes sur une grande variété de cas pratiques. Nous montrons que ces concepts apportent beaucoup d'informations sur les caractéristiques de ces ensembles de données. Straph, une bibliothèque python, a été développée afin de disposer d'une ressource fiable afin de manipuler, analyser et visualiser les stream graphs
For a long time, structured data and temporal data have been analysed separately. Many real world complex networks have a temporal dimension, such as contacts between individuals or financial transactions. Graph theory provides a wide set of tools to model and analyze static connections between entities. Unfortunately, this approach does not take into account the temporal nature of interactions. Stream graph theory is a formalism to model highly dynamic networks in which nodes and/or links arrive and/or leave over time. The number of applications of stream graph theory has risen rapidly, along with the number of theoretical concepts and algorithms to compute them. Several theoretical concepts such as connected components and temporal paths in stream graphs were defined recently, but no algorithm was provided to compute them. Moreover, the algorithmic complexities of these problems are unknown, as well as the insight they may shed on real-world stream graphs of interest. In this thesis, we present several solutions to compute notions of connectivity and path concepts in stream graphs. We also present alternative representations - data structures designed to facilitate specific computations - of stream graphs. We provide implementations and experimentally compare our methods in a wide range of practical cases. We show that these concepts indeed give much insight on features of large-scale datasets. Straph, a python library, was developed in order to have a reliable library for manipulating, analysing and visualising stream graphs, to design algorithms and models, and to rapidly evaluate them

À l'échelle macroscopique, les ondes et les particules sont des objets distincts. La découverte d'objets appelés marcheurs, constitués d'une goutte rebondissant sur un bain liquide vibré verticalement, a montré qu'il n'en était rien. La goutte est autopropulsée, guidée sur la surface du liquide par l'onde qu'elle a elle-même créée lors des rebonds précédents. Ces objets possèdent une dynamique originale dominée par le concept de mémoire de chemin. La structure du champ d'onde qui guide la goutte dépend, en effet, de la position des rebonds passés disposés le long de la trajectoire. La profondeur de cette mémoire peut, de plus, être contrôlée expérimentalement en changeant l'accélération du bain. De nombreuses réalisations expérimentales ont mis en évidence les comportements dynamiques singuliers de ces systèmes couplés goutte/onde. Cette thèse répond à la nécessité d'une compréhension théorique des effets non locaux en temps introduit par la mémoire de chemin. Pour ce faire, nous étudierons l'évolution d'un marcheur numérique en potentiel harmonique bidimensionnel. Un ensemble relativement restreint de trajectoires stables est obtenu. Nous constaterons que ces dernières sont quantifiées en extension moyenne et en moment angulaire moyen. Nous analyserons comment s'imbriquent les différentes échelles de temps de la dynamique, permettant ainsi de dissocier les termes propulsifs à temps court de l'émergence de structures ondulatoires cohérentes à temps long. Nous verrons en quoi l'expression du caractère non-local d'un marcheur permet d'en révéler les symétries internes et d'assurer la convergence du système dynamique vers un jeu d'états propres de basse dimension
Waves and particles are distinct objects at a macroscopic scale. The existence of walkers, drops bouncing on a vertically vibrated fluid bath is a surprising case of dual objects at our scale. The drop is self-propelled, piloted by the standing surface waves generated by its previous rebounds. These objects exhibit a rich dynamics relying on the concept of path memory. Indeed, the wave field results from the position of the past impacts left all along the walker trajectory. The memory is tunable at will by simply changing the vertical acceleration of the bath. A series of experiments have revealed the surprising dynamical behaviors of this dual drop-wave entity. In this PhD, we give a theoretical understanding of the temporal non local structure of walkers. We explore the dynamics of numerical walkers in a two-dimensional harmonic potential. We observe that the system only reaches a relatively limited set of stable attractors, quantized in both extension and mean angular momentum, in excellent agreement with the experimental results. We investigate how the different time scales are intertwined, which decouples the short-time acting propulsion from the build-up of coherent wave structures at much longer time scales. We analyze the non-local mechanism revealing the internal symmetries of the walker which drives the convergence of the dynamics to a set of low-dimensional eigenstates

Le but de ce travail est de fournir un modèle expressif de représentation des informations temporelles qualitatives et quantitatives indépendant de tout domaine d'application ainsi qu'un système de raisonnement capable de manipuler les informations représentées par ce modèle et fournir des résultats directement exploitables dans des délais de temps acceptables. Afin de répondre à ces besoins, nous avons défini un modèle qui généralise l'algèbre de Allen afin d'intégrer des informations métriques. L'objet temporel que nous manipulons est l'événement correspondant au couple (symbole [Phy], I) ou symbole [Phy] est une assertion logique atemporelle et I l'intervalle de temps durant lequel symbole [Phy] est vraie. Les informations symboliques sont traduites sous forme de disjonctions de relations de base définies par Allen permettant de situer deux événements temporels entre eux. Les informations numériques sont exprimées sous forme de domaines de variation attachés à chaque événement et permettant de situer ce dernier dans ou par rapport a un référentiel temporel. Le système de raisonnement que nous proposons, et permettant de résoudre des problèmes de contraintes temporelles symboliques et numériques représentés par notre modèle, est basé sur un algorithme de recherche de solutions avec retour arrière utilisant des algorithmes de consistance locale permettant de réduire la taille du problème à résoudre. Nous utilisons les algorithmes de consistance d'arcs sur les contraintes numériques et les algorithmes de consistance de chemins sur les contraintes symboliques. Afin d'améliorer les performances des algorithmes de consistance locale utilisés par notre algorithme général, nous avons introduit des heuristiques que nous avons définies en étudiant les propriétés des contraintes temporelles

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

Cette thèse a été conduite dans le cadre d’une convention industrielle avec SNCF Réseau. Elle se situe dans le domaine de la géovisualisation d’informations spatio-temporelles, et porte plus particulièrement sur l’élaboration de méthodes de visualisation cartographiques adaptées à l’analyse des impacts des inondations sur le système ferroviaire. Les événements historiques sont une source d’informations importante pour la compréhension et la gestion des risques naturels. La cartographie s’est imposée comme un outil clé pour appréhender les risques dans leurs contextes territoriaux. Mais l’élaboration de visualisations cartographiques qui soient lisibles tout en restituant la complexité des processus survenus lors d’une catastrophe naturelle n’est pas aisée. Les verrous principaux sont la nécessité de représenter à la fois les dimensions spatiales et temporelles des événements issus de risques, le besoin de visualiser les effets dominos, qui conduisent à amplifier les dommages, et la volonté d’adapter les représentations aux besoins et aux capacités cognitives des utilisateurs. Ce travail a conduit à quatre contributions. La première contribution a consisté à formaliser les récits d’inondations dans une ontologie de domaine, qui décrit à la fois les événements issus d’inondations, les effets dominos et leurs impacts sur le système ferroviaire et les mesures de réaction pour ramener le système ferroviaire à l’état d’équilibre. Cinq cas d’inondations historiques ont été instanciés dans le modèle. Leur étude a permis de formuler des principes sémiologiques génériques pour cartographier les récits d’inondations, ce qui constitue la deuxième contribution. La troisième contribution est la production d’une interface de géovisualisation intégrant des représentations graphiques innovantes pour visualiser les temporalités associées aux événements. Cette interface de géovisualisation a fait l’objet d’une expérimentation auprès des experts ferroviaires. Les résultats ont validé les propositions relatives à la représentation du temps mais ont infirmé les propositions de visualisation des effets dominos. Suite à l’analyse des résultats, la quatrième contribution consiste en un modèle de protocole expérimental réutilisable, adapté au test d’interfaces de géovisualisation
This research was led in an industrial partnership with SNCF Réseau. In the field of geovisualization of spatio-temporal information, it focuses on developing cartographical visualization methods adapted to the analysis of the impacts of floods on the railway system.Historical events are of great help to understand and manage natural risks. Cartography became a key tool to analyze risks in their territorial contexts. But making maps which remain legible while showing all the complexity of risk processes that occurred during natural disaster is not easy. The main challenges are the need to represent both the temporal and the spatial dimensions of risk events, the need to visualize domino-effect, because they often lead to worsen damages, and the will to adapt representations to the cognitive capacities of users.This research resulted in four contributions. The first one is the formalization of flood narratives in a domain ontology, which describes flood events, domino-effects, their impacts on the railway system and also response measures to restore the system. Five case studies of historical floods were instantiated in the model. Resulting from their study, the second contribution consists in generic semiology principles to visualize the narratives of floods on maps. The third contribution is a geovisualization interface, which includes original graphical representations to visualize the temporal features associated with flood events. This geovisualization interface was tested in an experiment with expert users of the railway field. Results confirmed the proposals of representation of time but disconfirm proposals of visualization of domino effects. The analysis of results led to the fourth contribution, which consists in a reusable model of an experimental procedure that is adapted to test geovisualization interfaces

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

Les modèles de simulation de foules visent généralement à produire des foules visuellement crédibles avec l'intention d'insuffler de la vie à des environnements virtuels. Notre travail se concentre sur la génération de comportements statistiquement cohérents qui peuvent être utilisés pour piloter des modèles de simulation de foules sur de longues périodes de temps, jusqu'à plusieurs jours. Dans les foules réelles, les comportements des individus dépendent principalement de l'activité qu'ils ont l'intention d'effectuer. La façon d’ordonnancer cette activité repose sur l'interaction étroite qui existe entre l'environnement, les contraintes spatiales et temporelles associées à l'activité et les caractéristiques personnelles des individus. Par rapport à l'état de l'art, notre modèle gérer mieux cette interaction. Nos principales contributions se situent dans le domaine de l'ordonnancement d'activités et de la planification de chemin. Dans un premier temps, nous proposons un processus d'ordonnancement d'activités individuelles et son extension aux activités coopératives. Basé sur les descriptions de l'environnement, des activités désirées et des caractéristiques des agents, ces processus génèrent une séquence de la tâche pour chaque agent. Des lieux où ces tâches doivent être effectuées sont sélectionnés et un timing relâché est produit. Cet ordonnancement est compatible avec les contraintes spatiales et temporelles liées à l'environnement et à l'activité prévue par l'agent et par d'autres agents en coopération. Il prend également en compte les caractéristiques personnelles des agents, induisant de la diversité dans les ordonnancements produits. Nous montrons que notre modèle produit des comportements statistiquement cohérents avec ceux produits par des personnes dans les mêmes situations. Dans un second temps, nous proposons un processus de planification de chemins hiérarchique. Il repose sur un processus d'analyse de l'environnement automatique qui produit une représentation hiérarchique sémantiquement cohérente des villes virtuelles. La nature hiérarchique de cette représentation est utilisée pour modéliser différents niveaux de prise de décisions. Un chemin grossier est d'abord calculé, puis raffiné pendant la navigation lorsque de l'information pertinente est disponible, permettant ainsi à l'agent d'adapter son chemin à des événements inattendus. Le modèle proposé gère des décisions rationnelles à long terme guidant la navigation des agents dans les villes virtuelles. Il prend en compte la forte relation entre le temps, l'espace et l'activité pour produire les comportements des agents plus crédibles de. Il peut être utilisé pour peupler facilement des villes virtuelles avec des foules au sein desquelles des phénomènes observables émergent de l'activité individuelle
Crowd simulation models usually aim at producing visually credible crowds with the intent of giving life to virtual environments. Our work focusses on generating statistically consistent behaviours that can be used to pilot crowd simulation models over long periods of time, up to multiple days. In real crowds, people's behaviours mainly depend on the activities they intend to perform. The way this activity is scheduled rely on the close interaction between the environment, space and time constraints associated with the activity and personal characteristics of individuals. Compared to the state of the art, our model better handle this interaction. Our main contributions lie in the domain of activity scheduling and path planning. First, we propose an individual activity scheduling process and its extension to cooperative activity scheduling. Based on descriptions of the environment, of intended activities and of agents' characteristics, these processes generate a task schedule for each agent. Locations where the tasks should be performed are selected and a relaxed agenda is produced. This task schedule is compatible with spatial and temporal constraints associated with the environment and with the intended activity of the agent and of other cooperating agents. It also takes into account the agents personal characteristics, inducing diversity in produced schedules. We show that our model produces schedules statistically coherent with the ones produced by humans in the same situations. Second, we propose a hierarchical path-planning process. It relies on an automatic environment analysis process that produces a semantically coherent hierarchical representation of virtual cities. The hierarchical nature of this representation is used to model different levels of decision making related to path planning. A coarse path is first computed, then refined during navigation when relevant information is available. It enable the agent to seamlessly adapt its path to unexpected events. The proposed model handles long term rational decisions driving the navigation of agents in virtual cities. It considers the strong relationship between time, space and activity to produce more credible agents' behaviours. It can be used to easily populate virtual cities in which observable crowd phenomena emerge from individual activities

Avec les tendances « More Moore » et basse consommation, il devient de plus en plus délicat d'optimiser ou seulement prédire les performances finales des circuits numériques. En effet, les phénomènes de variabilité et les difficultés de modélisation des comportements des transistors constituent un frein tandis que nous approchons des dimensions nanométriques. Les méthodes de conception actuelles utilisent généralement des marges de garde afin de prévenir les incertitudes et garantir la fonctionnalité du circuit. Mais ces marges reflètent de moins en moins la réalité du circuit, empêchant dès lors les optimisations et baissant le rendement des circuits. De nombreuses solutions très hétéroclites existent afin de surmonter ces difficultés, se résumant en deux objectifs distincts et complémentaires : l'augmentation de la robustesse aux incertitudes durant la phase de conception, notamment grâce à de meilleures analyses des performances ; et l'adaptation post-silicium du circuit à son état technologique et à son environnement. Dans ce travail de thèse, nous avons approché ces deux concepts : en implantant (1) une méthodologie d'analyse statistique SSTA (Statistical Static Timing Analysis) nous permettant d'examiner finement les effets des variations dans le respect des contraintes temporelles ; et en proposant (2) un système de diagnostic basé sur l'observabilité de chemins critiques, autorisant ainsi la mise en œuvre de techniques adaptatives. Celles-ci permettent de s'ajuster au plus près des caractéristiques réelles du circuit en rognant sur les marges de conception, et d'améliorer les performances en fréquence et consommation, de même que le rendement
With the « More Moore » and low power trends, optimizing or only well predicting the final performances of digital circuits become more and more difficult. Indeed, variability and hardness to accurately model transistor behavior impede the dimension scaling benefits. Current design methods generally use guard margins to prevent from the incertitude generated by these limits and to guarantee functional yield. But as we go in the nanometer era, the margin use is not efficient anymore, because of an increasing over-design, limiting optimizations and decreasing yield. Very different numerous solutions exist in order to overcome these troubles, following two main goals which are dissimilar but also complementary: increasing the robustness to uncertainty during the design levels, notably thanks to better performance analysis; and adapting the final circuit to its real process corner and to its environment. In this work, we considered these two directions: the first one thanks to (1) an implementation of a specific methodology called SSTA (Statistical Static Timing Analysis), allowing to perform statistical analysis on timing performances; this methodology allows us to accurately observe process variation effects on delays; and the second one in proposing (2) an efficient diagnostic system based on the in situ critical path monitoring concept and allowing all adaptive solution implementations. The latter answer to variability issue allows to know the real characteristics of the circuit, to crop design margins, to improve power consumption and frequency performances, and even to increase yield

Les travaux développés dans cette thèse visent à assister le processus d’ingénierie des exigences temporelles pour les systèmes complexes à contraintes de temps. Nos contributions portent sur trois volets : la spécification des exigences, la modélisation du comportement et la vérification. Pour le volet spécification, une nouvelle classification des exigences temporelles les plus communément utilisées a été proposée. Ensuite, afin de cadrer l’utilisateur durant l’expression des exigences, une grammaire de spécification à base de motifs prédéfinis en langage naturel est développée. Les exigences générées sont syntaxiquement précises et correctes quand elles sont prises individuellement, néanmoins cela ne garantie pas la cohérence de l’ensemble des exigences exprimées. Ainsi, nous avons développé des mécanismes capables de détecter certains types d’incohérences entre les exigences temporelles. Pour le volet modélisation du comportement, nous avons proposé un algorithme de transformation des state-machine avec des annotations temporelles en des automates temporisés. L’idée étant de manipuler une notation assez intuitive et de générer automatiquement des modèles formels qui se prêtent à la vérification. Finalement, pour le volet vérification, nous avons adopté une technique de vérification à base d’observateurs et qui repose sur le model-checking. Concrètement, nous avons élaboré une base de patterns d’observation (ou observateurs) ; chacun des patterns développés est relatif à un type d’exigence temporelle dans la nouvelle classification. Ainsi, la vérification est réduite à une analyse d’accessibilité des états correspondants à la violation de l’exigence associée
The work developed in this thesis aims to assist the engineering process of temporal requirements for time-constrained complex systems. Our contributions concern three phases: the specification, the behaviour modelling and the verification. For the specification of temporal requirements, a new temporal properties typology taking into account all the common requirements one may meet when dealing with requirements specification, is introduced. Then, to facilitate the expression, we have proposed a structured English grammar. Nevertheless, even if each requirement taken individually is correct, we have no guarantee that a set of temporal properties one may express is consistent. Here we have proposed an algorithm based on graph theory techniques to check the consistency of temporal requirements sets. For the behaviour modelling, we have proposed an algorithm for transforming UML State Machine with time annotations into Timed Automata (TA). The idea is to allow the user manipulating a quite intuitive notation (UML SM diagramsduring the modelling phase and thereby, automatically generate formal models (TA) that could be used directly by the verification process. Finally, for the verification phase, we have adopted an observer-based technique. Actually, we have developed a repository of observation patterns where each pattern is relative to a particular temporal requirement class in our classification. Thereby, the verification process is reduced to a reachability analysis of the observers’ KO states relatives to the requirements’ violation

This dissertation is concerned with the problem of estimating travel time per links in urban context using sparsely sampled GPS data. One of the challenges in this thesis is use the sparsely sampled data. A part of this research work, i developed a digital map with its new geographic information system (GIS), dealing with map-matching problem, where we come out with an enhancement tecnique, and also the shortest path problem.The thesis research work was conduct within the project PUMAS, which is an avantage for our research regarding the collection process of our data from the real world field and also in making our tests. The project PUMAS (Plate-forme Urbaine de Mobilité Avancée et Soutenable / Urban Platform for Sustainable and Advanced Mobility) is a preindustrial project that has the objective to inform about the traffic situation and also to develop an implement a platform for sustainable mobility in order to evaluate it in the region, specifically Rouen, France. The result is a framework for any traffic controller or manager and also estimation researcher to access vast stores of data about the traffic estimation, forecasting and status.

La sécurité des personnes et des équipements est un élément capital dans le domaine des transports routiers et ferroviaires. Depuis quelques années, les Passages à Niveau (PN) ont fait l’objet de davantage d'attention afin d'accroître la sécurité des usagers sur cette portion route/rail considérée comme dangereuse. Nous proposons dans cette thèse un système de vision stéréoscopique pour la détection automatique des situations dangereuses. Un tel système permet la détection et la localisation d'obstacles sur ou autour du PN. Le système de vision proposé est composé de deux caméras supervisant la zone de croisement. Nous avons développé des algorithmes permettant à la fois la détection d'objets, tels que des piétons ou des véhicules, et la localisation 3D de ces derniers. L'algorithme de détection d'obstacles se base sur l'Analyse en Composantes Indépendantes et la propagation de croyance spatio-temporelle. L'algorithme de localisation tridimensionnelle exploite les avantages des méthodes locales et globales, et est composé de trois étapes : la première consiste à estimer une carte de disparité à partir d'une fonction de vraisemblance basée sur les méthodes locales. La deuxième étape permet d'identifier les pixels bien mis en correspondance ayant des mesures de confiances élevées. Ce sous-ensemble de pixels est le point de départ de la troisième étape qui consiste à ré-estimer les disparités du reste des pixels par propagation de croyance sélective. Le mouvement est introduit comme une contrainte dans l'algorithme de localisation 3D permettant l'amélioration de la précision de localisation et l'accélération du temps de traitement
Within the past years, railways undertakings became interested in the assessment of Level Crossings (LC) safety. We propose in this thesis an Automatic Video-Surveillance system (AVS) at LC for an automatic detection of specific events. The system allows automatically detecting and 3D localizing the presence of one or more obstacles which are motionless at the level crossing. Our research aims at developing an AVS using the passive stereo vision principles. The proposed imaging system uses two cameras to detect and localize any kind of object lying on a railway level crossing. The cameras are placed so that the dangerous zones are well (fully) monitored. The system supervises and estimates automatically the critical situations by detecting objects in the hazardous zone defined as the crossing zone of a railway line by a road or path. The AVS system is used to monitor dynamic scenes where interactions take place among objects of interest (people or vehicles). After a classical image grabbing and digitizing step, the processing is composed of the two following modules: moving and stationary objects detection and 3-D localization. The developed stereo matching algorithm stems from an inference principle based on belief propagation and energy minimization. It takes into account the advantages of local methods for reducing the complexity of the inference step achieved by the belief propagation technique which leads to an improvement in the quality of results. The motion detection module is considered as a constraint which allows improving and speeding up the 3D localization algorithm

Les grandes entreprises ferroviaires intègrent au niveau du matériel roulant une grande variété de systèmes complexes qui se doivent d'être fiables et ce, dès le démarrage du service commercial. Ce travail de thèse propose une méthodologie expérimentale pour l'amélioration de la robustesse d'un système prédominant, à savoir l'accès voyageurs. L'objectif est d'améliorer sa fiabilité intrinsèque dans un laps de temps raisonnable dans le cadre de projet industriel contraint par le temps. La méthodologie expérimentale proposée s'appuie sur la méthode des essais aggravés et accélérés de fiabilité, et se veut être optimisée grâce à l'utilisation de plans d'expériences D-optimaux. Après une analyse bibliographique, suivie d'une étude sur l'utilisation des plans d'expériences D-optimaux, ce travail expose les méthodes et moyens expérimentaux mis en place pour utiliser les plans d'expériences dans un contexte industriel. La dernière partie de cette thèse contient les résultats quantitatifs et qualitatifs issus des expérimentations réaliséessur le banc d'essais du système accès voyageurs développé par Bombardier.

Les travaux présentés dans ce document traitent de méthodes arborescentes pour la résolution de problèmes combinatoires d'optimisation ou de décision. Le premier chapitre présente les contributions que nous avons apportées pour les méthodes de résolution dites " à divergences ". Ces contributions concernent les modes de comptage des divergences pour les problèmes à variables discrètes, le développement d'une heuristique dynamique à pondération de variables, ainsi que, dans un contexte d'optimisation, l'utilisation de bornes ou d'heuristiques pour la sélection des points de divergences. Ces différentes contributions sont illustrées sur des problèmes d'ordonnancement ou sur des problèmes de satisfaction de contraintes. Le deuxième chapitre traite de propagation de contraintes pour la résolution de problèmes d'ordonnancement disjonctifs en présence de contraintes temporelles généralisées. Des extensions de méthodes de propagation de contraintes efficaces dans ce contexte sont proposées et des applications à la résolution de différents problèmes d'ordonnancement sont également présentées. Le troisième chapitre s'intéresse à un problème de calcul d'itinéraires point à point sur des réseaux de transport multi-modaux. La prise en compte de la multi-modalité fait surgir à la fois de nouvelles contraintes permettant d'exprimer si la séquence de modes d'un itinéraire conduit ou non à une solution admissible, mais aussi de nouveaux objectifs comme la minimisation du nombre de changement de modes. Le problème étudié (minimisation du temps de trajet et du nombre de transferts) est polynomial et différentes variantes basées sur le principe de l'algorithme de Dijkstra sont présentées et évaluées sur un cas réel.

Les analyses statiques de pire temps d’exécution sont utilisées pour garantir les délais requis pour les systèmes critiques. Afin d’estimer des bornes précises sur ces temps d’exécution, ces analyses temporelles nécessitent des considérations sur la (micro)- architecture. Habituellement, ces modèles de micro-architecture sont construits à la main à partir des manuels des processeurs. Cependant, les initiatives du matériel libre et les langages de description de matériel de haut niveau (HCLs), permettent de réaborder la problématique de la génération automatique de ces modèles de micro-architecture, et plus spécifiquement des modèles de pipeline. Nous proposons un workflow qui vise à construire automatiquement des modèles de chemin de données de pipeline à partir de conceptions de processeurs décrites dans des langages de contruction de matériel (HCLs). Notre workflow est basé sur la chaine de compilation matériel Chisel/FIRRTL. Nous construisons au niveau de la représentation intermédiaire les modèles de pipeline du chemin de données. Notre travail vise à appliquer ces modèles pour prouver des propriétés liées à la prédictibilité temporelle. Notre méthode repose sur la vérification formelle. Les modèles générés sont ensuite traduits en modèles formels et intégrés dans une procédure existante basée sur la vérification de modèles pour détecter les anomalies de temps. Nous utilisons le langage de modélisation et de vérification TLA+ et expérimentons notre analyse avec plusieurs processeurs RISC-V open-source. Enfin, nous faisons progresser les études en évaluant l’impact de la génération automatique à l’aide d’une série de critères synthétiques
Static worst-case timing analyses are used to ensure the timing deadlines required for safety-critical systems. In order to derive accurate bounds, these timing analyses require precise (micro-)architecture considerations. Usually, such micro-architecture models are constructed by hand from processor manuals.However, with the open-source hardware initiatives and high-level Hardware Description Languages (HCLs), the automatic generation of these micro-architecture models and, more specifically, the pipeline models are promoted. We propose a workflow that aims to automatically construct pipeline datapath models from processor designs described in HCLs. Our workflow is based on the Chisel/FIRRTL Hardware Compiler Framework. We build at the intermediate representation level the datapath pipeline models. Our work intends to prove the timing properties, such as the timing predictability-related properties. We rely on the formal verification as our method. The generated models are then translated into formal models and integrated into an existing model checking-based procedure for detecting timing anomalies. We use TLA+ modeling and verification language and experiment with our analysis with several open-source RISC-V processors. Finally, we advance the studies by evaluating the impact of automatic generation through a series of synthetic benchmarks