In many sensing applications we must continuously gather in- formation to provide a good estimate of the state of the envi- ronment at every point in time. A robot may tour an environ- ment, gathering information every hour. In a wireless sensor network, these tours correspond to packets being transmitted. In these settings, we are often faced with resource restrictions, like energy constraints. The users issue queries with certain expectations on the answer quality. Thus, we must optimize the tours to ensure the satisfaction of the user constraints, while at the same time minimize the cost of the query plan. For a single timestep, this optimization problem is NP-hard, but recent approximation algorithms with theoretical guaran- tees provide good solutions. In this paper, we present a new efficient nonmyopic greedy algorithm, exploiting submodu- larity of the information collected, that efficiently plans data collection tours for an entire (finite) horizon. Our algorithm can use any single step procedure as a black box, and, based on its properties, provides strong theoretical guarantees for the solution. We also provide an extensive empirical analysis demonstrating the benefits of nonmyopic planning in a real world sensing application.

@inproceedings{meliou07nonmyopic,
	author = {Alexandra Meliou and Andreas Krause and Carlos Guestrin and Joseph M. Hellerstein},
	booktitle = {Conference on Artificial Intelligence (AAAI)},
	month = {July},
	title = {Nonmyopic Informative Path Planning in Spatio-Temporal Models},
	year = {2007}}