Doctor of Philosophy / Department of Industrial & Manufacturing Systems Engineering / David H. Ben-Arieh / Chih-Hang Wu / Patients who suffer from sepsis or septic shock are of great concern in the healthcare system. Recent data indicate that more than 900,000 severe sepsis or septic shock cases developed in the United States with mortality rates between 20% and 80%. In the United States alone, almost $17 billion is spent each year for the treatment of patients with sepsis. Clinical trials of treatments for sepsis have been extensively studied in the last 30 years, but there is no general agreement of the effectiveness of the proposed treatments for sepsis. Therefore, it is necessary to find accurate and effective tools that can help physicians predict the progression of disease in a patient-specific way, and then provide physicians recommendation on the treatment of sepsis to lower risk for patients dying from sepsis. The goal of this research is to develop a risk assessment tool and a risk management tool for sepsis. In order to achieve this goal, two system dynamic mathematical models (SDMMs) are initially developed to predict dynamic patterns of sepsis progression in innate immunity and adaptive immunity. The two SDMMs are able to identify key indicators and key processes of inflammatory responses to an infection, and a sepsis progression. Second, an integrated-mathematical-multi-agent-based model (IMMABM) is developed to capture the stochastic nature embedded in the development of inflammatory responses to a sepsis. Unlike existing agent-based models, this agent-based model is enhanced by incorporating developed SDMMs and extensive experimental data. With the risk assessment tools, a Markov decision process (MDP) is proposed, as a risk management tool, to apply to clinical decision-makings on sepsis. With extensive computational studies, the major contributions of this research are to firstly develop risk assessment tools to identify the risk of sepsis development during the immune system responding to an infection, and secondly propose a decision-making framework to manage the risk of infected individuals dying from sepsis. The methodology and modeling framework used in this dissertation can be expanded to other disease situations and treatment applications, and have a broad impact to the research area related to computational modeling, biology, medical decision-making, and industrial engineering.

This research is motivated by our collaborations with a large French university teaching hospital in order to reduce the Length of Stay (LoS) of stroke patients treated in the neurovascular department. Quick diagnosis is critical for stroke patients but relies on expensive and heavily used imaging facilities such as MRI (Magnetic Resonance Imaging) scanners. Therefore, it is very important for the neurovascular department to reduce the patient LoS by reducing their waiting time of imaging examinations. From the neurovascular department perspective, this thesis proposes a new MRI examinations reservation process in order to reduce patient waiting times without degrading the utilization of MRI. The service provider, i.e., the imaging department, reserves each week a certain number of appropriately distributed contracted time slots (CTS) for the neurovascular department to ensure quick MRI examination of stroke patients. In addition to CTS, it is still possible for stroke patients to get MRI time slots through regular reservation (RTS). This thesis first proposes a stochastic programming model to simultaneously determine the contract decision, i.e., the number of CTS and its distribution, and the patient assignment policy to assign patients to either CTS or RTS. To solve this problem, structure properties of the optimal patient assignment policy for a given contract are proved by an average cost Markov decision process (MDP) approach. The contract is determined by a Monte Carlo approximation approach and then improved by local search. Computational experiments show that the proposed algorithms can efficiently solve the model. The new reservation process greatly reduces the average waiting time of stroke patients. At the same time, some CTS cannot be used for the lack of patients.To reduce the unused CTS, we further explore the possibility of the advance cancellation of CTS. Structure properties of optimal control policies for one-day and two-day advance cancellation are established separately via an average-cost MDP approach with appropriate modeling and advanced convexity concepts used in control of queueing systems. Computational experiments show that appropriate advance cancellations of CTS greatly reduce the unused CTS with nearly the same waiting times.

In service-oriented environments, services are put together in the form of a workflow with the aim of distributed problem solving. Capturing the execution details of the services' transformations is a significant advantage of using workflows. These execution details, referred to as provenance information, are usually traced automatically and stored in provenance stores. Provenance data contains the data recorded by a workflow engine during a workflow execution. It identifies what data is passed between services, which services are involved, and how results are eventually generated for particular sets of input values. Provenance information is of great importance and has found its way through areas in computer science such as: Bioinformatics, database, social, sensor networks, etc. Current exploitation and application of provenance data is very limited as provenance systems started being developed for specific applications. Thus, applying learning and knowledge discovery methods to provenance data can provide rich and useful information on workflows and services. Therefore, in this work, the challenges with workflows and services are studied to discover the possibilities and benefits of providing solutions by using provenance data. A multifunctional architecture is presented which addresses the workflow and service issues by exploiting provenance data. These challenges include workflow composition, abstract workflow selection, refinement, evaluation, and graph model extraction. The specific contribution of the proposed architecture is its novelty in providing a basis for taking advantage of the previous execution details of services and workflows along with artificial intelligence and knowledge management techniques to resolve the major challenges regarding workflows. The presented architecture is application-independent and could be deployed in any area. The requirements for such an architecture along with its building components are discussed. Furthermore, the responsibility of the components, related works and the implementation details of the architecture along with each component are presented.

We present results and research projects about the computational aspects of classical problems in Artificial Intelligence. We are interested in the setting of agents able to describe their environment through a possibly huge number of Boolean descriptors, and to act upon this environment. The typical applications of this kind of studies are to the design of autonomous robots (for exploring unknown zones, for instance) or of software assistants (for scheduling, for instance). The ultimate goal of research in this domain is the design of agents able to learn autonomously, by learning and interacting with their environment (including human users), also able to reason for producing new pieces of knowledge, for explaining observed phenomena, and finally, able to decide on which action to take at any moment, in a rational fashion. Ideally, such agents will be fast, efficient as soon as they start to interact with their environment, they will improve their behavior as time goes by, and they will be able to communicate naturally with humans. Among the numerous research questions raised by these objectives, we are especially interested in concept and preference learning, in reinforcement learning, in planning, and in some underlying problems in complexity theory. A particular attention is paid to interaction with humans and to huge numbers of descriptors of the environment, as are necessary in real-world applications.

A wireless sensor network consists of a number of sensor devices and coordinator(s) or sink(s). A coordinator collects the sensed data from the sensor devices for further processing. In such networks, sensor devices are generally powered by batteries. Since wireless transmission of packets consumes significant amount of energy, it is important for a network to adopt a medium access control (MAC) technology which is energy efficient and satisfies the communication performance requirements. Carrier sense multiple access with collision avoidance (CSMA/CA), which is a popular access technique because of its simplicity, flexibility and robustness, suffers poor throughput and energy inefficiency performance in wireless sensor networks. On the other hand, time division multiple access (TDMA) is a collision free and delay bounded access technique but suffers from the scalability problem. For this reason, this thesis focuses on design and analysis of hybrid channel access schemes which combine the strengths of both the CSMA/CA and TDMA schemes. In a hybrid CSMA/CA-TDMA scheme, the use of the CSMA/CA period and the TDMA period can be optimized to enhance the communication performance in the network. If such a hybrid channel access scheme is not designed properly, high congestion during the CSMA/CA period and wastage of bandwidth during the TDMA period result in poor communication performance in terms of throughput and energy efficiency. To address this issue, distributed and centralized channel access schemes are proposed to regulate the activities (such as transmitting, receiving, idling and going into low power mode) of the sensor devices. This regulation during the CSMA/CA period and allocation of TDMA slots reduce traffic congestion and thus improve the network performance. In this thesis work, time slot allocation methods in hybrid CSMA/CA-TDMA schemes are also proposed and analyzed to improve the network performance. Finally, such hybrid CSMA/CA-TDMA schemes are used in a cellular layout model for the multihop wireless sensor network to mitigate the hidden terminal collision problem.

In the past few years, we have witnessed the continuous growth in popularity of delay-sensitive applications. Applications like live video streaming, multimedia conferencing, VoIP and online gaming account for a major part of Internet traffic these days. It is also predicted that this trend will continue in the coming years. This emphasizes the significance of developing efficient scheduling algorithms in communication networks with guaranteed low delay performance. In our work, we try to address the delay issue in some major instances of wireless communication networks. First, we study a wireless content distribution network (CDN), in which the requests for the content may have service deadlines. Our wireless CDN consists of a media vault that hosts all the content in the system and a number of local servers (base stations), each having a cache for temporarily storing a subset of the content. There are two major questions associated with this framework: (i) content caching: which content should be loaded in each cache? and (ii) wireless network scheduling: how to appropriately schedule the transmissions from wireless servers? Using ideas from queuing theory, we develop provably optimal algorithms to jointly solve the caching and scheduling problems. Next, we focus on wireless relay networks. It is well accepted that network coding can enhance the performance of these networks by exploiting the broadcast nature of the wireless medium. This improvement is usually evaluated in terms of the number of required transmissions for delivering flow packets to their destinations. In this work, we study the effect of delay on the performance of network coding by characterizing a trade-off between latency and the performance gain achieved by employing network coding. More specifically, we associate a holding cost for delaying packets before delivery and a transmission cost for each broadcast transmission made by the relay node. Using a Markov decision process (MDP) argument, we prove a simple threshold-based policy is optimal in the sense of minimum long-run average cost. Finally, we analyze delay-sensitive applications in wireless peer-to-peer (P2P) networks. We consider a hybrid network which consists of (i) an expensive base station-to-peer (B2P) network with unicast transmissions, and (ii) a free broadcast P2P network. In such a framework, we study two popular applications: (a) a content distribution application with service deadlines, and (b) a multimedia live streaming application. In both problems, we utilize random linear network coding over finite fields to simplify the coordination of the transmissions. For these applications, we provide efficient algorithms to schedule the transmissions such that some quality of service (QoS) requirements are satisfied with the minimum cost of B2P usage. The algorithms are proven to be throughput optimal for sufficiently large field sizes and perform reasonably well for finite fields.

<p>This dissertation describes sequential decision making problems in non-stationary environments. Online learning algorithms deal with non-stationary environments, but generally there is no notion of a dynamic state to model future impacts of past actions. State-based models are common in stochastic control settings, but well-known frameworks such as Markov decision processes (MDPs) assume a known stationary environment. In recent years, there has been a growing interest in fusing the above two important learning frameworks and considering an MDP setting in which the cost function is allowed to change arbitrarily over time. A number of online MDP algorithms have been designed to work under various assumptions about the dynamics of state transitions so far and provide performance guarantees, i.e. bounds on the regret defined as the performance gap between the total cost incurred by the learner and the total cost of the best available stationary policy that could have been chosen in hindsight. </p><p>However, most of the work in this area has been algorithmic: given a problem, one</p><p>would develop an algorithm almost from scratch and prove the performance guarantees on a case-by-case basis. Moreover, the presence of the state and the assumption of an arbitrarily varying environment complicate both the theoretical analysis and the development of computationally efficient methods. Another potential issue is that, by removing distributional assumptions about the mechanism generating the cost sequences, the existing methods have to consider the worst-case scenario, which may render their solutions too conservative in situations where the environment exhibits some degree of predictability. </p><p>This dissertation contributes several novel techniques to address the above challenges of the online MDP framework and opens up new research directions for online MDPs. </p><p>Our proposed general framework for deriving algorithms in the online MDP setting leads to a unifying view of existing methods and provides a general procedure for constructing new ones. Several new algorithms are developed and analyzed using this framework. We develop convex-analytical algorithms that take advantage of possible regularity of observed sequences, yet maintain the worst case performance guarantees. To further study the convex-analytic methods we applied above, we take a step back to consider the traditional MDP problem and extend the LP approach to MDPs by adding a relative entropy regularization term. A computationally efficient algorithm for this class of MDPs is constructed under mild assumptions on the state transition models. Two-player zero-sum stochastic games are also investigated in this dissertation as an important extension of the online MDP setting. In short, this dissertation provides in-depth analysis of the online MDP problem and answers several important questions in this field.</p> / Dissertation

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

No description available.

La demande en énergie dans les réseaux de téléphonie mobile augmente en raison de l’émergence de nouvelles technologies et de nouveaux services aux exigences de plus en plus élevées (débits de données, délais, etc.). Dans ce contexte, l'opérateur de réseau mobile (ORM) doit fournir d'avantage de ressources radio et de capacité de traitement dans son réseau, entraînant ainsi des coûts financiers plus élevés. L’ORM n’a pas d’autre choix que de mettre en œuvre des stratégies d’économie d’énergie sur plusieurs niveaux de son infrastructure, notamment au niveau du réseau d’accès radio (RAN).En parallèle, le réseau électrique devient plus intelligent, avec de nouvelles fonctionnalités pour équilibrer l'offre et la demande en faisant varier les prix de l'électricité, permettant ainsi à certains agrégateurs d'énergie de faire partie du processus d'approvisionnement et en signant des accords de réponse à la demande avec ses clients les plus important. Dans le contexte d'un réseau électrique intelligent et fiable, l'ORM, qui compte des milliers de evolved NodeB (eNB) répartis sur tout le pays, doit jouer un rôle majeur dans le réseau en agissant en tant que consommateur potentiel capable de vendre de l'électricité. Toutefois, dans les pays d'Afrique subsaharienne, le réseau peut ne pas être fiable, voire même inexistant, l'ORM n'a d'autre choix que de déployer une centrale électrique virtuelle (VPP) qui l'alimente partiellement ou totalement.Dans cette thèse, nous étudions les interactions entre l’opérateur de réseau et le réseau électrique, qu’il soit fiable ou non, dans les pays développés comme dans les pays en cours de développement. Nous étudions la gestion optimale de l'énergie à long et à court terme, dans le but de minimiser le coût total de possession (TCO) en énergie de l'opérateur par station de base, qui correspond à la somme de ses dépenses d'investissement (CAPEX) et de ses dépenses opérationnelles (OPEX), en assurant la satisfaction des besoins croissants en trafic de ses utilisateurs dans la cellule.L'étude à long terme nous permet de prendre des décisions d'investissement semestrielles pour le dimensionnement de la batterie et des sources énergies renouvelables, en tenant compte de la dégradation des performances des équipements, des prévisions de la croissance du trafic des utilisateurs et de l'évolution du marché de l'électricité sur une longue période de temps comptée en années.Dans le cas où elle est alimentée par un réseau intelligent fiable, la politique à court terme aide l’opérateur à définir quotidiennement une stratégie de gestion optimale de la batterie assurant l'arbitrage ou à le trading d’électricité tout en exploitant les fluctuations horaires des prix de l’électricité afin de minimiser la facture énergétique journalière de l'ORM tout en respectant certaines règles d'utilisation de ces équipements.Dans le cas d'un réseau électrique non fiable ou complètement inexistant, l'opérateur est alimenté par des sources hybrides couplant stockage (batteries), générateurs diesel, énergie solaire et le réseau électrique si ce dernier est opérationnel. Ici, nous définissons un ordre de priorité fixe sur l’utilisation de ces sources qui vise à étendre la durée de vie de la batterie et maintenir ses performances / The energy demand in mobile networks is increasing due to the emergence of new technologies and new services with higher requirements (data rates, delays, etc). In this context, the Mobile Network Operator (MNO) has to provide more radio and processing resources in its network leading for higher financial costs. The MNO has no choice but to implement energy saving strategies in all the parts of its infrastructure and especially at the Radio Access Network (RAN).At the same time, the electrical grid is getting smarter including new functionalities to balance supply and demand by varying the electricity prices, allowing some aggregators to be part of the supply process and signing demand response agreements with its clients. In the context of reliable smart grid, the MNO having thousands of evolved NodeB (eNB) spread over all the country, has to play major role in the grid by acting as a prosumer able to sell electricity. In African Sub-Saharan countries however, the grid may be not reliable or even non existent, the MNO has no choice but to deploy a Virtual Power Plant (VPP) and rely partially or totally on it.In this thesis, we study the interactions between the network operator and the grid either reliable or not in both developed and developing countries. We investigate both long term and short term optimal energy related management, with the aim of minimising the operator's Total Cost of Ownership (TCO) for energy per base station which is the sum of its Capital Expenditure (CAPEX) and Operational Expenditure (OPEX) while satisfying the growing needs of its user traffic in the cell.The long term study enables us to make semestral based investment decisions for the battery and renewable energy sources dimensioning considering equipment performance degradation, predictions on users traffic growth and electricity market evolution over a long period of time counted in years.In the case of being powered by a reliable smart grid, the short term policy helps the operator to set on a daily basis, an optimal battery management strategy by performing electricity arbitrage or trading that takes advantage of the electricity prices hourly fluctuations in order to minimize the MNO daily energy bill while respecting some rules on the usage of its equipments.In the case of a non reliable or off-grid environment, the operator is powered by hybrid sources coupling storage, diesel generators, solar power and the grid if the latter is operational. Here, we define a fixed order of priority on the use of these sources that extends the battery lifetime and maintain its performance