Select Lab Publications

Near-optimal Sensor Placements in Gaussian Processes (2005)

By: Carlos Guestrin, Andreas Krause, and Ajit Singh

Abstract: When monitoring spatial phenomena, which are often modeled as Gaussian Processes (GPs), choosing sensor locations is a fundamental task. A common strategy is to place sensors at the points of highest entropy (variance) in the GP model. We propose a mutual information criteria, and show that it produces better placements. Furthermore, we prove that finding the configuration that maximizes mutual information is NP-complete. To address this issue, we describe a polynomial-time approximation that is within (1 - 1/e) of the optimum by exploiting the submodularity of our criterion. This algorithm is extended to handle local structure in the GP, yielding significant speedups. We demonstrate the advantages of our approach on two real-world data sets.

Download Information
Carlos Guestrin, Andreas Krause, and Ajit Singh (2005). "Near-optimal Sensor Placements in Gaussian Processes." International Conference on Machine Learning (ICML). Winner of the Best Paper Runner-up Award. pdf long talk poster  
BibTeX citation

author = {Carlos Guestrin and Andreas Krause and Ajit Singh},
title = {Near-optimal Sensor Placements in {G}aussian Processes},
booktitle = {International
Conference on Machine Learning (ICML)},
month = {August},
year = {2005},
wwwfilebase = {icml2005-guestrin-krause-singh},
wwwtopic = {Observation Selection},
wwwaward = {Winner of the Best Paper Runner-up Award}

full list