Alexandra Meliou and Andreas Krause and Carlos Guestrin and Joseph M. Hellerstein

EECS Department, University of California, Berkeley

Technical Report No. UCB/EECS-2007-44

April 18, 2007

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2007/EECS-2007-44.pdf

In many sensing applications, like environmental monitoring, we must continuously gather information in order to provide a good estimate of the state of the environment at every point in time. A robot may tour an environment, 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. When users issue queries, they have certain expectations on the answer quality. Thus, we must optimize the tours in order 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 guarantees provide good solutions. In this paper, we present a new efficient algorithm, exploiting dynamic programming and submodularity of the information being 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 provides strong theoretical guarantees about the solution, based on the properties of the single step approach. We also provide an extensive empirical analysis demonstrating the benefits of nonmyopic planning in two real world sensing applications.

---

BibTeX citation:

@techreport{Meliou:EECS-2007-44,
    Author= {Meliou, Alexandra and Krause, Andreas and Guestrin, Carlos and Hellerstein, Joseph M.},
    Title= {Nonmyopic Informative Path Planning in Spatio-Temporal Models},
    Year= {2007},
    Month= {Apr},
    Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2007/EECS-2007-44.html},
    Number= {UCB/EECS-2007-44},
    Abstract= {In many sensing applications, like environmental monitoring, we must continuously gather information in order to provide a good estimate of the state of the environment at every point in time. A robot may tour an environment, 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. When users issue queries, they have certain expectations on the answer quality. Thus, we must optimize the tours in order 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 guarantees provide good solutions. In this paper, we present a new efficient algorithm, exploiting dynamic programming and submodularity of the information being 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 provides strong theoretical guarantees about the solution, based on the properties of the single step approach. We also provide an extensive empirical analysis demonstrating the benefits of nonmyopic planning in two real world sensing applications.},
}

EndNote citation:

%0 Report
%A Meliou, Alexandra 
%A Krause, Andreas 
%A Guestrin, Carlos 
%A Hellerstein, Joseph M. 
%T Nonmyopic Informative Path Planning in Spatio-Temporal Models
%I EECS Department, University of California, Berkeley
%D 2007
%8 April 18
%@ UCB/EECS-2007-44
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2007/EECS-2007-44.html
%F Meliou:EECS-2007-44