AI_ConstraintSatisfaction_(2).pptxmmmmmm

Ai notes

1. Constraint Satisfaction Constraint satisfaction means solving a problem under certain constraints or rules . Constraint satisfaction is a technique where a problem is solved when its values satisfy certain constraints or rules of the problem. Such type of technique leads to a deeper understanding of the problem structure as well as its complexity. Constraint satisfaction problems (or CSPs) consist of variables with constraints on them. Many important real- world problems can be described as CSPs. The structure of a CSP can be represented by its constraint graph . CSPs are mathematical questions defined as a set of objects whose state must satisfy a number of constraints or limitations.

2. Constraint Satisfaction We use a factored representation for each state: a set of variables, each of which has a value. A problem is solved when each variable has a value that satisfies all the constraints on the variable. A problem described this way is called a constraint satisfaction problem, or CSP.

3. Components Constraint satisfaction depends on three components , namely: X: It is a set of variables. D: It is a set of domains where the variables reside. There is a specific domain for each variable. C: It is a set of constraints which are followed by the set of variables.

4. Components In constraint satisfaction, domains are the spaces where the variables reside . Values assigned to variables in X must be one of their domain in D. The constraint value consists of a pair of {scope, rel} . The scope is a tuple of variables which participate in the constraint and rel is a relation which includes a list of values which the variables can take to satisfy the constraints of the problem.

5. Components For example, if X1 and X2 both have the domain {A,B}, then the constraint saying the two variables must have different values can be written as {(X1,X2), [(A, B), (B, A)]} or as {(X1,X2),X1 != X2}. A = {1,2} and B = {2,4} C = {(X1,X2)[(1,2)(2,4)]}

6. An assignment that does not violate any constraints is called a consistent or legal assignment. A complete assignment is one in which every variable is assigned, and a solution to a CSP is a consistent, complete assignment. A partial assignment is one that assigns values to only some of the variables.

7. The simplest kind of CSP involves variables that have discrete, finite domains. Map- coloring problems and scheduling with time limits are both of this kind. The 8- queens problem can also be viewed as a finite-domain CSP, where the variables Q1, . . . ,Q8 are the positions of each queen in columns 1, . . . , 8 and each variable has the domain Di = {1, 2, 3, 4, 5, 6, 7, 8}.

8. The unary constraint, restricts the value of a single variable. For example, in the map- coloring problem it could be the case that South Australians won’t tolerate the color green; we can express that with the unary constraint (SA),SA != green. A binary constraint relates two variables. For example, SA = NSW is a binary constraint. A constraint involving an arbitrary number of variables is called a global constraint. One of the most common global constraints is Alldiff , which says that all of the variables involved in the constraint must have different values. In Sudoku problems, all variables in a row or column must satisfy an Alldiff constraint. An other example is provided by cryptarithmetic puzzles.

9. CSP Problems Constraint satisfaction includes those problems which contains some constraints while solving the problem. CSP includes the following problems: Map Coloring (coloring different regions of map, ensuring no adjacent regions have the same color) Sudoku (a number grid) CryptArithmetic (Coding alphabets to numbers.) n- Queen (In an n- queen problem, n queens should be placed in an nXn matrix such that no queen shares the same row, column or diagonal.) Crossword (everyday puzzles appearing in newspapers) Latin Square Problem

10. Converting Process & Example A problem to be converted to CSP requires the following steps: Step 1: Create a variable set. Step 2: Create a domain set. Step 3: Create a constraint set with variables and domains (if possible) after considering the constraints. Step 4: Find an optimal solution.

11. Job Shop scheduling Consider the problem of scheduling the assembly of a car. The whole job is composed of tasks, and we can model each task as a variable, where the value of each variable is the time that the task starts, expressed as an integer number of minutes. Constraints can assert that one task must occur before another—for example, a wheel must be installed before the hubcap is put on—and that only so many tasks can go on at once. Constraints can also specify that a task takes a certain amount of time to complete. We consider a small part of the car assembly, consisting of 15 tasks: install axles (front and back), affix all four wheels (right and left, front and back), tighten nuts for each wheel, affix hubcaps, and inspect the final assembly. We can represent the tasks with 15 variables: X = {AxleF , AxleB,WheelRF ,WheelLF ,WheelRB,WheelLB, NutsRF , NutsLF , NutsRB, NutsLB, CapRF , CapLF , CapRB, CapLB, Inspect} . The value of each variable is the time that the task starts. Next we represent precedence constraints between individual tasks. Whenever a task T1 must occur before task T2 and task T1 takes duration d1 to complete, we add an arithmetic constraint of the form :T1 + d1 ≤ T2 .

12. In our example, the axles have to be in place before the wheels are put on, and it takes 10 minutes to install an axle, so we write AxleF + 10 ≤ WheelRF ; AxleF + 10 ≤ WheelLF ; AxleB + 10 ≤ WheelRB; AxleB +10 ≤ WheelLB . Next we say that, for each wheel, we must affix the wheel (which takes 1 minute), then tighten the nuts (2 minutes), and finally attach the hubcap (1 minute, but not represented yet): WheelRF + 1 ≤ NutsRF ; NutsRF + 2 ≤ CapRF ; WheelLF + 1 ≤ NutsLF ; NutsLF +2 ≤ CapLF ; WheelRB + 1 ≤ NutsRB; NutsRB + 2 ≤ CapRB; WheelLB + 1 ≤ NutsLB; NutsLB + 2 ≤ CapLB . Suppose we have four workers to install wheels, but they have to share one tool that helps put the axle in place. We need a disjunctive constraint to say that AxleF and AxleB must not overlap in time; either one comes first or the other does: (AxleF + 10 ≤ AxleB) or (AxleB + 10 ≤ AxleF ) .

13. Graph Coloring: We are given a map, i.e. a planar graph, and we are told to color it using three colors, green, red, and blue, so that no two neighboring countries have the same color. The constraint is that a color that is assigned to a region cannot be assigned to the adjacent regions (no adjacent sides can have the same color). The variables which are the regions, the domains are the colors that we can assign to the variables (red, green, yellow, blue).

14. Example Map of Australia showing each of its states and territories. We are given the task of coloring each region either red, green, or blue in such a way that no neighboring regions have the same color. X = {WA,NT ,Q,NSW ,V,SA,T} . Each variable represents a region of Australia.

15. Contd.. Now, if we had to color this map three different colors, say red, green and blue, this would be a valid solution to our map coloring problem:

16. Contd.. The domain of each variable is the set D i = {red, green, blue} . The constraints require neighboring regions to have distinct colors. Since there are nine places where regions border, there are nine constraints: C = {SA != WA, SA != NT , SA != Q, SA != NSW , SA != V, WA != NT , NT != Q, Q != NSW , NSW != V } . Where SA != WA can be fully enumerated in turn as {(red , green ), (red , blue), (green , red ), (green , blue), (blue, red ), (blue, green )} . There are many possible solutions to this problem, such as {WA = red , NT = green, Q= red , NSW = green, V = red , SA = blue, T = red }

17. Constraint graph It can be helpful to visualize a CSP as a constraint graph, as shown in Figure. The nodes of the graph correspond to variables of the problem, and a link connects any two variables that participate in a constraint .

18. Contd..

19. Backtracking Search Backtracking search is just a search algorithm that finds some assignment that satisfies a CSP. At a very high level, the algorithm assigns a value to each variable one-by- one until either reaching a valid assignment or an invalid assignment that violates some constraint , at which point it backtracks to a place in the search where there are no violations yet .

20. Example Graph coloring is the procedure of assignment of colors to each vertex of a graph G such that no adjacent vertices get same color. The objective is to minimize the number of colors while coloring a graph. The smallest number of colors required to color a graph G is called its chromatic number of that graph.

21. Example

22. Example

23. Sudoku Playing: Consider a Sudoku game with some numbers filled initially in some squares. You are expected to fill the empty squares with numbers ranging from 1 to 9 in such a way that no row, column or a block has a number repeating itself . This is a very basic constraint satisfaction problem. You are supposed to solve a problem keeping in mind some constraints. The remaining squares that are to be filled are known as variables , and the range of numbers (1- 9) that can fill them is known as a domain. Variables take on values from the domain. The conditions governing how a variable will choose its domain are known as constraints.

24. Sudoku Playing: The gameplay where the constraint is that no number from 0- 9 can be repeated in the same row or column and block. Suppose that a row, column and block already have 3, 5 and 7 filled in. Then the domain for all the variables in that row, column and block will be {1, 2, 4, 6, 8, 9}.

25. Contd.. Variables. X = {A1, A2, …, I8, I9}. We’ll just have a variable for each cell in the sudoku puzzle for a total of 81 variables. the variable A1 is just a variable that represents the cell in the Ath row and the 1st column. Domains. D = {1, 2, 3, 4, 5, 6, 7, 8, 9}. For the domain of each variable, we’ll just start with all of the numbers from 1 to 9. Constraints. We’ll have three types of constraints here: a constraint that says all of the variables in each column has to differ, all of the variables in each row has to differ, and all of the variables in each square has to differ.

26. n- queen problem: In n- queen problem, the constraint is that no queen should be placed either diagonally, in the same row or column.

27. n- queen problem: (2, 4, 1, 3) (3, 1, 4, 2)

28. Crossword: In crossword problem, we have a grid with blocked and unblocked cells and a dictionary of words and the constraint is that there should be the correct formation of the words , and it should be meaningful.

29. Crossword: In the crossword puzzle, Variables: Unblocked cells. Domains: The domain of each variable is the set of letters/words of the alphabet. Constraints: For each vertical or horizontal contiguous segment of unblocked cells , constraining the letters assigned to the cells in that segment to form a word that appears in the dictionary.

30. Cryptarithmetic Problem: Cryptarithmetic Problem is a type of constraint satisfaction problem where the game is about digits and its unique replacement either with alphabets or other symbols. Cryptarithmetic problem is a mathematical puzzle, in which the digits (0- 9) get substituted by some possible alphabets or symbols . The task in cryptarithmetic problem is to substitute each digit with an alphabet to get the result arithmetically correct. This problem has one most important constraint that is, we cannot assign a different digit to the same character. All digits should contain a unique alphabet.

31. Contd.. There should be a unique digit to be replaced with a unique alphabet . The result should satisfy the predefined arithmetic rules, i.e., 2+2 =4, nothing else. Digits should be from 0- 9 only . There should be only one carry forward , while performing the addition operation on a problem. The problem can be solved from both sides, i.e., left hand side (L.H.S), or righthand side (R.H.S) All the same, alphabets have the same numbers . The numbers should satisfy all the operations that any normal number does.

32. Cryptarithmetic Problem: TO ● +GO OUT

33. Cryptarithmetic Problem: ● IS +THIS YEAR

34. Cryptarithmetic Problem: 21+81 = 102 9567+1085 = 10652 65+8965 = 9030 96233+62513 = 158746 1934+8534 = 10468

35. Latin square Problem: In this game, the task is to search the pattern which is occurring several times in the game. They may be shuffled but will contain the same digits.