Next: Compositional Model Repositories Up: Dynamic Constraint Satisfaction with Previous: Partial ordering of OMPs

This section presents a basic algorithm for solving aDPCSPs. Although OMPs are used in this work, this algorithm can take any aDPCSP provided that it employs a preference calculus with a commutative, associative and monotonic combination operator. However, the use of OMPs provides a convenient way of specifying incomplete preference information.

An aDPCSP is similar to valued CSPs as presented by Schiex, Fargier and Verfaillie [37] and also to semiring based CSPs [2]. However, it extends both approaches with activity constraints and involves different underlying presumptions in its valuation structure. The preference valuations in this work are allowed to be ordered partially, as opposed to the valued CSPs.

An aDPCSP represents an important type of constraint satisfaction optimisation problem [41]. In order to tackle the optimisation of preferences an A* type algorithm is employed [13,34]. A* algorithms are known to be efficient in terms of the total number of nodes explored in an effort to find optimal solutions, with a given amount of information. On the downside, they have an exponential space complexity. Naturally, a number of alternative approaches could have been explored, including conventional constraint-based solving methods such as depth first branch and bound search. However, the use of an A*-like algorithm is sufficient for solving the aDPCSPs in the domain of the present interest. In particular, algorithm 1 implements an A* search strategy that is capable of handling activity constraints, which involves the use of basic CSP techniques such as constraint propagation and backtracking.

An A* algorithm maintains the explored attribute-value assignments by means of a priority queue of nodes. Each node in corresponds to a set of attribute-value assignments: solution. The search proceeds through a number of iterations. At each iteration, a node is taken from , and replaced by nodes that extend solution with an additional attribute-value assignment. More specifically, for each node in , a set of remaining active but unassigned attributes is maintained. At each iteration, the possible assignments of the first attribute , where is the node taken from at the current iteration, are processed. For every assignment that is consistent with solution (i.e. solution), a new child node , with solutionsolution and , is created and added to .

The activity constraints are processed via propagation rather than constraint satisfaction. Whenever a node is taken from such that is empty, the activity constraints are fired in order to obtain a new set of active but unassigned attributes. That is, is assigned

 solution   active

where represents the active, but already assigned attributes in node .

In the priority queue , nodes are maintained by means of two heuristics: committed preference and potential preference . Here, given a node ,

where is the set of unassigned attributes that can still be activated given the partial assignment solution() (as indicated previously, the actual implementation employs an assumption-based truth maintenance system [7] to efficiently determine which attribute's activity can no longer be supported). In other words, is the preference associated with the partial attribute-value assignment in node and is combined with the highest possible preference assignments taken from all the values of the domains of those attributes in . Thus, computes an upper boundary on the preference of an aDPCSP solution that includes the partial attribute-value assignments corresponding to .

The following theorem shows that algorithm 1 is guaranteed to find the set of attribute-value pairs with the highest combined preferences, within the set of solutions that satisfy the constraints.

Proof: is an A* algorithm guided by a heuristic function , where is the actual preference of node and . It follows from the previous discussion that is greater than or equal to the combined preference of any value-assignment of unassigned attributes that is consistent with the partial solution of . In this algorithm, the nodes are maintained in a priority queue in descending order of . Let be a distance function that reverses the preference ordering such that . can then be described as an A* algorithm, where the nodes in the priority queue are ordered in ascending order of , such that and is a lower bound on the distance between and the optimal solution. Therefore, following the work by Hart, Nilsson and Raphael [13], is an admissible algorithm, guaranteed to find a solution with a minimal or a maximal .

To illustrate algorithm 1, consider the problem of finding an ecological model that describes the behaviour of two populations, one of which predates on the other. An aDPCSP is constructed for the compositional modelling problem with the following attributes and domains. Note that section 3 demonstrates how the attributes, domains and constraints of this problem can be constructed automatically and that section 4 illustrates these ideas in the context of a larger example.

The attributes , and respectvely describe the relevance of the following phenomena: the change in size of the predator population, the change in size of the prey population and the predation of the prey by the predator. The attributes and represent the choice of type of population growth model. Two types of such models are incorporated in the problem: the logistic one and the other''. Finally, attribute is associated with the choice of model type of the predation phenomenon. Here, two types of model, the Holling model and the Lotka-Volterra model, are included.

Because the Holling predation model presumes that logistic models are employed to describe population growth, and because the Lotka-Volterra Model incorporates its own population growth model, the combinations of assignments to , , and are restricted. Hence, the aDPCSP contains a set of compatibility constraints, with:

Furthermore, a model type of predator/prey growth must be selected if and only if the corresponding population growth phenomenon is deemed relevant. Also, a model type of predation must be selected if and only if both population growth phenomena and the predation phenomenon are deemed relevant (because ecological models describing predation rely on submodels describing population growth of the predator and the prey). Hence, the aDPCSP contains a set of activity constraints, with:

Finally, let the preference calculus consist of two orders of magnitude and , with , where

The OMP assignments are as follows:

When applied to this problem, algorithm 1 initialises the search by creating a node , where:

• , the set of currently active attributes, is initialised to , because the activity of these attributes does not depend on other attribute-value assignments.
• and are initialised to the empty set and to 0 respectively, since no attributes have been assigned yet.
• Finally, equals because this is the combination of highest OMPs associated with each domain.

This initial node is enqueued in . Next, the algorithm proceeds through a number of iterations. At each iteration, the node with most potential (as measured by and ) is dequeued, and its children are generated and enqueued in . The nodes that are created in this way are depicted in Figure 2. The number in the subscript of each node indicates the order of node generation, and the thick arrows show the order in which the search space is explored.

Note that there are three important features of the algorithm that could not be clearly demonstrated within Figure 2. Firstly, at node , the initial set of unassigned attributes is exhausted: . Therefore, the activity constraints are fired when is explored. Because corresponds to the assignment yesyesyes, the remaining attributes are activated and is reset to .

Secondly, node corresponds to an assignment of all (active) attributes that is consistent with the activity and compatibility constraints:

 yesyesyesotherotherLotka-Volterra

This assignment is not a solution to the aDPCSP, because the corresponding preference is not guaranteed to be maximal (and, the assignment is, in fact, not optimal). After the creation of , the priority queue looks as follows (the ordering between and may vary since and ):

Therefore, the next node to be explored (after and the subsequent creation of ) is .

Thirdly, node does correspond with an optimal solution. After its creation, equals:

As a consequence, is dequeued in the next iteration. Because no children of can be created ( and the activity constraints activate no more attributes), is retained as a solution.

If the user is interested in finding multiple alternative solutions, the search may proceed until contains no more nodes with a value that is not smaller than the maximum preference of the first solution. In this case, and hence, there is only one solution to this aDPCSP.

Next: Compositional Model Repositories Up: Dynamic Constraint Satisfaction with Previous: Partial ordering of OMPs
Jeroen Keppens 2004-03-01