COMM7370
AI Theories and Applications
Lecture 3
Advanced Uninformed Search
Informed Search
Heuristics
Dr. Paolo Mengoni
[email protected]
Visiting Scholar @HKBU School of Communication
Agenda
▪Search strategies
▪Tree Search recap
▪Advanced Uninformed Search
▪Informed Search
▪Greedy Best First
▪A*
▪Heuristics
COMM7370 AI Theories and Applications
Tree Search
COMM7370 AI Theories and Applications
Tree-based Search
▪State: a possible configuration for the problem
▪State space: a set of the possible configurations
▪Basic idea:
▪Exploration of state space by generating successors of
already-explored states (i.e. expanding states).
▪Use a tree-like representation
▪Every state is evaluated: is it a goal state?
▪Example 8 puzzle game
▪State configuration to tree node
COMM7370 AI Theories and Applications
State Spaces versus Search Trees
▪State Space
▪Set of valid states for a problem
▪ Linked by operators
▪e.g., 20 valid states (cities) in the Romanian travel problem
▪Search Tree
▪Root node = initial state
▪Child nodes = states that can be visited from parent
▪Note that the depth of the tree can be infinite
▪ E.g., via repeated states
▪Partial search tree
▪ Portion of tree that has been expanded so far
▪ Fringe
▪ Leaves of partial search tree, candidates for expansion
▪Search trees = data structure to search state-space
COMM7370 AI Theories and Applications
Search Tree for the 8 puzzle problem
COMM7370 AI Theories and Applications
Advanced Uninformed
Search
COMM7370 AI Theories and Applications
Depth-First Search (DFS)
▪Expand deepest unexpanded node
▪Fringe
▪ last-in-first-out (LIFO) queue
▪ E.g. the elevator with only one door
▪new successors go at beginning of the queue
▪Repeated nodes?
▪Simple strategy:
▪To avoid loops do not add a state as a leaf if that state is
on the path from the root to the current node
COMM7370 AI Theories and Applications
COMM7370 AI Theories and Applications
Depth-limited search
▪To overcome the problem of DFS search, set a depth limit
and perform tree search
▪DLS = Depth Limited Search
▪ Set limit l
▪ Use DFS
▪When the limit l is reached the nodes have no successors
▪ IDS = Iterative Deepening Search
▪ Perform depth limited search
▪ Increase the depth limit until the solution is found
COMM7370 AI Theories and Applications
Iterative deepening search l =0
COMM7370 AI Theories and Applications
Iterative deepening search l =1
COMM7370 AI Theories and Applications
Iterative deepening search l =2
COMM7370 AI Theories and Applications
Iterative deepening search l =3
COMM7370 AI Theories and Applications
Iterative deepening search
▪Number of nodes generated in a depth-limited search to
depth d with branching factor b:
NDLS = b
0 + 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)b
0 + 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%
COMM7370 AI Theories and Applications
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
Informed search strategies recap
COMM7370 AI Theories and Applications
▪Comparison between DFS and BFS
▪DFS use less space, in average may be faster
▪BFS is complete and optimal
Measure DFS BFS IDS
Completeness No Yes Yes
Time Complexity bm bm bd
Space Complexity b x m bm b x d
Optimality No Yes Yes
Informed search
COMM7370 AI Theories and Applications
Informed Search
▪Motivations: Limitations of uninformed search
methods
▪Too many nodes to expand
▪Informed (or heuristic) search uses problem-
specific heuristics to improve efficiency
▪This leads to different strategies
▪Best-first
▪A*
▪Can provide significant speed-ups in practice
▪e.g., on 8-puzzle
COMM7370 AI Theories and Applications
Best-first search
▪Idea: use an evaluation function (also called
heuristic ℎ ) for each node estimate of "desirability“
▪Expand most desirable unexpanded node
▪Implementation:
▪Order the nodes in fringe by their heuristics value
▪Most desirable nodes have higher priority
▪Expands the node that appears to be closest to goal
▪ Not always true
▪Special cases:
▪greedy best-first search
▪A* search
▪Note
▪Evaluation function is an estimate of node quality
▪More on heuristics later
COMM7370 AI Theories and Applications
Example heuristic functions for 8-puzzle
▪8-puzzle
▪A good heuristic function can reduce the search process
▪Commonly used heuristics
▪Number of misplaced tiles
▪ Example: ℎ = 8
COMM7370 AI Theories and Applications
Example Romania with step costs in km
▪Map navigation
▪Commonly used heuristics
▪Straight line distance to destination
▪ Example: ℎ = 366
COMM7370 AI Theories and Applications
Greedy best-first search example
COMM7370 AI Theories and Applications
Greedy best-first search example
COMM7370 AI Theories and Applications
Greedy best-first search example
COMM7370 AI Theories and Applications
Greedy best-first search example
COMM7370 AI Theories and Applications
Optimal Path
COMM7370 AI Theories and Applications
Optimal vs Greedy BestFirst
COMM7370 AI Theories and Applications
h(Fagaras)=176
h(RimnicuVilcea)=193
H
e
Properties of greedy best-first search
▪Complete? No
▪can get stuck in loops
▪e.g., Iasi → Neamt → Iasi → Neamt → …
▪Time? O(bm)
▪Worst case
▪A good heuristic can give dramatic improvement
▪Space? O(bm)
▪Keeps all nodes in memory
▪Optimal? No
COMM7370 AI Theories and Applications
A* Search
▪Expand node based on estimate of total path cost
through node
▪Idea: avoid expanding paths that are already
expensive
▪Evaluation function = + ℎ considers
▪cost so far
▪estimated cost to goal ℎ
▪Efficiency of search will depend on quality of
heuristic
COMM7370 AI Theories and Applications
A* search example
COMM7370 AI Theories and Applications
A* search example
COMM7370 AI Theories and Applications
A* search example
COMM7370 AI Theories and Applications
A* search example
COMM7370 AI Theories and Applications
A* search example
COMM7370 AI Theories and Applications
A* search example
COMM7370 AI Theories and Applications
Heuristics
COMM7370 AI Theories and Applications
Admissible heuristics
▪A heuristic h(n) is admissible if for every node n,
h(n) ≤ h*(n)
▪where h*(n) is the true cost to reach the goal state from n
▪An admissible heuristic never overestimates the
cost to reach the goal, i.e. it is optimistic
▪E.g.: in the map navigation problem, the heuristic
straight-line distance never overestimates the actual
road distance)
▪Theorem: If h(n) is admissible, A* is optimal
COMM7370 AI Theories and Applications
Optimality of A*
▪A* expands nodes in order of increasing f value
▪Gradually adds "f-contours" of nodes
▪Contour i has all nodes with f=fi, where fi < fi+1
COMM7370 AI Theories and Applications
Properties of A*
▪Complete?
▪Yes (unless there are infinitely many nodes with f ≤ f(G) )
▪Time?
▪Exponential
▪Space?
▪Keeps all nodes in memory
▪Optimal?
▪Yes
COMM7370 AI Theories and Applications
Admissible heuristics
▪E.g., for the 8-puzzle:
▪h1(n) = number of misplaced tiles
▪h2(n) = total Manhattan distance
▪ i.e. n. of squares from desired location of each tile
▪h1(S) = ?
▪h2(S) = ?
COMM7370 AI Theories and Applications
Admissible heuristics
▪E.g., for the 8-puzzle:
▪h1(n) = number of misplaced tiles
▪h2(n) = total Manhattan distance
▪ i.e. n. of squares from desired location of each tile
▪h1(S) = 8
▪h2(S) = 3+1+2+2+2+3+3+2 = 18
COMM7370 AI Theories and Applications
Dominance
▪ If h2(n) ≥ h1(n) for all n (both admissible)
▪ then h2 dominates h1
▪ i.e. h2 is better for search
▪Typical search costs (average number of nodes expanded):
▪d=12 IDS = 3,644,035 nodes
A*(h1) = 227 nodes
A*(h2) = 73 nodes
▪d=24 IDS = too many nodes
A*(h1) = 39,135 nodes
A*(h2) = 1,641 nodes
▪ IDS = Iterative Deepening Search
COMM7370 AI Theories and Applications
Relaxed problems
▪A problem with fewer restrictions on the actions is
called a relaxed problem
▪The cost of an optimal solution to a relaxed
problem is an admissible heuristic for the original
problem
▪If the rules of the 8-puzzle are relaxed so that a tile
can move anywhere, then h1(n) gives the shortest
solution
▪If the rules are relaxed so that a tile can move to
any adjacent square, then h2(n) gives the shortest
solution
COMM7370 AI Theories and Applications