4. Constraint Networks for Managing Information

The critical challenge for the Heracles system is in integrating multiple information sources, programs, and constraints into a cohesive, effective tool. We have seen some examples of these diverse capabilities in the Travel Assistant, for example, retrieving scheduling information from a calendar system, computing the duration of a given meeting, and invoking a web wrapper to find directions to the meeting.

Constraint reasoning technology offers a clean way to integrate multiple heterogeneous subsystems in a plug-and-play approach, maximizing overall efficiency via rapid information propagation between components. The basis for our approach is a constraint representation where we model each piece of information as a distinct variableand describe the relations that define the valid values of a set of variables as constraints. A constraint can be implemented either by a local procedure within the constraint engine, or by an external component that interfaces to the constraint engine (such as a wrapper or an off-the-shelf scheduler).

Using a constraint-based representation as the basis for control has the advantage that it is a declarative representation and can have many alternative execution paths. Thus, we need not commit to a specific order for executing components or propagating information. The constraint propagation system will determine the execution order in a natural manner. The constraint reasoning system propagates information entered by the user as well as the system's suggestions, decides when to launch information requests, evaluate constraints, and compute preferences. All of these tasks run as asynchronous processes to give the user as much support as possible without interfering with his work.

In order to manage the complexity and capture the task structure of the application, closely related variables and constraints are encapsulated into templates. The templates are organized hierarchically so that a higher-level template representing an abstract task (e.g., Trip) may be decomposed into a set of more specific subtasks, called subtemplates (e.g., Fly, Drive, etc). This hierarchical task network structure helps to manage the complexity of the application for the user by hiding less important details until the major decisions have been achieved.

In this section, we describe the representation for the variables, the constraints, the hierarchical templates, and the constraint propagation algorithm.