Artificial Intelligence Beyond

(CS30002) Classical Search

Dr. Jaydeep Das

Content
➢ Local Search Algorithms

➢ Hill Climbing Algorithm

➢ Simulated Annealing
➢ Local Beam Search
➢ Genetic Algorithms
Local Search Algorithms and Optimization
Problems
❖ Systematic Search problems:
➢ Search algorithms are designed to explore search spaces systematically.
➢ Keep one or more paths in memory and by recording alternatives have been explored at each
point along the path.
➢ When a goal is found, the path to that goal also constitutes a solution to the problem (a
sequence of actions from initial state to goal state).
❖ Local Search problems:
➢ These algorithms perform purely local search in the state space.
➢ Evaluating and modifying one or more current states rather than systematically exploring paths
from an initial state.
➢ These algorithms are suitable for problems in which all that matters is the solution state, not the
path cost to reach it.
➢ The path to the goal is irrelevant.
Example: In 8-queens problem, what matters is the final configuration of queens, not the
order in which they are added.
Local Search Algorithms and Optimization
Problems (contd…)
• The same general property holds for many important applications as
indicated below:
• Integrated-circuit design
• Factory-floor layout
• Job-shop scheduling
• Automatic programming
• Telecommunications network optimization
• Vehicle routing
• Portfolio management

The family of local search algorithms includes:

✓ Hill Climbing, Simulated Annealing (inspired by statistical physics)
✓ Local Beam Search, Genetic Algorithms (inspired by evolutionary biology)
Local Search Algorithms and Optimization
Problems (contd…)
• Local search methods keep small number of nodes in memory. They are suitable
for problems where the solution is the goal state itself not the path.

• Local search algorithms operate using a single current node (rather than
multiple paths) and generally move only to neighbors of that node. Typically, the
paths followed by the search are not retained. Although local search algorithms
are not systematic, they have two key advantages:
(i) Use very little memory- usually a constant amount.
(ii) Can often find reasonable solutions in large or infinite (continuous) state
spaces for which systematic algorithms are not suitable.
Local Search Algorithms and Optimization
Problems (contd…)
• In addition to finding goals, local search algorithms are useful for solving pure
optimization problems, in which the aim is to find the best state according to an
objective function.

• Many optimization problems do not fit the “standard” search model (both
uninformed and informed).

• For example, nature provides an objective function - reproductive fitness - that

Darwinian evolution could be seen as attempting to optimize, but there is no
“goal test” and no “path cost” for this problem.
Local Search Algorithms and Optimization
Problems (contd…)
• To understand local search, we find it useful to consider the state-space landscape. A
landscape has both “location” (defined by the state) and “elevation” (defined by the value
of the heuristic cost function or objective function).

• If elevation corresponds to cost, then the aim is to find the lowest valley- a global
minimum.

• If elevation corresponds to an objective function, then the aim is to find the highest peak-
a global maximum.

• We can convert from one to the other just by inserting a minus sign.

• Local search algorithms explore this landscape. A complete local search algorithm always
finds a goal if one exists; an optimal algorithm always finds a global minimum/maximum.
Local Search Algorithms and Optimization
Problems (contd…)
 Hill Climbing
• It is often used when a good heuristic function is available for evaluating
states but when no other useful knowledge is available.
• This algorithm is simply a loop that continuously moves in the direction of
increasing value i.e., uphill.
• It terminates when it reaches a “peak” where no neighbor has a higher
value.
• The algorithm doesn’t maintain a search tree, so the current node data
structure only records the state and its objective function value.
• Hill–climbing doesn’t look ahead beyond the immediate neighbors of the
current state.
 Hill Climbing Algorithm
1. Evaluate the initial state (IS). If it is the goal state (GS), then return it
and quit. Else consider IS as the current state (CS) and proceed.

2. Loop until a solution is found or there are no new operator (OP) to be

applied to the CS.
a) Select an OP that has not yet been applied to the CS and apply it to produce a new
state (NS).
b) Evaluate the NS:
I. If NS is a GS , then return it and quit.
II. If it is not a GS but better than the CS, then consider it as the current state(i,e., CS NS)
and proceed.
III. If NS is not better than CS then continue in the loop by selecting the next appropriate OP for
CS.
Steepest – Ascent Hill Climbing Algorithm
• It considers all the moves from the CS and selects the best one as the next state.
It is also called gradient search.

• The steepest-Ascent algorithm is a variation of the simple hill-climbing algorithm.

This algorithm examines all the neighbouring nodes of the current state and
selects one neighbour node which is closest to the goal state. This algorithm
consumes more time as it searches for multiple neighbours

• Algorithm
1. Evaluate the initial state (IS). If it is the goal state (GS) , then return it and
quit. Else consider IS as the current state (CS) and proceed.
2. Loop until a solution is found or until a complete iteration produces no change
to the CS:
Steepest – Ascent Hill Climbing Algorithm
a) Let successor (SUCC) be a state such that any NS that can be generated from
CS is better than SUCC. [ i.e., setting SUCC to a minimum value at the
beginning of an iteration or set CS as SUCC]

b) For each operator OP that applies to the CS do:

I. Apply OP to CS and generate a NS.
II.Evaluate the NS. If it is a GS then return it and quit. If not , compare it with SUCC. If NS is
better than SUCC, then set SUC to NS; else leave SUCC unchanged.

c) If the SUCC is better than CS, then set CS to SUCC [i.e move to the next best
state]
Hill-Climbing Search
• "Like climbing Everest in thick fog with amnesia"
Limitations: Hill-Climbing Search
• Both basic and steepest-ascent hill climbing may fail to find a solution . Either
algorithm may terminate not by finding a goal state but by getting to a state from
which no better states can be generated. This will happen if the program has
reached either a local maximum, a plateau or a ridge.

• A local maximum is a state that is better than all its neighbors but is not better
than some other states further away.

• Solution of local maxima:-

– Move in some arbitrary direction
– Back track to an ancestor and try some other alternatives.
Limitations: Hill-Climbing Search
• A Plateau is a flat area in the search space in which all the neighboring states
have the same heuristic function value.

• Solution of Plateau
– Expand few generation ahead to move to a different section of the search space.

• A Ridge is an area in the search space which is higher than its surroundings but
itself has slopes. It is not possible to traverse a ridge by a single move i.e., no
such operator is available.

• Solution of Ridges
– Apply several operators before doing the evaluation
Hill-Climbing Search (via ridge)
Hill-Climbing Search
• Problem: depending on initial state, can get stuck in local maxima
Hill-Climbing Search: 8 Queens Problem

• h = number of pairs of queens that are

attacking each other, either directly or
indirectly

• h = 17 for the this state

• The best moves (or successors) having h = 12

are marked
Hill-Climbing Search: 8 Queens Problem

• A local minimum with h = 0

Hill-Climbing Search: 8 Queens Problem

• A local minimum with h = 1

Variants of Hill Climbing
• 1. Stochastic hill climbing: It chooses at random from among the uphill moves; the probability of
selection can vary with the steepness of the uphill move. This usually converges more slowly than
steepest ascent, but in some state landscapes, it finds better solutions.

• 2. First-choice hill climbing: It implements stochastic hill climbing by generating successors

randomly until one is generated that is better than the current state. This is a good strategy when
a state has many (e.g., thousands) of successors.
(The hill-climbing algorithms described so far are incomplete—they often fail to find a goal
when one exists because they can get stuck on local maxima.)

• 3. Random-restart hill climbing adopts the well-known adage, “If at first you don’t succeed, try,
try again.” It conducts a series of hill-climbing searches from randomly generated initial states,
until a goal is found.
(The success of hill climbing depends very much on the shape of the state-space landscape: if
there are few local maxima and plateaus, random-restart hill climbing will find a good solution
very quickly.)
Simulated Annealing
• A hill-climbing algorithm that never makes “downhill” moves toward states with lower
value (or higher cost) is guaranteed to be incomplete, because it can get stuck on a local
maximum.

• In contrast, a purely random walk—that is, moving to a successor chosen uniformly at

random from the set of successors—is complete but extremely inefficient.

• Therefore, it seems reasonable to try to combine hill climbing with a random walk in
some way that yields both efficiency and completeness.

• Simulated annealing is such an algorithm.

• Simulated annealing was first used extensively to solve VLSI layout problems in the early
1980s. It has been applied widely to factory scheduling and other large-scale
optimization tasks.
Simulated Annealing
• In metallurgy, annealing is the process used to temper or harden metals and glass by
heating them to a high temperature and then gradually cooling them, thus allowing the
material to reach a low energy crystalline state.

• To explain simulated annealing, we switch our point of view from hill climbing to
gradient descent (i.e., minimizing cost) and imagine the task of getting a ping-pong ball
into the deepest crevice in a bumpy surface.

• If we just let the ball roll, it will come to rest at a local minimum. If we shake the
surface, we can bounce the ball out of the local minimum. The trick is to shake just hard
enough to bounce the ball out of local minima but not hard enough to dislodge it from
the global minimum.

• The simulated-annealing solution is to start by shaking hard (i.e., at a high temperature)

and then gradually reduce the intensity of the shaking (i.e., lower the temperature).
Simulated Annealing Algorithm
function SIMULATED-ANNEALING(problem, schedule) returns a solution state
inputs: problem, a problem
schedule , a mapping from time to “temperature” • The simulated annealing
current ← MAKE-NODE (problem.INITIAL-STATE) algorithm, a version of stochastic
hill climbing where some
for t = 1 to ∞ do downhill moves are allowed.
T ← schedule (t) • Downhill moves are accepted
readily early in the annealing
if T = 0 then return current schedule and then less often as
Next ← a randomly selected successor of current time goes on.
ΔE ← next.VALUE – current.VALUE • The schedule input determines
the value of the temperature T
if ΔE >0 then current ← next as a function of time.)
else current ← next only with probability 𝑒 ΔE/T
Local Beam Search
• Keeping just one node in memory might seem to be an extreme reaction to the problem
of memory limitations.
• The local beam search algorithm, which is a path-based algorithm keeps track of k states
rather than just one. It begins with k randomly generated states.
• At each step, all the successors of all k states are generated. If any one is a goal, the
algorithm halts. Otherwise, it selects the k best successors from the complete list and
repeats.
• At first sight, a local beam search with k states might seem to be nothing more than
running k random restarts in parallel instead of in sequence.
• In a local beam search, useful information is passed among the parallel search threads.
In effect, the states that generate the best successors say to the others, “Come over
here, the grass is greener!” The algorithm quickly abandons unfruitful searches and
moves its resources to where the most progress is being made.
Local Beam Search
• In its simplest form, local beam search can suffer from a lack of diversity among
the k states—they can quickly become concentrated in a small region of the state
space, making the search little more than an expensive version of hill climbing.

• A variant called stochastic beam search, analogous to stochastic hill climbing,

helps alleviate this problem. Instead of choosing the best k from the pool of
candidate successors, stochastic beam search chooses k successors at random,
with the probability of choosing a given successor being an increasing function of
its value.

• Stochastic beam search bears some resemblance to the process of natural

selection, whereby the “successors” (offspring) of a “state” (organism) populate
the next generation according to its “value” (fitness).
Genetic Algorithms
• A genetic algorithm (or GA) is a variant of stochastic beam search in which successor
states are generated by combining two parent states rather than by modifying a single
state.
• The analogy to natural selection is the same as in stochastic beam search, except that
now we are dealing with mimicking the natural real life reproduction rather than asexual
reproduction as in stochastic beam search. (Later normally does not happen in real life).
• Like beam searches, GAs begin with a set of k randomly generated states, called the
population. Each state, or individual, is represented as a string over a finite alphabet—
most commonly, a string of 0s and 1s.
• For example, an 8-queens state must specify the positions of 8 queens, each in a column
of 8 squares, and so requires 8 × log28 bits.
• Alternatively, the state could be represented as 8 digits, each in the range from 1 to 8.
• These two encodings behave differently.
Flowchart: Genetic Algorithms
Genetic Algorithms

(Figure shows a population of four 8-digit strings representing 8-queens states)

Genetic Algorithms

2 4 7 4 8 5 5 2 3 2 7 5 2 4 1 1
(24 non-attacking pairs of queens) (23 non-attacking pairs of queens)
Genetic Algorithms
• (a) shows a population of four 8-digit strings representing 8-queens states.

• The production of the next generation of states is shown in Figures (b)–(e).

• In (b), each state is rated by the objective function, or (in GA terminology) the fitness function.
A fitness function should return higher values for better states.

• So, for the 8-queens problem, we use the number of nonattacking pairs of queens, which has a
value of 28 for a solution.

• The values of the given four states are 24, 23, 20, and 11.

• In this particular variant of the genetic algorithm, the probability of being chosen for reproducing
is directly proportional to the fitness score, and the percentages are shown next to the raw
scores.
Genetic Algorithms
• In Figure (c), two pairs are selected at random for reproduction, in accordance with the
probabilities in (b). It is to be noticed that one individual is selected twice and one not
at all.

• For each pair to be mated, a crossover point is chosen randomly from the positions in
the string. In Figure, the crossover points are after the third digit in the first pair and
after the fifth digit in the second pair.

• In Figure (d), the offspring themselves are created by crossing over the parent strings at
the crossover point. For example, the first child of the first pair gets the first three
digits from the first parent and the remaining digits from the second parent, whereas
the second child gets the first three digits from the second parent and the rest from the
first parent. The 8-queens states involved in this reproduction step are shown in the
next figure.
Genetic Algorithms

The 8-queens states corresponding to the first two parents in Figure (c) and
the first offspring in Figure (d). The shaded columns are lost in the crossover
step and the unshaded columns are retained.
Genetic Algorithms
• The example shows that when two parent states are quite different, the crossover
operation can produce a state that is a long way from either parent state.

• It is often the case that the population is quite diverse early on in the process, so
crossover (like simulated annealing) frequently takes large steps in the state space early
in the search process and smaller steps later on when most individuals are quite similar.

• Finally, in Figure (e), each location is subject to random mutation with a small
independent probability.

• One digit was mutated in the first, third, and fourth offspring.

• In the 8-queens problem, this corresponds to choosing a queen at random and moving it
to a random square in its column.
Genetic Algorithms
• function GENETIC-ALGORITHM(population, FITNESS-FN) returns
an individual • function REPRODUCE(x , y) returns an individual
• inputs: population, a set of individuals • inputs: x , y, parent individuals
• n←LENGTH(x ); c←random number from 1 to n
• FITNESS-FN, a function that measures the fitness of an individual
• return APPEND(SUBSTRING(x, 1, c), SUBSTRING(y, c +
• repeat 1, n))
• new population ←empty set
• for i = 1 to SIZE(population) do
• x ←RANDOM-SELECTION(population, FITNESS-FN)
(A genetic algorithm is the same as the one
• y ←RANDOM-SELECTION(population, FITNESS-FN)
diagrammed in Figure, with one variation: in
• child ←REPRODUCE(x , y) this more popular version, each mating of
• if (small random probability) then child ←MUTATE(child ) two parents produces only one offspring, not
• add child to new population two.)
• population ←new population
• until some individual is fit enough, or enough time has elapsed
• return the best individual in population, according to FITNESS-FN
Constraint Satisfaction Problem (CSP)
 Content
➢ Introduction
➢ Constraint Satisfaction Problems (CSP)
➢ Map Coloring
➢ N-Queen Problem
➢ Crossword Puzzle
➢ Sudoku
➢ Cryptarithmetic Problem
➢ Job-shop Scheduling
➢ Variations on CSP Formalism
➢ Solving CSP Problems
➢ Generate-and-Test
➢ Backtracking Search
➢ Consistency Driven
➢ Forward Checking
Introduction
• We have so far explored the idea that problems can be solved by searching in a space of states.
These states can be evaluated by domain-specific heuristics and tested to see whether they are goal
states.

• From the point of view of the search algorithm, each state is atomic, or indivisible—a black box with
no internal structure.

• However, there is a way to solve a wide variety of problems more efficiently. 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

Introduction (contd…)
Introduction (contd…)
• CSP search algorithms take advantage of the structure of states and use general-purpose rather
than problem-specific heuristics to enable the solution of complex problems.

• The main idea is to eliminate large portions of the search space all at once by identifying
variable/value combinations that violate the constraints.

• An assignment of values to some or all of the variables that does not violate any constraints is
called a consistent or legal assignment.

• A complete assignment is that in which every variable is mentioned and if it satisfies all the
constraints, then it is a solution.
Constraint Satisfaction Problem (CSP)
• A constraint satisfaction problem consists of three components, X, D, and C:
• X is a set of variables, {X1, . . . ,Xn}.
• D is a set of domains, {D1, . . . ,Dn}, one for each variable.
• C is a set of constraints that specify allowable combinations of values.

• Each domain Di consists of a set of allowable values, {v1, . . . , vk} for variable Xi.

• Each constraint Ci consists of a pair <scope, rel> , where

• scope is a tuple of variables that participate in the constraint
• rel is a relation that defines the values that those variables can take on.
CSP (contd…)
A relation can be represented as an explicit list of all tuples of values that satisfy the constraint, or
as an abstract relation that supports two operations:

1) Testing if a tuple is a member of the relation

2) Enumerating the members of the relation.

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>.
Why formulate a problem as a CSP ?
• One reason is that the CSPs yield a natural representation for a wide variety of problems; if we
already have a CSP-solving system, it is often easier to solve a problem using it than to design a
custom solution using another search technique. In addition, CSP solvers can be faster than state-
space searchers because the CSP solver can quickly eliminate large swatches of the search space.

• For example, once we have chosen {SA=blue} in the Australia problem, we can conclude that none
of the five neighboring variables can take on the value blue.

• Without taking advantage of constraint propagation, a search procedure would have to consider
3^5=243 assignments for the five neighboring variables;

• With constraint propagation we never have to consider blue as a value, so we have only 2^5=32
assignments to look at, a reduction of 87%.
Varieties of Constraints
• Unary constraints involve a single variable, e.g., SA != green

• Binary constraints involve pairs of variables, e.g., SA != WA.

• Higher-order constraints involve 3 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
• - constrained optimization problems.
CSP Example 1: Map Coloring
Suppose that we are looking at a 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. To formulate this as a CSP, we define the variables to be the regions
X = {WA, NT, Q, NSW, V, SA, T}

The domain of each variable is the set

Di = {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}
CSP Example1: Map Coloring (contd…)
• SA != WA is a shortcut for <(SA,WA), SA != WA>, 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}
CSP Example1: Map Coloring (contd…)
• Constraint graph
• Binary CSP: Each constraint relates two variables
• Constraint graph: Nodes are variables, arcs are constraints

Constraint Graph
CSP Example 2: n-Queen problem
• Problem proposed: Chess player Max Bazzel (1848)
• Solution: S. Gunther(1874), J.W.L. Glaisher (refiner)
• The eight queens puzzle has 92 distinct solutions.
• If solutions that differ only by symmetry operations (rotations and reflections) of the board are
counted as one, the puzzle has 12 unique solutions.
• The following table gives the number of solutions for n queens, both unique and distinct.

• Note that the 6 queens puzzle has, interestingly, fewer solutions than the 5 queens puzzle!
CSP Example 3: Crossword Puzzle
• Complete the following puzzle with words:
AFT, ALE, EEL, HEEL, HIKE, HOSES, KEEL, KNOT, LASER, LEE, LINE, SAILS, SHEET, STEER, TIE

• The numbers 1,2,3,4,5,6,7,8 in the crossword puzzle correspond

to the words that will start at those locations.
• Solution:
VARIABLE | STARTING CELL | DOMAIN
================================================
1 ACROSS | 1 | {HOSES, LASER, SAILS, SHEET, STEER}
4 ACROSS | 4 | {HEEL, HIKE, KEEL, KNOT, LINE}
7 ACROSS | 7 | {AFT, ALE, EEL, LEE, TIE}
8 ACROSS | 8 | {HOSES, LASER, SAILS, SHEET, STEER}
2 DOWN | 2 | {HOSES, LASER, SAILS, SHEET, STEER}
3 DOWN | 3 | {HOSES, LASER, SAILS, SHEET, STEER}
5 DOWN | 5 | {HEEL, HIKE, KEEL, KNOT, LINE}
6 DOWN | 6 | {AFT, ALE, EEL, LEE, TIE}
CSP Example 4: Sudoku Problem
• The Popular Sudoku puzzle has
introduced millions of people to
constraint satisfaction problems,
although they may not recognize
it.

• A Sudoku board consists of 81

squares, some of which are
initially filled with digits from 1 to
9.

• The puzzle is to fill in all the

remaining squares such that no
digit appears twice in any row,
column, or 3x3 box.
 CSP Example 4: Sudoku Problem (contd…)
• A Sudoku puzzle can be considered with 81 variables, one for each square.
• We use the variable names A1 through A9 for the top row (left to right), down to I1 through I9 for the bottom
row.
• The empty squares have the domain {1, 2, 3, 4, 5, 6, 7, 8, 9} and the prefilled squares have a domain consisting
of a single value.
 CSP Example 5: Cryptarithmetic Problem
• In the following pattern: C4 C3 C2 C1
S E N D S E N D
M O R E M O R E
--------------- ---------------------------
M O N E Y M O N E Y

• Replace each letter by a distinct digit so that the resulting sum is correct.

1. D + E = 10 * C1 + Y
2. C1 + N + R = 10 * C2 + E
3. C2 + E + O = 10 * C3 + N
4. C3 + S + M = 10 * C4+ O
5. C4 = M = 1 (As M has to be non-zero.)
Where C1, C2, C3 and C4 can be either 0 or 1.
Other alphabets can take unique values from the set { 0,1, 2, 3, 4, 5, 6, 7, 9}
 CSP Example 5: Cryptarithmetic Problem
• In the following pattern: Initial state
S E N D
M O R E M=1 (As C4 =1)
--------------- S=8 OR 9
O=0 OR 1 O=0
M O N E Y N=E OR E+1 N=E+1
C2=1
C1=1 C1=0 D=Y+5 N+R>8
R=8 E<>9 , E = 2, 3, 4 ends with conflict

SOLUTION:
{S=9, E=5, N=6, D=7, M=1, O=0, N=6 R=9
C3= 0 AND S=9 Contradiction
R=8, Y=2} R=9 - C1 as S=9
{ C1 =1, C2 = 1, C3 =0, C4 = 1} 5+D=Y OR 5+D=10 + Y
Y= 2
 CSP Example 5: Cryptarithmetic Solution
• In the following pattern:
S E N D C4 C3 C2 C1 1 0 1 1
M O R E -------------------- --------------------
--------------- S E N D 9 5 6 7

M O N E Y + M O R E + 1 0 8 5
______________ ______________

C1=1 C1=0 M O N E Y 1 0 6 5 2
SOLUTION:
{S=9, E=5, N=6, D=7, M=1, O=0, R=8, Y=2} and
{ C1 =1, C2 = 1, C3 =0, C4 = 1}
 CSP Example 5: Cryptarithmetic Problem
• These constraints can be represented in a constraint hypergraph as shown in the figure.
• A hypergraph consists of ordinary nodes (the circles in the figure) and hypernodes (the squares),
which represent n-ary constraints.

• Variables: F T U W R O

• Domains: {0,1,2,3,4,5,6,7,8,9}

• Constraints: Alldiff (F,T,U,W,R,O)

O + O = R + 10 · C1
C1 + W + W = U + 10 · C2
C2 + T + T = O + 10 · C3
C3 = F, T ≠ 0, F ≠ 0
CSP Example 5: Cryptarithmetic Solution
CSP Example 6: Job-shop scheduling
• Factories have the problem of scheduling a day’s worth of jobs, subject to various constraints. In
practice, many of these problems are solved with CSP techniques.

• 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 so many tasks can go on at once.

• Constraints can also specify that a task takes a certain amount of time to complete.

• We now 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.
CSP Example 6: Job-shop scheduling
• 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.

• 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
CSP Example 6: Job-shop scheduling
• 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 .
CSP Example 6: Job-shop scheduling

Disjunctive constraint:

• 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)

• This looks like a more complicated constraint, combining arithmetic and logic. But it still
reduces to a set of pairs of values that AxleF and AxleB can take on.
CSP Example 6: Job-shop scheduling
• We also need to assert that the inspection comes last and takes 3 minutes.

• For every variable except Inspect, we add a constraint of the form

X + 𝒅_𝑿≤ Inspect.

• Finally, suppose there is a requirement to get the whole assembly done in 30 minutes. We can
achieve that by limiting the domain of all variables:
Di = {1, 2, 3, . . . , 27}

• This particular problem is trivial (i.e. not important) to solve, but CSPs have been applied to
job-shop scheduling problems like this with thousands of variables. In some cases, there are
complicated constraints that are difficult to specify in the CSP formalism, and more advanced
planning techniques are used.
 Variations on CSP Formalism
A) Discrete Variables

1. Discrete Finite Domains:

Examples: 1) Map-coloring problems

2) Job scheduling with time limits
3) 8-queens problem
[This 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}.]

No. of possible complete assignments = O(dn) where n variables, domain size d

e.g. Finite domain CSPs include Boolean CSPs, whose variables can be either true or false.

• Boolean CSPs include as special cases some NP-complete problems.

• In worst case , we can not expect to solve finite-domain CSPs in less than exponential time.
• In most practical applications, however, general-purpose CSP algorithms can solve problems orders of magnitude
larger than those solvable via the general-purpose search algorithms.
Variations on CSP Formalism (cont…)

2. Discrete Infinite Domains:

Examples: 1) The set of integers or strings

2) The job-scheduling problem without deadline
[There would be an infinite number of start times for each variable.]

• With infinite domains, it is no longer possible to describe constraints by enumerating all

allowed combinations of values.
• Instead, a constraint language must be used that understands constraints such as T1 + d1 ≤ T2
directly, without enumerating the set of pairs of allowable values for (T1, T2).
Variations on CSP Formalism (contd…)
B) Continuous Variables

Continuous domains: Constraint satisfaction problems with continuous domains are common in the
real world and are widely studied in the field of operations research.

Examples:

1) Scheduling of experiments on the Hubble Space Telescope

It requires very precise timing of observations; the start and finish of each observation and maneuver are
continuous-valued variables that must obey a variety of astronomical, precedence, and power constraints.

2) Linear programming problems

Where constraints must be linear equalities or inequalities. Linear programming problems can be solved in time
polynomial in the number of variables.
Variations on CSP Formalism (contd…)
C) Constraints

• Unary constraint: It restricts the value of a single variable.

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>

• Binary constraint: It relates two variables.

Example: SA != NSW is a binary constraint. (A binary CSP is one with only binary constraints; it can be
represented as a constraint graph).

• There are also higher-order constraints such as Ternary constraint.

Example: Asserting that the value of Y is between X and Z, with the ternary constraint Between(X, Y, Z).
Variations on CSP Formalism (contd…)

• Global Constraints:

• A constraint involving an arbitrary number of variables is called a global constraint. (The name is
traditional but confusing because it need not involve all the variables in a problem).

• One of the most common global constraints is Alldiff , which says that all of the variables involved in
the constraint must have different values.

Examples:

✓ Sudoku problems: All variables in each row or column or 3 ˟ 3 matrix must satisfy an Alldiff
constraint.)

✓ Cryptarithmetic puzzles: Each letter in a cryptarithmetic puzzle represents a different digit.

Real-World CSPs
• Assignment problems
e.g., who teaches what class
• Timetabling problems
e.g., which class is offered when and where?
• Transportation scheduling
• Factory scheduling
(Notice that many real-world problems involve real-valued variables)

• The constraints we have described so far have all been absolute constraints, violation of which
rules out a potential solution.

• Many real-world CSPs include preference constraints indicating which solutions are preferred.
Real-World CSPs (contd…)
• Example: In a university class-scheduling problem, there are absolute constraints that no
professor can teach two classes at the same time. But we also may allow preference constraints:
Prof. R might prefer teaching in the morning, whereas Prof. N prefers teaching in the afternoon.
A schedule that has Prof. R teaching at 2 p.m. would still be an allowable solution but would not
be an optimal one.

• Preference constraints can often be encoded as costs on individual variable assignments—for

example, assigning an afternoon slot for Prof. R costs 2 points against the overall objective
function, whereas a morning slot costs 1.

• With this formulation, CSPs with preferences can be solved with optimization search methods,
either path-based or local. We call such a problem a constraint optimization problem, or COP.
Real-World CSPs (contd…)

• In regular state-space search, an algorithm can do only one thing: search.

• In CSPs there is a choice: an algorithm can search (choose a new variable assignment from
several possibilities) or do a specific type of inference called constraint propagation (use the
constraints to reduce the number of legal values for a variable, which in turn can reduce the
legal values for another variable, and so on.)

• Constraint propagation may be intertwined with search, or it may be done as a preprocessing

step, before search starts. Sometimes this preprocessing can solve the whole problem, so no
search is required at all.
Backtracking Search
• Variable assignments are commutative, i.e.,
[ WA = red then NT = green ] same as [ NT = green then WA = red ]

• Only need to consider assignments to a single variable at each node

• Depth-first search for CSPs with single-variable assignments is called backtracking search

• Backtracking search is the basic uninformed algorithm for CSPs

• Can solve n-queens for n ≈ 24

Backtracking Search (contd…)
• A variant of depth-first search called backtracking search uses still less memory.
• In backtracking, only one successor is generated at a time rather than all successors; each partially
expanded node remembers which successor to generate next. In this way, only O(m) memory is
needed rather than O(bm).
• Backtracking search facilitates yet another memory-saving (and time-saving) trick: the idea of
generating a successor by modifying the current state description directly rather than copying it
first.
• This reduces the memory requirements to just one state description and O(m) actions.
• For this to work, we must be able to undo each modification when we go back to generate the next
successor.
• For problems with large state descriptions, such as robotic assembly, these techniques are critical to
success.
Backtracking Search Algorithm
Backtracking Search Example
Backtracking Search Example
Backtracking Search Example
Improving Backtracking Efficiency

General-purpose methods can give huge gains in speed:

1. Which variable should be assigned next?

2. In what order should its values be tried?

3. Can we detect inevitable failure early?

4. Can we take advantage of problem structure?

Most constrained variable

• Most constrained variable:

choose the variable with the fewest legal values

• Minimum remaining values (MRV) heuristic

Most constraining variable
• Tie-breaker among most constrained variables
• Most constraining variable:

• Choose the variable with the most constraints on remaining variables

Least constraining value
• Given a variable, choose the least constraining value:

• The one that rules out the fewest values in the remaining variables

• Combining these heuristics makes 1000 queens feasible

Forward Checking
• Idea:

• Keep track of remaining legal values for unassigned variables

• Terminate search when any variable has no legal values
Forward Checking
Forward Checking
 Local Consistency
• If we treat each variable as a node in a graph and each binary constraint as an arc, then the process
of enforcing local consistency in each part of the graph causes inconsistent values to be eliminated
throughout the graph.

There are different types of local consistency:

1) Node Consistency: A single variable (corresponding to a node in the CSP network) is node-
consistent if all the values in the variable’s domain satisfy the variable’s unary constraints. For
example, in the variant of the Australia map-coloring problem where South Australians dislike green, the
variable SA starts with domain {red, green, blue}, and we can make it node consistent by eliminating
green, leaving SA with the reduced domain {red , blue}.

•We say that a network is node-consistent if every variable in the network is node-consistent.

•It is always possible to eliminate all the unary constraints in a CSP by running node consistency. It is
also possible to transform all n-ary constraints into binary ones. (Ex.6.6)
Local Consistency
• 2) Arc Consistency: A variable in a CSP is arc-consistent if every value in its domain
satisfies the variable’s binary constraints. More formally, Xi is arc-consistent with respect to
another variable Xj if for every value in the current domain Di there is some value in the
domain Dj that satisfies the binary constraint on the arc (Xi,Xj). A network is arc-consistent
if every variable is arc consistent with every other variable.

• For example, consider the constraint Y = 𝑋^2 where the domain of both X and Y is the set of
digits. We can write this constraint explicitly as (X, Y ), {(0, 0), (1, 1), (2, 4), (3, 9))} .

• To make X arc-consistent with respect to Y , we reduce X’s domain to {0, 1, 2, 3}. If we also
make Y arc-consistent with respect to X, then Y ’s domain becomes {0, 1, 4, 9} and the
whole CSP is arc-consistent.
Local Consistency
• Arc Consistency:
Simplest form of propagation makes each arc consistent X →Y is consistent iff
for every value x of X there is some allowed value y of Y
 Local Consistency
• Arc Consistency:
• Simplest form of propagation makes each arc consistent
• X →Y is consistent iff
for every value x of X there is some allowed value y of Y

If X loses a value, neighbors of X need to be rechecked If X loses a value, neighbors of X need to be rechecked
Arc consistency detects failure earlier than forward
checking
Can be run as a preprocessor or after each assignment
Local Consistency
• Arc Consistency Algorithm:

• Time complexity: O(n2d3)

Local Search for CSPs: 4-Queen Problem
States:
4 queens in 4 columns (44 = 256 states)

Actions:
move queen in column

Goal test:
no attacks

Evaluation:
h(n) = number of attacks

[Given random initial state, can solve n-

queens in almost constant time for arbitrary
n with high probability (e.g., n = 10,000,000)]
Local Search for CSPs: 8-Queen Problem

In choosing a new value

for a variable, the most
obvious heuristic is to
select the value that
results in the minimum
number of conflicts
with other variables—
the min-conflicts
heuristic
Minimum Conflicts Algorithm (Local
Search)
Summary
• CSPs are a special kind of problem:
• states defined by values of a fixed set of variables
• goal test defined by constraints on variable values

• Backtracking = depth-first search with one variable assigned per node

• Variable ordering and value selection heuristics help significantly

• Forward checking prevents assignments that guarantee later failure

• Constraint propagation (e.g., arc consistency) does additional work to constrain

values and detect inconsistencies

• Iterative min-conflicts is usually effective in practice

 THANK YOU

Reference: Artificial Intelligence by Stuart_J_Russell_and_Peter_Norvig

Online Contents