Robust Sensor Placements and Submodular Functions

In this talk, we tackle a fundamental problem that arises when using sensors to monitor the ecological condition of rivers and lakes, the network of pipes that bring water to our taps, or the activities of an elderly individual when sitting on a chair: Where should we place the sensors in order to make effective and robust predictions?

Optimizing the informativeness of the observations collected by the sensors is an NP-hard problem, even in the simplest settings. We will first identify a fundamental property of sensing tasks, submodularity, an intuitive diminishing returns property. By exploiting submodularity, we develop effective approximation algorithms for the placement problem which have strong theoretical guarantees in terms of the quality of the solution. These algorithms address settings where, in addition to sensing, nodes must maintain effective wireless connectivity, the data may be collected by mobile robots, or we seek to have solutions that are robust to adversaries.

We demonstrate our approach on several real-world settings, including data from real deployments, from a built activity recognition chair, and from a sensor placement competition.

This talk is primarily based on joint work with Andreas Krause.

Speaker Details

Carlos Guestrin’s current research spans the areas of planning, reasoning and learning in uncertain dynamic environments, focusing on applications in sensor networks. He is an assistant professor in the Machine Learning and in the Computer Science Departments at Carnegie Mellon University. Previously, he was a senior researcher at the Intel Research Lab in Berkeley. Carlos received his MSc and PhD in Computer Science from Stanford University in 2000 and 2003, respectively, and a Mechatronics Engineer degree from the Polytechnic School of the University of Sao Paulo, Brazil, in 1998. Carlos Guestrin received best paper awards at the Knowledge Discovery and Data Mining (KDD-2007), the Information Processing in Sensor Networks (IPSN) in 2005 and 2006, the Very Large Data Bases (VLDB-2004), and the Neural Information Processing Systems (NIPS-2003) conferences, runner-up best paper awards at the Uncertainty in Artificial Intelligence (UAI-2005) and Machine Learning (ICML-2005) conferences, and the 2007 IJCAII-JAIR Best Paper prize in the Journal of Artificial Intelligence Research (JAIR). He is also a recipient of the NSF Career Award, Alfred P. Sloan Fellowship, IBM Faculty Fellowship, the Siebel Scholarship and the Stanford Centennial Teaching Assistant Award.

Date:
Speakers:
Carlos Guestrin
Affiliation:
Computer Science Departments at Carnegie Mellon University

    • Portrait of Jeff Running

      Jeff Running