Chapter Three

Solving Problems by
Searching and Constraint
Satisfaction Problem
 Solving Problems by Searching and Constraint
Satisfaction Problem
Outline of the chapter
 Problem Solving by Searching
 Problem Solving Agents
 Problem Formulation
 Search Strategies
 Avoiding Repeated States
 Constraint Satisfaction Search
 Games as Search Problems

2
Introduction
 Problem-solving agents use atomic representations
- that is states of the world are considered as
wholes, with no internal structure visible to the
problem solving algorithms.
 Goal-based agents that use more advanced
factored or structured representations are
usually called planning agents
 In this chapter, we limit ourselves to the simplest
kind of task environment, for which the solution to a
problem is always a fixed sequence of actions.

3
Problem Solving Agents
 Problem-solving agents are one kind of goal-based
agent.
 Problem-solving agents decide what to do by finding
sequences of actions that lead to desirable states.
 Intelligent agents are supposed to act in such a way
that the environment goes through a sequence of
states that maximizes the performance measure.
We Need Goal?
 Goals help to organize behavior by limiting the
objectives that the agent is trying to achieve and
hence the actions it needs to consider.
 Goal formulation, based on the current situation
and the agent's performance measure, is the first
step in problem solving.
 Problem formulation is the process of deciding
what actions and states to consider, given a goal.
What is Search?
 In general, an agent with several immediate options
of unknown value can decide what to do by first
examining different possible sequence of actions that
lead to state of known value, then choosing the best
sequence.
 This process of looking for a sequence of actions
that reaches the goal is called search.
 A search algorithm takes a problem as input and
returns a solution in the form of an action sequence.
Why Search?
 To achieve goals or to maximize our utility we need
to predict what the result of our actions in the
future will be.
 There are many sequences of actions, each with
their own utility.
 We want to find, or search for, the best one.
 Once a solution is found, the actions it recommends
can be carried out.
 This is called the execution phase.
 Thus, we have a simple “formulate, search, execute”
design for the agent.
A Real World Scenario (A Touring Agent Problem)
 Imagine an agent in a city of Arad, Romania, enjoying a
touring holiday. Suppose the agent has a nonrefundable
ticket to fly out of Bucharest the following day. In the case,
it makes sense for the agent to adapt the goal of getting
into Bucharest.
 Formulate goal:
 be in Bucharest
 Formulate problem:
 states: various cities
 actions: drive between cities or choose next city
 Find solution:
 sequence of cities, e.g., Arad, Sibiu, Fagaras, Bucharest
9
Problem Formulation
 A problem can be defined formally by five components:
 The initial state that the agent starts in.
 For example, the initial state for our agent in Romania
might be described as In(Arad).
Actions - set of possible actions in current state s.
 Given a particular state s, ACTIONS(s) returns the set of
actions that can be executed in s.
 We say that each of these actions is applicable in s.
 For example, from the state In(Arad), the applicable
actions are {Go(Sibiu), Go(Timisoara), Go(Zerind)}.

10
Problem Formulation
 Transition model - a description of what each action does;
specified by a function RESULT(s, a) that returns the state
that results from doing action a in state s.
 For example, we have RESULT(In(Arad),Go(Zerind)) = In(Zerind) .
 The state space of the problem - the set of all states reachable from
the initial state by any sequence of actions.
 The state space forms a directed graph in which the nodes are
states and the links between nodes are actions.
 A path in the state space is a sequence of states connected by
a sequence of actions.
 The Goal test, which determines whether a given state is a
goal state.
 Sometimes there is an explicit set of possible goal states, and the test
simply checks whether the given state is one of them. 11
Problem Formulation
 Path cost function that assigns a numeric cost to each path.
 The problem-solving agent chooses a cost function that reflects
its own performance measure.
 For the agent trying to get to Bucharest, time is of the essence,
so the cost of a path might be its length in kilometers.
 The cost of a path can be described as the sum of the costs of
the individual actions along the path
 The step cost of taking action a in state s to reach state s’ is
denoted by c(s, a, s’).
 The step costs for Romania are route distances.
 A solution to a problem is an action sequence that leads from the
initial state to a goal state.
 Solution quality is measured by the path cost function, and an
optimal solution has the lowest path cost among all solutions.
12
Formulating Problems
 Abstraction - process of removing details from state
descriptions because they are irrelevant for finding solution.
 Real world is highly complex
 state space must be abstracted for problem solving
 (Abstract) state - set of real states
 (Abstract) action - complex combination of real actions
 e.g., "Arad  Zerind" represents a complex set of possible routes,
detours, rest stops, etc.
 For guaranteed reliability, any real state "in Arad” must get to
some real state "in Zerind”.
 (Abstract) solution - set of real paths that are solutions in the real
world
 Each abstract action should be "easier" than the original problem

13
Example Problems (A Touring Agent Problem)
 Total solutions = N * N2, For Romania state N = 20,
Total solutions = 20 * 202
Steps In Problem Formulation
 Initial State : IN (STSATE) IN (ARAD)
 Action : ACTION (STSATE) -> GO (STATE)
GO (Zerind)
ACTION (Arad) GO (SIbiu)
GO (Timisoara)

 Transitional Model: RESULT (s, a) -> IN (X)

RESULT (IN (Arad), GO(Zerind)) = IN(Zerind)
 Goal Test: IN (X) == { IN(g)}, IN (X) == { IN(Bucharest)}
 Path Cost: C (S, a, X) == p, C(IN(Arad),GO(Zerind), IN(Zerind)) == 75
C(IN(Arad),GO(Sibiu), IN(Sibiu)) == 140
C(IN(Arad),GO(Timisoara), IN(Timisoara)) == 118
 Solution quality is measured by path cost function, and an optional solution has
the lowest path cost among all solution. 14
Example Problems
 A toy problem is intended to illustrate or exercise various
problem-solving methods.
 It can be given a concise, exact description and hence is
usable by different researchers to compare the performance
of algorithms.
 A real-world problem is one whose solutions people
actually care about.
 Such problems tend not to have a single agreed-upon
description, but we can give the general flavor of their
formulations.

15
The state space for the vacuum world.

 Links denote actions: L = Left, R = Right, S = Suck.

16
Toy problems
 This can be formulated as a problem as follows:
 States: The state is determined by both the agent location and the dirt
locations.
 The agent is in one of two locations, each of which might or might not
contain dirt.
 Thus, there are 2 × 22 = 8 possible world states.
 A larger environment with n locations has n × 2n states.
 Initial state: Any state can be designated as the initial state.
 Actions: In this simple environment, each state has just three actions:
Left, Right, and Suck. Larger environments might also include Up and Down.
 Transition model: The actions have their expected effects, except that
moving Left in the leftmost square, moving Right in the rightmost square,
and Sucking in a clean square have no effect.
 Goal test: This checks whether all the squares are clean.
 Path cost: The path cost is the number of steps in the path.
17
A typical instance of the 8-puzzle.
 The 8-puzzle, an instance of which is shown in the following
figure, consists of a 3×3 board with eight numbered tiles and
a blank space.
 A tile adjacent to the blank space can slide into the space.
 The objective is to reach a specified goal state, such as the
one shown on the right of the figure. The standard
formulation is as follows:

18
A typical instance of the 8-puzzle.
 States: A state description specifies the location of each of the
eight tiles and the blank in one of the nine squares.
 Initial state: Any state can be designated as the initial state. Note
that any given goal can be reached from exactly half of the possible
initial states
 Actions: The simplest formulation defines the actions as
movements of the blank space Left, Right, Up, or Down. Different
subsets of these are possible depending on where the blank is.
 Transition model: Given a state and action, this returns the
resulting state; for example, if we apply Left to the start state, the
resulting state has the 5 and the blank switched.
 Goal test: This checks whether the state matches the goal
configuration shown in the figure.
 Path cost: The path cost is the number of steps in the path.
19
8-queens Problem
 The goal of the 8-queens problem is to place eight queens on a
chessboard such that no queen attacks any other.
 The following figure shows an attempted solution that fails: the
queen in the right most column is attacked by the queen at the top
left.
 Although efficient special-purpose algorithms exist for this problem
and for the whole n-queens family, it remains a useful test problem
for search algorithms.
 There are two main kinds of formulation. An incremental
formulation involves operators that augment the state
description, starting with an empty state; for the 8-queens problem,
this means that each action adds a queen to the state.
 A complete-state formulation starts with all 8 queens on the
board and moves them around. In either case, the path cost is of
no interest because only the final state counts. 20
8-queens problem
 The first incremental formulation
one might try is the following:
 States: Any arrangement of 0 to 8
queens on the board is a state.
 Initial state: No queens on the
board.
 Actions: Add a queen to any
empty square.
 Transition model: Returns the
board with a queen added to the
specified square.
 Goal test: 8 queens are on the
board, none attacked.  Almost a solution to the
8-queens problem.

21
Real-World Problems
 We have already seen how the route-finding problem is defined in
terms of specified locations and transitions along links between them.
 Route-finding algorithms are used in a variety of applications.
 Some, such as Web sites and in-car systems that provide driving
directions, are relatively straightforward extensions of the Romania
example.
 Others, such as routing video streams in computer networks, military
operations planning, and airline travel-planning systems, involve much
more complex specifications.
 Consider the airline travel problems that must be solved by a travel-
planning Web site:
 States: Each state obviously includes a location (e.g., an airport) and the
current time. Furthermore, because the cost of an action (a flight
segment) may depend on previous segments, their fare bases, and their
status as domestic or international, the state must record extra
information about these “historical” aspects. 22
Real-World Problems
 Initial state: This is specified by the user’s query.
 Actions: Take any flight from the current location, in any seat
class, leaving after the current time, leaving enough time for within-
airport transfer if needed.
 Transition model: The state resulting from taking a flight will
have the flight’s destination as the current location and the flight’s
arrival time as the current time.
 Goal test: Are we at the final destination specified by the user?
 Path cost: This depends on monetary cost, waiting time, flight
time, customs and immigration procedures, seat quality, time of
day, type of airplane, frequent-flyer mileage awards, and so on.
 Commercial travel advice systems use a problem formulation
of this kind, with many additional complications to handle the
byzantine fare structures that airlines impose. 23
Example: Robotic assembly

 States: real-valued coordinates of robot joint angles

parts of the object to be assembled
 Initial state: rest configuration
 Actions: continuous motions of robot joints
 Goal test: complete assembly
 Path cost: time to execute + energy used
Searching for Solutions
 Having formulated some problems, we now need to solve
them.
 A solution is an action sequence, so search algorithms work
by considering various possible action sequences.
 The possible action sequences starting at the initial state form
a search tree with the initial state at the root; the branches
are actions and the nodes correspond to states in the state
space of the problem.
 As shown in the following figure, the first few steps in
growing the search tree for finding a route from Arad to
Bucharest.
 A general tree-search algorithm considers all possible paths
to find a solution, whereas a graph-search algorithm avoids
consideration of redundant paths. 25
Searching for Solutions
 Then we need to consider taking various actions.
 We do this by expanding the current state; that is, applying
each legal action to the current state, thereby generating a
new set of states.
 In this case, we add three branches from the parent node
In(Arad) leading to three new child nodes: In(Sibiu),
In(Timisoara), and In(Zerind).
 Now we must choose which of these three possibilities to
consider further.
 This is the essence of search-following up one option now and
putting the others aside for later, in case the first choice does
not lead to a solution. Suppose we choose Sibiu first.
 We check to see whether it is a goal state (it is not) and then expand
it to get In(Arad), In(Fagaras), In(Oradea), and In(RimnicuVilcea).
26
Searching for Solutions
 We can then choose any of these four or go back and choose
Timisoara or Zerind.
 Each of these six nodes is a leaf node, that is, a node with no
children in the tree.
 The set of all leaf nodes available for expansion at any given point
is called the frontier. In figure, the frontier of each tree consists
of those nodes with bold outlines
 The process of expanding nodes on the frontier continues until
either a solution is found or there are no more states to expand.
 Search algorithms all share this basic structure; they vary primarily
according to how they choose which state to expand next the so-
called search strategy.
 As shown in the search tree the path from Arad to Sibiu and back to
Arad again! We say that In(Arad) is a repeated state in the search tree,
generated in this case by a loopy path. 27
28
Search algorithm
 Two functions needed for conducting search
Generator (or successors) function: Given a state and action, produces
its successor states (in a state space)
Tester (or IsGoal) function: Tells whether given state S is a goal state
IsGoal(S)  True/False
IsGoal and Successors functions depend on problem domain.
 Two lists maintained during searching
OPEN list: stores the nodes we have seen but not explored
CLOSED list: the nodes we have seen and explored
Generally, search proceeds by examining each node on the OPEN list,
performing some expansion operation that adds its children to the OPEN
list, and moving the node to the CLOSED list.
Merge function: Given successor nodes, it either append,
prepend or arrange based on evaluation cost
Path cost: function assigning a numeric cost to each path
Either from initial node to current node and/or from current node to goal node
Search algorithm
 Input: a given problem (Initial State + Goal state + transit states
and actions) and
 Output: returns a solution, i.e. an optimal sequence of actions to
reach the goal.
function GeneralSearch (problem, strategy){
open = (C_0); //put initial state C_0 in the List
closed = {}; //maintain list of nodes examined earlier
while (not (empty (open))) {
f = remove_first(open);
if IsGoal (f) then return (f);
closed = append (closed, f);
l = not-in-set ( Successors (f), closed );
open = merge ( rest(open), l); //append or pre_pend l to open list
}
return ('fail') }
Measuring Problem-Solving Performance
 Before we get into the design of specific search algorithms, we need to
consider the criteria that might be used to choose among them.
 We can evaluate an algorithm’s performance in four ways:
 Completeness: Is the algorithm guaranteed to find a solution
when there is one?
 Optimality: Does the strategy find the optimal solution?
 Time complexity: How long does it take to find a solution?
 Space complexity: How much memory is needed to perform
the search?
 Complexity is expressed in terms of three quantities: b, the
branching factor or maximum number of successors of any node;
d, the depth of the shallowest goal (i.e., the number of steps
along the path from the root); and m, the maximum length of
any path in the state space.
31
Measuring Problem-Solving Performance
 Time is often measured in terms of the number of nodes
generated during the search, and space in terms of the maximum
number of nodes stored in memory.
 For the most part, we describe time and space complexity for
search on a tree; for a graph, the answer depends on how
“redundant” the paths in the state space are.
 To assess the effectiveness of a search algorithm, we can consider
just the search cost which typically depends on the time
complexity
 But can also include a term for memory usage or we can use the
total cost, which combines the search cost and the path cost of the
solution found.
 For the problem of finding a route from Arad to Bucharest, the
search cost is the amount of time taken by the search and the
solution cost is the total length of the path in kilometers. 32
Search Strategies
 Uninformed search (also called blind search) - strategies
have no additional information about states beyond that
provided in the problem definition.
 Uses no information about the problem to guide the
search and therefore may not be very efficient.
 Informed search or heuristic search - strategies that
know whether one non-goal state is “more promising” than
another.
 Uses information about the problem to guide the search,
usually guesses the distance to a goal state and therefore
efficient, but the search may not be always possible.

33
Search Strategies

• Breadth first
Uninformed •
•
Depth first
Uniform cost
search • Depth limited search
• Iterative deepening

• Greedy search
Informed • A*-search
search •
•
Iterative improvement,
Constraint satisfaction

34
 Breadth-first search
 Expands the shallowest
unexpanded node
 The root node is expanded first, then
all the successors of the root node
are expanded, then their successors,
and so on
 All the nodes (at a given depth in the
search tree) are expanded before any
nodes at the next level are expanded
 Implementation: uses a FIFO
queue for the frontier (set of all
leaf nodes available for expansion)
 New successors go at the end, put
successors at the end of the queue
 Pop nodes from the front of the queue
BFS Figure 35
Breadth-first search
 Goal node is H

 Solution: F, D, J, B, E, G, K, A, C, I, H

36
Algorithm for Breadth first search
function BFS (problem){
open = (C_0); //put initial state C_0 in the List
closed = {}; /maintain list of nodes examined earlier
while (not (empty (open))) {
f = remove_first(open);
if IsGoal (f) then return (f);
closed = append (closed, f);
l = not-in-set (Successors (f), closed );
open = merge ( rest(open), l); //append to the list
}
return ('fail')
}
Breadth-first search
 Completeness? Yes
 If the shallowest goal node is at some finite depth
d, breadth-first search will eventually find it after
generating all shallowest nodes (provided the
branching factor be is finite)
 Optimality? Yes
As soon as goal node is generated, we know it is
the shallowest goal node
Breadth first search is optimal if the path cost is a
non-decreasing function of the depth of the
node
38
Breadth-first search
 Time complexity?
b+b2+b3+… +bd = O(bd) (where d = level,
b= number of node generated from each node.
If the algorithm applies the goal test to nodes
when selected for expansion, the whole layer of
nodes at depth d would be expanded before the
goal was detected
Thus, in the worst case, the time complexity
would be O(bd+1) i.e. exponential
 Space complexity?
Keeps every node in memory O(bd) 39
Uniform-cost search
 Uniform-cost search - algorithm expands nodes in the order
of their cost from the source.
 When all step costs are equal, breadth-first search is optimal
because it always expands the shallowest unexpanded node.
 In uniform cost search the newly generated nodes are put in
OPEN according to their path costs. It-expands the node n
with the lowest path cost g(n).

Part of the Romania state space, selected to illustrate uniform-cost search

40
Uniform-cost search
 The successors of Sibiu are Rimnicu Vilcea and Fagaras, with
costs 80 and 99, respectively.
 The least-cost node, Rimnicu Vilcea, is expanded next, adding
Pitesti with cost 80 + 97=177.
 The least-cost node is now Fagaras, so it is expanded, adding
Bucharest with cost 99+211=310.
 Now a goal node has been generated, but uniform-cost search
keeps going, choosing Pitesti for expansion and adding a
second path to Bucharest with cost 80+97+101= 278.
 Now the algorithm checks to see if this new path is better
than the old one; it is, so the old one is discarded.
 Bucharest, now with g-cost 278, is selected for expansion and
the solution is returned.
41
Uniform-cost search
 Equivalent to breadth-first if all step costs all equal.
 Complete? Completeness is guaranteed provided
the cost of every step exceeds some small positive
constant ε .Yes, if step cost ≥ ε (otherwise it can
get stuck in infinite loops)
 Time? Number of nodes with path cost ≤ cost of
optimal solution.
 Space? Number of nodes with path cost ≤ cost of
optimal solution.
 Optimal? Yes, for any step cost ≥ ε
42
Depth-first search
 Expands the deepest node in the
current frontier of the search tree
 Uses LIFO queue
 The most recently generated
node is chosen for
 It is common to implement
depth-first search with a
recursive function that calls
itself on each of its children in
turn.
 A variant of depth-first search called
backtracking search uses still less
memory.
Depth-first search
 Goal node is H

 Solution: F, D, B, A, C, E, J, G, I, H, K
44
Algorithm for Depth first search
function DFS (problem){
open = (C_0); //put initial state C_0 in the List
closed = {}; /maintain list of nodes examined earlier
while (not (empty (open))) {
f = remove_first(open);
if IsGoal (f) then return (f);
closed = append (closed, f);
l = not-in-set (Successors (f), closed );
open = merge ( rest(open), l); //prepend to the list
}
return ('fail')
}
Depth-first search
 Completeness? No
 Fails in infinite depth spaces, spaces with loops
 Complete in finite state spaces
 Optimality? No
 Time complexity?
 O(bm) where m is the maximum depth of any node
 m > d the depth of the shallowest solution
m can be infinite
 Space complexity? O(bm)
 – i.e. linear space
 Backtracking search – use less memory 46
Iterative Deepening Search (IDS)
IDS solves the issue of choosing the best depth limit by trying all
possible depth limit:
Perform depth-first search to a bounded depth d, starting at d = 1 and
increasing it by 1 at each iteration.
This search combines the benefits of DFS and BFS
DFS is efficient in space, but has no path-length guarantee
BFS finds min-step path towards the goal, but requires memory space
IDS performs a sequence of DFS searches with increasing depth-cutoff until
goal is found

Limit=0 Limit=1 Limit=2

Examples of IDS
 Goal is 11

 1st Iteration : 1
 2nd Iteration : 1,2,3
 3rd Iteration : 1,2,4,5,3,6,7
 4th Iteration : 1,2,4,8,9,5,10,11
48
Algorithm for IDS
function IDS (problem){
open = (C_0); //put initial state C_0 in the List
closed = {}; /maintain list of nodes examined earlier
while (not reached maxDepth) {
while (not (empty (open))) {
f = remove_first(open);
if (IsGoal (f)) then return (f);
closed = append (closed, f);
l = not-in-set (Successors (f), closed);
if (depth(l) < maxDepth) then
open = merge (rest(open), l); //prepend to the list
}}
return ('fail')
}
Comparing Uninformed Search

 b is branching factor,
 d is depth of the shallowest solution,
 m is the maximum depth of the search tree,
 l is the depth limit
51
Informed (Heuristic) Search Strategies
 Informed search algorithms attempt to use extra domain
knowledge to inform the search, in an attempt to reduce
search time.
 A particular class of informed search algorithms is known as
best-first search.
 In best-first search, we use a heuristic function to estimate
which of the nodes in the fringe is the “best” node for
expansion.
 Best-first search is an instance of the general tree-search or
graph-search algorithm in which a node is selected for
expansion based on an evaluation function, f(n).
 The evaluation function is construed as a cost estimate, so the
node with the lowest evaluation is expanded first.
52
Informed (Heuristic) Search Strategies
 Most best-first algorithms include as a component of f a
heuristic function, denoted h(n):
 h(n) = estimated cost of the cheapest path from the state at
node n to a goal state. if n is a goal node, then h(n)=0.
 (Notice that h(n) takes a node as input, but, unlike g(n), it
depends only on the state at that node.)
 This heuristic function, h(n), estimates the cost of the
cheapest path from node n to the goal state. In other words,
it tells us which of the nodes in the fringe it think is “closest”
to the goal.
 Best-first search algorithms: greedy best-first and A*
search.
53
Best-First Search Algorithm
1. Put the initial node on a list START
2. If (START is empty) or (START =GOAL) terminate
search
3. Remove the first node form START. Call this node n.
4. If (n = GOAL) terminate search with success.
5. Else if node n has successor, generate all of them.
Find out how far the goal node. Sort all the children
generated so far by the remaining distance from the
[Link] this list as START1
6. Replace START with START1
7. Goto Step2.
Greedy best-first search
 It is the simplest best-first search algorithm.
 Simply expands the node that is estimated to be closest to
the goal. With the lowest value of the heuristic function h(n).
 Evaluation function f(n) = h(n) (heuristic) = estimate of cost
from n to goal
 That means the agent prefers to choose the action which is
assumed to be best after every action.
 Example, hSLD(n) = straight-line distance from n to X
(destination)
 Greedy best-first search expands the node that appears to be
closest to goal (It tries to minimizes the estimated cost to
reach the goal)
 Example route finding in Romania: Straight line distance heuristic,
SLD 55
56
Greedy best-first search
 The first node to be expanded from Arad will be Sibiu
because it is closer to Bucharest than either Zerind or
Timisoara.
Arad(366)

Sibiu(253) Timisoara(329) Zerind(374)

Arad(366) Fagaras(176) Oradea(380) RimnicuVilcea(193)

Sibiu(253) Bucharest(0)

 Is Arad  Sibiu  Fagaras  Bucharest optimal? Total cost = 450

57
Greedy Best-First Search Example
 The following figure is an example of a route finding problem.
S is the starting state, G is the goal state.

 Strait Line Distance n to goal

58
Greedy Best-First Search Example
 The greedy search algorithm for the graph given in the first
figure. The straight line distance heuristic estimates for the
nodes are shown in the second figure.
 Step 1: S is expanded. Its children are A and D.
 Step 2: D has smaller cost and is expanded next.

 The path obtained is A-D-E-F-G and its cost is 13

59
Greedy Best-First Search Properties
 Greedy best-first search using hSLD finds a solution without
ever expanding a node that is not on the solution path; hence,
its search cost is minimal.
 As shown in route finding, it is not optimal, however: the path
via Sibiu and Fagaras to Bucharest is 32 kilometers longer
than the path through Rimnicu Vilcea and Pitesti.
 Greedy best-first tree search is also incomplete even in a
finite state space, much like depth-first search. Consider the
problem of getting from Iasi to Fagaras.
 The heuristic suggests that Neamt be expanded first because
it is closest to Fagaras, but it is a dead end.
 The worst-case time and space complexity for the tree
version is O(bm), where m is the maximum depth of the
search space. Greedy best-first search is not optimal. 60
A*-search Algorithm
 The most widely known form of best-first search is called A∗
search.
 It evaluates nodes by combining g(n), the cost to reach the node,
and h(n), the cost to get from the node to the goal.
 f(n) = h(n) + g(n)
 Since g(n) gives the path cost from the start node to node n, and
h(n) is the estimated cost of the cheapest path from n to the goal,
we have f(n) = estimated cost of the cheapest solution through n .
 Expand the node for which the evaluation function f(n) is lowest
 The heuristic function h(n) satisfies certain conditions, A∗ search
is both complete and optimal.
 The algorithm is identical to uniform-cost-search except that A∗
uses g + h instead of g.
A* Search Conditions for optimality:
Admissibility and consistency
 A∗ search expands nodes with minimal f(n) = g(n) + h(n).
 A∗ is complete and optimal, provided that h(n) is admissible
(for TREE-SEARCH) or consistent (for GRAPH-SEARCH).
 The space complexity of A∗ is still prohibitive.
 A heuristic function is said to be admissible, if it is never
overestimate the cost to the goal.
 Consistency (or sometimes monotonicity) is required
only for applications of A∗ to graph search.
 A heuristic h(n) is consistent if, for every node n and every
successor n' of n generated by any action a, the estimated
cost of reaching the goal from n is no greater than the step
cost of getting to n plus the estimated cost of reaching the
goal from n: h(n)≤c(n , a ,n' )+h(n' ) 62
A*-search Algorithm
 This is a form of the general triangle inequality, which
stipulates that each side of a triangle cannot be longer than
the sum of the other two sides.
 Here, the triangle is formed by n, n', and the goal Gn closest
to n.
 For an admissible heuristic, the inequality makes perfect
sense: if there were a route from n to Gn via n' that was
cheaper than h(n), that would violate the property that h(n)
is a lower bound on the cost to reach Gn.

63
64
 Solution to Route Finding
Arad f(n) = 0 + 366

393 =140+253 447=118+329 449=75+374

Sibiu ⱱ
Timisoara Zerind

646=280+366 415=239+176 413 =220+193

671=291+380

Arad Fagaras Oradea Rimnicu Vilcea ⱱ

591=338+253 450=450+0
526=366+160 553=300+253

Sibiu 417=317+100
Bucharest Craiova
Pitestiⱱ Sibiu
418=418+0
615=455+160 607=414+193
Bucharest ⱱ
Craiova Rimnicu
A* search Route Finding
65
A* Example


66
Memory-Bounded Heuristic Search
 The simplest way to reduce memory requirements for A∗ is
to adapt the idea of iterative deepening to the heuristic
search context, resulting in the iterative-deepening A∗ (IDA∗)
algorithm.
 The main difference between IDA∗ and standard iterative
deepening is that the cutoff used is the f-cost (g+h) rather
than the depth; at each iteration, the cutoff value is the
smallest f-cost of any node that exceeded the cutoff on the
previous iteration.
 IDA∗ is practical for many problems with unit step costs and
avoids the substantial overhead associated with keeping a
sorted queue of nodes.

67
Recursive best-first search (RBFS)
 Recursive best-first search (RBFS) is a simple recursive
algorithm that attempts to mimic the operation of standard
best-first search, but using only linear space.
 Its structure is similar to that of a recursive depth-first
search, but rather than continuing indefinitely down the
current path, it uses the f limit variable to keep track of the f-
value of the best alternative path available from any ancestor
of the current node.
 If the current node exceeds this limit, the recursion unwinds
back to the alternative path.
 As the recursion unwinds, RBFS replaces the f-value of each
node along the path with a backed-up value the best f-value
of its children.
68
Recursive best-first search (RBFS)
 As the recursion unwinds, RBFS replaces the f-value of each
node along the path with a backed-up value the best f-value
of its children.
 In this way, RBFS remembers the f-value of the best leaf in
the forgotten sub tree and can therefore decide whether it’s
worth re-expanding the sub tree at some later time.
 Like A∗ tree search, RBFS is an optimal algorithm if the
heuristic function h(n) is admissible.
 Its space complexity is linear in the depth of the deepest
optimal solution, but its time complexity is rather difficult to
characterize: it depends both on the accuracy of the heuristic
function and on how often the best path changes as nodes
are expanded.
 IDA∗ and RBFS suffer from using too little memory. 69
Adversarial Search: Games
 Searching in competitive multi-agent environment and
the agents’ goals are in conflict, giving rise to
adversarial search problems often called games .
 The term Game means a sort of conflict in which n
individuals or groups (known as players) participate).
 Game playing, besides the topic of attraction to the
people, has close relation to "intelligence", and its well-
defined states and rules.
 Game theory denotes games of strategy.
 Game theory allows decision-makers (players) to cope
with other decision-makers (players) who have
different purposes in mind.
 In other words, players determine their own strategies
in terms of the strategies and goals of their opponent.
71
Games as Search Problems
 The most commonly used AI technique in game is "Search".
 Zero-Sum Game: It is the game where the interests of the
players are diametrically opposed.
 Regardless of the outcome of the game, the winnings of the
player(s) are exactly balanced by the losses of the other(s).
 Perfect Information Games : Here all moves of all players are
known to everyone. e.g., Chess
 For example, if one player wins a game of chess, the other
player necessarily loses.
 It is this opposition between the agents’ utility functions that
makes the situation adversarial.

72
Application of Game Theory
 Applications of game theory are wide-ranging.
 Economic models : for markets of various commodities with
differing numbers of buyers and sellers, fluctuating values of
supply and demand, seasonal and cyclical variations, analysis
of conflicts of interest in maximizing profits and promoting
the widest distribution of goods and services.
 Social sciences : the n-person game theory has interesting
uses in studying the distribution of power in legislative
procedures, problems of majority rule, individual and group
decision making.
 Military strategists : turn to game theory to study conflicts of
interest resolved through "battles" where the outcome or
payoff of a war game is either victory or defeat.
73
Formal Definition of Game
 A game can be formally defined as a kind of search problem
with the following elements:
 S0: initial state, which specifies how the game is set up at the start.
 PLAYER(s): defines which player has the move in a state.
 ACTIONS(s): returns the set of legal moves in a state.
 RESULT(s, a): the transition model, which defines the result of a
move.
 TERMINAL-TEST(s): A terminal test, which is true when the
game is over and false otherwise. States where the game has
ended are called terminal states.
 UTILITY(s, p): A utility function (also called an objective
function or payoff function), defines the final numeric value for a
game that ends in terminal state s for a player p.
74
Game Tree
 The initial state, action function and results function define a game
tree for the game-
 A tree where the nodes are game states and the edges are moves.
 The game tree for tic-tac-toe from the initial state, MAX has nine
possible moves.
 Play alternates between MAX’s placing an X and MIN’s placing an
O until we reach leaf nodes corresponding to terminal states such
that one player has three in a row or all the squares are filled.
 The number on each leaf node indicates the utility value of
the terminal state from the point of view of MAX; high values
are assumed to be good for MAX and bad for MIN.
 For tic-tac-toe the game tree is relatively small-fewer than 9! = 362, 880
terminal nodes
 Regardless of the size of the game tree, it is MAX's job to search
for a good move 75
Partial Game Tree for Tic-Tac-Toe Problem
Optimal Decisions in Game
 In a normal search problem, the optimal solution would be a
sequence of actions leading to a goal state - a terminal state
that is a win
 In adversarial search, MIN (“unpredictable opponent”) has
something to say about it
 MAX therefore must find a contingent strategy, which
specifies MAX's move in the initial state then MAX's moves in
the states depends on every possible response by MIN, and
so on
 Solution is a strategy specifying a move for every possible opponent
reply
 Roughly speaking, an optimal strategy leads to outcomes at least as
good as any other strategy when one is playing an infallible opponent
 How to find this optimal strategy?
Group Assignment
Local Search Algorithms
Hill-Climbing Search
Genetic Algorithms
Adversarial Search
Minimax Algorithm
Alpha-Beta Pruning
Constraint Satisfaction Problems
 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.
 The main idea is to eliminate large portions of the search space
all at once by identifying variable/value combinations that violate
the constraints.
 State is defined by variables Xi with values from domain Di
 A CSP consists of three components
 X – the set of variables {X1, . . . ,Xn}.,
 D – the set of domains {D1, . . . ,Dn}, one for each variable
 C – the set of constraints that specify allowable combination of values 79
Defining Constraint Satisfaction Problems
 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 and
 rel is a relation that defines the values that those
variables can take on.
 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.

80
Defining Constraint Satisfaction Problems
 To solve a CSP, we need to define a state space and the
notion of a solution
 Each state in a CSP is defined by an assignment of values
to some or all of the variables
 Consistent or legal assignment an assignment that
does not violate any constraints
 A complete assignment is one in which every variable
is assigned
 A partial assignment is one that assigns value to only
some of the variables
 A solution to a CSP is a consistent, complete
assignment 81
Example: Map-Coloring

 Variables WA, NT, Q, NSW, V, SA, T

 Domains Di = {red,green,blue}

 Constraints: adjacent regions must have different colors

 e.g., WA ≠ NT
82
Example: Map-Coloring

 Solutions are complete and consistent assignments, e.g.,

WA = red, NT = green, Q = red, NSW = green,
V = red,SA = blue,T = green
83
Variations on the CSP formalism
 The simplest kind of CSP involves variables that have
discrete, finite domains.
 Map-coloring problems and scheduling with time limits are both of this kind.
 A discrete domain can be infinite, such as the set of integers
or strings. (If we didn’t put a deadline on the job-scheduling
problem, 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).
 CSP with continuous domains are common in the real world
and are widely studied in the field of operations research.
84
Variations on the CSP formalism
 In addition to examining the types of variables that can
appear in CSPs, it is useful to look at the types of constraints.
 Unary constraint, which restricts the value of a single variable.
 For 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
 A binary constraint relates two variables.
 For example, SA = NSW is a binary constraint.
 A binary CSP is one with only binary constraints; it can be
represented as a constraint graph
 Higher-order constraints, such as asserting that the value of Y is between
X and Z, with the ternary constraint Between(X, Y,Z).
 Global constraint involving an arbitrary number of variables. One of the
most common global constraints is Alldiff , which says that all of the
variables involved in the constraint must have different values 85
Variations on the CSP formalism
 Many real-world CSPs include preference constraints indicating which
solutions are preferred.
 For 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 (unless Prof. R happens to be the department chair) but would
not be an optimal one.
 Preference constraints can often be encoded as costs on individual
variable assignments for e.g., assigning an afternoon slot for Prof. R costs
2 points against the overall objective function, whereas a morning slot
costs 1.
 CSPs with preferences can be solved with optimization search methods,
either path-based or local. We call such a problem a constraint
86
optimization problem, or COP
Constraint graph
 CSP can be visualized as constraint graph
 Constraint graph: Nodes are variable, Link connects any two variables
that participate in a constraint
 General purpose CSP algorithms use the graph structure to
speed up search

87
Constraint Propagation: Inference In CSPs
 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: using
the constraints to reduce the number of legal values for a variable
 Constraint propagation 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. The key idea is 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.
88
Constraint Propagation: Inference In CSPs
 There are different types of local consistency
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
 It is always possible to eliminate all the unary constraints in a CSP by
running node consistency.
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.
89
Constraint Propagation: Inference In CSPs
 Arc consistency tightens down the domains (unary
constraints) using the arcs (binary constraints). To make
progress on problems like map coloring, we need a stronger
notion of consistency.
 Path consistency tightens the binary constraints by using
implicit constraints that are inferred by looking at triples of
variables.
 A two-variable set {Xi,Xj} is path-consistent with respect to a
third variable Xm if, for every assignment {Xi = a,Xj = b}
consistent with the constraints on {Xi,Xj}, there is an
assignment to Xm that satisfies the constraints on {Xi,Xm}
and {Xm,Xj}.
 This is called path consistency because one can think of it as
looking at a path from Xi to Xj with Xm in the middle. 90
Backtracking Search For CSPs
 Backtracking search algorithms that work on partial
assignments.
• Special property of CSPs: They are commutative: This means:
the order in which we assign variables does not matter.
• Better search tree: First order variables, then assign them
values one-by-one.
 Backtracking search:
 depth-first search that chooses values for one variable at a time
 backtracks when a variable has no legal values left to assign
 It repeatedly chooses an unassigned variable, and then
tries all values in the domain of that variable in turn, trying to
find a solution
91
Backtracking Search For CSPs
 Backtracking: search algorithms address the following
questions:
 Which variable should be assigned next (SELECT-
UNASSIGNED-VARIABLE), and in what order should its
values be tried (ORDER-DOMAIN-VALUES)?
 What inferences should be performed at each step in the
search (INFERENCE)?
 When the search arrives at an assignment that violates a
constraint, can the search avoid repeating this failure?
 The subsections that follow answer each of these questions
in turn.

92
Backtracking example Part of the search tree for the map-coloring problem

93
Local search for CSPs
 The path to the solution is unimportant, so we can apply
local search!
 To apply to CSPs:
 allow states with unsatisfied constraints
 operators reassign variable values
 Variable selection: randomly select any conflicted variable
 Use a complete-state formulation
 The initial state assigns a value to every variable
 The search changes the value of one variable at a time
 Value selection by min-conflicts heuristic:
 choose value that violates the fewest constraints
 i.e., hill-climb with h(n) = total number of violated constraints

94
Example: 4-Queens
 States: 4 queens in 4 columns (44 = 256 states)
 Actions: move queen in column
 Goal test: no attacks
 Evaluation: h(n) = number of attacks

95