Computational Sustainability

Connecting Machine Learning with Global Sustainability challenges.

In the field of Computational Sustainability, I have worked on learning predictive models of and optimizing policies for domains in invasive species control, forest harvest management and forest fire management. These types of domains offer unique challenges for traditional artificial intelligence and machine learning algorithms for decision making, prediction and anomaly detection.

See my blog for more writing on this topic.

Our Papers on Computational Sustainability

Semantic Workflows and Machine Learning for the Assessment of Carbon Storage by Urban Trees

Juan Carrillo, Daniel Garijo, Mark Crowley, Yolanda Gil, and Katherine Borda.

In Third International Workshop on Capturing Scientific Knowledge (Sciknow 2019), Collocated with the tenth International Conference on Knowledge Capture (K-CAP). Los Angeles, California, USA. 2019.
A Complementary Approach to Improve WildFire Prediction Systems.

Sriram Ganapathi Subramanian, and Mark Crowley

In Neural Information Processing Systems (AI for social good workshop). NeurIPS. 2018.

PDF URL
MCTS+A3C

Combining MCTS and A3C for prediction of spatially spreading processes in forest wildfire settings

Sriram Ganapathi Subramanian, and Mark Crowley

In Canadian Conference on Artificial Intelligence. Toronto, Ontario, Canada. 2018.

Abs PDF URL

In recent years, Deep Reinforcement Learning (RL) algorithms have shown super-human performance in a variety Atari and classic board games like chess and GO. Research into applications of RL in other domains with spatial considerations like environmental planning are still in their nascent stages. In this paper, we introduce a novel combination of Monte-Carlo Tree Search (MCTS) and A3C algorithms on an online simulator of a wildfire, on a pair of forest fires in Northern Alberta (Fort McMurray and Richardson fires) and on historical Saskatchewan fires previously compared by others to a physics-based simulator. We conduct several experiments to predict fire spread for several days before and after the given spatial information of fire spread and ignition points. Our results show that the advancements in Deep RL applications in the gaming world have advantages in spatially spreading real-world problems like forest fires. \textcopyright Springer International Publishing AG, part of Springer Nature 2018.
Using Spatial Reinforcement Learning to Build Forest Wildfire Dynamics Models From Satellite Images

Sriram Ganapathi Subramanian, and Mark Crowley

Frontiers in ICT. 5, (6). Frontiers, Apr, 2018.

Abs PDF URL

Machine learning algorithms have increased tremendously in power in recent years but have yet to be fully utilized in many ecology and sustainable resource management domains such as wildlife reserve design, forest fire management and invasive species spread. One thing these domains have in common is that they contain dynamics that can be characterized as a Spatially Spreading Process (SSP) which requires many parameters to be set precisely to model the dynamics, spread rates and directional biases of the elements which are spreading. We present related work in Artificial Intelligence and Machine Learning for SSP sustainability domains including forest wildfire prediction. We then introduce a novel approach for learning in SSP domains using Reinforcement Learning (RL) where fire is the agent at any cell in the landscape and the set of actions the fire can take from a location at any point in time includes spreading North, South, East, West or not spreading. This approach inverts the usual RL setup since the dynamics of the corresponding Markov Decision Process (MDP) is a known function for immediate wildfire spread. Meanwhile, we learn an agent policy for a predictive model of the dynamics of a complex spatially-spreading process. Rewards are provided for correctly classifying which cells are on fire or not compared to satellite and other related data. We examine the behaviour of five RL algorithms on this problem: Value Iteration, Policy Iteration, Q-Learning, Monte Carlo Tree Search and Asynchronous Advantage Actor-Critic (A3C). We compare to a Gaussian process based supervised learning approach and discuss the relation of our approach to manually constructed, state-of-the-art methods from forest wildfire modelling. We also discuss the relation of our approach to manually constructed, state-of-the-art methods from forest wildfire modelling. We validate our approach with satellite image data of two massive wildfire events in Northern Alberta, Canada, the Fort McMurray fire of 2016 and the Richardson fire of 2011. The results show that we can learn predictive, agent-based policies as models of spatial dynamics using RL on readily available satellite images that other methods and have many additional advantages in terms of generalizability and interpretability.
PAC Optimal MDP Planning with Application to Invasive Species Management

Majid Alkaee Taleghan, Thomas G. Dietterich, Mark Crowley, Kim Hall, and H. Jo Albers.

Journal of Machine Learning Research. 16, 2015.

Abs URL

In a simulator-defined MDP, the Markovian dynamics and rewards are provided in the form of a simulator from which samples can be drawn. This paper studies MDP planning algorithms that attempt to minimize the number of simulator calls before terminating and outputting a policy that is approximately optimal with high probability. The paper introduces two heuristics for efficient exploration and an improved confidence interval that enables earlier termination with probabilis- tic guarantees. We prove that the heuristics and the confidence interval are sound and produce with high probability an approximately optimal policy in polynomial time. Experiments on two benchmark problems and two instances of an invasive species management problem show that the improved confidence intervals and the new search heuristics yield reductions of between 8% and 47% in the number of simulator calls required to reach near-optimal policies.
Using equilibrium policy gradients for spatiotemporal planning in forest ecosystem management

markcrowley.

IEEE Transactions on Computers. 63, (1). IEEE computer Society Digital Library. IEEE Computer Society., 2014.

Abs URL

Spatiotemporal planning involves making choices at multiple locations in space over some planning horizon to maximize utility and satisfy various constraints. In Forest Ecosystem Management, the problem is to choose actions for thousands of locations each year including harvesting, treating trees for fire or pests, or doing nothing. The utility models could place value on sale of lumber, ecosystem sustainability or employment levels and incorporate legal and logistical constraints on actions such as avoiding large contiguous areas of clearcutting. Simulators developed by forestry researchers provide detailed dynamics but are generally inaccesible black boxes. We model spatiotemporal planning as a factored Markov decision process and present a policy gradient planning algorithm to optimize a stochastic spatial policy using simulated dynamics. It is common in environmental and resource planning to have actions at different locations be spatially interelated, this makes representation and planning challenging. We define a global spatial policy in terms of interacting local policies defining distributions over actions at each location conditioned on actions at nearby locations. Markov chain Monte Carlo simulation is used to sample landscape policies and estimate their gradients. Evaluation is carried out on a forestry planning problem with 1,880 locations using a variety of value models and constraints. Index
PAC Optimal Planning for Invasive Species Management: Improved Exploration for Reinforcement Learning from Simulator-Defined MDPs

Thomas G Dietterich, Majid Alkaee Taleghan, and Mark Crowley

In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI-2013). Bellevue, WA, USA. 2013.

Abs URL

Often the most practical way to define a Markov Decision Process (MDP) is as a simulator that, given a state and an action, produces a resulting state and immediate reward sampled from the corresponding distributions. Simulators in natural resource management can be very expensive to execute, so that the time required to solve such MDPs is dominated by the number of calls to the simulator. This paper presents an algorithm, DDV, that combines improved confidence intervals on the Q values (as in interval estimation) with a novel upper bound on the discounted state occupancy probabilities to intelligently choose state-action pairs to explore. We prove that this algorithm terminates with a policy whose value is within εof the optimal policy (with probability 1−δ) after making only polynomially-many calls to the simulator. Experiments on one benchmark MDP and on an MDP for invasive species management show very large reductions in the number of simulator calls required.
Policy Gradient Optimization Using Equilibrium Policies for Spatial Planning Domains

markcrowley.

In 13th INFORMS Computing Society Conference. Santa Fe, NM, United States. 2013.
Managing Invasive Species in a River Network

Kim Hall, Majid Alkaee Taleghan, Heidi J. Albers, Thomas Dietterich, and Mark Crowley

In Third International Conference on Computational Sustainability. Copenhagen, Denmark. 2012.

Abs URL

There are many pest species that invade valuable ecosystems and damage ecosystem services. An important management goal is to limit the spread of these species or even eradicate them. From the computational perspective, these problems can be formulated as Markov Decision Processes. However, solving them is difficult, because of their spatial nature. Viewed abstractly, the current state of the ecosystem can be formalized as a graph. Each node of the graph may be invaded or not, and at each time step, a “local” action must be selected at each node. Consequently, at the level of the whole MDP, each global action is a vector of local actions of length N, the number of nodes in the graph. The exponentially large action space raises major computational problems. During the state transitions, the invasive species can spread along the edges of the graph. We study a specific instance of this general problem based on the spread of Tamarisk in river networks. In this formulation, we work with the dual of the standard river network graph. Each node corresponds to a stretch of the river between two confluences (also called a “reach”). We divide each reach into H “slots”, where each slot can either be occupied by a single native tree, occupied by a single Tamarisk tree, or empty. In each time step, the plants (both native and invader) first must survive through winter (with some probability). Then, the surviving trees produce seeds that disperse through the river network according to a dispersal kernel that prefers downstream movement with high probability. Each dispersing seed lands at some slot in some node of the network. All seeds arriving at a slot compete to establish themselves in that slot (if the slot is empty). In our model, there are three local actions: simple eradication of invasive plants, eradication followed by planting of native plants, or doing nothing at all. Doing nothing costs nothing, while eradication is more expensive, and eradication plus planting is the most expensive. One local action must be chosen for each node (reach) at each time step, and it applies to all H slots at that node. The actions only succeed stochastically. The planning goal is to minimize the expected discounted sum of the cost of invasive damage and the cost of management actions. To solve this planning problem, we apply the standard value iteration algorithm. However, standard value iteration requires a fully-specified state transition matrix. In our problem, it is easy to write a simulator for drawing samples of the dispersal and competition processes, but it is computationally intractable to compute the exact transition probabilities. Hence, we estimate those probabilities by drawing a large number of samples from the simulator. Once we have an optimal policy on the approximated MDP, we explore its behaviour both directly and via simulated rollouts. The optimal policy can be visualized with one picture per state annotated by the types of plants in each reach and the optimal action that should be taken in each reach. We also run the optimal policy forward in time on many simulated trajectories in order to gather statistics about its behaviour such as: how long it takes to reach a steady state, average cost of a policy over time, or the frequency with which completely invaded or uninvaded states are reached. Comparisons of these statistics show that in many situations our optimal policies greatly outperform established rules of thumb from the literature. An example of a rule of thumb is to always prioritize treatment of upstream over downstream reaches. Another rule targets the most invaded reaches (those with the most slots occupied by Tamarisk) first. We have found that the optimality of these rules of thumb depends strongly on the dispersal and competition parameters. Some contributions this work makes to bioeconomics and ecology are showing evidence that the stochastic spread of the invasion process needs to be modelled and that the spatial characteristics of the system under invasion are relevant to optimal management. The computational challenges raised by this problem have led us into research on methods for planning that can provide bounds on the optimality of the policy while minimizing the number of calls to expensive simulators. We are also studying algorithms that can scale to large graphs with thousands of nodes and large out-degrees. Finally, we see potential in these problems for intelligently reducing the size of the state space and the complexity of the policy description by utilizing domain knowledge.
phd-thesis

Equilibrium Policy Gradients for Spatiotemporal Planning

markcrowley.

UBC Library, Vancouver, BC, Canada.. 2011.

Abs PDF URL

In spatiotemporal planning, agents choose actions at multiple locations in space over some planning horizon to maximize their utility and satisfy various constraints. In forestry planning, for example, the problem is to choose actions for thousands of locations in the forest each year. The actions at each location could include harvesting trees, treating trees against disease and pests, or doing nothing. A utility model could place value on sale of forest products, ecosystem sustainability or employment levels, and could incorporate legal and logistical constraints such as avoiding large contiguous areas of clearcutting and managing road access. Planning requires a model of the dynamics. Existing simulators developed by forestry researchers can provide detailed models of the dynamics of a forest over time, but these simulators are often not designed for use in automated planning. This thesis presents spatiotemoral planning in terms of factored Markov decision processes. A policy gradient planning algorithm optimizes a stochastic spatial policy using existing simulators for dynamics. When a planning problem includes spatial interaction between locations, deciding on an action to carry out at one location requires considering the actions performed at other locations. This spatial interdependence is common in forestry and other environmental planning problems and makes policy representation and planning challenging. We define a spatial policy in terms of local policies defined as distributions over actions at one location conditioned upon actions at other locations. A policy gradient planning algorithm using this spatial policy is presented which uses Markov Chain Monte Carlo simulation to sample the landscape policy, estimate its gradient and use this gradient to guide policy improvement. Evaluation is carried out on a forestry planning problem with 1880 locations using a variety of value models and constraints. The distribution over joint actions at all locations can be seen as the equilibrium of a cyclic causal model. This equilibrium semantics is compared to Structural Equation Models. We also define an algorithm for approximating the equilibrium distribution for cyclic causal networks which exploits graphical structure and analyse when the algorithm is exact.
Seeing the Forest Despite the Trees : Large Scale Spatial-Temporal Decision Making

Mark Crowley, John Nelson, and David Poole.

In Conference on Uncertainty in Artificial Intelligence (UAI09). Montreal, Canada. 2009.

Abs URL

We introduce a challenging real world planning problem where actions must be taken at each location in a spatial area at each point in time. We use forestry planning as the motivating application. In Large Scale Spatial-Temporal (LSST) planning problems, the state and action spaces are defined as the cross-products of many local state and action spaces spread over a large spatial area such as a city or forest. These problems possess state uncertainty, have complex utility functions involving spatial constraints and we generally must rely on simulations rather than an explicit transition model. We define LSST problems as reinforcement learning prob- lems and present a solution using policy gradients. We compare two different policy formulations: an explicit policy that identifies each location in space and the action to take there, and an abstract policy that defines the proportion of actions to take across all locations in space. We show that the abstract policy is more robust and achieves higher rewards with far fewer parameters than the elementary policy. This abstract policy is also a better fit to the properties that practitioners in LSST problem domains require for such methods to be widely useful