As described above, Freuder introduced solution synthesis as a means to ``gather up'' all solutions for a CSP without resorting to traditional search methods. Freuder's algorithm created a set of two-variable nodes that contained combinations of every two variables. These two variable nodes were then combined into three variable nodes, and so on, until a node containing all the variables, i.e. the solution, was synthesized. At each step, constraints were propagated down and then back up the ``tree'' of synthesized nodes.
Tsang improved greatly on this scheme with the Essex Algorithms. These algorithms assumed that a list of the variables could be made, after which two-variable nodes were created only between adjacent variables in the list. Higher order nodes were then synthesized as usual, starting from the two-variable nodes. Tsang noted that some orderings of the original list would prove more efficient than others, most notably a Minimal Bandwidth Ordering'' (MBO), which seeks to minimize the distance between constrained variables.
This work extends the concept of MBO and carries it to a higher level. The whole concept of synthesizing solution sets one order higher than their immediate ancestors is thrown out. Synthesis, here, is aimed at maximally interacting groupings of variables, of any order. Furthermore, this process of using maximally interacting groupings, or circles, extends to the highest levels of synthesizing. Tsang only creates second order nodes from adjacent variables in a list, with the list possibly ordered to maximize second order interactions. After that, third and higher order nodes are blindly created from combinations of second order nodes. In this work, in a sense, MBO is continued on to the higher levels. The circles of co-constrained variables described in the previous section guide the synthesis process from beginning to end.
The main improvement of this approach comes from a recognition that much
of the work in SS-FREUDER and SS-TSANG was wasted on finding valid
combinations of variables which were not related. For example, in the
computational semantic example given above, the words ``IBM'' (I), ``Jacob-Smith'' (J) and
``ten-million-dollars'' (T) (among others) are not directly related by any
constraints. Despite this, valid combinations for
are calculated by SS-FREUDER and,
depending on the ordering used, could also be calculated by SS-TSANG.
Furthermore, the SS-TSANG algorithm tends to carry along unneeded
ambiguity. As shown above, if two related variables are not adjacent
in the original list, their disambiguating power will not be applied
until they happen to co-occur in a higher-order synthesis. It should
be noted that Freuder's algorithm does not have this disadvantage,
because all combinations of variables are
created.
The current work
combines the efficiency of Tsang's algorithms with the
early-disambiguation power of Freuder.
The SS-GATHERER Algorithm
The SS-GATHERER algorithm to be defined below only expends energy on variables directly related by constraints. For instance, a constraint graph of the example computational semantic problem would look like Figure 16. Only two lower order circles, IAJ and AFT would be synthesized:
= {(ORG,T-O,ORG),(ORG,OBT,ORG)}
= {(T-O,COST,MON),(OBT,COST,MON)}
The answer is then directly synthesized from these:
= {(ORG,T-O,ORG,COST,MON),(ORG,OBT,ORG,COST,MON)}
Notice that the bulk of disambiguation occurs in the lower order circles which were chosen to maximize this phenomena. Because the same solution was obtained in only three steps, it goes without saying that all of the other combinations of variables used in SS-Freuder (24 extra nodes, not including first order nodes) and SS-TSANG (8 extra nodes) were superfluous. Focusing the synthesizer on circles that will maximally disambiguate produces huge savings while still guaranteeing the correct solution.
One objection that could be raised to this process is that, in
spurning the second order nodes, more work is needed to create higher
level nodes. For instance, if each variable had three possible
values, one
needs to test 9 (
) combinations for each second-order node, but
27 (
)
combinations for third order nodes. This
argument only is valid, however, if disambiguation is possible at the
lower nodes. For example, if two second-order nodes could be created
that would form the third-order node, and each second order node could
be completely disambiguated to a single solution, then the third order
node could be created without any combinatorics, yielding a total of
18 combinations (9 + 9) that were searched. Directly creating the
third-order node requires the 27 combinations to be searched.
However, if the second order nodes do not disambiguate, nothing is
gained from them. For this reason, initial circles can be further
sub-divided into groups of second-order nodes, if those
second-order nodes are connected in the constraint
graph.
The algorithm below accepts a list of Circles, created as shown in the previous section (with the above addition). Each circle is in the form:
(List-of-Vars List-of-Sub-Circles)
The list is ordered from smaller circles to larger circles. For the
example in the previous section, graphically displayed in
Figure 13, the following would be the
list of input circles:
(¯((adquirir grupo-roche) nil)
((adquirir dr-andrew) nil)
((adquirir a-traves-de) nil)
((a-traves-de compania) nil)
((compania su) nil)
((en compania) nil)
((en espana) nil)
((adquirir grupo-roche dr-andrew)
((adquirir grupo-roche) (adquirir dr-andrew)))
((adquirir a-traves-de compania)
((adquirir a-traves-de) (a-traves-de compania)))
((en compania espana)
((en compania) (en espana)))
((adquirir a-traves-de compania en espana su)
((adquirir a-traves-de compania) (en compania espana)))
((adquirir grupo-roche dr-andrew a-traves-de compania en espana su)
(¯(adquirir grupo-roche dr-andrew)
(adquirir a-traves-de compania en espana su)))
)
An algorithm that implements this methodology follows. In it, a ``plan'' refers to a specific assignment of values to some number of variables. Section 3.3 will work out a complete example demonstrating SS-GATHERER used in conjunction with branch-and-bound techniques.
1 PROCEDURE SS-GATHERER(Circles);; This procedure returns value of last PROCESS-CIRCLE.
;; The last circle processed should be the entire problem.
2 FOR each Circle in Circles
3 PROCESS-CIRCLE(Circle)
4 PROCEDURE PROCESS-CIRCLE(Circle)
5 Output-Plans <-- nil
6 Name <-- FIRST(Circle)
;; The circle ``name'' is referenced by the (consistently)
;; ordered list of variables in it
7 Incoming-Circles <-- SECOND(Circle)
;; Incoming-Circles is a list of sub-circles that make up Circle
8 Incoming-Non-Circles <-- REMOVE all variables in Incoming-Circles from Name
9 Non-Circle-Combos <-- Get-Combos(Incoming-Non-Circles)
10 Circle-Combos <-- Combine-Circles(Incoming-Circles)
11 FOR each Non-Circle-Combo in Non-Circle-Combos
12 FOR each Circle-Combo in Circle-Combos
;; each incoming circle has consistency info stored in arrays:
13 AC-Info <-- access arc constraint info from input circles
14 Plan <-- add Non-Circle-Combo to Incoming-Plan
;; Plan is a potential solution for this Circle
;; with a value assigned to each variable.
15 IF Arc-Consistent(Plan,AC-Info) THEN
16 Output-Plans <-- Output-Plans + Plan
17 ;; update AC-Info for this circle
18 RETURN Output-Plans
The Get-Combos procedure (line 9) simply produces all combinations of
value assignments for the input variables. This procedure has complexity
O(
), where x is the number of variables in the input
Incoming-Non-Circles, and a is the maximum number of values for a
variable. In the worst case, x will be n; this is the case when
the initial circle contains all the variables and no sub-circles. Of course,
this is simply an exhaustive search, not Solution Synthesis. In practice, the
circles usually contain no more than two variables not involved in input
sub-circles, the exceptions almost always pertaining to the
base circle, in which case the combine-circles procedure does not add
complexity.
The combine-circles procedure (line 10) combines all consistent plans already
calculated for each input Incoming-Circle. In the worst case, where each
Incoming-Circle contained a single variable, and Incoming-Circles contained
every variable, then the time complexity would be
O(
), where a is the maximum size of a variable domain. This is
unavoidable, and is the nature of CSPs. However, if the number of circles in
Incoming-Circles is limited to c, and each circle has at most p
possible Plans, then the complexity of this step is O(
). This step,
without the branch-and-bound modifications presented in the next section,
dominates the time complexity of SS-GATHERER. Section 3.3 illustrates how this
number can be reduced to a ``near'' constant value.
The FOR loops in lines 11 and 12 combine the possible Plan-Combos from
the Incoming-Non-Circles with the Circle-Combos calculated for the
Incoming-Circles. The worst-case time complexity is no worse than the
worst-case time complexity for either Combine-Circles or Get-Var-Combos. If
Get-Var-Combos produces 
combinations, then Combine-Circles will
produce none, and vice-versa. In practice, Combine-Circles produces
combinations while Plan-Combos produces a constant number of combinations. The total
complexity of PROCESS-CIRCLE is therefore O(
). Again, this number
can be reduced to a ``near'' constant. The complexity of
SS-GATHERER, then, is O(
) times the number of circles, which is
proportional to the number of variables, n. If O(
) can be
shown to be a ``near'' constant, then SS-GATHERER has time complexity that is
``near'' linear with respect to the number of variables.
For each synthesis, arc consistency may be performed (line 15). As discussed above, however, un-modified CSP techniques such as arc-consistency are not usually helpful in problems with non-binary constraints. The next section presents a computational substitute that will produce similar efficiency for these kinds of problems. Arc consistency does play a role, however, in the text planning system, PICARD, described in section 3.4. It also comes into play when THRESH is set to a non-zero value, which can create straightforward constraints. Arc-consistency techniques described in section 2.1 are used. These techniques are further discussed in section 4.2 below.
