Solving aDPCSPs

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 $Q$ of nodes. Each node $n$ in $Q$ corresponds to a set of attribute-value assignments: solution$(n)$. The search proceeds through a number of iterations. At each iteration, a node $n$ is taken from $Q$, and replaced by nodes that extend solution$(n)$ with an additional attribute-value assignment. More specifically, for each node $n$ in $Q$, a set $X_u(n)$ of remaining active but unassigned attributes is maintained. At each iteration, the possible assignments of the first attribute $x\in X_u(n)$, where $n$ is the node taken from $Q$ at the current iteration, are processed. For every assignment $x:d$ that is consistent with solution$(n)$ (i.e. solution$(n)\cup\{x:d\},\mathbf{C}\nvdash\bot$), a new child node $n'$, with solution$(n')=$solution$(n)\cup\{x:d\}$ and $X_u(n')=X_u(n)-\{x\}$, is created and added to $Q$.

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

$$\{x_i\mid (n), \mathbf{A}\vdash (x_i)\} -X_a(n)$$

where $X_a(n)$ represents the active, but already assigned attributes in node $n$.

In the priority queue $Q$, nodes are maintained by means of two heuristics: committed preference $CP(n)$ and potential preference $PP(n)$. Here, given a node $n$,

$$CP(n) =\oplus_{x:d\in\text{solution}(n)}P(x:d)$$

$$PP(n) =CP(n)\oplus(\oplus_{x\in X_{nd}(n)}\max_{d\in D_x}P(x:d))$$

where $X_{nd}(n)$ is the set of unassigned attributes that can still be activated given the partial assignment solution($n$) (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, $CP(n)$ is the preference associated with the partial attribute-value assignment in node $n$ and $PP(n)$ is $CP(n)$ combined with the highest possible preference assignments taken from all the values of the domains of those attributes in $X_{nd}(n)$. Thus, $PP(n)$ computes an upper boundary on the preference of an aDPCSP solution that includes the partial attribute-value assignments corresponding to $n$.

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.

Theorem 1   $\CALL{solve}{\mathbf{X},\mathbf{D},\mathbf{C},\mathbf{A},P}$ is admissible
Proof: $\CALL{solve}{\mathbf{X},\mathbf{D},\mathbf{C},\mathbf{A},P}$ is an A* algorithm guided by a heuristic function $PP(n)=CP(n)\oplus h(n)$, where $CP(n)$ is the actual preference of node $n$ and $h(n)=\oplus_{x\in X_{nd}(n)}\max_{d\in D_x}P(x:d)$. It follows from the previous discussion that $h(n)$ is greater than or equal to the combined preference of any value-assignment of unassigned attributes that is consistent with the partial solution of $n$. In this algorithm, the nodes $n$ are maintained in a priority queue in descending order of $PP(n)$. Let $\delta$ be a distance function that reverses the preference ordering such that $\delta(P_1)\prec\delta(P_2)\leftrightarrow P_1\succ P_2$. $\CALL{solve}{\mathbf{X},\mathbf{D},\mathbf{C},\mathbf{A},P}$ can then be described as an A* algorithm, where the nodes $n$ in the priority queue $Q$ are ordered in ascending order of $\delta(PP(n))$, such that $\delta(PP(n))=\delta(CP(n))\oplus \delta(h(n))$ and $\delta(h(n))$ is a lower bound on the distance between $n$ and the optimal solution. Therefore, following the work by Hart, Nilsson and Raphael [13], $\CALL{solve}{\mathbf{X},\mathbf{D},\mathbf{C},\mathbf{A},P}$ is an admissible algorithm, guaranteed to find a solution $S$ with a minimal $\delta(P(S))$ or a maximal $P(S)$.

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.

$$\begin{split}\mathbf{X}=\{&x_1,x_2,x_3,x_4,x_5,x_6\}\\ D_{x_1... ...D_{x_6}=\{&\text{Holling},\text{Lotka-Volterra}\}\\ \end{split}$$

The attributes $x_1$, $x_2$ and $x_3$ 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 $x_4$ and $x_5$ 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 $x_6$ 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 $x_4$, $x_5$, and $x_6$ are restricted. Hence, the aDPCSP contains a set $\mathbf{C}=\{c_{\{x_4,x_6\}},c_{\{x_5,x_6\}}\}$ of compatibility constraints, with:

$$\begin{split}c_{\{x_4,x_6\}}=\{&\langle x_4:\text{other},x_6:... ...gle x_5:\text{logistic},x_6:\text{Holling}\rangle\} \end{split}$$

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 $\mathbf{A}=\{a_{x_4,\{x_1\}},a_{x_5,\{x_2\}},a_{x_6,\{x_1,x_2,x_3\}}\}$ of activity constraints, with:

$$\begin{split}a_{x_4,\{x_1\}}=\{&\langle x_1:\text{yes},\text{... ...t{no},x_3:\text{no},\neg\text{active}(x_4)\rangle\} \end{split}$$

Finally, let the preference calculus consist of two orders of magnitude $O_{\text{growth}}$ and $O_{\text{predation}}$, with $O_{\text{growth}}\ll O_{\text{predation}}$, where

$$\begin{split}O_{\text{growth}}= &\{p_{\text{other}},p_{\text{... ... with }p_{\text{Lotka-Volterra}}<p_{\text{Holling}} \end{split}$$

The OMP assignments are as follows:

$$\begin{split}P(x_4:\text{other})=P(x_5:\text{other})=&p_{\tex... ...6:\text{Lotka-Volterra})=&p_{\text{Lotka-Volterra}} \end{split}$$

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

• $X_u(n_0)$, the set of currently active attributes, is initialised to $\{x_1,x_2,x_3\}$, because the activity of these attributes does not depend on other attribute-value assignments.
• $X_a(n_0)$ and $CP(n_0)$ are initialised to the empty set and to 0 respectively, since no attributes have been assigned yet.
• Finally, $PP(n_0)$ equals $p_{\text{other}}\oplus p_{\text{other}}\oplus p_{\text{Holling}}$ because this is the combination of highest OMPs associated with each domain.

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

Figure 2: Search space explored by algorithm 1 when solving sample aDPCSP

Note that there are three important features of the algorithm that could not be clearly demonstrated within Figure 2. Firstly, at node $n_5$, the initial set of unassigned attributes is exhausted: $X_u(n_5)=\{\}$. Therefore, the activity constraints are fired when $n_5$ is explored. Because $n_5$ corresponds to the assignment $\{x_1:$yes$,x_2:$yes$,x_3:$yes$\}$, the remaining attributes are activated and $X_u(n_5)$ is reset to $\{x_4,x_5,x_6\}$.

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

$$\{x_1: ,x_2: ,x_3: ,x_4: ,x_5: ,x_6: \}$$

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 $n_{12}$, the priority queue $Q$ looks as follows (the ordering between $n_2$ and $n_4$ may vary since $PP(n_2)=PP(n_4)$ and $CP(n_2)=CP(n_4)$):

$$\{n_{10},n_8,n_{12},n_6,n_2,n_4\}$$

Therefore, the next node to be explored (after $n_9$ and the subsequent creation of $n_{12}$) is $n_{10}$.

Thirdly, node $n_{19}$ does correspond with an optimal solution. After its creation, $Q$ equals:

$$\{n_{19},n_{12},n_6,n_2,n_4\}$$

As a consequence, $n_{19}$ is dequeued in the next iteration. Because no children of $n_{19}$ can be created ( $X_u(n_{19})=\emptyset$ and the activity constraints activate no more attributes), $n_{19}$ is retained as a solution.

If the user is interested in finding multiple alternative solutions, the search may proceed until $Q$ contains no more nodes with a $PP$ value that is not smaller than the maximum preference of the first solution. In this case, $PP(n_{12})\prec CP(n_{19})$ and hence, there is only one solution to this aDPCSP.