Study Notes on Constraint Satisfaction Problems (CSPs) and Search Techniques

Artificial Intelligence

What is Search For?

• Assumptions about the world:
  • A single agent
  • Deterministic actions
  • Fully observed state
  • Discrete state space
• Planning: Sequences of actions
• Path to the goal: The important aspect is the path taken to achieve the goal, rather than just the goal itself.
• Path characteristics:
  • Paths may have various costs and depths.
• Heuristics: Provide problem-specific guidance to improve efficiency in finding solutions.
• Identification: Refers to assignments made to variables with respect to finding a goal.
• Goal Importance: The goal is significant beyond the path taken to achieve it.
• Depth in paths: Sometimes all paths at the same depth are considered for certain formulations.
• CSPs:
  • Constraint Satisfaction Problems (CSPs) are specifically designed for identification problems.

Constraint Satisfaction Problems (CSPs)

• CSP Definition:
  • A subset of search problems characterized by:
  • State: Defined by variables $X_i$ with values taken from a domain $D$ (where $D$ can sometimes depend on $i$).
  • Goal test: Comprises a set of constraints that specify permissible combinations of values for subsets of variables.
• Importance: CSPs allow for the implementation of general-purpose algorithms that are more powerful than standard search algorithms.

CSP Examples

• Geographical Example:
  • Regions:
  • Western Australia
  • Northern Territory
  • South Australia
  • Queensland
  • New South Wales
  • Victoria
  • Tasmania

Example: Map Coloring

• Variables:
  • Regions needing a color assignment.
• Domains:
  • Different colors available for assignment.
• Constraints:
  • Adjacent regions must be assigned different colors.
• Solutions:
  • Solutions must satisfy all constraints, examples include both implicit and explicit solutions:
  • Implicit:
    • Constraints and rules understood without explicit stipulation.
  • Explicit:
    • Clearly defined legal tuples satisfying the constraints.

N-Queens Problem

• Formulation 1:

  • Variables: $X_{ij}$
  • Domains: $ext{{Values allowed: }} ext{{ exttt{{0, 1}}}}$
  • Constraints:
  • Vi,j,k(X_{ij}, X_{ik}) = egin{cases} (0, 0) \ (0, 1) \ (1, 0) \ ext{and similar constraints for row and column} \ ext{sum of } ext{ all assignments} ext{ equals } N \ ext{where } i, j

• Formulation 2:

  • Variables: $Q_k$ (Queens)
  • Domains: $ext{{Values: }} ext{{ exttt{1, 2, …, N}}}$
  • Constraints:
  • Not placing queens where they attack each other:
    • $Vi,j: ext{non-threatening (e.g. } (Q_i, Q_j)$ is valid.
    • Example tuples include pairs like $(1,3), (1,4), …$

Constraint Graphs

• Binary CSP:
  • Each constraint relates at most two variables.
• Definition of Binary Constraint Graph:
  • Nodes are the variables, and the arcs indicate constraints between pairs.
• CSP Algorithms:
  • Utilize graph structure to enhance search efficiency.
  • Example: Tasmania can represent an independent subproblem.

Example: Cryptarithmetic

• Variables: Symbols to represent digits, e.g., FTU, WR, O, X1, X2, X3.
• Domains: Digits in the set $ext{{ exttt{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}}}$
• Constraints:
  • All different constraint:
  • $ext{{alldiff(F, T, U, W, R, O)}}$
  • Equation relationships:
  • e.g., $O + 0 = R + 10 imes X_1$
  • Cryptarithmetic example depicted:
    • SEND + MORE = MONEY.

Example: Sudoku

• Variables:
  • Each open square must be filled.
• Domains:
  • Digits: $ext{{ exttt{1, 2, …, 9}}}$
• Constraints:
  • 9-way all different constraints for:
  • Each row
  • Each column
  • Each region, which can include pairwise inequality constraints.

Varieties of CSPs and Constraints

• General Definition of CSPs:
  • Components:
  • Variables
  • Domains
  • Constraints
  • Types of Constraints:
  • Implicit: Generated through computation.
  • Explicit: Enumerated in legal tuples.
  • Types: Unary, Binary, N-ary
• Goals:
  • Find any solution, or all, or best solutions.

Varieties of CSPs

• Discrete Variables:
  • Involve finite domains.
  • Size $d$ translates to $O(d^n)$ complete assignments.
  • Example: Boolean CSPs, specifically Boolean satisfiability (NP-complete).
• Infinite Domains:
  • Including variables as integers or strings; e.g., job scheduling with variables for the start and end times.
  • Linear constraints: Solvable.
  • Nonlinear constraints: Undecidable.
• Continuous Variables:
  • Example: Start/end times for observations with the Hubble Telescope.

Varieties of Constraints

• Unary Constraints:
  • Involve a single variable (reducing domains).
• Binary Constraints:
  • Involve pairs of variables.
• Higher-order Constraints:
  • Involve three or more variables, e.g., cryptarithmetic column constraints.
• Preferences (Soft Constraints): Elite constraints where performance is graded, such as preferring red over green, often modeled with cost on assignments.

Real-World CSPs

• Examples of Application:
  • Assignment problems within educational contexts (who teaches which class).
  • Timetabling issues (class scheduling times and locations).
  • Hardware and transportation scheduling.
  • Factory scheduling practices.
  • Circuit design/layout considerations.
  • Fault diagnosis.
  • Many more real-world problems often involve real-valued variables.

Solving CSPs

Standard Search Formulation

• States: Defined by values assigned so far; represents partial assignments.
• Initial State: Start with the empty assignment, represented as {}.
• Successor Function: Assigning a value to an unassigned variable.
• Goal Test: Evaluate if current assignment is complete and if all constraints are satisfied.

Search Methods

• BFS (Breadth-First Search) and DFS (Depth-First Search): Serve as foundational algorithms, but each may encounter unique problems while processing CSPs.

Backtracking Search

• Definition: Basic uninformed algorithm for solving CSPs.
• Core Ideas:
  • Assign one variable at a time.
  • Variable assignments are not influenced by the order of assignment; therefore, ordering can be set irrespective of variable processing.
  • Monitor constraints as assignments occur. Only account for values adhering to previously set conditions.
  • Incremental goal testing, which is bound to depth-first search, sees enhanced efficiency through backtracking techniques, resolving problems like N-Queens for n >> 25.

Improving Backtracking

• General Methods: Significant speed improvements through strategically improving approaches:
  • Ordering: Determine which variable would be processed next.
  • Filtering: Identify potential failures early on within search environments.
  • Structure: Leverage structural insights within the problems to find efficient solutions.

Filtering Techniques

• Definition: Track domains for unassigned variables and eliminate poor options from possibilities.
  • Forward Checking: This approach involves deleting values that would violate constraints once assigned values are applied.

Constraint Propagation

• Forward Checking Scope: Propagates necessary information from assigned to unassigned variables, yet does not guarantee early detection of all potential failures.
  • Example failure of constraints with regions not being able to share specific colors.

K-Consistency

• Degrees of Consistency:
  • 1-Consistency (Node Consistency): Each node's domain includes values that fulfill unrevised unary constraints.
  • 2-Consistency (Arc Consistency): For each node pair, any valid assignment to one can be sustained in another.
  • K-Consistency: Extends into k nodes, where every consistent assignment for $k-1$ nodes must be extendable to the k-th. Higher $k$ leads to more significant computation costs.

Strong K-Consistency

• Definition: Strong k-consistency encapsulates degrees found across k-1, k-2, … up to single-node consistency.
• Claim: A problem exhibiting strong n-consistency should theoretically resolve without backtracking due to facilitated choices.

Ordering Strategies

• Variable Ordering:
  • Minimum Remaining Values (MRV): Select variables with the fewest remaining legal values in their domain, known as the “most constrained variable,” optimizing for faster failure detection.
• Value Ordering (Least Constraining Value): Choose values leading to rulings out the least amount of unfavored outcomes in remaining variables; this may require additional filtering testing to enact.

Summary of CSPs

• CSPs represent a particular segment of search problems, framed as partial assignment states evaluated through goal-testing constraints.
• Initial solutions generally succeed through backtracking algorithms, augmented bonus strategies such as ordering, filtering, and structural exploitation contribute significantly towards operational efficiency in resolving CSPs.