Automated Planning is an active area within Artificial Intelligence. With the help of computers we can quickly find good plans in complicated problem domains, such as planning for search and rescue after a natural disaster. When planning in realistic domains the exact duration of an action generally cannot be predicted in advance. Temporal planning therefore tends to use upper bounds on durations, with the explicit or implicit assumption that if an action happens to be executed more quickly, the plan will still succeed. However, this assumption is often false. If we finish cooking too early, the dinner will be cold before everyone is at home and can eat. Simple Temporal Networks with Uncertainty (STNUs) allow us to model such situations. An STNU-based planner must verify that the temporal problems it generates are executable, which is captured by the property of dynamic controllability (DC). If a plan is not dynamically controllable, adding actions cannot restore controllability. Therefore a planner should verify after each action addition whether the plan remains DC, and if not, backtrack. Verifying dynamic controllability of a full STNU is computationally intensive. Therefore, incremental DC verification algorithms are needed. We start by discussing two existing algorithms relevant to the thesis. These are the very first DC verification algorithm called MMV (by Morris, Muscettola and Vidal) and the incremental DC verification algorithm called FastIDC, which is based on MMV. We then show that FastIDC is not sound, sometimes labeling networks as dynamically controllable when they are not.  We analyze the algorithm to pinpoint the cause and show how the algorithm can be modified to correctly and efficiently detect uncontrollable networks. In the next part we use insights from this work to re-analyze the MMV algorithm. This algorithm is pseudo-polynomial and was later subsumed by first an n5 algorithm and then an n4 algorithm. We show that the basic techniques used by MMV can in fact be used to create an n4 algorithm for verifying dynamic controllability, with a new termination criterion based on a deeper analysis of MMV. This means that there is now a comparatively easy way of implementing a highly efficient dynamic controllability verification algorithm. From a theoretical viewpoint, understanding MMV is important since it acts as a building block for all subsequent algorithms that verify dynamic controllability. In our analysis we also discuss a change in MMV which reduces the amount of regression needed in the network substantially. In the final part of the thesis we show that the FastIDC method can result in traversing part of a temporal network multiple times, with constraints slowly tightening towards their final values.  As a result of our analysis we then present a new algorithm with an improved traversal strategy that avoids this behavior.  The new algorithm, EfficientIDC, has a time complexity which is lower than that of FastIDC. We prove that it is sound and complete.

Ziel dieser Arbeit ist es, die Rolle von Pfaden für die Ausbreitung von Infektionskrankheiten auf komplexen Netzwerken zu untersuchen. Wir zeigen die Relevanz von Pfaden im Kontext der Epidemiologie in statischen und zeitabhängigen Netzwerken. Ein zentrales Ergebnis ist hierbei die Erreichbarkeitsentwicklung, die eine Analyse der Pfadstruktur zeitabhängiger Netzwerke erlaubt. In dieser Dissertation wird der Einfluss zweier bestimmter Merkmale statischer Netzwerke auf die Eigenschaften ihrer Pfadstruktur untersucht. Als Fallbeispiel analysieren wir hierfür ein Viehhandelsnetzwerk in Deutschland. Dieses Netzwerk besitzt eine Riesenkomponente und eine modulare Struktur. Die wichtigsten Ergebnisse sind hierbei, dass Netzwerke, die nahe an der Perkolationsschwelle liegen, mit großer Wahrscheinlichkeit zwei disjunkte Risikoklassen für Knoten aufweisen und, dass eine modulare Struktur eine signifikante Verzögerung von Krankheitsausbrüchen zur Folge hat. Hervorzuheben sind außerdem die Methoden, die hier zur Analyse zeitabhängiger Netzwerke vorgestellt werden. Das sind Systeme, in denen das Auftreten von Kanten mit der Zeit variiert. In dieser Arbeit stellen wir eine neue Methode vor, mit der die kausale Erreichbarkeit eines zeitabhängigen Netzwerks berechnet werden kann. Darüber hinaus stellen wir Erreichbarkeitsentwicklung als eine neue Methode zur Berechnung kürzester Pfaddauern in zeitabhängigen Netzwerken vor. Diese Herangehensweise ermöglicht es, charakteristische Zeitskalen für das Durchqueren von zeitabhängigen Netzwerken aufzuzeigen. Die Kenntnis solcher Zeitskalen ist von fundamentaler Wichtigkeit für die Abschätzung von Zeiten, die für die Verbreitung von Epidemien benötigt werden. Die Erreichbarkeit eines zeitabhängigen Netzwerks kann mit ihrem aggregierten Gegenstück verglichen werden. Damit definieren wir die Kausalitätstreue, die die Güte einer statischen Approximation eines zeitabhängigen Netzwerks quantifiziert. / The objective of this thesis is to examine the role of paths for the spread of infectious diseases on complex networks. We demonstrate the importance of paths in the context of epidemiology for the case of static and temporal networks. As a central result, we introduce the unfolding accessibility method, that allows for the analysis of the path structure of temporal networks. In this thesis, we analyze the impact of two particular attributes of static networks on the properties of their path structure. As a case study, we analyze the properties of a livestock trade network in Germany. This network exhibits a giant component and a modular structure. The main findings here are that networks close to the percolation threshold are likely to show two disjoint risk classes for the nodes and, a modular structure causes a significant delay for disease outbreaks. Furthermore, special emphasis should be placed on the methods introduced in this thesis for the analysis of temporal networks, i.e. systems where the occurrence of edges varies over time. In this work we introduce a novel method to obtain the causal accessibility graph of a temporal network. Moreover, we introduce unfolding accessibility as a novel formalism for the evaluation of shortest path durations in temporal networks. This approach is able to reveal characteristic timescales for the traversal of temporal networks. Knowledge of these timescales is of fundamental importance for the estimation of times needed for the spread of infectious diseases. The accessibility graph of a temporal network can be compared to its aggregated counterpart. Hence we define the causal fidelity, which quantifies the goodness of the static approximation of a temporal network from the causal point of view.

Master of Science / Department of Electrical and Computer Engineering / Faryad Darabi Sahneh / Recent experience of Ebola outbreak of 2014 highlighted the importance of immediate response to impede Ebola transmission at its very early stage. To this aim, efficient and effective allocation of limited resources is crucial. Among standard interventions is the practice of following up with physical contacts of individuals diagnosed with Ebola virus disease -- known as contact tracing. In an effort to objectively understand the effect of possible contact tracing protocols, we explicitly develop a model of Ebola transmission incorporating contact tracing. Our modeling framework has several features to suit early–stage Ebola transmission: 1) the network model is patient–centric because when number of infected cases are small only the myopic networks of infected individuals matter and the rest of possible social contacts are irrelevant, 2) the Ebola disease model is individual–based and stochastic because at the early stages of spread, random fluctuations are significant and must be captured appropriately, 3) the contact tracing model is parameterizable to analyze the impact of critical aspects of contact tracing protocols. Notably, we propose an activity driven network approach to contact tracing, and develop a Monte-Carlo method to compute the basic reproductive number of the disease spread in different scenarios. Exhaustive simulation experiments suggest that while contact tracing is important in stopping the Ebola spread, it does not need to be done too urgently. This result is due to rather long incubation period of Ebola disease infection. However, immediate hospitalization of infected cases is crucial and requires the most attention and resource allocation. Moreover, to investigate the impact of mitigation strategies in the 2014 Ebola outbreak, we consider reported data in Guinea, one the three West Africa countries that had experienced the Ebola virus disease outbreak. We formulate a multivariate sequential Monte Carlo filter that utilizes mechanistic models for Ebola virus propagation to simultaneously estimate the disease progression states and the model parameters according to reported incidence data streams. This method has the advantage of performing the inference online as the new data becomes available and estimating the evolution of the basic reproductive ratio R₀(t) throughout the Ebola outbreak. Our analysis identifies a peak in the basic reproductive ratio close to the time of Ebola cases reports in Europe and the USA.

Les fonctions cognitives reposent sur la communication dynamique de régions cérébrales interconnectées. Dans la maladie d’Alzheimer (MA), les travaux antérieurs suggèrent que le processus neuropathologique cible de façon précoce un ou plusieurs systèmes anatomo-fonctionnels spécifiques. La dysfonction du réseau par défaut a été objectivée de façon consistante. Cependant, ses relations avec les symptômes cliniques et avec l’atteinte des régions du lobe temporal interne qui lui sont fonctionnellement connectées restent à clarifier. L’IRM fonctionnelle de repos est une technique pertinente pour caractériser in vivo chez l’Homme la connectivité cérébrale.Par une approche des systèmes neuraux, ce travail de thèse a pour objectif de caractériser la réorganisation fonctionnelle neuronale dans la MA, ses corrélats cliniques, ainsi que l’influence de l’âge de début des symptômes. Par le recueil et l’analyse des données neuropsychologiques, en IRMf de repos et en IRM structurale, acquises chez des sujets avec des troubles de la mémoire et avec une forme mnésique légère de MA, notre travail apporte des éclairages : i) sur l’implication du réseau temporal antérieur dans la mémoire déclarative décontextualisée et ses modifications dans le cours de la MA ; ii) sur les similitudes et spécificités des systèmes anatomo-fonctionnels ciblés dans les deux formes cliniques distinctes - à début précoce et tardif - de la MA ; iii) sur la réorganisation de l’organisation topologique cérébrale dans son ensemble de ces deux formes de la maladie. / Cognitive functions rely on the dynamic interplay of connected brain regions. Previous studies suggest that in Alzheimer disease (AD), early pathological changes target one or several specific anatomo-functional networks. Dysfunction of the default mode network is a consistent finding. However, its relationship with clinical symptoms and interconnected medial temporal regions remains to be clarified. Resting state functional MRI (fMRI) is an emerging method aimed at characterizing in vivo brain connectivity in the Human.Using a neural system approach, the aim of this thesis was to characterize neuronal functional reorganization in AD, its clinical correlates, and to determine the influence of age at onset. Neuropsychological data, structural and fMRI were obtained in subjects with early memory impairment and mild “amnestic” AD. This work provides new insights into : i) the functional role of the anterior temporal network in context-free declarative memory and its changes throughout the course of AD; ii) the common and specific features in targeted anatomo-functional networks between early and late onset AD ; iii) the reorganization of whole brain topological properties in the two forms of the disease.

No description available.