Constraint Propagation next up previous
Next: User Interface Design Up: Constraint Networks for Managing Previous: Hierarchical Template Representation

4.3 Constraint Propagation

The domain expressions define a directed graph on the variables. In the current version of the system, the constraint graph must be a acyclic, which means that information flows in one direction. This directionality simplifies the interaction with the user. The structure of the graph is given by the dependency relations present in the domain expressions. Variable Y depends on variable X if the domain expression of Y mentions a constraint that includes variable X. The idea here is that if variable X changes, variable Y may have to be recalculated.

The constraint propagation algorithm proceeds as follows. When a given variable is assigned a value, either directly by the user or by the system, the algorithm recomputes the possible value sets and assigned values of all its dependent variables. This process continues recursively until there are no more changes in the network. More specifically, when a variable X changes its value, the system evaluates the domain expression of each variable Y dependent on X. This may generate a new set of possible values for Y. If this set changes, the preference constraint is evaluated selecting one of the possible values as the new assigned value for Y. If this assigned value is different from the previous one, it causes the system to recompute the values for further downstream variables. Values that have been assigned by the user are always preferred as long as they are consistent with the constraints.

Consider the sample constraint network in Figure 8. First, the constraint that finds the closest airport to the user's home address assigns the value LAX to the variable DepartureAirport. Then, the constraint getParkingRate, which is a call to a web wrapper, fires producing a set of rates for different parking lots.[*]The preference constraint selects terminal parking which is $16.00/day. This value is multiplied by the duration of the trip to compute the ParkingTotal of $64 (using the simple local constraint multiply). A similar chain of events results in the computation of the TaxiFare. Once both the ParkingTotal and the TaxiFare are computed, the selectModeToAirport constraint compares the costs and chooses the cheapest means of transportation, which in this case is to take a Taxi.

There are some issues in terms of how aggressively the system should propagate constraints. We have considered four general constraint propagation strategies: propagation on confirmation, propagation within a template, one-level look-ahead propagation, and full propagation.

next up previous
Next: User Interface Design Up: Constraint Networks for Managing Previous: Hierarchical Template Representation
Jose-Luis Ambite 2001-02-17