Graduate Thesis Or Dissertation
 

Scheduling and Online Planning in Stochastic Diffusion Networks

Público Deposited

Contenido Descargable

Descargar PDF
https://ir.library.oregonstate.edu/concern/graduate_thesis_or_dissertations/k0698f81q

Descriptions

Attribute NameValues
Creator
Abstract
  • Diffusion processes in networks are common models for many domains, including species colonization, information/idea cascade, disease propagation and fire spreading. In diffusion networks, a diffusion event occurs when a behavior spreads from one node to the other following a probabilistic model, where the behavior could be species, an idea, a virus, fire, etc. In the real world, in addition to observing diffusion processes, people are usually able to control the influence of diffusion by conducting operations on each individual node or node groups. Then the diffusion network control problem is to decide how to perform possible controls in order to maximize or minimize the range of diffusion, especially when there is a limited resource for doing controls. Diffusion network control problems are challenging for most AI planning techniques. The complexity comes from highly stochastic exogenous events, a large action branching factor (the number of combinations of individual operations), a long time horizon, and the need to reason about numeric resource limits. In this thesis, we explore approaches that offer high-quality policies of controlling diffusion processes in large-scale networks. We first propose a non-adaptive policy in conservation planning, where the goal is to encourage species spread in a long term. Given a set of control operations of interest, this policy specifies the deadline of taking each operation, so that the resource is used with the most flexibility while keeping the loss of diffusion influence within a desired ratio. This is particularly applicable in cases where a domain expert can develop a set of control operations that captures their own objectives. Then our approach provides a way of trading off diffusion influence and resource usage. We further propose a fully adaptive approach for this conservation planning problem by computing a Hindsight Optimization (HOP) solution at every time step. Instead of computing a HOP action in the traditional way which is linear in the number of actions, we take advantage of its separable structure and develop an effective algorithm that scales for exponentially large, factored action spaces. From experiments on both synthetic and real data sets, we show that our algorithm returns near-optimal HOP solutions while scaling to large problems. Moreover, we extend our implementation of HOP policy to a general framework of online planning for diffusion network control problems. In particular, we give a general and formal representation of diffusion network problems. Our framework proposes a schema of effectively computing multiple lookahead policies, some of which have been successfully applied to various probabilistic planning problems. We evaluate our ap-proach on diffusion network control problems in conservation planning, epidemic control and firefighting. The experimental results demonstrate the behaviors of these lookahead policies and the advantage of each in different domains.
License
Resource Type
Fecha de Emisión
Degree Level
Degree Name
Degree Field
Degree Grantor
Commencement Year
Advisor
Committee Member
Academic Affiliation
Declaración de derechos
Publisher
Peer Reviewed
Language

Relaciones

Parents:

This work has no parents.

En Collection:

Elementos

Miniatura Título Fecha de subida Visibilidad Acciones
file details XueShan2020.pdf 2020-03-20 Público Descargar