Constraint Satisfaction in Artificial Intelligence
Many problems in Al can be viewed as problems of “constraint satisfaction” in which the es of this sort of problem include cryptarithmetic puzzles (as described in Section 2.6) and many real-world perceptual labelling problems. Design tasks can also be viewed as constraint-satisfaction problems in which design must be created within fixed limits goal is to discover some problem state that satisfies a given set of constraints. Example on time, cost, and materials.
A Necessary Backward Propagation
By viewing a problem as one of “constraint satisfaction”, it is often possible to reduce substantially the amount of search that is required as compared with a method that attempts to form partial solutions directly by choosing specifiç values for components of the eventual solution. For example, a straightforward search procedure to solve a “cryptarithmetic” problem might operate in a state space of partial solutions in which letters are assigned particular numbers as their values.
A depth-first control scheme could then follow a path of assignments until either a solution or an inconsistency is discovered. In contrast to this, a constraint satisfaction approach to solving this problem avoids making guesses on particular assignments of numbers to letters until. Instead, the initial set of constraints, which says that each number may correspond to only one letter and that sums of the digits must be as they are given in the problem, first augmented to include restrictions that can be inferred from the rules of arithmetic. Although guessing may still be required, the number of allowable guesses is reduced and so the degree of search is curtailed.
Constraint Satisfaction Algorithm in Artificial Intelligence
Algorithm: Constraint Satisfaction Algorithm
1. Propagate available constraints. To do this, first set OPEN to the set of all object that must have values assigned to them in a complete solution. Then do until an inconsistency is detected or until OPEN is empty:
(a) Select an object OB from OPEN. Strengthen as much as possible the set of constraints that apply to OB.
(b) If this set is different from the set that was assigned the last time OB way examined or if this is the first time OB has been examined, then add to OPEN all objects that share any constraints with OB.
(c) Remove OB from OPEN.
2. If the union of the constraints discovered above defines a solution, then quit and report the solution.
3. If the union of the constraints discovered above defines a contradiction, then return failure.
4. If neither of the above occurs, then it is necessary to make a guess at something in order to proceed. To do this, loop until a solution is found or all possible solutions have been eliminated:
(a) Select an object value is not yet determined to select a way of strengthening the constraints that object.
(b) Recursively invoke constraint satisfaction with the current set of constraints augmented by the strengthening constraint just selected.
No tow letter have the same value.
The sums of the digits must be as shown in the problem.
A Cryptarithmetic Problem in Ai
This algorithm has been stated as generally as possible. To apply it in a particular problem domain requires the use of two kinds of rules: rules that define the way constraints may validly be propagated and rules that suggest guesses when guesses are necessary. It is worth noting, though, that in some problem domains guessing may 0 not be required. For example, the Waltz algorithm for propagating line labels in a picture, which is described in Chapter 14, is a version of this constraint satisfaction algorithm with the guessing step eliminated. In general, the more powerful the rules for propagating constraints, the less need there is for guessing.
The result of the first few cycles of processing this example is shown in Figure 3.14, Since constraints never disappear at lower levels, only the ones being added are shown for each level. It will not be much harder for the problem solver to access the constraint as a set of lists than as one long list, and this approach is efficient both in terms of st space and the ease of backtracking. Another reasonable approach for this problem would be to store all the constraints in one central database and also to record at each node the changes that must be undone during backtracking. C1, C2, C3, and C4 indicate the carry bits out of the columns, numbering from the right.
Constraint Satisfaction Problem Artificial Intelligence
Initially, rules for propagating constraints generate the following additional constraints:
- M = 1, since two single-digit numbers plus a carry cannot total more than 19.
- S = 8 or 9, since S+M+C3> 9 (to generate the carry) and M=1,S+ 1+C3> 9, so S+ C3> 8 and C3 is at most 1.
- 0 =0 , since S + M(l) + C3(<=1) must be at least 10 to generate a carry and it can be at most 11. But M is already 1, so O must be 0.
- N=E or E+1, depending on the value of C2. But N cannot have the same value as E. So N=E +1 and C2 is 1.
- In order for C2 to be 1, the sum of N + R + CI must be greater than 9, so N +R must be greater than 8.
- N+ R cannot be greater than 18, even with a carry in, so E cannot be 9.
At this point, let us assume that no more constraints can be generated. Thea. to make progress from here, we must guess. Suppose E is assigned the value 2 (We chose to guess a value for E because it occurs three times and thus interacts highly with the other letters) Now the next cycle begins.
The constraint propagator now observes that:
N =3, since N =E+1.
R = 8 0r 9 , since R + N ( 3 ) + Cl ( l or 0 ) = 2 or 12. But since N is already 3 , the sum of these nonnegative numbers cannot be less than 3. Thus R+3+(0 or l)= 12 and R = 8 or 9 .
2 + D = Y or 2 + D = 10 + Y , from the sum in the rightmost column .
Again, assuming no further constraints can be generated, a guess is required, Suppose Cl is chosen to guess a value for. If we try the value I, then we eventually reach dead ends, as shown in the figure. When this happens, the process will backtrack and try C1 = 0.
A couple of observations are worth making on this process. Notice that all that is required of the constraint propagation rules is that they do not infer spuriously constrains They do not have to enter all legal ones. For example, we could have reasoned through to the result that CI equals. We could have done so by observing that for CI to be I. the following must hold: 2+ D-10+ Y. For this to be the case, D would have been 8 or 9. But both S and R must be either 8 or 9 and three letters cannot share two values. So Cl cannot be I. if we had realized this initially, some search could have bee avoided. But since the constraint propagation rules we used were not that sophisticated.
Solving Cryptarithmetic Problems
it took son the constraint propagation r required for constraint propagation. search. Whether the search route takes more or less actual time than does constraints pro at Dodson how on it takes to perform the reasoning ing to notice is that there are often two kinds of constraints. The simple; they just list possible values for a single object.
The second kind is more complex; they describe relationships between or among objects. Both kinds of constraints play the same role in the constraint satisfaction process, and in the cryptarithmetic example, they were treated identically. For some problems, however, it may be useful to represent the two kinds of constraints differently. The simple, value- Listing constraints are always dynamic, and so must always be represented explicitly in each problem state.
The more complicated, relationship-expressing constraints are second the first kind are s dynamic in the cryptarithmetic domain since they are different for each cryptarithmetic problem. But in many other domains, they are static. For example, in the Waltz line labelling algorithm, the only binary constraints arise from the nature of the physical world, in which surfaces can meet in only a fixed number of possible ways. These ways are the same for all pictures that that algorithm may see. Whenever the binary in the state description but rather to encode them in don it may be computationally efficient not to represent them explicitly the algorithm directly. When this is are possible values. But the essential algorithm e, the only things that get propagated is the same in both cases.