Les crises actuelles de l’économie, mais aussi de la démocratie représentative, impactent fortement les processus de conception de la ville contemporaine, les faisant passer d’un modèle de planification traditionnelle (rationnel et hiérarchique) à un modèle consensuel fondé sur la négociation, la communication et l’interaction entre les différents acteurs du territoire. Le mode projet, en tant que mode de conception privilégié des espaces urbains, récupère à notre sens une bonne partie des limitations et des paradoxes d’une planification urbaine confrontée à un contexte de plus en plus complexe. L’étude de plusieurs interventions urbaines en France et en Espagne, conçues avec différents degrés d’incertitude, nous fournira des conditions qui permettront de discuter d’un renouvellement des pratiques de conception des espaces urbains, en même temps que nous nous interrogerons sur la pertinence de continuer à penser la ville « en mode projet ».Notre objectif de recherche concerne donc la définition d’un mode de conception alternatif et transitionnel, incorporant de l’incertitude. Celui-ci s’appuie sur la co-construction d’un projet-processus collectif, soutenu par l’expérimentation, la schématisation et la démocratisation des pratiques de conception, que nous appelons « Projet Urbain Stochastique ». / The current crises of the economy, but also of representative democracy, influence strongly the contemporary design processes of city, moving them from a traditional planning model (rational and hierarchical) to a consensual model based on negotiation, communication and interaction between several stakeholders in the territory.The “project mode”, as a preferred way of designing urban spaces, recovers a good part of limitations and paradoxes of urban planning confronted with an increasingly complex context.The study of several urban interventions in France and Spain, conceived with different degrees of uncertainty, will provide us with conditions that will allow us to discuss a renewal of the design practices of urban spaces, at the same time that we will question the relevance to continue thinking about city in “project mode”.Our research goal therefore concerns the definition of an alternative and transitional design mode, incorporating uncertainty. This latter is based on the co-construction of a collective project-process, supported by the experimentation, schematization and democratization of design practices, which we call "Stochastic Urban Project".

Markov decision processes (MDPs) are finite-state probabilistic systems with both strategic and random choices, hence well-established to model the interactions between a controller and its randomly responding environment. An MDP can be mathematically viewed as a one and half player stochastic game played in rounds when the controller chooses an action, and the environment chooses a successor according to a fixed probability distribution.<p><p>There are two incomparable views on the behavior of an MDP, when the strategic choices are fixed. In the traditional view, an MDP is a generator of sequence of states, called the state-outcome; the winning condition of the player is thus expressed as a set of desired sequences of states that are visited during the game, e.g. Borel condition such as reachability. The computational complexity of related decision problems and memory requirement of winning strategies for the state-outcome conditions are well-studied.<p><p>Recently, MDPs have been viewed as generators of sequences of probability distributions over states, called the distribution-outcome. We introduce synchronizing conditions defined on distribution-outcomes, which intuitively requires that the probability mass accumulates in some (group of) state(s), possibly in limit. A probability distribution is p-synchronizing if the probability mass is at least p in some state, and a sequence of probability distributions is always, eventually, weakly, or strongly p-synchronizing if respectively all, some, infinitely many, or all but finitely many distributions in the sequence are p-synchronizing.<p><p>For each synchronizing mode, an MDP can be (i) sure winning if there is a strategy that produces a 1-synchronizing sequence; (ii) almost-sure winning if there is a strategy that produces a sequence that is, for all epsilon > 0, a (1-epsilon)-synchronizing sequence; (iii) limit-sure winning if for all epsilon > 0, there is a strategy that produces a (1-epsilon)-synchronizing sequence.<p><p>We consider the problem of deciding whether an MDP is winning, for each synchronizing and winning mode: we establish matching upper and lower complexity bounds of the problems, as well as the memory requirement for optimal winning strategies.<p><p>As a further contribution, we study synchronization in probabilistic automata (PAs), that are kind of MDPs where controllers are restricted to use only word-strategies; i.e. no ability to observe the history of the system execution, but the number of choices made so far. The synchronizing languages of a PA is then the set of all synchronizing word-strategies: we establish the computational complexity of the emptiness and universality problems for all synchronizing languages in all winning modes.<p><p>We carry over results for synchronizing problems from MDPs and PAs to two-player turn-based games and non-deterministic finite state automata. Along with the main results, we establish new complexity results for alternating finite automata over a one-letter alphabet. In addition, we study different variants of synchronization for timed and weighted automata, as two instances of infinite-state systems. / Doctorat en Sciences / info:eu-repo/semantics/nonPublished

Le sujet de cette thèse concerne l’inférence statistique sur le processus de Mino que nous définissons comme un processus auto-excité de mémoire 1 dont l’intensité est de forme particulière. Nous donnons tout d’abord une description générale des processus auto-excités et des méthodes possibles pour estimer les paramètres de l’intensité de ces processus. Puis, nous considérons le cas particulier d’un processus auto-excité de mémoire 1 que l’on rencontre en traitement du signal et que nous avons dénommé : processus de Mino. Nous montrons que ce processus est un processus de renouvellement dont les interarrivées ont une distribution particulière que nous étudions en détails. Nous envisageons alors le problème de l’estimation des paramètres de l’intensité du processus de Mino en utilisant la méthode du maximum de vraisemblance. Nous résolvons les équations de vraisemblance en utilisant l’algorithme de Newton-Raphson. La méthode est appliquée à des données simulées. La convergence de l’algorithme de Newton-Raphson est démontrée, de même que l’existence et l’unicité des estimateurs. Nous terminons par la construction d’un test d’hypothèses qui permet de détecter si un processus ponctuel est auto-excité ou non / The subject of this PhD thesis is the statistical inference on Mino process that we define as a one-memory self-exciting point process which intensiy has a special form. We begin with a general description of self-exciting point processes and we present methods used to estimate the intensity parameters of these processes. We consider the special case of a one-memory self-exciting point process, used in signal processing. We call the process: the Mino process. This process can be interpreted as a renewal process which interarrival times that follow a special distribution that we study in details. In order to estimate the parameters of a Mino process intensity, we utilize the maximum likelihood method. We solve the likelihood equations with a Newton-Raphson algorithm. We show the efficiency of the method on simulated data. The convergence of the Newton-Raphson algorithm and, the existence and uniqueness of the maximun likelihood estimators are proved. Lastly, we construct a test of hypothesis to assess whether a point process is self-exciting or not.

Dans ce travail de thèse, nous étudions les fluctuations macroscopiques dans un modèle de boules aléatoires. Un modèle de boules aléatoires est une agrégation de boules dans Rd dont les centres et les rayons sont aléatoires. On marque également chaque boule par un poids aléatoire. On considère la masse M induite par le système de boules pondérées sur une configuration μ de Rd. Pour réaliser l’étude macroscopique des fluctuations de M, on réalise un "dézoom" sur la configuration de boules. Mathématiquement cela revient à diminuer le rayon moyen tout en augmentant le nombre moyen de centres par unité de volume. La question a déjà été étudiée lorsque les composantes des triplets (centre, rayon, poids) sont indépen- dantes et que ces triplets sont engendrés selon un processus ponctuel de Poisson sur Rd × R+ × R. On observe alors trois comportements distincts selon le rapport de force entre la vitesse de diminution des rayons et la vitesse d’augmentation de la densité des boules. Nous proposons de généraliser ces résultats dans trois directions distinctes. La première partie de ce travail de thèse consiste à introduire de la dépendance entre les centres et les rayons et de l’inhomogénéité dans la répartition des centres. Dans le modèle que nous proposons, le comportement stochastique des rayons dépend de l’emplacement de la boule. Dans les travaux précédents, les convergences obtenues pour les fluctuations de M sont au mieux des convergences fonctionnelles en dimension finie. Nous obtenons, dans la deuxième partie de ce travail, de la convergence fonctionnelle sur un ensemble de configurations μ de dimension infinie. Dans une troisième et dernière partie, nous étudions un modèle de boules aléatoires (non pondérées) sur C dont les couples (centre, rayon) sont engendrés par un processus ponctuel déterminantal. Contrairement au processus ponctuel de Poisson, le processus ponctuel déterminantal présente des phénomènes de répulsion entre ses points ce qui permet de modéliser davantage de problèmes physiques. / In this thesis, we study the macroscopic fluctuations in random balls models. A random balls model is an aggregation of balls in Rd whose centers and radii are random. We also mark each balls with a random weight. We consider the mass M induced by the system of weighted balls on a configuration μ of Rd. In order to investigate the macroscopic fluctuations of M, we realize a zoom-out on the configuration of balls. Mathematically, we reduce the mean radius while increasing the mean number of centers by volume unit. The question has already been studied when the centers, the radii and the weights are independent and the triplets (center, radius, weight) are generated according to a Poisson point process on Rd ×R+ ×R. Then, we observe three different behaviors depending on the comparison between the speed of the decreasing of the radii and the speed of the increasing of the density of centers. We propose to generalize these results in three different directions. The first part of this thesis consists in introducing dependence between the radii and the centers and inhomogeneity in the distribution of the centers. In the model we propose, the stochastic behavior of the radii depends on the location of the ball. In the previous works, the convergences obtained for the fluctuations of M are at best functional convergences in finite dimension. In the second part of this work, we obtain functional convergence on an infinite dimensional set of configurations μ. In the third and last part, we study a random balls model (non-weighted) on C where the couples (center, radius) are generated according to determinantal point process. Unlike to the Poisson point process, the determinantal point process exhibits repulsion phenomena between its points which allows us to model more physical problems.

Dans cette thèse, nous nous intéressons au problème de détection de mesures GPS erronées. En effet, en zones urbaines, les acquisitions sont fortement dégradées par des phénomènes de multi-trajets ou de multiples réflexions des signaux avant d’arriver à l’antenne réceptrice. En forêt, de multiples obstacles bloquent les signaux satellites, ce qui diminue la redondance des mesures. Alors que les algorithmes présents dans les récepteurs GPS détectent au maximum une mesure erronée par pas de temps, avec une combinaison de différents systèmes de navigation, l’hypothèse d’une seule erreur à la fois n’est plus tenable et la détection et gestion des données erronées (défaillantes, aberrantes ou outliers selon les différentes terminologies) représente un enjeu majeur dans les applications de navigation autonome et de localisation robuste et devient un nouveau défi technologique.La contribution principale de cette thèse est un algorithme de détection de mesures de pseudo-distances aberrantes exploitant la modélisation a contrario. Deux critères fondés sur l’espérance du nombre de fausses alarmes (NFA) sont utilisés pour mesurer la cohérence d’un ensemble de mesures sous l’hypothèse d’un modèle de bruit.Notre seconde contribution concerne l’introduction des mesures Doppler dans le processus de localisation. Nous étendons la détection d’outliers conjointement dans les mesures de pseudo-distance aux mesures Doppler et proposons une localisation par couplage avec le filtre particulaire soit SIR soit de Rao-Blackwell qui permet d’estimer analytiquement la vitesse.Notre troisième contribution est une approche crédibiliste pour la détection des mesures aberrantes dans les pseudo-distances. S’inspirant du RANSAC, nous choisissons, parmi les combinaisons d’observations possibles, la plus compatible selon une mesure de cohérence ou d’incohérence. Une étape de filtrage évidentiel permet de tenir compte de la solution précédente. Les approches proposées donnent de meilleures performances que les méthodes usuelles et démontrent l’intérêt de retirer les données aberrantes du processus de localisation. / In this work, we focus on the problem of detection of erroneous GPS measurements. Indeed, in urban areas, acquisitions are highly degraded by multipath phenomena or signal multiple reflections before reaching the receiver antenna. In forest areas, the satellite occlusion reduces the measurements redundancy. While the algorithms embedded in GPS receivers detect at most one erroneous measurement per epoch, the hypothesis of a single error at a time is no longer realistic when we combine data from different navigation systems. The detection and management of erroneous data (faulty, aberrant or outliers depending on the different terminologies) has become a major issue in the autonomous navigation applications and robust localization and raises a new technological challenge.The main contribution of this work is an outlier detection algorithm for GNSS localization with an a contrario modeling. Two criteria based on number of false alarms (NFA) are used to measure the consistency of a set of measurements under the noise model assumption.Our second contribution is the introduction of Doppler measurements in the localization process. We extend the outlier detection to both pseudo-ranges and Doppler measurements, and we propose a coupling with either the particle filter SIR or the Rao-Blackwellized particle filter that allows us to estimate analytically the velocity.Our third contribution is an evidential approach for the detection of outliers in the pseudo-ranges. Inspired by the RANSAC, we choose among possible combinations of observations, the most compatible one according to a measure of consistency or inconsistency. An evidential filtering step is performed that takes into account the previous solution. The proposed approaches achieve better performance than standard methods and demonstrate the interest of removing the outliers from the localization process.

La dissémination collaborative d'une information d'un agent à tous les autres agents d'un système distribué est un problème fondamental qui est particulièrement important lorsque l'on veut obtenir des algorithmes distribués qui sont à la fois robustes et fonctionnent dans un cadre anonyme, c'est-à-dire sans supposer que les agents possèdent des identifiants distincts connus. Ce problème, connu sous le nom de problème de propagation de rumeur , est à la base de nombreux algorithmes de communication sur des réseaux de capteurs sans-fil [Dimakis et al. (2010)] ou des réseaux mobiles ad-hoc. Il est aussi une brique de base centrale pour de nombreux algorithmes distribués avancés [Mosk-Aoyama et Shah (2008)].Les méthodes les plus connues pour surmonter les défis de robustesse et d'anonymat sont les algorithmes basés sur les ragots ( gossip-based algorithms ), c'est-à-dire sur la paradigme que les agents contact aléatoirement les autres agents pour envoyer ou récupérer l'information. Nousproposons une méthode générale d'analyse de la performance des algorithmes basés sur les ragots dans les graphes complets. Contrairement aux résultats précédents basés sur la structure précise des processus étudiés, notre analyse est basée sur la probabilité et la covariance des évènements correspondants au fait qu'un agent non-informé s'informe. Cette universalité nous permet de reproduire les résultats basiques concernant les protocoles classiques de push, pull et push-pull ainsi qu'analyser les certaines variantions telles que les échecs de communications ou les communications simultanés multiples réalisées par chaque agent. De plus, nous sommescapables d'analyser les certains modèles dynamiques quand le réseaux forme un graphe aléatoire échantillonné à nouveau à chaque étape [Clementi et al. (ESA 2013)]. Malgré sa généralité, notre méthode est simple et précise. Elle nous permet de déterminer l'espérance du temps de la diffusion à une constante additive près, ce qu'il est plus précis que la plupart des résultatsprécédents. Nous montrons aussi que la déviation du temps de la diffusion par rapport à son espérance est inférieure d'une constante r avec la probabilité au moins 1 − exp(Ω(r)).À la fin, nous discutons d'une hypothèse classique que les agents peuvent répondre à plusieurs appels entrants. Nous observons que la restriction à un seul appel entrant par agent provoque une décélération importante du temps de la diffusion pour un protocole de push-pull. En particulier, une phase finale du processus prend le temps logarithmique au lieu du temps double logarithmique. De plus, cela augmente le nombre de messages passés de Θ(n log log n) (valeur optimale selon [Karp et al. (FOCS 2000)]) au Θ(n log n) . Nous proposons une variation simple du protocole de push-pull qui rétablit une phase double logarithmique à nouveau et donc le nombre de messages passés redescend sur sa valeur optimal. / Epidemic algorithms are distributed algorithms in which the agents in thenetwork involve peers similarly to the spread of epidemics. In this work, we focus on randomized rumor spreading -- a class of epidemic algorithms based on the paradigm that nodes call random neighbors and exchange information with these contacts. Randomized rumor spreading has found numerous applications from the consistency maintenance of replicated databases to newsspreading in social networks. Numerous mathematical analyses of different rumor spreading algorithms can be found in the literature. Some of them provide extremely sharp estimates for the performance of such processes, but most of them are based on the inherent properties of concrete algorithms.We develop new simple and generic method to analyze randomized rumor spreading processes in fully connected networks. In contrast to all previous works, which heavily exploit the precise definition of the process under investigation, we only need to understand the probability and the covariance of the events that uninformed nodes become informed. This universality allows us to easily analyze the classic push, pull, and push-pull protocols both in their pure version and in several variations such as when messages fail with constant probability or when nodes call a random number of others each round. Some dynamic models can be analyzed as well, e.g., when the network is a random graph sampled independently each round [Clementi et al. (ESA 2013)]. Despite this generality, our method determines the expected rumor spreading time precisely apart from additive constants, which is more precise than almost all previous works. We also prove tail bounds showing that a deviation from the expectation by more than an additive number of r rounds occurs with probability at most exp(−Ω(r)).We further use our method to discuss the common assumption that nodes can answer any number of incoming calls. We observe that the restriction that only one call can be answered leads to a significant increase of the runtime of the push-pull protocol. In particular, the double logarithmic end phase of the process now takes logarithmic time. This also increases the message complexity from the asymptotically optimal Θ(n log log n) [Karp, Shenker, Schindelhauer, Vöcking (FOCS 2000)] to Θ(n log n). We propose a simple variation of the push-pull protocol that reverts back to the double logarithmic end phase and thus to the Θ(n log log n) message complexity.

Le sujet de cette thèse est l'inférence statistique de processus d'Ornstein-Uhlenbeck multi-dimensionnels. Dans une première partie, nous introduisons un modèle de graphes stochastiques définis comme observations binaires de trajectoires. Nous montrons alors qu'il est possible de déduire la dynamique de la trajectoire sous-jacente à partir des observations binaires. Pour ceci, nous construisons des statistiques à partir du graphe et montrons de nouvelles propriétés de convergence dans le cadre d'une observation en temps long et en haute fréquence. Nous analysons aussi les propriétés des graphes stochastiques du point de vue des réseaux évolutifs. Dans une deuxième partie, nous travaillons sous l'hypothèse d'information complète et en temps continu et ajoutons une hypothèse de sparsité concernant le paramètre de textit{drift} du processus d'Ornstein-Uhlenbeck. Nous montrons alors des propriétés d'oracle pointues de l'estimateur Lasso, prouvons une borne inférieure sur l'erreur d'estimation au sens minimax et démontrons des propriétés d'optimalité asymptotique de l'estimateur Lasso Adaptatif. Nous appliquons ensuite ces méthodes pour estimer la vitesse de retour à la moyenne des retours journaliers d'actions américaines ainsi que des prix de futures de dividendes pour l'indice EURO STOXX 50. / The subject if this thesis is the statistical inference of multi-dimensional Ornstein-Uhlenbeck processes. In a first part, we introduce a model of stochastic graphs, defined as binary observations of a trajectory. We show then that it is possible to retrieve the dynamic of the underlying trajectory from the binary observations. For this, we build statistics of the stochastic graph and prove new results on their convergence in the long-time, high-frequency setting. We also analyse the properties of the stochastic graph from the point of view of evolving networks. In a second part, we work in the setting of complete information and continuous time. We add then a sparsity assumption applied to the drift matrix coefficient of the Ornstein-Uhlenbeck process. We prove sharp oracle inequalities for the Lasso estimator, construct a lower bound on the estimation error for sparse estimators and show optimality properties of the Adaptive Lasso estimator. Then, we apply the methods to estimate mean-return properties of real-world financial datasets: daily returns of SP500 components and EURO STOXX 50 Dividend Future prices.

L’allocation de ressources est un problème omniprésent qui survient dès que des ressources limitées doivent être distribuées parmi de multiples agents autonomes (e.g., personnes, compagnies, robots, etc). Les approches standard pour déterminer l’allocation optimale souffrent généralement d’une très grande complexité de calcul. Le but de cette thèse est de proposer des algorithmes rapides et efficaces pour allouer des ressources consommables et non consommables à des agents autonomes dont les préférences sur ces ressources sont induites par un processus stochastique. Afin d’y parvenir, nous avons développé de nouveaux modèles pour des problèmes de planifications, basés sur le cadre des Processus Décisionnels de Markov (MDPs), où l’espace d’actions possibles est explicitement paramétrisés par les ressources disponibles. Muni de ce cadre, nous avons développé des algorithmes basés sur la programmation dynamique et la recherche heuristique en temps-réel afin de générer des allocations de ressources pour des agents qui agissent dans un environnement stochastique. En particulier, nous avons utilisé la propriété acyclique des créations de tâches pour décomposer le problème d’allocation de ressources. Nous avons aussi proposé une stratégie de décomposition approximative, où les agents considèrent des interactions positives et négatives ainsi que les actions simultanées entre les agents gérants les ressources. Cependant, la majeure contribution de cette thèse est l’adoption de la recherche heuristique en temps-réel pour l’allocation de ressources. À cet effet, nous avons développé une approche basée sur la Q-décomposition munie de bornes strictes afin de diminuer drastiquement le temps de planification pour formuler une politique optimale. Ces bornes strictes nous ont permis d’élaguer l’espace d’actions pour les agents. Nous montrons analytiquement et empiriquement que les approches proposées mènent à des diminutions de la complexité de calcul par rapport à des approches de planification standard. Finalement, nous avons testé la recherche heuristique en temps-réel dans le simulateur SADM, un simulateur d’allocation de ressource pour une frégate. / Resource allocation is an ubiquitous problem that arises whenever limited resources have to be distributed among multiple autonomous entities (e.g., people, companies, robots, etc). The standard approaches to determine the optimal resource allocation are computationally prohibitive. The goal of this thesis is to propose computationally efficient algorithms for allocating consumable and non-consumable resources among autonomous agents whose preferences for these resources are induced by a stochastic process. Towards this end, we have developed new models of planning problems, based on the framework of Markov Decision Processes (MDPs), where the action sets are explicitly parameterized by the available resources. Given these models, we have designed algorithms based on dynamic programming and real-time heuristic search to formulating thus allocations of resources for agents evolving in stochastic environments. In particular, we have used the acyclic property of task creation to decompose the problem of resource allocation. We have also proposed an approximative decomposition strategy, where the agents consider positive and negative interactions as well as simultaneous actions among the agents managing the resources. However, the main contribution of this thesis is the adoption of stochastic real-time heuristic search for a resource allocation. To this end, we have developed an approach based on distributed Q-values with tight bounds to diminish drastically the planning time to formulate the optimal policy. These tight bounds enable to prune the action space for the agents. We show analytically and empirically that our proposed approaches lead to drastic (in many cases, exponential) improvements in computational efficiency over standard planning methods. Finally, we have tested real-time heuristic search in the SADM simulator, a simulator for the resource allocation of a platform.

Dans ce mémoire, on traite des méthodes et d'outils d'évaluation de la fiabilité des systèmes mécanique. La fiabilité dans ce contexte est définie comme étant la probabilité que la résistance soit supérieure à la sollicitation que le système subit. On considère que la résistance est aléatoire et que l'occurrence et l'intensité de la sollicitation sont aléatoires. Les outils d'analyse et d'évaluation de la fiabilité, retenus dans ce travail, permettent d'évaluer et d'optimiser les performances d'un système existant ou d'intégrer le caractère aléatoire de sollicitation et de la résistance, en phase de conception. Des exemples d'applications issus des domaines du génie mécanique et de la sécurité des structures sont rapportés dans ce mémoire pour illustrer les différents concepts théoriques. Le contenu de ce mémoire a été conçu et structuré de manière à servir de document de référence pour la conception et l'exploitation de systèmes assujettis à des sollicitations dont l'intensité et l'occurrence sont aléatoires et dont la résistance se dégrade, aléatoirement également, selon l'âge et l'usage du système.

Cette thèse traite des fonctionnelles exponentielles du mouvement brownien et porte en particulier sur des calculs explicites de prix de bonds zéro-coupon associés au modèle de taux d'intérêt de Dothan. En utilisant des méthodes de noyaux de la chaleur et de résolution d'équations de Fokker-Planck, nous donnons des formules explicites de densités de probabilités ou de leurs transformées de Laplace. Les différentes formules intégrales obtenues complètent celles de l'article original "On the Term Structure of Interest Rates" (L. U. Dothan). La méthode utilisée est directe et implique notamment une nouvelle représentation intégrale pour le module au carré de la fonction Gamma. Nous étudions ensuite les applications à la physique et aux mathématiques financières des résultats obtenus pour les fonctionnelles périodiques et hyperboliques du mouvement brownien. Nous traitons aussi de calculs de sensibilités d'options par le calcul de Malliavin. Nous donnons des expressions explicites de l'indicateur delta pour des prix d'options asiatiques et des obligations reposant sur des taux courts traités dans la première partie de la thèse.