CS3081_AI_Lec5_Ch5_CSP(3).pdf

Chapter 5: Constraint Satisfaction Problems What is CSP? CS 3081: Introduction to Artificial Intelligence Dr. Akila Sarirete Fall 2024 Effat University 1 / 30 Outline What is Search For? Constraint Satisfaction Problems CSP Example:...

Chapter 5: Constraint Satisfaction Problems What is CSP? CS 3081: Introduction to Artificial Intelligence Dr. Akila Sarirete Fall 2024 Effat University 1 / 30 Outline What is Search For? Constraint Satisfaction Problems CSP Example: Map Coloring Constraint Graphs Standard Search Formulation 2 / 30 What is Search for? 3 / 30 What is Search For? Assumptions about the world: A single agent, deterministic actions, fully observed state, discrete state space. Planning: Planning is about figuring out a sequence of steps (the path) to reach a goal efficiently. The path to the goal is the important thing. Paths have various costs, depths. Heuristics give problem-specific guidance. Identification: The goal itself is important, not the path. All paths at the same depth (for some formulations). CSPs are a specialized class of identification problems. 4 / 30 Constraint Satisfaction Problems 5 / 30 Constraint Satisfaction Problems Standard search problems: State is a ”black box”: arbitrary data structure. Goal test can be any function over states. Successor function can also be anything. Constraint satisfaction problems (CSPs): A special subset of search problems. State is defined by variables Xi with values from a domain D (sometimes D depends on i). Goal test is a set of constraints specifying allowable combinations of values for subsets of variables. Allows useful general-purpose algorithms with more power than standard search algorithms. 6 / 30 CSP Example: Map Coloring 7 / 30 Example: Map Coloring Variables: WA, NT, Q, NSW, V, SA, T Domains: D = {red, green, blue} Constraints: adjacent regions must have different colors Implicit: WA ̸= NT Explicit: (WA, NT ) ∈ State {(red, green), (red, blue),... } Western Australia Solutions are assignments satisfying all Northern Territory constraints, e.g.: Queensland New South Wales {WA=red, NT=green, Q=red, Victoria NSW=green, V=red, SA=blue, South Australia T=green} Tasmania 8 / 30 Australia Map Exploration 9 / 30 Example: N-Queens - Formulation 1 N-Queens Problem: The goal is to place N queens on an N × N chessboard such that no two queens threaten each other (i.e., no two queens can share the same row, column, or diagonal). Formulation 1: Variables: Xij ; Domains: {0, 1} Constraints: ∀i, j, k (Xij , Xik ) ∈ {(0, 0), (0, 1), (1, 0)} ∀i, j, k (Xij , Xkj ) ∈ {(0, 0), (0, 1), (1, 0)} ∀i, j, k (Xij , Xi+k,j+k ) ∈ {(0, 0), (0, 1), (1, 0)} ∀i, j, k (Xij , Xi+k,j−k ) ∈ {(0, 0), (0, 1), (1, 0)} X Xij = N i,j 10 / 30 Explanation: N-Queens Formulation 1 Variables Xij : Represents whether a queen is placed at row i and column j. It can take values from the domain {0, 1}, where: Xij = 1 means a queen is placed at position (i, j). Xij = 0 means there is no queen at that position. Constraints: The constraints ensure that no two queens threaten each other. This is achieved by enforcing the following rules: No two queens in the same row: (Xij , Xik ) ∈ {(0, 0), (0, 1), (1, 0)} No two queens in the same column: (Xij , Xkj ) ∈ {(0, 0), (0, 1), (1, 0)} No two queens on the same diagonal (right-sloping): (Xij , Xi+k,j+k ) ∈ {(0, 0), (0, 1), (1, 0)} No two queens on the same diagonal (left-sloping): (Xij , Xi+k,j−k ) ∈ {(0, 0), (0, 1), (1, 0)} Finally, the total number of queens placed must be exactly N: X Xij = N i,j 11 / 30 Example: N-Queens - Formulation 2 Formulation 2: Variables: Qk Domains: {1, 2, 3,... N} Constraints: Implicit: ∀i, j non-threatening(Qi , Qj ) Explicit: (Q1 , Q2 ) ∈ {(1, 3), (1, 4),... }... 12 / 30 Explanation: N-Queens Formulation 2 **Variables Qk **: Represent the row positions of the queens. Each Qk corresponds to a queen’s column in row k. **Domain {1, 2, 3,... , N}**: The set of columns available for placing queens in each row. **Constraints**: **Implicit**: No two queens can threaten each other. This means they cannot share the same row, column, or diagonal. **Explicit**: Specific allowed positions, e.g., Q1 in column 3, Q2 in column 1, etc., such that no queens are attacking each other. **Chessboard Representation**: Shows an example of non-threatening queen placements, demonstrating how queens are placed without sharing the same row, column, or diagonal. 13 / 30 Constraint Graphs 14 / 30 Constraint Graphs Binary CSP: each constraint relates (at most) two variables. Binary constraint graph: nodes are variables, arcs show constraints. General-purpose CSP algorithms use the graph structure to speed up search, e.g., Tasmania is an independent subproblem! 15 / 30 Example: Cryptarithmetic Cryptarithmetic Problems: These are puzzles where each letter represents a unique digit, and the goal is to assign digits to letters such that the arithmetic operation is valid. Variables: F , T , U, W , R, O, X1 , X2 , X3 Domains: {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} Constraints: alldiff(F , T , U, W , R, O) O + O = R + 10 · X1... 16 / 30 Explanation: Cryptarithmetic Example Variables: - The letters F , T , U, W , R, O represent the variables that will be assigned a unique digit from the domain. - Additionally, X1 , X2 , X3 are carry-over variables used in solving multi-digit additions (for example, when the sum of two digits exceeds 9). Domains: - The domain for each variable is the set {0, 1, 2,... , 9}, meaning that each letter can be mapped to one of these digits. Constraints: - The alldiff constraint ensures that all letters F , T , U, W , R, O represent distinct digits (no two letters have the same digit). - The equation O + O = R + 10 · X1 represents the arithmetic operation in the puzzle. It means that when you add the two O’s, you get R, with the carry X1 added to the tens column. Example Puzzle (TWO + TWO = FOUR): - The puzzle displayed is an example of how cryptarithmetic works. Here, the letters T, W, O, and F are assigned digits that satisfy the addition: TWO + TWO = FOUR. 17 / 30 Varieties of CSPs Discrete Variables Finite domains Size d means O(d n ) complete assignments e.g., Boolean CSPs, including Boolean satisfiability (NP-complete) Infinite domains (integers, strings, etc.) e.g., job scheduling, variables are fixed start/end times for each job Continuous Variables e.g., start/end times for Hubble Telescope observations. 18 / 30 Explanation: Varieties of CSPs **Discrete Variables**: **Finite Domains**: - These are variables that have a limited, fixed set of values they can take. For example, in a Boolean CSP, variables can take values from {0, 1}. - The complexity of finding a complete assignment for n variables with a domain of size d is proportional to O(d n ), where n is the number of variables. **Infinite Domains**: - These are variables that can take an infinite number of possible values, such as integers, real numbers, or strings. - An example is **job scheduling**, where the start and end times of jobs are variables that can be assigned infinite values. **Continuous Variables**: - These variables can take any value in a continuous range. An example of this is the start/end times for Hubble Telescope observations, where times can be any point in a continuous interval. 19 / 30 Varieties of Constraints Varieties of Constraints: Unary Constraints involve a single variable (equivalent to reducing domains), e.g: SA ̸= green Binary constraints involve pairs of variables , e.g.: SA ̸= WA Higher-order constraints involve 2 or more variables, e.g., cryptarithmetic column constraints. Preferences (soft constraints) e.g., red is better than green Often representable by a cost for each variable assignment Gives constrained optimization problems 20 / 30 Real-World CSPs Scheduling problems: e.g., when can we all meet? Timetabling problems: e.g., which class is offered when and where? Assignment problems: e.g., who teaches what class? Hardware configuration Transportation scheduling Factory scheduling Circuit layout Fault diagnosis... lots more! Many real-world problems involve real-valued variables... 21 / 30 Standard Search Formulation 22 / 30 Standard Search Formulation States defined by the values assigned so far (partial assignments): Initial state: the empty assignment, {} Successor function: assign a value to an unassigned variable Goal test: the current assignment is complete and satisfies all constraints We’ll start with the straightforward, naı̈ve approach, then improve it. 23 / 30 Search Methods NT WA Q What would BFS do? SA NSW What would DFS do? V T 24 / 30 Breadth-First Search (BFS) in CSP How BFS works: BFS explores all possible color NT assignments for WA first. Then, moves to adjacent regions (NT, SA). WA Q Ensures the shallowest solution is found first, but may explore SA NSW unnecessary branches. Solution Example: V Start by coloring WA: Red. Assign NT: Green, SA: Blue. T Continue until all regions are colored. 25 / 30 BFS: Color the states NT WA Q SA NSW V T 26 / 30 Depth-First Search (DFS) in CSP How DFS works: DFS assigns a color to WA, then recursively assigns colors to adjacent regions. NT It goes deep into one branch (e.g., WA → NT → Q), checking WA Q constraints. If a conflict occurs (e.g., adjacent SA NSW regions have the same color), it backtracks. V Solution Example: Start by coloring WA: Red. T Then color NT: Green, Q: Blue. Continue recursively to assign colors while checking constraints. 27 / 30 DFS: Coloring NT WA Q SA NSW V T 28 / 30 4-Queens Puzzle: CSP Formulation 2 Variables: Qk for each row k, where k = 1, 2, 3, 4 Domains: {1, 2, 3, 4} for each Qk representing column numbers Constraints: Implicit: Non-threatening positions for all pairs (Qi , Qj ) Explicit: (Q1 , Q2 ) ∈ / {(1, 1), (1, 2), (2, 1), (2, 3)} and so forth for all queen pairs 29 / 30 Solution Steps for 4-Queens Puzzle Q Q Placement of Q1 at (1,1) and Q2 at (3,2) avoids any direct or diagonal conflicts 30 / 30