language: en

Information Gathering Plans With Sensing Actions

Naveen Ashish and Craig A. Knoblock Alon Levy
Information Sciences Institute and AT&T Bell Laboratories Department of Computer Science AI Principles Research Dept.
University of Southern California
600 Mountain Ave., Room 2A-440 4676 Admiralty Way Murray Hill, NJ 07974 Marina del Rey, CA 90292
levy@research.att.com fashish,knoblockg@isi.edu

Abstract Information gathering agents can automate the task of retrieving and integrating data from a large number of diverse information sources. The key issue in their performance is efficient query planning that minimizes the number of information sources used to answer a query. Previous work on query planning has considered generating information gathering plans solely based on compile-time analysis of the query and the models of the information sources. We argue that at compile-time it may not be possible to generate an efficient plan for retrieving the requested information because of the large number of possibly relevant sources. We describe an approach that naturally extends query planning to use run-time information to optimize queries that involve many sources. First, we describe an algorithm for generating a discrimination matrix, which is a data structure that identifies the information that can be sensed at run-time to optimize a query plan. Next, we describe how the discrimination matrix is used to decide which of the possible run-time sensing actions to perform. Finally, we demonstrate that this approach yields significant savings (over 90% for some queries) in a real-world task.

[The first and second authors is supported in part by Rome Laboratory of the Air Force Systems Command and the Advanced Research Projects Agency under contract no. F30602-94-C-0210, and in part by the National Science Foundation under grant number IRI-9313993. The views and conclusions contained in this paper are the author's and should not be interpreted as representing the official opinion or policy of ARPA, RL, NSF, AT&T Labs, or any person or agency connected with them.]