Reflections on Professor Bistra Dilkina’s MD4SG Talk: Combinatorial Optimization for Wildlife Planning
This post is a summary of a recent MD4SG talk by Professor Bistra Dilkina, Associate Professor of Computer Science at the University of Southern California and Co-Director of the Center for AI in Society (CAIS). This blog series represents our members’ reflections on the monthly MD4SG Colloquium on different topics related to mechanism design and access to opportunity.
There’s little doubt of the epochal changes we are living through and the challenges we face to conserve biodiversity. Anthropogenic pressures have had an unprecedented impact on the planet — the biomass of land mammals has reduced to a mere 4%; 10–40% of animal and plant species are threatened with extinction, with millions of cases still undocumented; the average surface temperature of the earth has increased by 1.4 degrees Fahrenheit over the past century. The mounting evidence calls for action to address the loss of biodiversity and climate change — and to seek tangible ways of achieving the at times nebulous goals of sustainable development.
Despite extensive research on biodiversity conservation, the use of AI to inform research and decisions-making is not yet commonplace. On October 30th, 2020, the MD4SG Environment and Climate working group had the privilege of hosting an invited talk by Professor Bistra Dilkina. Dilkina presented her research using AI technologies to guide wildlife conservation policy, with a focus on combating climate and conservation concerns.
Dilkina started her PhD with Professor Carla Gomes at Cornell University, where she was planning to work on improving combinatorial algorithms and tackling NP-hard problems. During the second year of her graduate studies, Dilkina became interested in seeking intellectual satisfaction in a domain that combined her interest in nature and wildlife. She was ecstatic to learn that she could look at the same algorithmic problems from the lens of conservation planning and sustainability, finding synergies between ecology and computer science. Around the same time, Gomes had received an NSF grant to start the Institute for Computational Sustainability, an interdisciplinary initiative that helped pioneer the field of computational sustainability.
Connectivity in Conservation
In her talk, Dilkina highlighted the importance of landscape connectivity as an emerging priority for conservation — critical for maintaining genetic diversity and ecosystem resilience. Ecologists increasingly believe that creating islands of protected habitat among already-developed landscapes is detrimental for the persistence of animals who need wildlife corridors (connections between habitat fragments to allow animal movement) to ride out environmental disturbances, find resources, and breed across landscapes.
One way ecologists model landscape connectivity is to think of the landscape as a graph, where each node on the graph is associated with the movement cost — i.e., how difficult it may be for the animal species to move and cross over. For instance, ecologists routinely gather observations on presence and movement of species using camera traps and GPS collars, among others. This data, when correlated with environmental and anthropogenic factors such as elevation, land cover, and distance from human settlements, sheds light on which factors impact the ability of species to move. Each node can therefore be associated with a resistance or movement cost. Connectivity between two locations is then measured as the length of resistance-weighted shortest path, assuming the species is likely to travel through nodes with least resistance. Such paths are called the wildlife corridors.
However, not all landscapes are equally costly for the government to conserve. It is therefore important to have cost-effective solutions for the conservation planning problem. Given that the government has a limited budget, how can we find wildlife corridors that connect each pair of core areas, that minimize species movement resistance while satisfying the budget constraint? The California Essential Habitat Connectivity Project had already identified large remaining chunks of important natural landscape or core areas for movement of species across California. However, their model is based only on ecological benefits without taking into account economic costs of such decisions. That is, there may be corridors that are only slightly longer but a lot more economically viable. Another consideration Dilkina highlighted is robustness — ensuring multiple, disjoint paths between core areas. Preserving a single link between core areas can be precarious due to environmental perturbations such as wildfires and other calamities, creating a pressing need for robustness.
Dilkina’s research translates the conservation planning problem into a graph optimization problem. This graph problem can be formulated into mixed integer linear programming (MILP). Although the problem is NP-hard, we can leverage efficient solvers to find optimal solutions with some guarantees. One major challenge is to find and construct datasets for the input of the model. For example, where do the land conservation costs come from? Interestingly, Dilkina’s team estimated the costs based on tax-records for public and private properties, which are publically available, and information on conserved land. Another challenge is choosing the right resolution in terms of the number of nodes in the graph. For instance, increasing resolution from 1 km sq. to 200 m sq. results in an explosion in the number of nodes in the graph. Also, as the number of target species increases, the MILP becomes increasingly difficult to solve.
Application to grizzlies and wolverines in the Northern Rockies
Dilkina’s team spent a significant amount of time working with domain experts so that the model can be applied to solve a large-scale real-world network design problem. Specifically, her team studied the conservation of wolverine and grizzly bear populations in the U.S. Rocky Mountains (Montana). Although both species are listed as least-concern by the International Union for Conservation of Nature, their natural habitat has shrunk significantly. The species exhibit different sensitivities to land characteristics and thereby different movement costs and requirements. Grizzly bears are able to travel large distances and thrive in a wide-array of habitats. Their high-resistance areas include human settlements. Wolverines are small versatile predators, reputed for their ferocity and strength. They prefer snow-covered steep alpine mountain regions. The problem then translates to: given these two species with their respective movement costs and core areas, compute the optimal solution for a fixed budget for core area pairs of both species.
When Dilkina and her team only optimized with the objective to minimize ecological resistance, they ended up with solutions that have very low resistance but high costs (~$32 million). On the other end of the spectrum, when economic costs were solely prioritized ignoring resistances, there was a 10-fold decrease in cost (~$3 million). This implies drastic differences between ecological and economical optimality. For exposition, setting the budget for 4.5 million achieved a connectivity close to the best ecological plan. Therefore, marginal increases in overall budget (beyond the minimum) can have great ecological returns. They also found that jointly optimizing for both species (versus separate spending on each) can result in improved outcomes for both species. It is therefore crucial for the decision-making process to allow for systematic analyses of trade-offs between environmental and economic variables.
Research challenges
Landscape connectivity and environmental sustainability are topics that are close to the heart of the MD4SG Environment and Climate working group. We are a group of disciplinary and geographically diverse researchers studying how computational methods can help address environmental challenges, particularly those that exacerbate the climate crisis.
In her talk, Dilkina presented the problem of designing conservation strategies for endangered species. The goal is to use limited economic resources in the most effective way using systematic budget-constrained conservation planning. This work opens up several follow-up questions that are of interest to the MD4SG community:
- How does this framework capture stochastic dispersal of species? For instance, when there are probabilities of dispersal from one location to another in highly variable environments?
- How to incorporate components beyond habitat and economic costs, e.g. impact on local communities?
- How is decision-making impacted by dynamic changes such as- availability of parcels for purchase?
- What other data sources can be used as a surrogate for approximating landscape costs in addition to tax assessor data?
- What new algorithmic approaches would allow further scaling up of the results?
Our working group is currently considering theoretical and practical approaches to some of these questions, which we hope to further explore in our work/conversations. We welcome thoughts and suggestions!
Written by Harman Jaggi on behalf of the MD4SG Environment and Climate Working Group. This is part of an ongoing conversation within the MD4SG Environment and Climate Working Group — if you would like to join this conversation, please feel free to reach out to us at organizers@md4sg.com.
References:
- Bar-On, Yinon M., Rob Phillips, and Ron Milo. “The biomass distribution on Earth.” Proceedings of the National Academy of Sciences 115, no. 25 (2018): 6506–6511.
- https://ipbes.net/global-assessment
- Global Climate Change Indicators, National Centers for Environmental Information.
- Le Bras, R., Dilkina, B., Xue, Y., Gomes, C. P., McKelvey, K. S., Schwartz, M. K., & Montgomery, C. A. (2013). Robust network design for multispecies conservation. In Proceedings of the Twenty-Seventh AAAI Conference on Artificial Intelligence. 27: 1305–1312. (pp. 1305–1312).
- Dilkina, Bistra, Rachel Houtman, Carla P. Gomes, Claire A. Montgomery, Kevin S. McKelvey, Katherine Kendall, Tabitha A. Graves, Richard Bernstein, and Michael K. Schwartz. “Trade‐offs and efficiencies in optimal budget‐constrained multispecies corridor networks.” Conservation Biology 31, no. 1 (2017): 192–202.
