Artificial Intelligence and Expert Systems

Lecture Five Constraint Satisfactory Problem

November 12, 2024

Breadth-First Search (BFS)

• Type: Uninformed
• Strategy: Explores all nodes level by level.
• Advantages:
• Complete and will always find a solution if one exists.
• Guarantees the shortest path if all actions have the same cost.
• Disadvantages:
• Explores all possibilities, which can be inefficient in large spaces.
• High memory consumption.

2/56
Depth-First Search (DFS)

• Type: Uninformed
• Strategy: Explores as far down one branch as possible before backtracking.
• Advantages:
• Low memory consumption.
• Can be useful for problems where solutions are deep in the search space.
• Disadvantages:
• Not guaranteed to find the shortest path.
• Can get stuck in deep, irrelevant paths.

3/56
Uniform-Cost Search (UCS)

• Type: Uninformed
• Strategy: Expands the node with the lowest path cost, ensuring the cheapest
path to the goal.
• Advantages:
• Guaranteed to find the optimal solution.
• Complete.
• Disadvantages:
• Can be slow if all actions have similar costs.
• Can explore in irrelevant directions.

4/56
Informed Search Overview

• Type: Heuristic-based search algorithms.

• Strategy: Uses additional information (heuristics) to estimate the cost from a
node to the goal.
• Examples: Greedy Best-First Search, A* Search.
• Advantages:
• Can significantly reduce the search space.
• More efficient than uninformed search in many cases.
• Disadvantages:
• Performance depends heavily on the quality of the heuristic.
• May not guarantee the optimal solution (depends on the specific algorithm).

5/56
Greedy Best-First Search

• Type: Informed.
• Strategy: Expands the node that appears to be closest to the goal according to
the heuristic.
• Heuristic: Uses only h(n) (estimate of cost to reach the goal).
• Advantages:
• Often faster than uninformed search methods.
• Useful when a good heuristic is available.
• Disadvantages:
• Not complete; may get stuck in loops or local minima.
• Not guaranteed to find the optimal solution.

6/56
A* Search

• Type: Informed.
• Strategy: Expands the node with the lowest combined cost f(n) = g(n) + h(n),
where:
• g(n): Cost to reach node n from the start.
• h(n): Estimated cost from node n to the goal.
• Advantages:
• Complete and optimal if h(n) is admissible (never overestimates).
• Balances path cost and estimated cost to the goal.
• Disadvantages:
• Memory-intensive due to the need to store all explored nodes.
• Can be slow in large search spaces if h(n) is not efficient.

7/56
Introduction

• What is a Constraint Satisfaction Problem (CSP)?

• Applications: Scheduling, Sudoku, Graph Coloring
• Focus on basic definitions, naive search, and backtracking

8/56
Agenda

1. Introduction
2. Constraint Networks
3. Consistency and Solutions
4. Naïve Backtracking “Variable and Value Ordering”
5. Filter Ordering
6. Arc Consistency
7. Conclusion and References

9/56
Search Algorithms

Search algorithms solve diverse problems effectively. We categorize them as follows:

• Shortest-path Search
• Goal: Find the least-cost path.
• Example: Puzzle-solving, path finding.
• Constraint Satisfaction
• Goal: Meet fixed constraints.
• Example: Scheduling, n-queens.
• Adversarial Search
• Goal: Best outcome against adversary.
• Example: Chess, strategic games.
Comparison Overview:
• Shortest-path vs. Optimization: Depth difference.
• Constraint Satisfaction: Focus on constraints.
• Adversarial: Dynamic, opponent-driven.
10/56
Understanding Constraint Satisfaction Problems
(CSPs)
• Assumptions about the environment:
• The problem operates in a setting with a single agent.
• Actions are deterministic, meaning outcomes are predictable.
• The agent has full visibility of the current state.
• States are distinct and finite, represented in a discrete space.
• Planning approach:
• Emphasis is placed on finding a sequence of actions leading to a goal.
• The path taken is crucial, with variations in cost, depth, and complexity.
• Heuristics can provide targeted guidance specific to each problem.
• Identification focus:
• Concern lies in finding suitable variable assignments to satisfy constraints.
• The solution itself is the priority rather than the path to reach it.
• Solutions can be viewed at the same level, depending on problem formulation.
• CSPs are designed specifically to address problems involving identification.
11/56
Standard Search vs. Constraint Satisfaction
Problems (CSPs)

• Standard Search Problems:

• State is a “black box” with any data structure.
• Goal test: any condition over states.
• Successor function: no specific form.
• Constraint Satisfaction Problems (CSPs):
• Special subset of search problems.
• State defined by variables Xi with values from domain D.
• Goal test: constraints on valid variable combinations.
• Advantages of CSPs:
• Structured for efficient problem representation.
• Allows powerful, general-purpose algorithms.

12/56
 Constraint Satisfaction Problem Example

• Variables: A, B, C, D, E, F, G
• Domains: D = {yellow, blue, green}
• Constraints: Adjacent nodes must have
different colors
• Implicit: A ̸= B
• Explicit:
(A, B) ∈ {(yellow, blue), (yellow, green), . . .}
• Solutions: Assignments that meet all
constraints, e.g.,

{A = yellow, B = blue, C = yellow, D = green,

Figure: Example of CSP with variable
E = blue, F = yellow, G = green } assignments 13/56
Types of Constraint Satisfaction Problems (CSPs)
• Discrete Variables
• Finite Domains
• For domain size d, total assignments are O(dn )
• Examples: Boolean CSPs, such as satisfiability
problems (NP-complete)
• Infinite Domains (e.g., integers, strings)
• Example: Task scheduling, where variables
represent start and end times
• Linear constraints can be solved, but non-linear
constraints may be undecidable
• Continuous Variables
• Example: Start and end times in scientific
observations (e.g., telescope scheduling)
• Linear constraints are solvable in polynomial time
using linear programming (LP) methods
14/56
Types of Constraints in CSPs
• Types of Constraints
• Unary Constraints: Affect a single variable (often limit
the domain), e.g.,

Color of A ̸= blue

• Binary Constraints: Relate pairs of variables, e.g.,

A ̸= B

• Higher-Order Constraints: Involve three or more

variables, such as constraints in arithmetic puzzles. Figure: Example of Constraint
Types
• Preferences (Soft Constraints)
• Example: Preferring certain colors, like red over green.
• Often represented with a cost for each variable
assignment.
• Used in optimization tasks but not required to be 15/56
Applications of Real-World CSPs

• Assignment problems: e.g., assigning instructors

to classes
• Scheduling tasks: e.g., determining time and
location for classes
• Configuring hardware
• Planning transportation schedules
• Production planning in factories
Figure: Example of a Scheduling
• Designing circuit layouts Problem
• Fault detection and diagnosis
• And many more...
16/56
Constraint Networks and Solutions
Constraint Networks and Solutions

• Constraint Networks:
• Defined by a set of variables,
each with a finite domain
• Constraints specify allowed
values for variable pairs
• A CSP consists of finding values
for all variables satisfying all
constraints

• Consistency and Solutions:

• Consistency: No constraints
violated in partial assignments
• Solution: Total consistent
assignment for all variables
• CSP is solvable if a solution
figureColoring Australia as CSP 17/56
Example: Sudoku as CSP

• Variables: Each cell in a 9x9 grid

• Domains: Numbers 1 to 9
• Constraints: Unique numbers in
each row, column, and block

SudoKu as CSP

18/56
Example: Coloring Australia

• Variables: States (WA, NT, SA, etc.)

• Domains: Colors (red, green,
blue)
• Constraints: Adjacent states
must have different colors

Coloring Australia
19/56
Standard Search Approach for CSPs

• Basic Search Formulation for CSPs

• Define states based on values assigned so far
(partial solutions)
• Initial State: No variables assigned initially,
represented by an empty set {}
• Successor Function: Assign a value to the next
unassigned variable
• Goal Test: All variables are assigned, and the
assignment meets all constraints
• We’ll first explore the simple, basic method and
then discuss improvements.

Figure: Illustration of CSP Search

20/56
Search Methods in CSPs
Search Methods in CSPs: Breadth-First Search
(BFS)
• What would BFS (Breadth-First Search) do?
• BFS explores all possible assignments
level-by-level.
• Why it’s not ideal for CSPs: BFS is
memory-intensive as it needs to store all
partial assignments at each depth level. CSPs
often have large state spaces, making BFS
impractical.

• What issues arise with naive BFS?

• Naive BFS may redundantly explore invalid
assignments.
• Solution: Techniques like backtracking and
constraint propagation improve efficiency by 21/56
Search Methods in CSPs: Depth-First Search (DFS)
• What would DFS (Depth-First Search) do?
• DFS explores a path until a solution is found or
it backtracks upon reaching a dead end.
• Why it can work for CSPs: DFS uses less
memory than BFS, making it better suited for
large search spaces. However, naive DFS can
still be inefficient if there is no early
detection of conflicts.

• What issues arise with naive DFS?

• Naive DFS may redundantly explore invalid
assignments.
• Solution: Techniques like backtracking and
constraint propagation improve efficiency by
avoiding unnecessary explorations. Figure: Graph Representation of DFS in
CSP 22/56
BackTracking Search
Naïve Backtracking Algorithm

function NaïveBacktracking(assignment):
if assignment is complete:
return assignment
variable <- select unassigned variable
for each value in domain of variable:
if value consistent with assignment:
result <- NaïveBacktracking(assignment + {variable=value})
if result != failure:
return result
return failure

23/56
CSP Map Coloring

Figure: CSP Map Coloring

24/56
Backtracking

• Definition: A systematic method for finding a solution by exploring partial

assignments and backtracking when constraints are violated.
• How It Works:
• Starts with an empty assignment and iteratively assigns values to variables.
• If a constraint is violated, it backtracks to the previous variable and tries a
different value.
• Advantages:
• Simple and intuitive approach for solving constraint satisfaction problems (CSPs).
• Limitations:
• Can be inefficient as it may explore invalid paths without early conflict detection.

25/56
Backtracking Scenario

26/56
Step 1: Australian States and Territories Structure

NT QLD

WA SA NSW

VIC

27/56
Step 2: Start with Western Australia (WA)

NT NT NT

WA SA WA SA WA SA

Option 1: Red Option 2: Blue Option 3: Green

We choose Red for WA

28/56
Step 3: Coloring Northern Territory (NT)

NT QLD NT QLD

WA SA WA SA

NT = Blue NT = Green

We choose Blue for NT (can’t be Red due to WA)

29/56
Step 4: Coloring South Australia (SA)

NT QLD

WA SA NSW

VIC

30/56
Step 5: Coloring Queensland (QLD)

NT QLD

WA SA NSW

VIC

31/56
Step 6: Coloring New South Wales (NSW) and
Victoria (VIC)

NT QLD

WA SA NSW

VIC 32/56
Step 1: Coloring choices for vertex A

A = Red A = Blue A = Green

A A A

B D B D B D

C C C

E E E

We choose Red for A (leftmost option)

33/56
Step 2: Options for B (after A = Red)

B = Blue B = Green
A A

B D B D

C C

E E

We choose Blue for B (valid choices: Blue or Green)

34/56
Step 3: Options for D (after A = Red, B = Blue)

D = Blue D = Green
A A

B D B D

C C

E E

We choose Blue for D (simplifies remaining choices)

35/56
Step 4: Options for C (after A = Red, B = Blue, D =
Blue)

C = Green (only valid option)

B D

C must be Green (can’t be Red due to A, can’t be Blue due to B and D)

36/56
Step 5: Final Vertex E (after A = Red, B = Blue, D =
Blue, C = Green)

E = Red (only valid option)

B D

E must be Red (can’t be Blue due to D, can’t be Green due to C)

37/56
Course Scheduling Problem

Prof. Smith Prof. Jones

CS101 CS102 MATH101 PHYS101

Constraints:
- Each course needs one time slot (9AM, 10AM, 11AM, or 2PM)
- Same professor can’t teach at same time
- Group A takes CS101 and MATH101
- Group B takes CS102 and PHYS101

38/56
Step 1: Initial Time Slot Options for CS101 (Group A)

Option 1 Option 2 Option 3 Option 4

CS101 CS101 CS101 CS101

9 AM 10 AM 11 AM 2 PM

We choose 9 AM for CS101

39/56
Step 2: Options for MATH101 (Group A, after CS101 =
9AM)

CS101

9 AM

MATH101 MATH101 MATH101

10 AM 11 AM 2 PM

Option 1 Option 2 Option 3 40/56

Step 3: Options for CS102 (Group B)

CS101 MATH101

9 AM 10 AM

CS102 CS102

11 AM 2 PM

Option 1 Option 2
CS102 can’t be at:
- 9AM (Prof. Smith teaches CS101)
41/56
- 10AM (conflict with MATH101)
Step 4: Final Assignment - PHYS101 (Group B)

Prof. Smith Prof. Jones

CS101 (Group
MATH101
A) (Group
CS102
A) (Group
PHYS101
B) (Group B)

9 AM 10 AM 11 AM 2 PM

Final solution satisfies all constraints:

- No professor has overlapping classes
- Group A (CS101 + MATH101) and Group B
(CS102 + PHYS101) have no conflicts
- All courses are scheduled without overlap
between Group A and Group B 42/56
Improve Back Tracking
How to Improve the Backtracking ?

• Ordering
• Filtering

43/56
Variable Ordering

• Most Constrained Variable: Choose the variable with the fewest legal values
• Most Constraining Variable: Choose the variable involved in the most constraints
• Least Constraining Value: Choose the value that rules out the fewest choices
for other variables

44/56
Forward Checking

• Definition: A technique that checks the potential impact of each variable

assignment on future assignments.
• How It Works:
• After assigning a value to a variable, forward checking looks ahead to eliminate
values in the domains of unassigned variables that would violate constraints.
• If a variable’s domain becomes empty, it backtracks immediately.
• Advantages:
• Reduces the search space by detecting conflicts early.
• Limitations:
• Does not fully enforce consistency, so some conflicts might only be detected later
in the search.

45/56
Forward Checking

Figure: Forward Checking Image Source 46/56

Filtering: Constraint Propagation in Forward
Checking

• Forward Checking:
• Forward checking propagates information from assigned to unassigned variables,
helping to reduce the domain of possible values.
• After assigning a value to a variable, forward checking eliminates values in the
domains of unassigned neighboring variables that would violate constraints.
• Limitation of Forward Checking:
• Forward checking may not detect all potential conflicts early because it only looks
one step ahead.
• For example, if assigning colors to states on a map, it may not catch conflicts
between variables that are not directly connected (e.g., NT and SA cannot both be
blue, but this conflict may not be detected immediately).
• This technique does not fully propagate constraints across the entire network,
leading to possible missed conflicts until later in the search.
• Solution: Constraint Propagation 47/56
Arc Consistency

• Definition: A technique that ensures all binary constraints between pairs of

variables are satisfied by consistently filtering values in each variable’s domain.
• How It Works:
• For each pair of connected variables, if a value in one variable’s domain has no
matching value in the connected variable’s domain, it is removed.
• Repeats this filtering process until no more values can be removed.
• Advantages:
• Stronger consistency enforcement than forward checking; reduces unnecessary
search paths.
• Limitations:
• Can be computationally expensive to maintain full arc consistency throughout the
search.

48/56
Arc Consistency Example

Figure: Arc Consistency Step-by-Step Example

49/56
Arc Consistency: Initial Setup and First Assignment

• Initial Assignment: Start by assigning WA the color red.

• Initial Constraints: Adjacent regions cannot have the same
color.
• Update: Remove ”red” from the domains of NT and SA
(neighbors of WA).

Region Domain after WA = red

WA {red}
NT {green, blue}
Q {red, green, blue}
NSW {red, green, blue}
V {red, green, blue}
SA {green, blue}
T {red, green, blue}

Table: Domains after setting WA = red Figure: CSP Map Coloring

50/56
Arc Consistency: Step 1 - NT

• Process NT:
• NT has {green, blue}; ensure it doesn’t
conflict with its neighbors.
• Remove ”green” from Q’s domain if NT is
assigned ”green”.

Region Updated Domain

WA {red}
NT {green, blue}
Q {red, blue}
NSW {red, green, blue}
V {red, green, blue}
SA {green, blue}
T {red, green, blue}
Figure: CSP Map Coloring
Table: Domains after processing NT
51/56
Arc Consistency: Step 2 - Q

• Process Q:
• Q has {red, blue}; check consistency with its
neighbors.
• Remove ”blue” from NT’s domain if Q is
assigned ”blue”.

Region Updated Domain

WA {red}
NT {green}
Q {red, blue}
NSW {red, green, blue}
V {red, green, blue}
SA {green, blue}
T {red, green, blue}
Figure: CSP Map Coloring
Table: Domains after processing Q
52/56
Arc Consistency: Final Step

• Repeat arc consistency for all pairs until no more values can be
removed.
• Final domains show the colors that satisfy all adjacency
constraints.

Region Final Domain

WA {red}
NT {green}
Q {red}
NSW {green}
V {red, green}
SA {blue}
T {red, green, blue}

Table: Final Domains After Full Arc Consistency

Figure: CSP Map Coloring
53/56
Comparison of Backtracking, Forward Checking,
and Arc Consistency

• Backtracking:
• Simple approach, one variable at a time which may explore invalid paths without
early conflict detection.
• Forward Checking:
• Checks future assignments by eliminating values that lead to conflicts, reducing
the search space.
• Less thorough than arc consistency; only partially enforces constraints.
• Arc Consistency:
• Enforces consistency for all variable pairs, reducing search by eliminating
conflicting values early.
• Stronger but more computationally intensive than forward checking.
• Summary:
• Backtracking is a base technique.
• Forward checking is a more efficient improvement. 54/56
References

Some slides and ideas have been adapted from the following sources:
• Artificial Intelligence: A Modern Approach by Stuart Russell and Peter Norvig
Russell and Norvig (2010)
• Tutorial: Artificial Intelligence Tutorial (Week 3)

55/56
Thank you for your attention

November 12, 2024

Russell, S. and Norvig, P. (2010). Artificial Intelligence: A Modern Approach. Prentice
Hall, 3 edition.

56/56