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.

• Propagation on confirmation only starts constraint propagation when the user actually explicitly inputs or approves the values. The advantage of this mechanism is that there is no wasted computation, as every constraint evaluation (which could involve a potentially expensive computation) is guaranteed to be relevant to the user. The disadvantage is that it can be tedious for the user to approve every value suggested for the user and confusing from a user-interface perspective.

• Propagation within a template immediately fires constraints as soon as possible but without crossing template boundaries. This approach offers a good trade-off between computation by the system and input by the user. The system reasons thoroughly within a template assigning values for all the variables in the template. However, it waits for confirmation from the user in the proposed template expansion since a user may choose a different expansion for reasons not represented in the system. This is the default propagation strategy in Heracles.

• One-level look-ahead propagation fires constraints both within the current template as well as one-level down from this template. In the cases where the system correctly predicts the users' selections, this approach makes the system appear very responsive. The disadvantage is the increased resource requirements.

• Full Propagation evaluates the whole constraint network. The advantage is that this method is that the system can make recommendations based on values propagated up from subtemplates. The disadvantage is that the system may consume significant resources on paths that turn out to be irrelevant.