- Diﬀusion processes in networks are common models for many domains, including species colonization, information/idea cascade, disease propagation and ﬁre spreading. In diﬀusion networks, a diﬀusion 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, ﬁre, etc. In the real world, in addition to observing diﬀusion processes, people are usually able to control the inﬂuence of diﬀusion by conducting operations on each individual node or node groups. Then the diﬀusion network control problem is to decide how to perform possible controls in order to maximize or minimize the range of diﬀusion, especially when there is a limited resource for doing controls.
Diﬀusion 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 oﬀer high-quality policies of controlling diﬀusion processes in large-scale networks.
We ﬁrst 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 speciﬁes the deadline of taking each operation, so that the resource is used with the most ﬂexibility while keeping the loss of diﬀusion inﬂuence 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 oﬀ diﬀusion inﬂuence 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 eﬀective 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 diﬀusion network control problems. In particular, we give a general and formal representation of diﬀusion network problems. Our framework proposes a schema of eﬀectively computing multiple lookahead policies, some of which have been successfully applied to various probabilistic planning problems. We evaluate our ap-proach on diﬀusion network control problems in conservation planning, epidemic control and ﬁreﬁghting. The experimental results demonstrate the behaviors of these lookahead policies and the advantage of each in diﬀerent domains.