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 are adequate for problems whose constraints are of the straightforward yes/no variety. 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 ``circles'' guides the synthesis.

• Relatively independent circles. 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 circle. This variable can be optimized in all the possible combinations of variables that are effected outside the circle. 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. Circles are formed from the leaves up, by combining all children with their parent into a circle. At each synthesis, then, all of the children nodes will be optimized, since only the parent node is effected outside the circle.

  The prototypical form of unsuitable constraint graphs is the clique. In a clique, each variable affects every other variable. Circles 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 ``constraint-based'' circles described in section 3.1 is a beginning towards identifying and exploiting non-tree-based constraint groups. Again, the key to making such circles beneficial is finding ones that contain variables that are not effected outside the circle. Further research in this area may enable the application of HUNTER-GATHERER to a wider spectrum of problems.

In summary, constraint satisfaction finds the circles, 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.