Many AI tasks can be formulated as constraint-satisfaction problems (CSP), i.e., the assignment of values to variables subject to a set of constraints. While some CSPs are hard, those that are easy can often be mapped into sparse networks of constraints which, in the extreme case, are trees. This paper identifies classes of problems that lend themselves to easy solutions, and develops algorithms that solve these problems optimally. The paper then presents a method of generating heuristic advice to guide the order of value assignments based on both the sparseness found in the constraint network and the simplicity of tree-structured CSPs. The advice is generated by simplifying the pending subproblems into trees, counting the number of consistent solutions in each simplified subproblem, and comparing these counts to decide among the choices pending in the original problem.

To be useful in practice, a factory production schedule must reflect the influence of a large and conflicting set of requirements, objectives and preferences. Human schedulers are typically overburdened by the complexity of this task, and conventional computer-based scheduling systems consider only a small fraction of the relevent knowledge. This article describes research aimed at providing a framework in which all relevant scheduling knowledge can be given consideration during schedule generation and revision. Factory scheduling is cast as a complex constraint-directed activity, driven by a rich symbolic model of the factory environment in which various influencing factors are formalized as constraints. A variety of constraint-directed inference techniques are defined with respect to this model to provide a basis for intelligently compromising among conflicting concerns. Two knowledge-based factory scheduling systems that implement aspects of this approach are described.

Mackworth and Freuder have analyzed the time complexity of several constraint satisfaction algorithms [5]. We present here new algorithms for arc and path consistency and show that the arc consistency algorithm is optimal in time complexity and of the same-order space complexity as the earlier algorithms. A refined solution for the path consistency problem is proposed. However, the space complexity of the path consistency algorithm makes it practicable only for small problems. These algorithms are the result of the synthesis techniques used in alice (a general constraint satisfaction system) and local consistency methods [3].

O-Plan is an AI planner based on previous experience with the Nonlin planner and its derivatives. Nonlin and other similar planning systems had limited control architectures and were only partially successful at limiting their search spaces. O-Plan is a design and implementation of a more flexible system aimed at supporting planning research and development, opening up new planning methods and supporting strong search control heuristics. O-Plan takes an engineering approach to the construction of an efficient domain-independent planning system which includes a mixture of AI and numerical techniques from operations research. The main contributions of the work are centred around the control of search within the O-Plan planning framework, and this paper outlines the search control heuristics employed within the planner.

Backtrack search is often used to solve constraint satisfaction problems. A relationship involving the structure of the constraints is described that provides a bound on the backtracking required to advance deeper into the backtrack tree. This analysis leads to upper bounds on the effort required for solution of a class of constraint satisfaction problems. The solutions involve a combination of relaxation preprocessing and backtrack search. The bounds are expressed in terms of the structure of the constraint connections.

In Proc. First Conference on AI Applications, pp. 410–416.

In AAAI-84, pp. 251–254.

A constraint satisfaction problem revolves finding values for a set of variables subject to a set of constraints (relations) on those variables Backtrack search is often used to solve such problems. A relationship involving the structure of the constraints is described which characterizes to some degree the extreme case of mimmum backtracking (none) The relationship involves a concept called "width," which may provide some guidance in the representation of constraint satisfaction problems and the order m which they are searched The width concept is studied and applied, in particular, to constraints which form tree structures.

In this paper we explore the number of tree search operations required to solve binary constraint satisfaction problems. We show analytically and experimentally that the two principles of first trying the places most likely to fail and remembering what has been done to avoid repeating the same mistake twice improve the standard backtracking search. We experimentally show that a lookahead procedure called forward checking (to anticipate the future) which employs the most likely to fail principle performs better than standard backtracking, Ullman's, Waltz's, Mackworth's, and Haralick's discrete relaxation in all cases tested, and better than Gaschnig's backmarking in the larger problems.

The determination of subgraph and graph isomorphisms is an important application for the algebraic manipulation of networks of binary constraints. Simplified and streamlined arc consistency and tree search algorithms are introduced, and experimental results show substantial reduction in timings compared with previous algorithms for determining isomorphisms. Several path consistency algorithms, including a new one, have been timed experimentally on isomorphism problems, and found not to be cost effective despite their theoretical appeal. The importance of this result is enhanced by the absence of previously published experimentation with path consistency. A theoretical study of the new path consistency algorithm provides insight into the experimental results.