TY - CONF
A1 - Péron, Martin
A1 - Bartlett, Peter L.
A1 - Becker, Kai-Helge
A1 - Helmstedt, Kate
A1 - Chadès, Iadine
T1 - Two Approximate Dynamic Programming Algorithms for Managing Complete SIS Networks
T2 - COMPASS '18 Proceedings of the 1st ACM SIGCAS Conference on Computing and Sustainable Societies
N2 - Inspired by the problem of best managing the invasive mosquito Aedes albopictus across the 17 Torres Straits islands of Australia, we aim at solving a Markov decision process on large Susceptible-Infected-Susceptible (SIS) networks that are highly connected. While dynamic programming approaches can solve sequential decision-making problems on sparsely connected networks, these approaches are intractable for highly connected networks. Inspired by our case study, we focus on problems where the probability of nodes changing state is low and propose two approximate dynamic programming approaches. The first approach is a modified version of value iteration where only those future states that are similar to the current state are accounted for. The second approach models the state space as continuous instead of binary, with an on-line algorithm that takes advantage of Bellman's adapted equation. We evaluate the resulting policies through simulations and provide a priority order to manage the 17 infested Torres Strait islands. Both algorithms show promise, with the continuous state approach being able to scale up to high dimensionality (50 nodes). This work provides a successful example of how AI algorithms can be designed to tackle challenging computational sustainability problems.
Y1 - 2018
UR - https://opus4.kobv.de/opus4-zib/frontdoor/index/index/docId/7249
PB - ACM
ER -