Center for Automated Learning and Discovery
School of Computer Science, Carnegie Mellon University


Near-Optimal Sensor Placements in Gaussian Processes

Carlos Guestrin, Andreas Krause, Ajit Singh

June 2005


Also appears as Computer Science Department
Technical Report CMU-CS-05-120

Keywords: Gaussian processes, experimental design, active learning, spatial learning, sensor networks

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

SCS Technical Report Collection
School of Computer Science homepage

This page maintained by