An extended version of this paper appeared in the ASME Journal of Mechanical Design 114(1): 187-
`195, March 1992
`
`CONFIGURATION TREE SOLVER:
`A TECHNOLOGY FOR AUTOMATED DESIGN AND
`CONFIGURATION
`
`Alexander Kott, Gerald Agin
`Carnegie Group, Inc.
`Five PPG Place
`Pittsburgh, PA 15222
`
`David Fawcett
`Electronics Division
`Ford Motor Company
`Dearborn, MI 48121
`
`ABSTRACT
`
`Configuration is a process of generating a definitive description of a product that
`satisfies a set of specified requirements and known constraints. Knowledge-based
`technology is an important factor in automation of configuration tasks found in
`mechanical design. In this paper, we describe a configuration technique that is well
`suited for configuring "decomposable" artifacts with reasonably well defined
`structure and constraints. This technique may be classified as a member of a general
`class of decompositional approaches to configuration. The domain knowledge is
`structured as a general model of the artifact, an and-or hierarchy of the artifact’s
`elements, features, and characteristics. The model includes constraints and local
`specialists which are attached to the elements of the and-or-tree. Given the specific
`configuration requirements, the problem solving engine searches for a solution, a
`subtree, that satisfies the requirements and the applicable constraints. We describe an
`application of this approach that performs configuration and design of an automotive
`component.
`
`1 INTRODUCTION
`
`We describe a configuration technique that is well suited for configuring
`"decomposable" artifacts with reasonably well defined structure and constraints. This
`technique may be classified as a member of a general class of decompositional
`(abstract refinement (Mostow, 1984)) approaches to configuration. Other techniques
`within the same class of approaches have been utilized in (Brown and
`
`Page 1 of 17
`
`FORD 1207
`
`

`
`Chandrasekaran, 1985), (Maher and Fenves, 1985), (Mittal and Araya, 1986),
`(Mitchell et al., 1985), (Preiss, 1980), (Steinberg, 1987).
`
`"nearly
`This configuration methodology is intended for a weakly-connected,
`(Simon, 1969) configuration artifact. Such an artifact can be
`decomposable"
`subdivided into parts or characteristics with relatively weak interactions among
`them. Some of these parts or characteristics can, in turn, be decomposed into a
`number of sub-characteristics or parts, and so on.
`
`Many mechanical products may be viewed as "nearly decomposable." This is
`particularly true for those stages or types of design where the designer has a clear
`picture of the product’s composition, the design decisions that need to be made, the
`alternatives from which to choose, and the constraints that cause coupling between the
`decisions. These are the types of mechanical artifacts and the types of mechanical
`design processes for which this approach is applicable.
`
`The decomposition model represents the configuration process as a sequence of
`steps, where each step starts with an incomplete configuration state and produces
`a configuration state of a greater completeness (in the sense that the new state
`contains more information about the configuration object) by adding to one of the
`components its more detailed description (either its specific "committed"
`implementation, or
`its decompositional description). The new configuration state’s
`structure is the same as the initial state’s structure at least at the level of abstraction
`found in the initial state (Kott and May, 1989).
`
`The decomposition allows the configuration artifact to be viewed as a tree-like
`hierarchic structure. We call this structure the Configuration Knowledge Tree. The
`root of the tree is the final configuration artifact itself. The leaves are elementary
`objects, which are either predefined or are sufficiently simple to be configured by
`some predefined procedures. In general, each part of the tree may be configured
`in more than one way, and, correspondingly, may have more than one
`decomposition. Hence the generalized configuration artifact may be represented by
`an "and-or" tree (Figure 1).
`
`An or-node often represents a design variable. The children of an or-node are the
`alternative values available for this variable. In the process of design or
`configuration, an or-node is given an assignment, i.e., one of the alternative values is
`given to this design variable. An and-nodes may represent an assembly of physical
`objects or an aggregation of design variables.
`
`It is important to note that such a decomposition must be known a priori, before
`the configuration process begins.[Even though the decompositions may be generated
`dynamically in the design process (see sections 3.1 and 3.2), the knowledge for
`generating the decompositions must be available a priori.] Only in this case may
`the decomposition be useful for configuration purposes.
`In a decomposable
`configuration
`problem,
`all possible configurations of the configuration artifact are
`
`Page 2 of 17
`
`FORD 1207
`
`

`
`implicitly known beforehand. However, the space of all possible configurations is
`usually very large and to find a configuration that satisfies a particular set of
`configuration requirements is a computationally explosive problem.
`
`To guide the search through this large space of possible configurations we use
`two forms of domain-specific knowledge: Local Specialists and Constraints.
`
`A Local Specialist is assigned to suggest (guess) the direction of the search when
`constraints are not able to provide the answer, or to guess which of the or-nodes
`should be assigned next when there are no fully constrained or-nodes.
`
`A Constraint here is primarily a procedure that accepts values of one or more
`decision variables and returns the utility associated with this combination of the
`values. The primary role of the constraint is to evaluate how good or how bad is the
`given choice of the values for the decision variables.
`
`These three main concepts, Configuration Knowledge Tree, Constraints, and
`Local Specialists, are discussed in further detail below.
`
`2 CONFIGURATION KNOWLEDGE TREE
`
`A strong hierarchic structure is inherent in many industrial products and systems.
`A typical piece of machinery can be decomposed into a number of major modules,
`such that connectivity between elements within each given module is much stronger
`than between the modules themselves. The major modules can be further
`decomposed into submodules, assemblies, subassemblies,
`parts, features, etc.
`Decision-making in designing or configuring such an object is also done hierarchically:
`first, some top level features are established, then a more detailed level of assembly
`drawings is developed, etc. Decisions made at a higher level of the hierarchy have
`major impact on the lower level decisions. The knowledge about such an object is well
`suited for representation by the hierarchic schema approach.
`
`The hierarchic schema (frame) approach has been in favor with AI researchers
`It is a specialization of a
`since the 1960’s ( (Manheim, 1966), (Preiss, 1980)).
`fundamental problem reduction (decomposition) approach of AI. The problem
`reduction approach may be explained by observing that humans often solve
`problems by factoring them into smaller subproblems, then factoring these
`subproblems into even smaller elements, and so on until resulting subproblems are
`small enough to be solved by some simple means, such as using known solutions. This
`approach has been used successfully for a number of engineering design and
`configuration problems, where it is often referred to as a "refinement" method (
`(Stefik, 1981), (Maher and Fenves, 1985), (Mostow, 1984), (Mittal and Araya,
`1986), (Steinberg, 1987)).
`
`The task of configuring a piece of machinery is well suited for a problem
`reduction approach. A task of configuring a complete machine can be subdivided into
`
`Page 3 of 17
`
`FORD 1207
`
`

`
`tasks of configuring its major modules (or major features); the task of configuring a
`major module can be decomposed into tasks of configuring its major assemblies; and
`so on until we reduce our problem down to a task of choosing between standard
`assemblies or parts.
`
`Thus, to enable a computerized configurator to use the problem reduction approach,
`it must be given at least two categories of knowledge:
`
`1. How to decompose a given feature or a module into smaller sub-features or sub-
`modules.
`
`2. What alternative choices or
`feature or
`module.
`
`implementation options are available for each
`
`This information can be conveniently stored in an "and-or" tree of hierarchic
`schemata. A schema is a description of a concept, or an object, that contains its
`attributes, associated procedures, and relations to other schemata. Each schema is a
`node in a network (in our case it looks more like a tree) of schemata. Relations
`between the schemata form the links in the tree. This tree of schemata holds the
`knowledge of the products offered by a particular manufacturer.
`
`For our configuration problem we store in each schema either the parts and features
`that comprise the object (in this case we call that schema an "and-node"), or the
`alternative implementation options available for this object (in such a case we call
`that schema an "or-node"). For example, to describe an engine we form an or-node
`schema "engine" and include in it a number of alternatives - it can be a V6-ABC model,
`or V8-XYZ model, and so on.
`
`On the other hand, a particular engine model may include a number of
`components or features - engine block, cylinder head, cam-shaft, starting system, etc.
`The schema that represents the particular engine model is an and-node. These
`sub-
`items
`in turn have various optional implementation, or sub-elements.
`
`The combination of all these schemata forms an and-or tree (see Figure 1). Each
`time the configurator needs to configure a product, it can refer to this Configuration
`Knowledge Tree and find what alternative choices are available, and also how to
`subdivide the task of configuring the product into smaller tasks of configuring
`product’s sub-items. Note that schemata can hold other information as well
`-
`prices, weights, engineering limitations, drawing numbers, applicable standards,
`manufacturing and scheduling information, pending price or engineering changes, and
`so on. In this way a Configuration Knowledge Tree can be closely integrated with the
`Sales Order System, Computer Aided Design, Group Technology and MRP modules
`of the Computer Integrated Enterprize.
`
`This approach is predicated on model-based reasoning. In our opinion this
`approach fits closely the specific features of the configuration task that we discussed
`
`Page 4 of 17
`
`FORD 1207
`
`

`
`above. The knowledge base in our approach has a high content of declarative
`knowledge, is highly structured, organized into a network of locally self-sufficient
`chunks, connected with explicitly defined relations. Such a knowledge base is
`advantageous when ease of maintenance is of significant importance. In addition, this
`organization of knowledge is natural for a hierarchically structured product; it has a
`promise of making the most from the existing systems and information bases.
`Furthermore, this organization of knowledge does not limit us to any single
`direction of decision-making: it can be either a bottom-up configuration process, or a
`top-down process, or a combination of both.
`
`3 LOCAL SPECIALISTS
`
`The role of the Local Specialists is to carry the domain specific heuristics that help
`to guide the search through the space of possible configurations (as represented
`in the Configuration Knowledge Tree). They are expected to make a guess about
`which assignment of the or-node should be tried first when constraints do not have
`enough information to provide the answer, or to guess which of the or-nodes should be
`assigned next when there are no fully constrained or-nodes.
`
`In those design and configuration tasks that deal with hierarchically structured
`objects, there are significant advantages in organizing procedural knowledge as a
`hierarchy of local experts (Brown and Chandrasekaran, 1985).
`In our approach,
`Local Specialists are procedures or rules responsible for actually making the
`decisions about both the sequence of the configuration process and the
`selections
`among
`various
`alternative implementations/decompositions.
`Each of
`the
`local specialists is assigned to a single node (schema of an object) and contains
`only a limited amount of knowledge germane to that node. The specialists contain the
`bulk of the procedural knowledge available to the configurator. The maintenance of the
`knowledge is greatly simplified because
`
`- the knowledge is organized into relatively
`
`independent "chunks" - specialists;
`
`- each specialist deals with only one object and
`
`only at one level of hierarchy.
`
`Because there are two kinds of nodes in the Configuration Knowledge Tree
`- and-nodes and or-nodes - there are also two different kinds of specialists - and-
`specialists and or-specialists.
`
`The and-specialists are responsible for choosing an order in which parts of their
`respective and-nodes should be configured. Depending on the current state of
`configuration and on the constraints active for a given configuration session, this
`ordering can be different and may lead to a different outcome of the configuration
`process. In making its decisions, and-specialist refers to the previous decisions and to
`the constraints relevant to its node. All this information is entered into the rule or
`procedure of the specialist and then processed in order to obtain an ordering of the and-
`node parts.
`
`Page 5 of 17
`
`FORD 1207
`
`

`
`The or-specialists are responsible for selecting the most appropriate
`alternative/option among several ones associated with their respective or-nodes. An or-
`specialist contains procedures or rules which refer to the previously made decisions
`and to the constraints imposed on its node. The procedures/rules may either rank all of
`the available alternatives and pick the one with the highest ranking, or name a single
`alternative that is suitable under the current conditions, or generate an alternative
`by, for example, looking up a parts list.
`
`3.1 Or-Specialist
`
`A transformation of one configuration state into another one consists of selecting or
`generating a single child of an or-node and adding this configuration decision to a set
`of decisions made previously (section 5.5). This selection (or dynamic generation) is
`done by a Local Specialist. Each or-node has its own Local Specialist attached to
`it. A Local Specialist is a procedure, or a set of rules, that proposes the most suitable
`choice given the constraints and the choices already made.
`
`For example, an or-specialist attached to an or-node "engine-type" retrieves
`information about the end-user of the order, notices that this particular user requires
`high-power equipment and therefore selects alternative "V8-supercharged" as a
`preferred alternative.
`
`the knowledge embodied in an Or-
`In the mechanical design domain,
`Specialist is usually a compilation of various design constraints. This compilation may
`include considerations of functional capabilities (e.g., ability to deliver the required
`mechanical power), strength concerns, kinematic and geometric requirements, etc.
`Not all constraints can be precompiled in Or-Specialists. There are constraints that
`can be verified only after a set of decisions is made on a best-guess basis. These
`constraints are represented in Constraint schemata described below. For example, an
`Or-Specialist may select a particular cam profile based on an empirical rule-of-
`thumb. Later, after several other relevant design decisions are made by other Or-
`Specialists, a detailed kinematic and dynamic analysis is used to verify the initial
`profile selection in respect to, for example, constraints on noise generation.
`
`The weak connectivity of the configuration object allows the Local Specialists to
`contain only a relatively small amount of local knowledge, so that the Local
`Specialists can make their decisions with a fair degree of certainty. Often, a Local
`Specialist needs to have the information about only a few (e.g., 2 to 5) relevant
`configuration decisions in order to make its own decision. For example, a Local
`Specialist responsible for selection of the bolt for a bolted flange may need only
`the information about the flanges and the gasket. Information about the rest of the
`structure is usually irrelevant.
`
`In many cases, interactions within the object are weak enough to allow pre-ordering
`of the alternatives, in which case the Local Specialist is simplified to a "first-in-a-
`queue" rule.
`
`Page 6 of 17
`
`FORD 1207
`
`

`
`3.2 And-Specialist
`
`Every time when an automated configurator finds an and-node in the
`Configuration Knowledge Tree, it has to decide in which order the sub-elements of
`the and-node should be configured. Note that success of the configuration
`process may depend critically on the correct order of the decision-making. This
`ordering task is expedited by the Local Specialists of the and-nodes. The program
`attempts to choose a child of the and-node that promises the highest certainty
`(compare (Baykan and Fox, 1987)) of making the optimal decision. In some cases,
`an and-specialist may also generate the children of an and-node dynamically, as the
`design process progresses.
`
`For example, when an automated configurator configures a 4-stage turbine, at a
`certain point in the solution process it has to decide in which order to configure these
`four stages. The Local Specialist attached to the and-node "all-four-stages" uses
`domain-specific heuristic to suggest the following strategy: configure the last stage,
`then configure the first stage, then the second stage and the third stage.
`
`Often it may be possible to pre-order this selection. In fact, in many cases both
`or-specialists and and specialists can be nothing more than a predetermined order of
`preference. Indeed, most human configurators do their job by making design decision
`in a predetermined order and trying the alternative values for the design variable also
`in a (almost) predetermined order. In spite of apparent naivete of this approach, a
`large amount of powerful domain-specific knowledge can be conveyed
`rather
`inexpensively.
`
`4 CONSTRAINTS
`
`Constraints serve to evaluate suitability of the design decisions proposed by
`the Or-Specialists. The constraints may reflect concerns from any applicable
`discipline: geometric fit, strength considerations, fluid dynamics, chemical
`compatibility, etc. In some cases, a constraint may have a clear relation to an
`underlying engineering discipline, e.g., a constraint that calculates stress in a flywheel
`and compares it to the maximum allowable. On the other hand, a constraint may
`be of a highly compiled nature, e.g., it simply states that component X should not
`be used with component Y, without explicitly elucidating multiple reasons for
`this
`incompatibility.
`
`We view a constraint primarily as a procedure that accepts assignments of one or
`more or-nodes and returns the utility associated with this combination of assignments.
`The primary role of the constraint is to evaluate how good or how bad is the choice
`of the assignments for the or-nodes that have been made by the Local Specialists.
`There are also other aspects and functions born by the constraints that are discussed
`later.
`
`Page 7 of 17
`
`FORD 1207
`
`

`
`Constraints play a number of important roles in problem solving ( (Stefik,
`1981), (Fox, 1986)). A constraint acts on one or more of the product components
`(features, parts, etc.), either by checking that the constrained component indeed
`satisfies a certain condition encoded within the constraint, or by verifying proper
`relations between two or more components, e.g., compatibility of two
`arrangements. A constraint may also have a precondition which determines when
`constraint is ready to be checked. It may contain a measure of its importance, a
`penalty associated with its violation, and a range within which the violation is still
`tolerable. A constraint may be active or inactive, depending on the state of
`configuration and, possibly, on the state of other constraints. Constraint may contain
`information about the decisions it is dependent upon, and suggestions for possible
`fixes in case of violation. This information is used by the configuration inference
`engine in order to make an informed revision of some previous selections. By noting
`those constraints that are "almost" triggered (e.g., constraint relates two components
`of the product, and one of them has been already selected), the inference engine may
`determine which selection has been constrained the most and where its next decision
`should be made.
`
`In a typical configuration problem there may be a rather large number of
`constraints specified. The most important sources of the constraints are usually
`the existing engineering documents as well as undocumented knowledge of human
`experts. Often many of the constraints are binary or higher order compatibility
`constraints of a type:
`configuration alternative A5 of part A is incompatible
`with configuration alternative B21 of part B if alternative C537 of part C is used.
`Another common type of constraints assign a utility value to a given partial
`configuration:
`if distance between part A and part B is less than .25 in, the utility
`value is .2, if it is more than 1.5 in - the utility value is .6, otherwise the utility
`value is .9. Constraints generally involve a small subset of
`the configuration
`structure, not
`the configuration object as a whole, an indication of a weakly-
`connected configuration object.
`
`In our approach each of the constraints is represented by a schema. The most
`important elements of the constraint schema are two procedures. One procedure defines
`when the constraint is ready to be applied, i.e. when there is enough information
`available to evaluate the constraint. The second procedure evaluates the configuration
`state and returns its value, a measure of the "goodness" of the configuration state. In
`many cases the nature of the domain is such that most of the constraints are of a
`predicate nature (pass or fail). Each individual constraint tends to refer to only a few
`elements of the configuration, e.g., to compatibility of two particular parts. The
`constraints are localized.
`In order to evaluate a particular constraint, the problem
`solver needs to have information about only a small part of the overall configuration.
`Information about the rest of the configuration is irrelevant. Because the source of a
`constraint violation can be identified, it is possible to associate any constraint with
`information about the ways to fix that violation by reconsidering previously made
`decisions so that dependency-based and knowledge-based backtracking are possible
`(compare (Mittal and Araya, 1986), (Marcus, 1986)).
`
`Page 8 of 17
`
`FORD 1207
`
`

`
`5 PROBLEM SOLVING
`
`Having described the Configuration Knowledge Tree, the Local Specialists, and the
`Constraints, we now discuss the configuration process itself. The process of configuring
`a product or a system is thought of as a search process. The search takes place in the
`space of all possible configurations - both partial and complete ones. A partial
`configuration is the one where only some of the decisions required to configure the
`product are made. The search usually starts with a "partial configuration" that contains
`no decisions - an empty configuration. Each new decision creates a new partial
`configuration - a new state of the search space. The search proceeds (usually with
`some backtracking) until a complete and "good" configuration is found.
`
`5.1 Search Space
`
`The set of all possible configurations is implicitly represented by the Configuration
`Knowledge Tree. A subtree of this tree such that every non-terminal and-node has all
`of its children within the subtree, and every non-terminal or-node has exactly one
`child within the subtree is a particular configuration - a state in the search space. In
`this sense the search space is known before the solution process starts. The number of
`states in the search space is finite, although it can be very large. As search proceeds, the
`remaining search space becomes smaller and smaller. Because the search space in
`this type of problem is reasonably well structured and explicitly defined, a
`declarative representation of the knowledge appears to be particularly attractive. The
`large number of dissimilar objects, constraints, and relations that need to be
`represented places heavy demands on the representation language.
`
`5.2 State Representation
`
`An individual configuration representation is a list of alternatives chosen for this
`configuration, and a list of choices that have been tried but which have failed to
`satisfy constraints. The list of choices defines a subtree of the and-or tree. The list of
`failed choices serves to avoid making the same choice again in the same partial
`configuration state. The choices are hierarchically related. A lower level choice is
`dependent upon the higher level choices. Only certain lower level choices are
`compatible with a particular higher
`level choice, reflecting the hierarchic nature
`of the configuration object itself.
`
`The initial state is usually an empty state, i.e., its list of configuration choices is
`empty. As the search process proceeds, new choices (decisions) are added to list of
`choices, until a complete configuration is found. In this way, the search process
`generates the desired configuration.
`
`5.3 Search Strategy
`
`The number of configuration states implicitly represented in the
`Configuration Knowledge Tree is extremely large even for a problem with a
`
`Page 9 of 17
`
`FORD 1207
`
`

`
`relatively small number of design decisions. The search strategy must be such that
`only a relatively small subset of the search space needs to be visited (generated)
`during the search process.
`
`The search algorithm utilized in the proposed approach resembles the A* algorithm
`(Pearl, 1984). The state evaluation function combines the costs returned by those
`constraints that can be evaluated within the current state with the estimated costs of
`those constraints that are expected to be encountered before the goal state is
`reached. A state with the lowest cost is used to continue the configuration process.
`This approach exploits the weakly connected, decomposable nature of the
`configuration object, in which a constraint remains inactive until the configuration
`process reaches those parts of the object that are relevant to the constraint. Only a
`subset of the total number of the constraints is involved in the evaluation, and
`only the most recently configured part of the object needs to be considered, not the
`whole state.
`
`Assuming that no backtracking occurs, the number of states generated during the
`search process is equal to the number of decisions made in the complete
`configuration (number of or-nodes in the solution subtree). This number may range
`from several hundreds to several thousands for a typical configuration problem.
`
`5.4 Backtracking
`
`Even though there is an opportunity here to backtrack in a "best-first" fashion using
`the state evaluation, most of the backtracking occurs when the problem-solving
`mechanism fails to find an alternative for an or-node that satisfies all the constraints
`attached to it . In such a case, by examining the nodes attached to the offending
`constraint, it is possible to identify those previous configuration decisions that may
`need to be revised in order to correct the situation. In addition, a procedure may be
`(but does not have to be) attached to any constraint to help to decide which of the
`several configuration decisions is the one that may be revised most easily and how to
`revise it, so that both dependency-directed and knowledge-based backtracking are
`possible.
`
`5.5 Solution Process
`
`A queue LIST-OF-STATES (Figure 2) contains a number of partial configurations.
`Each partial configuration is represented by a schema. Function SELECT-BEST uses
`one of several possible criteria to choose the best of the partial configurations called
`BEST-STATE. The simplest criteria is to prefer the state with largest number of
`decisions made - this strategy allows the problem solver to arrive at a satisfactory
`(feasible) solution in the shortest time. A more complicated strategy would be to
`select a state with the optimum expected value of some objective function, e.g.,
`with lowest estimate of a life-time cost of ownership. This strategy leads to an
`(approximately) optimum solution rather than just a satisfactory one. The user of the
`system may choose one of
`the several predetermined strategies, or to mix them.
`
`Page 10 of 17
`
`FORD 1207
`
`

`
`The selected partial configuration BEST-STATE is passed to function ADD-
`DECISION which analyzes BEST-STATE and adds some information to the partial
`configuration, thus producing a new partial configuration NEW-STATE. Function
`ADD-DECISION can make two types of decisions. One type is a decision about the
`focus of the action - which part of the Configuration Knowledge Tree should be
`attacked next. It may be a part of the tree closer to the bottom of the tree, near the top
`of the tree, or someplace in the middle of the tree. This choice is non-trivial. There are
`three levels of knowledge that may be consulted in order to make this decision. First, the
`constraints are reviewed to see if some elements of the tree have become fully
`constrained so that it is easy now to make a decision about these elements. If no definite
`conclusion can be made from the evaluation of constraints , the hierarchical relations
`are considered - the objects higher up in the hierarchy are given preference. If this still
`does not give an answer, e.g., the choice needs to be made between the parts of an
`and-node, then the and-local specialists are asked to intervene and to use their
`heuristics to select a next element to configure. Even very simple and inexpensive
`local specialists can be very helpful in guiding the process of search.
`
`A second type of decision is made only after the first (focusing) decision has been
`made. This decision selects a particular alternative among alternatives associated with
`an or-node that has been chosen as a focal node. At least two levels of knowledge can
`be consulted - the constraints, and the local or-specialists. First, all available
`alternatives are filtered through the
`applicable constraints. A constraints is
`considered to be applicable if the focal node is connected to the constraint, and if the
`preconditions for evaluation are met (e.g., all the other nodes attached to the constraint
`have been already solved). In this way a constraint becomes active as soon as enough
`information is available to evaluate the constraint. Every candidate alternative is
`checked against the closest (directly connected to the last decision) constraint.
`If the
`closest constraint passes, then constraints associated with the higher level nodes are also
`checked if possible (i.e., if the partial configuration contains enough details to allow
`constraint to fire). Some look-ahead is also performed to assure that the alternative
`will not cause some impasse in respect to the remaining decisions. Commonly
`the constraints prune out some of the alternatives, yet still more than one
`alternative is left. In this case the local specialist is consulted to select the most
`promising of the alternatives. Again, even very simple local specialists (such as fixed
`ranking order) can drastically improve the performance of the algorithm. The new
`decision is added to the BEST-STATE and the result is a new partial configuration -
`NEW-STATE.
`
`There are cases when application of the constraints reveals that none of the
`alternatives can be used. This means that either the user requirements over-constrained
`the problem so that no solution is possible, or that some bad choices have been made
`earlier in the solution process. We call this situation a failure. The problem solver
`creates a FAILURE-REPORT that describes the constraints that have failed and
`passes them to the SELECT-BEST function that is responsible for handling failures.
`
`Page 11 of 17
`
`FORD 1207
`
`

`
`There may be several strategies to follow in a case of a failure. The simplest one is to
`dump the NEW-STATE and to return to a previous state. A more sophisticated strategy
`is to gather all the output from the constraint checking and determine which of the
`previous decisions should be changed in order to fix violated constraints. This
`information then is used for backtracking to the promising decision. The LIST-OF-
`STATES is pruned of all the states that contain the failed decision, and the process
`repeats.
`
`If failure does not occur (at least one satisfactory alternative i