Robust Sensor Placements and Submodular Functions

Опубликовано 6 сентября 2016, 16:42

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.