Planning, Executing, Sensing, and Replanning

for Information Gathering?

Craig A. Knoblock

Information Sciences Institute and Department of Computer Science

University of Southern California

4676 Admiralty Way

Marina del Rey, CA 90292

Email: knoblock@isi.edu

To appear in the Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence, Montreal, Canada, 1995.

Abstract

Current specialized planners for query processing are designed to work in local, reliable, and predictable environments. However, a number of problems arise in gathering information from large networks of distributed information. In this environment, the same information may reside in multiple places, actions can be executed in parallel to exploit distributed resources, new goals come into the system during execution, actions may fail due to problems with remote databases or networks, and sensing may need to be interleaved with planning in order to formulate efficient queries. We have developed a planner called Sage that addresses the issues that arise in this environment. This system integrates previous work on planning, execution, replanning, and sensing and extends this work to support simultaneous and interleaved planning and execution. Sage has been applied to the problem of information gathering to provide a flexible and efficient system for integrating heterogeneous and distributed data.

1 Introduction

The task of information gathering requires locating, retrieving, and integrating information from large numbers of distributed and heterogeneous information sources. In this environment, flexibility and efficiency are critical. The usual approach of generating a static plan for processing information and then executing it is inflexible and may be very inefficient if problems arise during query processing. The problem is that there may be many information sources from which to choose, actions may fail, the system has incomplete knowledge about

?The research reported here was supported in part by Rome Laboratory of the Air Force Systems Command and the Advanced Research Projects Agency under Contract Number F30602-91-C-0081, and in part by the National Science Foundation under Grant Number IRI-9313993. The views and conclusions contained in this paper are those of the author and should not be interpreted as representing the official opinion or policy of RL, ARPA, NSF, the U.S. Government, or any person or agency connected with them.

the available information, and new goals may arise at any time.

To address these problems, we have developed a planning system that builds on previous work on planning, execution, sensing, and replanning. The planner, which we call Sage, was implemented by augmenting ucpop [Penberthy and Weld, 1992; Barrett et al., 1993] with the capabilities to produce parallel execution plans [Wilkins, 1984; Knoblock, 1994], interleave planning and execution [Ambros-Ingerson, 1987; Etzioni et al., 1994], support run-time variables for sensing [Ambros-Ingerson, 1987; Etzioni et al., 1992], perform replanning where appropriate, and plan for new goals as they arise. We have integrated all of these capabilities into a single, unified system in which planning, sensing, and replanning can be performed during execution. This allows the system to replan portions of the plan that is currently being executed, receive and plan new tasks within the context of the executing plan, and interleave sensing actions with planning in order to improve efficiency.

Before describing the integration of planning and execution, we first describe the information gathering task and how it can be cast as a planning problem in a general planning framework (Section 2). Next, we present our approach to tightly integrating planning and execution (Section 3). This integration is used to support planning for new goals, replanning for failure, and the interleaving of sensing actions to gather additional information for planning (Section 4). We compare this work to previous work in planning as well as information gathering and query processing (Section 5). Finally, we conclude with a discussion of the contributions of the paper (Section 6).

2 Planning for Information Gathering

Information gathering requires selecting, integrating, and retrieving data from distributed and heterogeneous information sources in order to satisfy a query. The relevant data must be selected from numerous, possibly overlapping or replicated sources. Integrating the information may be costly, especially when combining data from different sites. Retrieving the information may be time consuming due to the distribution of data and the contention for limited resources.
To solve this problem, we have developed a planner