Many practical applications, such as environmental monitoring or placing sensors for event detection, require to select 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 are usually NP-hard. Previous approaches for tackling these sensing problems have mainly relied on myopic heuristics, i.e., approaches which only consider the next best observation to add, without planning ahead for future sensing opportunities. For those approaches, typically no performance guarantees are known. Existing nonmyopic approaches have involved computationally intensive techniques which are very difficult to scale to larger problems.

In this Thesis, we present a new class of approaches for observation selection, using techniques from combinatorial optimization. We show that 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. Examples include mutual information for spatial prediction and placing sensors for outbreak detection.

We also develop a suite of non-greedy approaches that systematically exploit this submodularity property in order to efficiently obtain provably near-optimal solutions to complex sensing problems. For example, the chosen observations often need to be robust against sensor failure or uncertainty about model parameters. Examples include minimizing the maximum posterior variance in spatial prediction and robust experimental design. We show, that many such problems require the optimization of an adversarially chosen submodular objective function. We will demonstrate that for this problem, existing greedy algorithms perform arbitrarily badly. We develop an algorithm, SATURATE, which performs near-optimally in this setting.

In addition to the problem of finding the best k observations (sensor locations), we consider problems with complex combinatorial constraints. For example, when placing wireless sensor networks, the chosen locations should not only be very informative, but also allow efficient communication. When using robots for making observations, the chosen locations need to lie on a collection of paths. We present PSPIEL, an efficient algorithm which finds solutions which near-optimally trade off sensing quality and cost.

When deploying wireless sensor networks, another fundamental constraint is battery lifetime. Since every measurement draws power, sensors can typically be activated only a fraction of the time. Hence, the problem of scheduling the sensors becomes of crucial importance. Traditionally, sensor placement and scheduling have been considered separately from each other. In this Thesis, we present ESPASS, an efficient algorithm for simultaneously optimizing the placement and scheduling. We show that this simultaneous approach leads to drastic improvements in network lifetime when compared to the traditional, stage-wise approach.

A key question in many observation selection problems is how much better a sequential algorithm, which decides on the next observation based on previous observations, can perform when compared to the best fixed set of observations chosen a priori. We present a partial answer to the question for spatial prediction in Gaussian Processes. We develop a theoretical bound quantifying the gap between the best sequential and a priori selections, and use it to develop an exploration-exploitation approach for active learning in Gaussian Processes.

Lastly, we look beyond submodular observation selection problems, and consider the problem of selecting optimal observations in graphical models. We show that in chain-graphical (Markovian) models, it is possible to efficiently find the optimal sequential policy. However, even for slightly larger classes of graphical models, we prove strong hardness results.

In addition to providing algorithms and theoretical analyses, we present extensive empirical evaluation of our approaches on several real-world case studies. These include building a sensing chair for posture recognition, monitoring environmental phenomena with mobile robots, securing municipal water distribution networks, and selecting informative weblogs to read on the Internet.

342 pages

Return to: SCS Technical Report Collection
School of Computer Science

This page maintained by reports@cs.cmu.edu