Classes of Problems for which HUNTER-GATHERER is Beneficial

Several different features must come together to produce a problem for which HUNTER-GATHERER is the preferred processing methodology:

• Constraint-based. HUNTER-GATHERER gains its efficiency by identifying and processing independently parts of the problem that are tightly constrained. A knowledge of constraints between various parts of the problem is therefore essential.

• Constraints are tendencies. Traditional CSP techniques can be used for problems whose constraints are of the straightforward yes/no variety (although HG is still more efficient - see section 8.1). The N-Queens problem is a good example of such a problem. Many ``real-world'' problems, however, do not have such a simple semantics. Context often decides whether a certain decision is preferred (or even relevant) or not. The branch-and-bound methods used by HUNTER-GATHERER can be viewed as constraint satisfaction for ``fuzzy'' constraints. Constraints are combined in context, with value assignment combinations that are guaranteed to be sub-optimal removed. Solution synthesis provides for efficient combination of partial solutions, while knowledge of constraint dependencies recorded in the subgraphs guides the synthesis.

• Relatively independent subgraphs. Imagine a new N-Queens' problem where the constraints were ``fuzzy.'' For instance, consider setting up constraints such that queens in odd-numbered columns attacking queens in other odd-numbered columns was relatively bad (possibly a score of 0.2), odd-numbered attacking even-numbered was not quite so bad (0.5), even-numbered combatants were not bad at all (a score of 0.9), and queens not attacking any other queens (pacifists) were given a score of 0.1. This violent version of N-Queens could then have the goal of finding the highest scored placement of queens. Obviously, straight-forward CSP techniques would be useless in this problem. HUNTER-GATHERER, although able to find the solution, cannot take advantage of its solution synthesis mechanism. A simple branch-and-bound algorithm would be enough to handle this, but it might take several centuries to process a 20-Queens' problem.

  The key reason the new N-Queens' problem is so difficult is because it is impossible to divide it into relatively independent sub-problems. HUNTER-GATHERER gains its efficiency in its ability, at each level of synthesis, to find at least one variable that is not effected outside the current synthesis subgraph. This variable can be optimized in all the possible combinations of variables that are effected outside the subgraph. In the new N-Queens' problem, every variable affects every other variable, making it impossible to perform this optimization.

  In terms of constraint graphs, the prototypical form of suitable problems will be tree-shaped. Subgraphs are formed from the leaves up, by combining all children with their parent into a subgraph. At each synthesis, then, all of the children nodes will be optimized, since only the parent node is effected outside the subgraph.

  The prototypical form of unsuitable constraint graphs is the clique. In a clique, each variable affects every other variable. Subgraphs cannot be constructed in this situation which will enable optimization at any level of synthesis.

  Of course, there is a wide spectrum of problems in between these two extremes. The next section briefly reports on our work applying HG to graph coloring problems. These types of problems are halfway between the mostly tree-shaped inputs found in computational semantics and the clique of the N-Queens problem. Section 9.4 goes even further, examining how the input topology of a problem affects HG's partitioning and, consequently, its overall complexity.

In summary, constraint satisfaction finds the subgraphs, branch-and-bound optimizes ``fuzzy'' constraints, and solution synthesis combines together partial solutions. These functions, in turn, depend on, or take advantage of, the availability of constraints, the ``fuzzy'' nature of the constraints, and the localized nature of the interactions.