Select Lab Publications

Near-optimal Observation Selection using Submodular Functions (2007)

By: Andreas Krause and Carlos Guestrin

Abstract: AI problems such as autonomous robotic exploration, automatic diagnosis and activity recognition have in common the need for choosing among a set of informative but possibly expensive observations. When monitoring spatial phenomena with sensor networks or mobile robots, for example, we need to decide which locations to observe in order to most effectively decrease the uncertainty, at minimum cost. These problems usually are NP-hard. Many observation selection objectives satisfy submodularity, an intuitive diminishing returns property adding a sensor to a small deployment helps more than adding it to a large deployment. In this paper, we survey recent advances in systematically exploiting this submodularity property to efficiently achieve near-optimal observation selections, under complex constraints. We illustrate the effectiveness of our approaches on problems of monitoring environmental phenomena and water distribution networks.

Download Information
Andreas Krause and Carlos Guestrin (2007). "Near-optimal Observation Selection using Submodular Functions." National Conference on Artificial Intelligence (AAAI), Nectar track. pdf   talk        
BibTeX citation

author = {Andreas Krause and Carlos Guestrin},
title = {Near-optimal Observation Selection using Submodular Functions},
booktitle = {National Conference on Artificial Intelligence (AAAI), Nectar track},
month = {July},
year = {2007},
wwwfilebase = {aaai2007-krause-guestrin},
wwwtopic = {Observation Selection},

full list