page 2  (8 pages)
to previous section1
3to next section

called Sage that builds on the ucpop partial-order planner [Barrett et al., 1993]. ucpop provides an expressive operator language that includes conjunction, negation, disjunction, existential and universal quantifiers, conditional effects, and a functional interface that allows preconditions to be implemented as Lisp functions. We extended this planner to support simultaneous action execution and to tightly integrate planning and execution. The execution is presented in the next section, and the support for simultaneous actions was previously addressed in [Knoblock, 1994] and will be briefly described here.

Partial-order planners, such as ucpop, produce plans with actions that are unordered. However, if two actions are left unordered they can be executed in either order, but not simultaneously. To execute actions in parallel in a partial-order planner requires that (1) actions can be executed simultaneously without changing the outcome of the individual actions, and (2) any potential resource conflicts must be captured in the representation of the operators in order to avoid conflicts during execution. We assume that the first condition holds (as it does in the information gathering domain described below) and we extended the planner to support the second condition. To support reasoning about resources, we added an explicit resource declaration to the action language, which describes the resources required when executing an action. We also augmented the planner to identify and remove potential resource conflicts. With these extensions, any actions left unordered in the final plan can be executed simultaneously.

In the remainder of this section we describe how the information gathering task is cast as a planning problem in Sage. This problem requires producing a plan for generating a requested set of data. This involves selecting the sources for the data, the operations for processing the data, the sites where the operations will be performed, and the order in which to perform the operations. Since data can be retrieved from multiple sources and the operations can be performed in a variety of orders, the space of possible plans is large.

An information gathering goal consists of a description of a set of desired data as well as the location where that data is to be sent. For example, Table 1 illustrates a goal which specifies that the set of data be sent to the output device of the sims information mediator [Arens et al., 1993; Knoblock et al., 1994]. The goal also specifies the data to be retrieved and is defined using the syntax of the query language of the Loom knowledge representation system [MacGregor, 1990]. This particular query requests all port names of seaports that are sufficiently deep to accommodate breakbulk" ships.

The initial state of a problem defines the available information sources (e.g., databases) and the servers (e.g., an Oracle DBMS) they are running on. The example shown in Table 2 defines two servers, an Oracle database server running on an HP workstation, called hp-oracle, and an another Oracle server running on a Sun workstation, called sun-oracle. Both servers contain identical copies of the geo and assets databases. In addition to this information, a description of the contents

(available output sims
(retrieve (?port-name)
(:and (seaport ?sport)
(port-name ?sport ?port-name)
(channel-of ?sport ?channel)
(channel-depth ?channel ?depth)
(transport-ship ?ship)
(vehicle-type-name ?ship "breakbulk")
(max-draft ?ship ?draft)
(< ?draft ?depth))))

Table 1: An information gathering goal

of the information sources is stored in a Loom knowledge base. However, this information is static and is accessed directly through the functional interface rather than through the literals listed in the initial state.

((source-available geo hp-oracle)
(source-available assets hp-oracle)
(source-available geo sun-oracle)
(source-available assets sun-oracle))

Table 2: An initial state

For this domain, Sage uses a set of ten general operators to plan out the processing of a query. They include a move operator for moving a set of data from one information source to another, a join operator that combines two sets of data into a combined set of data, and a select-source operator for selecting the information source for retrieving a set of data. The other operators perform additional processing of data (select, compute, and assignment) or reformulate queries using background knowledge (generalize, specialize, definition, and decompose). Each operator is instantiated at planning time with the particular set of data being manipulated as well as the database where the manipulation is being performed.

Consider the operator shown in Table 3, which defines a join performed in the local system. This operator is used to achieve the goal of making some information available in the local knowledge base of the sims information mediator. It does this by partitioning the request into two subsets of the requested data, retrieving that information into the local system, and then joining the data together to produce the requested set of data. The available preconditions are achieved by other operators and the join-partition precondition is defined by a function that produces the relevant partitions of the requested data.

(define (operator join)
:parameters (?join-op ?data ?data-a ?data-b) :precondition
(:and (join-partition ?data ?join-op
?data-a ?data-b)
(available local sims ?data-a)
(available local sims ?data-b))
:effect (available local sims ?data))

Table 3: The join operator