Solving Problems by Searching
Unit - 2
Syllabus:
Problem solving agents, searching for solutions.
Uninformed Search: Breadth first search, Depth first search, Uniform cost
search.
Informed Search: Informed search strategies, Greedy Best First Search, A*
search, Hill climbing, problems with hill climbing such as Local Maxima,
Plateau, Ridge, Genetic Algorithm.
Adversarial Search: Introduction to the Domain of a game, optimal
decisions in games, minimax algorithm, Alpha-beta pruning.
1
Sub Topics
◼ Problem-solving agents
◼ Problem spaces
◼ Problem types
◼ Problem formulation
◼ Example problems
◼ Basic search algorithms
2
Water-jug problem
◼ 1 (x,y) if x<4 -> (4,y) fill the 4-gallon jug
◼ 2 (x,y)if y<3 -> (x,3) fill the 3-gallon jug
◼ 3 (x,y)if x>0 -> (x-d,y) pour some water
out of the 4-gallon jug
◼ 4 (x,y) if y>0 -> (x,y-d) pour some water
out of the 4-gallon jug
◼ 5 (x,y) if x>0 -> (0,y) empty the 4-gallon jug on to
the ground
◼ 6 (x,y)if y>0 -> (x,0) empty the 3-gallon jug on to
the ground
◼ 7 (x,y) if (x+y>=4 and y>0) -> (4,y-(4-x)) pour water from
the 3 gallon jug into the 4 gallon jug
until the 4 gallon jug is full
3
Contd…..
◼ 8 (x,y) if (x+y>=3 and x>0) -> (x-(3-y),3) pour water from the 4
gallon jug into the 3 gallon jug
until the 3 gallon jug is full
◼ 9 (x,y) if x+y <=4 and y>0 -> (x+y,0) pour all the water from 3
gallon jug into the 4-
gallon jug
◼ 10 (x,y) if x+y <=3 and x>0 -> (0,x+y) pour all the water from
4 gallon jug into the 3-gallon jug
◼ 11 (0,2) -> (2,0) pour 2 gallon from 3 to 4-gallon jug
◼ 12 (2,y) -> (2,0) empty the 3-gallon jug on to ground
4
Necessary things to solve problems
◼ Define the problem precisely : what the
initial situations is? and what final situation
constitute acceptable solution to the
problem?
◼ Analyze the problem
◼ Isolate and represent the task knowledge
◼ Choose the best problem solving techniques
and apply them to the particular problem.
5
Problem-solving agents (goal based)
6
Example: Romania
7
Example: Romania
◼ On holiday in Romania; currently in Arad.
◼ Flight leaves tomorrow from Bucharest
◼ Formulate goal:
◼ be in Bucharest
◼
◼ Formulate problem:
◼ states: various cities
◼ actions: drive between cities
◼
◼ Find solution:
◼ sequence of cities, e.g., Arad, Sibiu, Fagaras, Bucharest
8
Problem types
◼ Deterministic, fully observable → single-state problem
◼ Agent knows exactly which state it will be in; solution is a sequence
◼ Non-observable → problem with no sensors
◼ Agent may have no idea where it is; solution is a sequence
◼ Nondeterministic and/or partially observable → contingency
problem
◼ A future event that is possible but can not guaranty with certainty
◼ percepts provide new information about current state
◼ often interleave of search & execution
◼ Unknown state space → exploration problem
9
General step to represent the problems
◼ Define the state space that contains all the
possible configurations of the relevant
objects
◼ Specify one or more state within that space
as initial state.
◼ Specify one or more state that would be
acceptable as solutions to the problem. Goal
◼ Specify a set of rules that describe the
actions available.
10
Example: vacuum world
◼ Single-state, start in #5.
Solution?
◼
11
Example: vacuum world
◼ Single-state, start in #5.
Solution? [Right, Suck]
◼
◼ Sensorless, start in
{1,2,3,4,5,6,7,8} e.g.,
Right goes to {2,4,6,8}
Solution?
◼
12
Example: vacuum world
◼ Sensorless, start in
{1,2,3,4,5,6,7,8} e.g.,
Right goes to {2,4,6,8}
Solution?
[Right,Suck dust,Left,Suck dust]
◼ Possibility
◼ Nondeterministic: Suck may
dirty a clean carpet
◼ Partially observable: location, dirt at current location.
◼ Percept: [L, Clean], i.e., start in #5 or #7
Solution?
13
Example: vacuum world
◼ Sensorless, start in
{1,2,3,4,5,6,7,8} e.g.,
Right goes to {2,4,6,8}
Solution?
[Right,Suck dust,Left,Suck dust]
◼ Possibility
◼ Nondeterministic: Suck may
dirty a clean carpet
◼ Partially observable: location, dirt at current location.
◼ Percept: [L, Clean], i.e., start in #5 or #7
Solution? [Right, if dirt then Suck]
14
Single-state problem formulation
A problem is defined by four items:
1. initial state e.g., "at Arad"
2. actions or successor function S(x) = set of action–state pairs
◼ e.g., S(Arad) = {<Arad → Zerind, Zerind>, … }
3. goal test, can be
◼ explicit, e.g., x = "at Bucharest"
◼ implicit, e.g., Checkmate (x)
4. path cost (additive)
◼ e.g., sum of distances, number of actions executed, etc.
◼ c(x,a,y) is the step cost, assumed to be ≥ 0
◼ A solution is a sequence of actions leading from the initial state to a
goal state
◼
15
Selecting a state space
◼ Real world is absurdly 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 realizability, 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
16
Vacuum world state space graph
◼ states?
◼ actions?
◼ goal test?
◼ path cost?
17
Vacuum world state space graph
◼ states? integer dirt and robot location
◼ actions? Left, Right, Suck
◼ goal test? no dirt at all locations
◼ path cost? 1 per action
18
Example: The 8-puzzle
◼ states?
◼ actions?
◼ goal test?
◼ path cost?
19
Example: The 8-puzzle
◼ states? locations of tiles
◼ actions? move blank left, right, up, down
◼ goal test? = goal state (given)
◼ path cost? 1 per move
◼
20
Example: robotic assembly
◼ states?: real-valued coordinates of robot joint
angles, parts of the object to be assembled
◼ actions?: continuous motions of robot joints
◼ goal test?: complete assembly
◼ path cost?: time to execute
21
Tree search algorithms
◼ Basic idea:
◼ Offline, simulated exploration of state space by
generating successors of already-explored states
22
Tree search example
23
Tree search example
24
Tree search example
25
Implementation: general tree search
26
Implementation: states vs. nodes
◼ A state is a (representation of) a physical configuration
◼ A node is a data structure constituting part of a search tree
includes state, parent node, action, path cost g(x), depth
◼ The Expand function creates new nodes, filling in the
various fields and using the SuccessorFn of the problem
to create the corresponding states.
27
Search strategies (control)
◼ A search strategy is defined by picking the order of node
expansion
◼ Strategies are evaluated along the following dimensions:
◼ completeness: does it always find a solution if one exists?
◼ time complexity: number of nodes generated
◼ space complexity: maximum number of nodes in memory
◼ optimality: does it always find a least-cost solution?
◼
◼ Time and space complexity are measured in terms of
◼ b: maximum branching factor of the search tree
◼ d: depth of the least-cost solution
◼ m: maximum depth of the state space (may be ∞)
◼
28
Types of searching the state space
◼ Uninformed (blind) Search
◼ Depth first search
◼ Breadth first search
◼ DFS with iterative deepening
◼ Bidirectional search
◼ Informed(heuristic) Search
◼ Best first search
◼ A* algorithm, AO* algorithm (searches)
◼ Hill climbing search
29
Uninformed search strategies
◼ Uninformed search strategies use only the
information available in the problem
definition i.e. it has no additional information
◼ It can generate successors and distinguish a
goal state from non goal state.
◼ Informed search strategies, that know
whether one non goal state is more
promising than the another.
30
Breadth-first search
◼ Expand shallowest unexpanded node
◼ Implementation:
◼ fringe is a FIFO queue, i.e., new successors go
at end
◼
31
Breadth-first search
◼ Expand shallowest unexpanded node
◼
◼ Implementation:
◼ fringe is a FIFO queue, i.e., new successors go
at end
◼
32
Breadth-first search
◼ Expand shallowest unexpanded node
◼
◼ Implementation:
◼ fringe is a FIFO queue, i.e., new successors go
at end
◼
33
Breadth-first search
◼ Expand shallowest unexpanded node
◼
◼ Implementation:
◼ fringe is a FIFO queue, i.e., new successors go
at end
◼
34
Properties of breadth-first search
◼ Complete? Yes (if b is finite)
◼
◼ Time? 1+b+b2+b3+… +bd + b(bd-1) = O(bd+1)
◼
◼ Space? O(bd+1) (keeps every node in memory)
◼
◼ Optimal? Yes (if cost = 1 per step)
◼
◼ Space is the bigger problem (more than time)
◼ 35
Depth-first search
◼ Expand deepest unexpanded node
◼ Implementation:
◼ fringe = LIFO queue, i.e., put successors at front
36
Depth-first search
◼ Expand deepest unexpanded node
◼ Implementation:
◼ fringe = LIFO queue, i.e., put successors at front
◼
37
Depth-first search
◼ Expand deepest unexpanded node
◼ Implementation:
◼ fringe = LIFO queue, i.e., put successors at front
◼
38
Depth-first search
◼ Expand deepest unexpanded node
◼
◼ Implementation:
◼ fringe = LIFO queue, i.e., put successors at front
◼
39
Depth-first search
◼ Expand deepest unexpanded node
◼
◼ Implementation:
◼ fringe = LIFO queue, i.e., put successors at front
◼
40
Depth-first search
◼ Expand deepest unexpanded node
◼
◼ Implementation:
◼ fringe = LIFO queue, i.e., put successors at front
◼
41
Depth-first search
◼ Expand deepest unexpanded node
◼
◼ Implementation:
◼ fringe = LIFO queue, i.e., put successors at front
◼
42
Depth-first search
◼ Expand deepest unexpanded node
◼
◼ Implementation:
◼ fringe = LIFO queue, i.e., put successors at front
◼
43
Depth-first search
◼ Expand deepest unexpanded node
◼
◼ Implementation:
◼ fringe = LIFO queue, i.e., put successors at front
◼
44
Depth-first search
◼ Expand deepest unexpanded node
◼
◼ Implementation:
◼ fringe = LIFO queue, i.e., put successors at front
◼
45
Depth-first search
◼ Expand deepest unexpanded node
◼
◼ Implementation:
◼ fringe = LIFO queue, i.e., put successors at front
◼
46
Depth-first search
◼ Expand deepest unexpanded node
◼
◼ Implementation:
◼ fringe = LIFO queue, i.e., put successors at front
◼
47
Properties of depth-first search
◼ Complete? No: fails in infinite-depth spaces, spaces
with loops
◼ Modify to avoid repeated states along path
→ complete in finite spaces
◼ Time? O(bm) : terrible if m is much larger than d
◼ but if solutions are dense, may be much faster than
breadth-first
◼
◼ Space? O(bm), i.e., linear space!
◼ Optimal? No
48
Depth-limited search
= depth-first search with depth limit l,
i.e., nodes at depth l have no successors
◼ Recursive implementation:
49
Iterative deepening search
50
Iterative deepening search l =0
51
Iterative deepening search l =1
52
Iterative deepening search l =2
53
Iterative deepening search l =3
54
Iterative deepening search
◼ Number of nodes generated in a depth-limited search to
depth d with branching factor b:
NDLS = b0 + b1 + b2 + … + bd-2 + bd-1 + bd
◼ Number of nodes generated in an iterative deepening
search to depth d with branching factor b:
NIDS = (d+1)b0 + d b^1 + (d-1)b^2 + … + 3bd-2 +2bd-1 + 1bd
◼ For b = 10, d = 5,
◼
◼ NDLS = 1 + 10 + 100 + 1,000 + 10,000 + 100,000 = 111,111
◼ NIDS = 6 + 50 + 400 + 3,000 + 20,000 + 100,000 = 123,456
◼ Overhead = (123,456 - 111,111)/111,111 = 11%
55
Properties of iterative deepening search
◼ Complete? Yes
◼
◼ Time? (d+1)b0 + d b1 + (d-1)b2 + … + bd =
O(bd)
◼
◼ Space? O(bd)
◼
◼ Optimal? Yes, if step cost = 1
56
Summary of algorithms
57
Bidirectional Search
◼ Two simultaneous search
◼ Forward form initial state
◼ Backward from goal state
◼ Stopping when two searches meet in middle
