Constraint Satisfaction Problems (CSPs) Overview

Constraint Satisfaction Problems (CSPs)

• What is Search For?:
  • Assumes a single agent, deterministic actions, fully observed state, and discrete state space.
  • Planning: focuses on finding a sequence of steps (path) to reach a goal efficiently. The path itself is important.
  • Identification: the goal is the primary focus, not the path. All paths are considered at the same depth.
  • CSPs are a specialized class of identification problems.

CSP Definition

• CSPs are a special subset of search problems.
• A state is defined by variables (Xi) with values from a domain D.
• The goal is to satisfy a set of constraints specifying permissible variable value combinations.
• CSPs provide a framework for solving complex problems using domain-specific algorithms.

CSP Example: Map Coloring

• Variables: WA, NT, Q, NSW, V, SA, T (representing regions of Australia).
• Domains: D = {red, green, blue} (colors).
• Constraints: Adjacent regions must have different colors.
  • Implicit: WA ≠ NT.
  • Explicit: (WA, NT) ∈ {(red, green), (red, blue), ...} (defining allowed color combinations).
• Solutions: Assignments that satisfy all constraints, e.g., {WA=red, NT=green, Q=red, NSW=green, V=red, SA=blue, T=green}.

N-Queens Problem: Formulation 1

• Variables: Xij (representing the presence or absence of a queen at row i, column j).
• Domains: {0, 1} (0 for no queen, 1 for a queen).
• Constraints:
  • No two queens on the same row, column, or diagonal:
    • (Xij, Xik) ∈ {(0, 0), (0, 1), (1, 0)} (same row)
    • (Xij, Xkj) ∈ {(0, 0), (0, 1), (1, 0)} (same column)
    • (Xij, Xi+k,j+k) ∈ {(0, 0), (0, 1), (1, 0)} (same right-sloping diagonal)
    • (Xij, Xi+k,j−k) ∈ {(0, 0), (0, 1), (1, 0)} (same left-sloping diagonal)
  • Total number of queens placed must be exactly N: X Xij = N i,j

N-Queens Problem: Formulation 2

• Variables: Qk (represents the column position of the queen in row k).
• Domains: {1, 2, 3,..., N} (representing possible column numbers).
• Constraints:
  • Implicit: No two queens can threaten each other.
  • Explicit: (Q1, Q2) ∈ {(1, 3), (1, 4), ...} (defining allowed combinations of column positions to avoid conflicts).

Constraint Graphs

• Binary CSP: Each constraint relates at most two variables.
• Binary constraint graph:
  • Nodes represent variables.
  • Arcs represent constraints between pairs of variables.
• The graph structure helps to accelerate CSP algorithms by identifying independent subproblems.

Cryptarithmetic Example

• Variables: F, T, U, W, R, O, X1, X2, X3 (representing digits).
• Domains: {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}.
• Constraints:
  • All different: alldiff(F, T, U, W, R, O) (ensuring unique digit assignments).
  • Column constraints: O + O = R + 10 · X1 (ensuring the arithmetic operation is correct).

Varieties of CSPs

• Discrete Variables:
  • Finite Domains: Variables have a limited, fixed set of possible values.
  • Infinite Domains: Variables can take an unlimited number of values, e.g., integers, strings.
• Continuous Variables: Variables can take any value within a continuous range.

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 more than two variables, e.g., cryptarithmetic column constraints.
• Preferences (Soft Constraints): Represent desired conditions that may not be absolutely strict, e.g., red is better than green.

Real-World CSPs Applications

• Scheduling, timetabling, assignment, hardware configuration, transportation scheduling, factory scheduling, circuit layout, fault diagnosis, and many more.

Standard Search Formulation

• States: Defined by the values assigned so far (partial assignments).
  • Initial State: The empty assignment {}.
  • Successor Function: Assigning a value to an unassigned variable.
  • Goal Test: The current assignment is complete and satisfies all constraints.
• Naive Approach: A straightforward approach that can be further optimized.

Search Methods (BFS and DFS)

• Breadth-First Search (BFS):
  • Explores all possible assignments systematically, layer by layer.
  • Guaranteed to find the shallowest solution, but may explore unnecessary branches.
• Depth-First Search (DFS):
  • Explores deeply in one branch, backtracking when conflicts arise.
  • More efficient than BFS in many cases, but does not guarantee finding the shallowest solution.

Constraint Satisfaction Problems (CSPs)

• CSPs are a specialized type of search problem where the state is defined by variables with values from a domain.
• The goal test in CSPs is a set of constraints that specify allowable combinations of values for subsets of variables.
• CSPs offer more powerful, general-purpose algorithms than standard search algorithms.

Example: Map Coloring

• Variables: WA, NT, Q, NSW, V, SA, T (representing regions on a map)
• Domains: {red, green, blue} (colors to assign to regions)
• Constraints: Adjacent regions must have different colors.

Example: N-Queens

• Two formulations for N-Queens:
  • Formulation 1: Each variable represents a queen's position (row, column) with a domain of all possible positions on the board.
  • Formulation 2: Each variable represents the column position where a queen is placed in each row, with a domain of {1, 2, 3, ..., N}, representing column numbers.
• Constraints ensure that no two queens can threaten each other:
  • Implicit constraint: No two queens can share the same row, column or diagonal.
  • Explicit constraints: Specific allowed positions that satisfy the implicit constraint.

Constraint Graphs

• Binary CSP: Each constraint relates (at most) two variables.
• Binary constraint graph: Nodes represent variables, and arcs represent constraints.
• The structure of the constraint graph can be used to speed up search algorithms in CSPs.

Example: Cryptarithmetic

• Variables: Letters that represent unique digits in a mathematical operation.
• Domains: {0, 1, 2, ..., 9} representing digits.
• Constraints:
  • alldiff constraint ensures that each letter represents a unique digit.
  • Arithmetic constraints ensure that the mathematical operation is valid.

Varieties of CSPs

• Discrete Variables:
  • Finite Domains: Variables have a limited number of values (e.g., Boolean CSPs).
  • Infinite Domains: Variables can take an infinite number of values (e.g., job scheduling).
• Continuous Variables: Variables can take any value in a continuous range (e.g., start/end times in scheduling).

Varieties of Constraints

• Unary Constraints: Involve a single variable (equivalent to reducing domains).
• Binary Constraints: Involve pairs of variables.
• Higher-Order Constraints: Involve more than two variables.
• Preferences (Soft Constraints): Represented by a cost for each variable assignment, leading to constrained optimization problems.

Real-World CSPs

• Scheduling problems.
• Timetabling problems.
• Assignment problems.
• Hardware configuration.
• Transportation scheduling.
• Factory scheduling.
• Circuit layout.
• Fault diagnosis.

Standard Search Formulation for CSPs

• State is defined by the values assigned to variables 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.

Search Methods for CSPs

• Breadth-First Search (BFS): Explores all possible assignments for one variable before moving to others, guaranteeing the shallowest solution.
• Depth-First Search (DFS): Assigns a value to one variable, then recursively assigns values to adjacent variables, backtracking if a conflict occurs.

Constraint Satisfaction Problems (CSPs)

• A specialized subset of search problems where the state is defined by variables with values from a domain.
• Goal is to find a set of values for the variables that satisfy a set of constraints.
• Advantages: Allows for general-purpose algorithms with more power than standard search algorithms.

CSP Example: Map Coloring

• Variables: Represent regions on the map (WA, NT, Q, NSW, V, SA, T).
• Domains: Set of possible colors (red, green, blue).
• Constraints: Adjacent regions must have different colors.
• Solution: An assignment of colors to regions that satisfies all constraints.

Constraint Graphs

• Binary CSP: Each constraint relates at most two variables.
• Binary Constraint Graph: Nodes represent variables, arcs represent constraints.
• Graph Structure: Useful for speeding up search algorithms, allowing for independent subproblem identification.

N-Queens Problem

• Goal: Place N queens on an N x N chessboard so that no two queens threaten each other (cannot share the same row, column, or diagonal).

• Formulation 1:*

• Variables: Xij, representing whether a queen is placed at row i and column j (0 for no queen, 1 for queen).

• Constraints: Ensure no two queens threaten each other via row, column, and diagonal constraints.

• Formulation 2:*

• Variables: Qk, representing the row position of the queen in column k.

• Domains: {1, 2, 3, ... N}, representing the possible row positions.

• Constraints: Implicitly define the non-threatening placement of queens, and explicitly define allowed positions.

Varieties of CSPs

• Discrete Variables:
  • Finite Domains: Variables have a finite number of values, like Boolean CSPs (values 0 or 1).
  • Infinite Domains: Variables can take an infinite number of values, like scheduling problems.
• Continuous Variables: Variables can take any value within a continuous range, like start/end times for observing objects.

Varieties of Constraints

• Unary Constraints: Involve a single variable, restricting its possible values.
• Binary Constraints: Involve pairs of variables, defining relationships between them.
• Higher-Order Constraints: Involve more than two variables.
• Preferences (Soft Constraints): Indicate preferred values or a cost associated with each variable assignment, leading to constrained optimization problems.

Real-World CSPs

• Scheduling problems
• Timetabling problems
• Assignment problems
• Hardware configuration
• Transportation scheduling
• Factory scheduling
• Circuit layout
• Fault diagnosis

Standard Search Formulation

• States: Defined by the values assigned so far, represented as a partial assignment.
• Initial State: An empty assignment.
• Successor Function: Assigns a value to an unassigned variable.
• Goal Test: The current assignment is complete and satisfies all constraints.

This quiz covers the basics of Constraint Satisfaction Problems (CSPs), including their definition, characteristics, and examples such as map coloring. It explores the differences between search and planning, as well as the significance of constraints in determining variable combinations. Test your understanding of how CSPs apply to complex problem-solving scenarios.