Machine Learning Department
School of Computer Science, Carnegie Mellon University
Optimzing Sensing: From Water to the Web
Andreas Krause*, Carlos Guestrin
Such sensing, or active learning, problems are typically NP-hard, and were commonly addressed using heuristics without theoretical guarantees about the solution quality. In this paper, we present algorithms which efficiently find provably near-optimal solutions to large, complex sensing problems. Our algorithms exploit submodularity, an intuitive notion of diminishing returns, common to many sensing problems: the more sensors we have already deployed, the less we learn by placing another sensor. In addition to identifying the most informative sensing locations, our algorithms can handle more challenging settings, where sensors need to be able to reliably communicate over lossy links, where mobile robots are used for collecting data or where solutions need to be robust against adversaries and sensor failures.
We also present results applying our algorithms to several real-world sensing tasks, including environmental monitoring using robotic sensors, activity recognition using a built sensing chair, a sensor placement challenge, and deciding which blogs to read on the web.
*Division of Engineering and Applied Science, California Institute of Technology, Pasadena, CA
||SCS Technical Report Collection
School of Computer Science homepage
This page maintained by firstname.lastname@example.org