Another experiment was performed, where the algorithms at each round attempt to recommend some
patches for conservation. However, these recommendations may fail (that is, cannot be implemented due
to external constraints). Here failures were considered that happen randomly, with probability 0.5
independently for each patch. Figure 4 (right) presents the result of this experiment. Here the dynamic
approaches achieved much better performance than
the static baseline. The reason for this is that the
dynamic approaches are able to substitute an
``important” failed selection by a similar alternative
that becomes available in a later round.
Running time for the optimization is less than 2
seconds for a typical problem instance on a standard
MacBook Pro with 2. 2 GHz and 8 GB RAM, enabling
near-real-time decision support. The implementation
is interactive: it allows to easily modify parameters,
incorporate constraints such as unavailability of certain patches, carry out the optimization and visualize
Conclusions and Discussion
Sequential decision making under uncertainty is a
central, yet notoriously hard problem in computational sustainability and AI more generally. In this
article, we have reviewed the structural property of
adaptive submodularity, which generalizes the classical notion of submodular set functions to planning
problems. For problems that exhibit this problem
structure, simple, efficient greedy policies are provably near-optimal. We have illustrated the concept
on two applications of relevance to computational
sustainability: collecting information in order to
make effective decisions, and protecting rare species
by recommending patches of land for conservation.
The latter case study is carried out in collaboration
with the USGS Patuxent Wildlife Research Center
and the U.S. Fish and Wildlife Service. Here, our
adaptive submodularity approach enables near-real
time interactive decision support with provable quality guarantees.
There are several interesting questions for future
work. First, in our value of information study, we
have shown how it is possible to construct adaptive
submodular surrogate functions even for problems
that are not submodular if considered naively. Are
there general principles for how such surrogate functions can be constructed for other applications? Second, we have shown how some results can be lifted
from classical submodular optimization to sequential
decision making. Are there more results that carry
over to this more challenging setting? Last, we have
sketched two applications relevant to the field of
computational sustainability. Given that sequential
decision making is a core challenge in this area and
AI more broadly, are there other natural applications
that can be addressed using this framework?
This research was partially supported by ONR grant
N00014-09-1-1044, NSF grants CNS-0932392 and
IIS-0953413, ERC StG 307036, the Caltech Center for
the Mathematics of Information, a Microsoft
Research Faculty Fellowship and by the U.S. Fish and
Wildlife Service. We thank J. Bakker, J. Bush, M.
Jensen, T. Kaye, J. Kenagy, C. Langston, S. Pearson,
M. Singer, D. Stinson, D. Stokes, T. Thomas, B. Gardner, S. Morey, I. Bogunovic, D. Ray, and C. Camerer
for their contributions.
1. This case study was first published by Golovin, Krause,
and Ray (2010).
2. This study was originally published by Golovin et al.
3. See also www.helsinki.fi/bioscience/consplan/software/
Ball, I.; Possingham, H.; and Watts, M. 2009. Marxan and
Relatives: Software for Spatial Conservation Prioritisation.
In Spatial Conservation Prioritisation: Quantitative Methods
and Computational Tools, ed. A. Moilanen, K. A. Wilson, H.
Possingham. Oxford, UK: Oxford University Press.
Golovin, D., and Krause, A. 2011. Adaptive Submodularity:
Theory and Applications in Active Learning and Stochastic
Optimization. Journal of Artifcial Intelligence Research 42:
Golovin, D.; Krause, A.; and Ray, D. 2010. Near-Optimal
Bayesian Active Learning with Noisy Observations. In
Advances in Neural Information Processing Systems 23: Proceedings of the 24th annual Conference on Neural Information
Processing Systems 2010, ed. J. Lafferty, C. K. I. Williams, J.
Shawe-Taylor, S. Zemel, and A. Culotta, 766–774. Red Hook,
NY: Curran Associates, Inc.
Golovin, D.; Krause, A.; Gardner, B.; Converse, C.; and
Morey, S. 2011. Dynamic Resource Allocation in Conservation Planning. In Proceedings of the Twenty-Fifth AAAI Conference on Artifcial Intelligence. Menlo Park, CA: AAAI Press.
Hanski, I. A.; Moilanen, A.; Pakkala, T.; and Kuussaari, M.
1996. The Quantitative Incidence Function Model and Persistence of an Endangered Butterfly Metapopulation.
Conservation Biology 10( 2): 578–590. dx.doi.org/10.1046/j.1523-
Howard, R. A. 1966. Information Value Theory. IEEE Transactions on Systems Science and Cybernetics 2( 1): 22–26.
Krause, A., and Golovin, D. 2014. Submodular Function
Maximization. In Tractability: Practical Approaches to Hard
Problems, ed. L. Bordeaux, Y. Hamadi, and Pushmeet Kohli.
New York: Cambridge University Press.
Krause, A., and Guestrin, C., 2009. Optimal Value of Information in Graphical Models. Journal of Artifcial Intelligence
Research 35: 557–591.
Leskovec, J.; Krause, A.; Guestrin, C.; Faloutsos, C.; Van-
Briesen, J.; and Glance, N. 2007. Cost-Effective Outbreak
Detection in Networks. In Proceedings of the 13th ACM
SIGKDD International Conference on Knowledge Discovery and