next up previous
Next: Constraint Propagation Up: Constraint Networks for Managing Previous: Constraints

4.2 Hierarchical Template Representation

In order to modularize an application and deal with its complexity, we organize the variables and constraints into a hierarchy of templates. This allows us to group the variables into more manageable units and provides an overall organization to the information that is presented to the user. For example, the top-level template of the Travel Assistant (shown in Figure 1) includes a set of variables associated with who you are meeting with, when the meeting will occur, and where the meeting will be held. In addition, it has several other variables that can be expanded to fill in more details about the trip, such as how you will get to the meeting and where you will stay once you get there. Each expansion corresponds to a subtemplate that has its own set of variables and constraints and may in turn be composed of lower level subtemplates.

A template is comprised of a name, parameters, variables, constraints, and expansions. The name uniquely identifies the template. The parameters specify the variables that can be passed into or out of a template. The variables have corresponding domain expressions (as defined in Section 4.1.2). The constraints define the set of primitive constraints that are used to compose the domain expressions. And the expansion specifies how a template is elaborated into the appropriate subtemplates based on the assigned value of the expansion variable.

A fragment of the specification of the Trip template is shown in Figure 9. The fragment focuses on the ModeToDestination decision, the variable definitions involved, the corresponding set of constraints, and the expansion that determines which subtemplate to call based on the value of this variable. The variables involved are Origin, Destination, Distance, and ModeToDestination. The getDistance constraint computes the distance between the origin and destination addresses by calling the YahooMap wrapper. The selectModeToDest constraint suggests a value for ModeToDestination. If the Distance is greater than 200 miles it suggests Fly, otherwise Drive. Note that this constraint never suggests taking a taxi, but the user may select this choice since it is an option in the ChooseTemplate statement and will appear in the interface.

Figure 9: Fragment of the Trip Template
template Trip() {
   variables: ...
      Distance = getDistance(Origin, Destination),
      ModeToDestination = selectModeToDest(Distance),
      getDistance(X,Y) {
            domain = travel;
            wrapper = yahoomap;
            query = "select distance from yahoomap 
                     where origin='X' and 
      selectModeToDest(Distance) {
         if Distance > 200 then Fly else Drive;}
      chooseTemplate(ModeToDestination) {
         "Take a Taxi" : Taxi(Origin, Destination)
         "Drive" : Drive(Origin, Destination)
         "Fly" : Fly(Origin, Destination, Distance)}}

The hierarchical organization of the templates for the Travel Assistant is illustrated in Figure 10. This figure shows the top-level Trip template and the subtemplates that can be expanded from this template. There are three subtasks that must be achieved for a trip: getting to the destination, finding an accommodation, and continuing the trip (if necessary). These decisions are associated with the three expansion variables: ModeToDestination, ModeHotel, and ModeNext. Since all these subtasks must be achieved for a successful trip, we label the subtask decomposition with an AND. Each of these subtasks can be achieved by several alternative means. The figure shows the choices as OR branches. For example, the ModeToDestination is a variable that can take the values Fly, Drive, or Taxi. For each of these possible values, there is a corresponding subtemplate that will be expanded and used to achieve the subtask. Also, note that the choices for ModeNext are recursive instantiations of the Trip template. In this way the system can handle trips of any number of legs.

Figure 10: Example of the Hierarchical Organization of Templates
Example of the Hierarchical Organization of Templates

next up previous
Next: Constraint Propagation Up: Constraint Networks for Managing Previous: Constraints
Jose-Luis Ambite 2001-02-17