Computer Science Department of Carnegie Mellon University
Talk
Andreas Krause received his Diplom in Computer Science and Mathematics from
the Technische Universität München. He currently is a Ph.D.
candidate at the Computer Science Department of Carnegie Mellon University,
advised by Prof. Carlos Guestrin. His research interests include machine
learning and probabilistic reasoning both in theory and applications, with a
focus on value of information problems arising in large distributed systems
such as sensor networks. His work received awards at several conferences
(KDD '07, IPSN '06, ICML '05, UAI '05).
When using networks of static and mobile sensors to monitor spatial
phenomena, such as the ecological condition of rivers and lakes, selecting
the most informative locations to observe is a fundamental task. Often,
observations are expensive, measured, e.g., in the cost or duration of an
experiment. In addition to the experimental cost, often complex constraints
are associated with the observation selection. When placing a network of
wireless sensors for example, the sensors need to be able to reliably
communicate over lossy links, constraining their locations not to be too far
apart. When using mobile robots for making observations, the chosen
locations have to lie on paths, which are each bounded by fuel or time
constraints.
Optimizing the informativeness of observations under such constraints is an
NP-hard problem. Myopic (greedy) approaches, which are commonly used for
selecting informative observations, do not perform well when such complex
constraints are present. In this talk, I will present nonmyopic approaches
for selecting observations under such complex constraints, and present
algorithms with strong theoretical guarantees, as well as empirical evidence
about their effectiveness on several real-world monitoring problems.