Adapting optimisation techniques for improved conservation management in large state spaces

Samuel Nicol (2010). Adapting optimisation techniques for improved conservation management in large state spaces PhD Thesis, School of Mathematics and Physics, The University of Queensland.

Attached Files (Some files may be inaccessible until you login with your UQ eSpace credentials)
Name Description MIMEType Size Downloads
s41332115_PhD_finalthesis.pdf s41332115_PhD_finalthesis.pdf application/pdf 1.38MB 25
Author Samuel Nicol
Thesis Title Adapting optimisation techniques for improved conservation management in large state spaces
School, Centre or Institute School of Mathematics and Physics
Institution The University of Queensland
Publication date 2010-09
Thesis type PhD Thesis
Supervisor Prof Hugh Possingham
Dr Iadine Chades
Dr Simon Linke
Total pages 152
Total colour pages 3
Total black and white pages 149
Subjects 01 Mathematical Sciences
Abstract/Summary The stakes are high for conservation managers charged with making timely decisions about endangered species. Wrong decisions can result in species extinction, but the precise state of the population in the future cannot be predicted. Stochastic Dynamic Programming (SDP) is the primary tool used by conservation scientists to optimise management decisions in the face of uncertain population dynamics over time. SDP considers the probable effects of a range of management actions and matches each state of the system with the action that is most likely to lead to the management objective being achieved. While SDP gives the globally optimal solution to a problem, its application is limited by the ``curse of dimensionality''. Adding new state variables to a problem exponentially increases the size of the state space, so state spaces become extremely large with only a few state variables. The time to compute the SDP solution increases polynomially with the size of the state and action spaces, meaning that SDP becomes computationally intractable for problems with large state spaces. Because of this, ecological modellers are forced to greatly simplify complex ecological processes. In this dissertation we present methods to circumvent the curse of dimensionality in conservation management problems. The methods that we introduce were developed in the fields of artificial intelligence and operations research. Our aim is to study the benefits of these methods in conservation and demonstrate that optimisation of complex ecological models is possible and can also make new problems accessible. In chapter 2, we examine the question: are many small habitat patches better than a few large ones? The question is notoriously hard because the state space of the problem increases exponentially with both the number of patches that can be added to the system and the size of each patch. To answer the question in the general case is very difficult because the number of potential patch configurations is infinite. We use a spatially implicit metapopulation model with equidistant patches and apply the model to an endangered Southern Emu-wren (Stipiturus malachurus intermedius) population. We find that SDP techniques out-perform heuristic algorithms and argue that SDP must be applied on a case-by-case basis to solve this difficult problem. The problem in chapter 2 demonstrates the complexity created by large state spaces and shows that management based on plausible rules of thumb can be ineffective. In chapters 3 and 4, we introduce two simulation-based algorithms that give optimal local solutions for any sized state space. Both algorithms trade the guarantee of global optimality for a faster local approximation by implementing SDP using only the states that are most likely to be visited rather than all possible states. Chapter 3 solves a spatially explicit fish metapopulation persistence problem using Kearns, Mansour and Ng's sparse sampling algorithm. The algorithm is very useful for problems with multiple habitat variables such as the fish metapopulation because the speed of the algorithm is independent of the size of the state space. However the speed of the algorithm depends on how far into the future we simulate. We use the case study to explore the trade off between minimising sampling error by sampling further into the future and reducing algorithm run-time. For the fish metapopulation, we find that looking three timesteps into the future gives us the best results that we can achieve with this algorithm. Chapter 4 improves upon the Kearns algorithm by implementing Peret and Garcia's heuristic sampling algorithm, which controls the sampling error while simulating. By keeping the error contained, we are able to set a maximum number of simulations and be assured that the algorithm will find the best possible solution given the constraints of our computing power. The algorithm is used to solve two case studies with extremely large state or action spaces. We first solve a spatially explicit malleefowl (Leipoa ocellata) metapopulation management problem with a very large action space. The model is interesting because we can take multiple actions in one timestep, subject to a budgetary constraint. We find that Peret and Garcia's algorithm out-performs a plausible rule of thumb and performs as well as SDP using a modest computational budget. In a second case study, we solve a ring-structured metapopulation problem with 33 million states. This is roughly three orders of magnitude larger than the largest problem that can be solved with SDP. In chapter 5, we take a different approach to dealing with large state spaces and reduce the size of the state space with an intelligent discretization algorithm. We use the Continuous U-Tree (CU-Tree) algorithm to compactly discretize a continuous state space using the Washington sea otter population as a case study. New states are only added where they are statistically necessary to maintain the optimal value function. By using CU-Tree, we reduce the number of states from 72 down to 13 states. The CU-Tree algorithm reduces the state space sufficiently so that the effects of partial observability on the optimal solution can be considered. This cannot be done when the state space is large. We use two methods to solve the sea otter Partially Observable Markov Decision Process (POMDP), which is a decision problem where the true state of the population is uncertain. We find that the sea otter population can be managed assuming perfect observability. This dissertation presents just a few of the techniques available in the artificial intelligence and operations research literature for solving large state space optimal management problems in conservation. We show in the dissertation that using large state space optimisation methods allows us to both to expand the domain of problems that can currently be optimised and to answer previously insoluble questions in conservation biology.
Keyword conservation
Decision Theory
Markov decision process
On-line sparse sampling algorithm
optimal management
partially observable Markov decision process
Reinforcement learning
State aggregation
Stochastic Dynamic Programming
Additional Notes Colour page numbers: 51, 55, 57

Citation counts: Google Scholar Search Google Scholar
Created: Sun, 20 Feb 2011, 13:06:11 EST by Mr Samuel Nicol on behalf of Library - Information Access Service