When monitoring spatial phenomena selecting the best locations for sensors is a fundamental task. To avoid strong assumptions, such as fixed sensing radii, and to tackle noisy measurements, Gaussian processes (GPs) are often used to model the underlying phenomena. A commonly used placement strategy is to select the locations that have highest entropy with respect to the GP model. Unfortunately, this criterion is indirect, since prediction quality for unsensed positions is not considered, and thus suboptimal positions are often selected. In this paper, we propose a mutual information criterion that chooses sensor locations that most reduce uncertainty about unsensed locations. We first show that choosing a set of k sensors that maximizes the mutual information is NP-complete. By exploiting the submodularity of mutual information we propose a polynomial-time algorithm that guarantees a placement within (1 − 1/e) of the maxima. This algorithm is extended to exploit local structure in the Gaussian process, significantly improving performance. Finally, we show that the sensor placements chosen by our algorithm can lead to significantly better predictions through extensive experimental validation on two real-world datasets.

13 pages

Return to: SCS Technical Report Collection
School of Computer Science homepage

This page maintained by reports@cs.cmu.edu