Nonmyopic Observation Selection: Theory and Applications

Many practical applications, such as environmental monitoring or placing sensors for event detection, require to select among a set of informative but possibly expensive obser-vations. 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 usually are NP-hard. Previous approaches to observation selection have mainly used myopic heuristics, i.e., approaches which only consider the next best observation to add, without planning ahead for future observation pos-sibilities. 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 proposal, we present a new class of approaches for observation selection, using techniques from combinatorial optimization. We show that many observation selection ob-jectives satisfy submodularity, an intuitive diminishing returns property – adding a sensor to a small deployment helps more than adding it to a large deployment. Our approaches sys