COMP3308/COMP3608, Lecture 2
ARTIFICIAL INTELLIGENCE
Problem Solving and Search. Uninformed Search: BFS, DFS, UCS and IDS Informed Search: Greedy Best-First
Reference: Russell and Norvig, ch. 3
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 2, 2021 1
Reminders
• Tutorials start this week
• All tutorials will be on Zoom live-streamed
• There are 2 on Tuesday and 14 on Wednesday
• Please attend your allocated tutorial
• 1 tutorial will be recorded and uploaded to Canvas (under “Recorded Lectures”)
• All students must submit their homework in Canvas by 4pm on Tuesday (no matter when your tutorial class is)
• Tutorial solutions will be available on Canvas on Wednesday at 6pm (after the last tutorial)
• Lecture slides are posted on Saturday morning at 9am
• They will not contain the answers to all questions and exercises that we
do during the lecture
• The complete lecture slides with the answers will be available on Monday at 12noon (after the lecture time)
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 2, 2021 2
• •
•
Problem-solving and search
Search strategies
• Uninformed (blind)
• Informed (heuristic)
Uninformed search strategies
• Breadth-first
• Uniform cost
• Depth-first
• Depth-limited
• Iterative-deepening
Informed search strategies
• Greedy best-first
• A* – next week
•
Irena Koprinska, irena.koprinska@sydney.edu.au
COMP3308/3608 AI, week 2, 2021 3
Outline
Problem Solving and Search
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 2, 2021 4
Solving Problems by Searching
• Many tasks can be formulated as search problems
• Task: to get from an initial problem state to a goal state
• Driving: starting address -> destination address
• Chess: initial board position -> checkmate position
• Reasoning: set of facts and rules + query -> answer
• Solution: a path from the initial state to the goal state
• Operators
• possible actions, possible moves in a game
• Cost (quality) of operators
• distance, time, money
• strength of board position in games
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 2, 2021 5
Example: Romania
• On holiday in Romania
• currently in Arad
• flight leaves tomorrow from Bucharest
• Step 1. Formulate goal: be in Bucharest
• Step 2. Formulate search problem:
• states: various cities
• operators: drive between cities, e.g. from Arad to Sibiu, from Arad to Zerind
• Step 3. Find solution (path):
• a sequence of cities from Arad to Bucharest, e.g. Arad, Sibiu,
Fagaras, Bucharest
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 2, 2021 6
Romania Example – Map
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 2, 2021 7
Romania
http://en.wikipedia.org/wiki/File:Location_Romania_EU_Europe.PNG
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 2, 2021 8
Search Problem Formulation
• A search problem is defined by 4 items
• 1) Initial state, e.g. Arad
• 2) Goal state (1 or more)
• Stated explicitly, e.g. Bucharest
• Stated implicitly with a goal test, e.g. checkmate state
• 3) Operators = actions
• A set of possible actions transforming 1 state to another , e.g. Arad-
>Zerind, Arad->Sibiu, etc.
• 4) Path cost function – assigns a numeric value to each path
• Reflectstheperformancemeasure
• E.g. time, path length in km, number of operators executed
• Solution – a path from the initial to a goal state
• Its quality is measured by the path cost
• Optimal solution is the one with the lowest path cost
• State space – all states reachable from the initial state by operators
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 2, 2021
9
Choosing States and Actions – Abstraction
• Real problems are too complex, to solve them we need to abstract them, i.e. to simplify them by removing the unnecessary details
• E.g. we ignore the weather, travel companion, scenery; they are irrelevant for the task of finding a path to Bucharest
• The actions need to be suitably specified, e.g. “turn the steering wheel to the left by 5 degrees” is not appropriate
• => the level of abstraction must be appropriate (valid and useful)
• (Abstract) state = set of real states
• (Abstract) action = complex combination of real actions
• (Abstract) solution = a real path that is solution in the real world
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 2, 2021
10
• States?
• Operators?
• Goal state?
• Path cost?
1 state = 1 board configuration of the tiles
Move blank left, right, up, down
Given
1 per move, i.e. path cost=length of path=number of steps
Example Problem 1: The 8-puzzle
a sliding block puzzle
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 2, 2021
11
Example Problem 2: The 8-queens
• Place 8 queens on a chessboard (8×8) so that no queen attacks each other
• Is this a solution?
• Goal state? 8 queens on board, none attacked
• Path cost? 0 (= only the goal state matters and not the number of
steps). Other options are also possible, e.g. 1 per move.
• States =? 1 state = 1 board configuration of the tiles
• Operators =? Put 1 queen on the board or move 1 queen
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 2, 2021 12
8-queens – Different Types of Problem Formulation
1. Incremental – start with an empty board, add 1 queen at a time
2. Complete-state – start with all 8 queens and move them around
Let’s take a closer look at 2 possible incremental formulations!
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 2, 2021 13
8-queens – Incremental Formulation 1
• States? Any arrangement of 0 to 8 queens
• Initial state? No queens on the board
• Operators? Add a queen to any square
• State space = 1.8 x 1014 states (= 64 x 63 x …x 57)
• Can you suggest a better formulation?
• Prohibit placing a queen in any square that is already
attacked!
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 2, 2021 14
8-queens – Incremental Formulation 2
• States? Any arrangement of 0 to 8 queens, 1 in each column, with no queen attacking another
• Initial state? No queens on the board
• Operators? Place a queen in the left-most empty column such
that it is not attacked by any other queen
• State space: 2057 states (has been proven)
• For 100-queens:
• formulation 1: 10400 states
• formulation 2: 1052 states (huge improvement but problem still not tractable)
• The problem formulation is very important!
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 2, 2021 15
Searching for Solutions
• How can we solve the 8-queens puzzle or the Romania example?
• By searching the state space
• We can generate a search tree starting from the initial state and applying the operators
• Or we can generate a search graph – in a graph the same state can be reached from multiple paths
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 2, 2021 16
•
Tree-Search algorithm – Pseudo Code
Basic idea: offline exploration of the state space by generating successors of the explored states (i.e. by expanding states)
start with the initial node
the initial node at the beginning
1. 2.
Choose a node for expansion based on the search strategy Check if it is a goal node
Yes-> return solution
No -> expand it by generating its children
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 2, 2021 17
Expanded and Fringe Lists
• We will keep two lists:
• Expanded – for nodes that have been expanded
• Fringe – for nodes that have been generated but not expanded yet.
• We will keep the fringe ordered (implemented as a priority queue) and always select for expansion the first node of the fringe
• For the figure:
• Expanded: Arad
• Fringe: Sibiu, Timisoara, Zerind
• All the other nodes have not been generated yet
• Note the notation in the figure for the different types of nodes
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 2, 2021 18
Tree Search Example
• Let’s put the children of the expanded node at the end of the fringe
Fringe: Arad Is Arad a goal node? No => expand it Expanded: none
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 2, 2021 19
Tree Search Example (2)
Fringe: Sibiu, Timisoara, Zerind Expanded: Arad
Is Sibiu a goal node? No => expand it
Irena Koprinska, irena.koprinska@sydney.edu.au
COMP3308/3608 AI, week 2, 2021 20
Tree Search Example (3)
Fringe: Timisoara, Zerind, Arad, Fagaras, Oradea, Riminicu Vilcea Expanded: Arad, Sibiu
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 2, 2021 21
Tree Search – More Detailed Pseudo Code
// nodes in fringe ordered based on their priority according to the search strategy //select node for expansion, then check if it is a goal
• We will keep the fringe ordered
Is the first node in the fringe a goal node? Yes =>stop and return solution
No => expand it:
– Move it to the expanded list
– Generate its children and put them in the
fringe in a order defined by the search strategy
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 2, 2021 22
(top of the fringe = most desirable child)
Nodes vs States
• A node is different than a state
• A node:
• represents a state
• is a data structure used in the search tree
• includes parent, children, and other relevant information e.g. depth and path cost g
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 2, 2021 23
Search Strategies
• A search strategy defines which node from the fringe is most promising and should be expanded next
• We will keep the nodes in the fringe ordered based on the search strategy and always expand the first one (i.e. the best one)
• Evaluation criteria
• Completeness – is it guaranteed to find a solution if one exists?
• Optimality – is it guaranteed to find an optimal (least cost path) solution?
• Time complexity – how long does it take to find the solution? (measured as number of generated nodes)
• Space complexity – What is the maximum number of nodes in memory?
• Time and space complexity are measured in terms of:
• b – max branching factor of the search tree (we can assume that it is finite)
• d – depth of the optimal (least cost) solution
• m – maximum depth of the state space (can be finite or not finite, i.e. )
• Two types of search methods: uniformed (blind) and informed (heuristic) Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 2, 2021 24
Uninformed (Blind) Search Strategies
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 2, 2021 25
Uninformed (Blind) Search Strategies
• Uninformed strategies:
• Do not use problem-specific heuristic knowledge
• Generate children in a systematic way, e.g. level by level, from left to right
• Know if a child node is a goal or non-goal node
• Do not know if one non-goal child is better (more promising) than another one. Exception: UCS, but this is not based on heuristic knowledge.
• In contrast, informed (heuristic) use heuristic knowledge to determine the most promising non-goal child
• 5 uninformed search strategies
• Breadth-first • Uniform-cost • Depth-first
• Depth-limited
• Iterative deepening
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 2, 2021 26
Breadth-First Search (BFS)
• Expands the shallowest unexpanded node
• Implementation: insert children at the end of the fringe
Fringe: A Expanded: none
Is the first node in the fringe a goal node? Yes => stop and return solution
No => expand it:
– Move it to the expanded list
– Generate its children and put them in the fringe in a order defined by the search strategy
Goal node
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 2, 2021 27
Breadth-First Search (BFS)
• Expands the shallowest unexpanded node
• Implementation: insert children at the end of the fringe
Fringe: B, C Expanded: A
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 2, 2021 28
Breadth-First Search (BFS)
• Expands the shallowest unexpanded node
• Implementation: insert children at the end of the fringe
Fringe: C, D, E Expanded: A, B
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 2, 2021
29
Breadth-First Search (BFS)
• Expands the shallowest unexpanded node
• Implementation: insert children at the end of the fringe
Fringe: D, E, F, G Expanded: A, B, C
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 2, 2021 30
Breadth-First Search (BFS)
• Expands shallowest unexpanded node
• Implementation: insert children at the end of the fringe
Fringe: E, F, G Expanded: A, B, C, D
Fringe: F, G
Expanded: A, B, C, D, E
Fringe: G
Expanded: A, B, C, D, E, F G is a goal node => stop
Order of expansion: ABCDEFG (the goal node is also included) Goal node found: G
Solution path found: ACG (requires tracing back)
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 2, 2021 31
BFS for Romania Example
• There will be loops (repeated states)
• Needs a repeated state checking mechanism
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 2, 2021 32
Properties of BFS
• Complete? Yes (if branching factor b is finite but we assume this) • Optimal?
• Optimal solution = least cost path
• It doesn’t consider the step cost + we need to know the step costs
• If all step costs are the same, e.g. =1, is BFS optimal? Yes
• If the step costs are different, is BFS optimal? No
The shallowest goal node is not necessarily the optimal one!
6 2
1 1
Suppose C and J were goal nodes and J is a better solution than C; BFS will find C – not optimal
Irena Koprinska, irena.koprinska@sydney.edu.au
COMP3308/3608 AI, week 2, 2021 33
• Complete? Yes
Properties of BFS (2)
• Optimal? Not optimal in general; Yes, if step cost is the same, e.g. =1
• Time? generated nodes = 1+b+b2+b3+b4 + … +bd = O(bd), exponential
• Space? O(bd) (keeps every node in memory)
• Both time and space are problems as they grow exponentially with
depth but space is the bigger problem!
Search problems with exponential complexity can NOT be solved by uninformed search except for small depth & small branching factor.
We may wait 13 days for the solution to an important problem but there is still no personal computer with 1 petabyte of memory!
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 2, 2021 34
Romania with Step Coast in km
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 2, 2021 35
•
Uniform Cost Search (UCS)
We saw that:
• BFS does not consider the step cost at all; it simply systematically expands the nodes level by level, from left to right
• BFS finds the shallowest goal node but this may not be always the optimal solution (least cost solution = shortest path)
UCS considers the step cost. It expands the least-cost unexpanded node – the node n with the lowest path cost g(n) from the initial state
Implementation: insert nodes in the fringe in order of increasing path cost from the root
• •
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 2, 2021 36
UCS for the Romania Example (1)
Fringe: Arad Expanded: none
Is Arad a goal state? No
-Move it to Expanded
-Generate its children and put them in Fringe in order
fringe
Irena Koprinska, irena.koprinska@sydney.edu.au
COMP3308/3608 AI, week 2, 2021 37
Arad
UCS for the Romania Example
Fringe: (Zerind,75), (Timisoara, 118), (Sibiu, 140) Expanded: Arad
75 Zerind
Arad
140 Sibiu
fringe
118 Timisoara
The fringe is ordered based on the path cost from the root
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 2, 2021
38
UCS for the Romania Example
Fringe: (Timisoara, 118), (Sibiu, 140), (Oradea,146), (Arad, 150) Expanded: Arad, (Zerind, 75)
75 Zerind
Arad
140 Sibiu
fringe
118 Timisoara
75
Arad Oradea
71
The fringe is ordered based on the path cost from the root
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 2, 2021
39
UCS for the Romania Example
Fringe: (Sibiu, 140), (Oradea,146), (Arad, 150), (Arad,228), (Lugoj, 229) Expanded: Arad, (Zerind, 75), (Timisoara, 118)
fringe
Zerind Sibiu Timisoara
75 71 110 111
Arad Oradea Arad Lugoj
The fringe is ordered based on the path cost from the root
Arad
75 118 140
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 2, 2021 40
UCS for the Romania Example
Fringe: (Oradea,146), (Arad, 150), (Riminicu Vilcea, 220), (Arad,228), (Lugoj, 229), (Fagaras, 239), (Oradea , 291) Expanded: Arad, (Zerind, 75), (Timisoara, 118), (Sibiu, 140)
75 Zerind
Arad
140 Sibiu
fringe
118 Timisoara
75 Arad
71 151 Arad Oradea
80 110 111 Fagaras Rimnicu Arad
99
Oradea
Vilcea
Lugoj
The fringe is ordered based on the path cost from the root
etc. – not finished
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 2, 2021 41
Properties of UCS
• Complete? Yes ( if step cost>0 )
• Optimal? Yes
• Time?
• Space? to characterize them in terms of b and d
Depend on path costs not depths => difficult
• Time? O(b 1+[C*/] ), typically > O(bd) -> because UCS may explore long
• Space? O(b 1+[C*/] )
• C* – cost of optimal solution
• – the smallest step cost
paths of small steps before exploring paths with large steps which might be more useful
Irena Koprinska, irena.koprinska@sydney.edu.au
COMP3308/3608 AI, week 2, 2021 42
•
UCS and BFS
When is UCS equivalent to BFS? What should be the step cost and the g(n) cost? Assume that among the nodes with the same priority the left most is expanded first. Reminder:
• g(n) is the cost from the root node to a given node
• step cost is the cost between 2 nodes
Answer – in all of these cases:
1. step cost is 1
2. step cost is the same (a constant) – generalization of case 1
3. g(n)=depth(n)
4. g(n) is the same at each level and increasing as the level increases, e.g. 5 for level 1, 7 for level 2, etc.
Draw a tree for each of these cases and run UCS and BFS!
•
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 2, 2021 43
Depth-First Search (DFS)
• Expands the deepest unexpanded node
• Implementation: insert children at the front of the fringe
Fringe: A Expanded: none
Goal node: M
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 2, 2021 44
Depth-First Search (DFS)
• Expands the deepest unexpanded node
• Implementation: insert successors at the front of the fringe
Fringe: B, C Expanded: A
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 2, 2021 45
Depth-First Search (DFS)
• Expands the deepest unexpanded node
• Implementation: insert successors at the front of the fringe
Fringe: D, E, C Expanded: A, B
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 2, 2021 46
Depth-First Search (DFS)
• Expands the deepest unexpanded node
• Implementation: insert successors at the front of the fringe
Fringe: H, I, E, C Expanded: A, B, D
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 2, 2021 47
Depth-First Search (DFS)
• Expands the deepest unexpanded node
• Implementation: insert successors at the front of the fringe
Fringe: I, E, C Expanded: A, B, D, H
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 2, 2021 48
Depth-First Search (DFS)
• Expands the deepest unexpanded node
• Implementation: insert successors at the front of the fringe
Fringe: E, C Expanded: A, B, D, H, I
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 2, 2021
49
Depth-First Search (DFS)
• Expands the deepest unexpanded node
• Implementation: insert successors at the front of the fringe
Fringe: J, K, C Expanded: A, B, D, H, I, E
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 2, 2021
50
Depth-First Search (DFS)
• Expands the deepest unexpanded node
• Implementation: insert successors at the front of the fringe
Fringe: K, C
Expanded: A, B, D, H, I, E, J
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 2, 2021
51
Depth-First Search (DFS)
• Expands the deepest unexpanded node
• Implementation: insert successors at the front of the fringe
Fringe: C
Expanded: A, B, D, H, I, E, J, K
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 2, 2021 52
Depth-First Search (DFS)
• Expands the deepest unexpanded node
• Implementation: insert successors at the front of the fringe
Fringe: F, G
Expanded: A, B, D, H, I, E, J, K, C
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 2, 2021 53
Depth-First Search (DFS)
• Expands the deepest unexpanded node
• Implementation: insert successors at the front of the fringe
Fringe: L, M, G
Expanded: A, B, D, H, I, E, J, K, C, F
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 2, 2021 54
Depth-First Search (DFS)
• Expands the deepest unexpanded node
• Implementation: insert successors at the front of the fringe
Fringe: M, G
Expanded: A, B, D, H, I, E, J, K, C, F, L
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 2, 2021 55
Depth-First Search (DFS)
• Expands the deepest unexpanded node
• Implementation: insert children at the front of the fringe
Fringe: M, G
Expanded: A, B, D, H, I, E, J, K, C, F, L
M is a goal node => stop
order of expansion: ABDHIEJKCFLM solution node found: M
solution path found: ACFM
B
D HIJ
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 2, 2021 56
E KL
DFS for Romania Example
• DFS can perform infinite cyclic explorations => needs a finite, non-cyclic search space or a repeated state checking mechanism
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 2, 2021 57
Properties of DFS
• Complete?
• No, fails in infinite-depth spaces (i.e. m = ) • Yes, in finite spaces (i.e. if m is finite)
• Optimal? No
• May find a solution longer than the optimal (even if step cost=1)
• Time? 1+b+b2+b3+b4 + … +bm = O(bm) similar to BFS
• higher than BFS as m>>d (m=max depth, d=least cost solution depth)
• Space? O(bm), linear; excellent; Why?
Can get stuck going down a very long (or even infinite) path e.g. suppose the left sub- tree was unbounded and did not contain a goal node – DFS would never terminate
Suppose J and C were goal nodes and C is a better solution than J; DFS will find J – not optimal
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 2, 2021 58
Space Complexity of DFS
• Space? O(bm), linear; excellent – why?
• Once a node has been expanded, it can be removed from memory as
soon as all its descendants have been fully explored
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 2, 2021 59
Depth-Limited Search
• Depth-limited search = DFS with depth limit l
• i.e. it imposes a cutoff on the maximum depth
• Properties – similar to DFS:
• Complete? Yes (as the search depth is always finite)
• Optimal? No
• Time? 1+b2+b3+b4 + … +bl = O(bl)
• Space? O(bl)
• Problem – how to select a good limit l? Based on domain knowledge.
• There are 20 cities on the map of Romania => if there is a solution it
must be of length 19 at most => l=19
• We can even see that any city can be reached from any other city in at
most 9 steps; this is called diameter of a state space => l=9
• However, for most problems the diameter of the state space is not
known in advance , i.e. before we have solved the problem
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 2, 2021 60
Iterative Deepening Search (IDS)
• Sidesteps the issue of choosing the best depth limit by trying all possible depth limits in turn (0, 1, 2, etc.) and applying DFS
• for depth=0 to do depth-limited search(depth):
• Tries to combine the benefits of DFS (low memory) and BFS (completeness if b is finite and optimality if step costs are the same) by repeated DFS searches with increased depth
• The nodes close to the root will be expanded multiple times but the number of these nodes is small – the majority of the nodes are close to the leaves, not the root => the overhead is small
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 2, 2021 61
IDS, l=0
cutoff limit l=0
A tree till level l=0; do DFS Goal found?
Yes -> stop
No -> increment l and repeat
Expanded: A
The tree we are searching – M is the goal node
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 2, 2021 62
IDS, l=1
cutoff limit l=1
A tree till level l=1; do DFS Goal found?
Yes -> stop
No -> increment l and repeat
Expanded: A, B, C
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 2, 2021 63
IDS, l=2
Expanded: A, B, D, E, C, F, G
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 2, 2021 64
IDS, l=3
Expanded: A, B, D, H, I, E, J, K, C, F, L, M (goal)
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 2, 2021 65
IDS – Overhead of Multiple Expansion
• May seem wasteful as many nodes are expanded multiple times
• But for most problems the overhead of this multiple expansion is
small!
• BFS: # expansions: 1+b+b2+…+bd, i.e. 111 111 for b=10, d=5
• IDS: #expansions: (d+1)1+(d)b+(d-1)b2+…+3bd-2+2bd-1+1bd , i.e. 123 456 for b=10, d=5 => only 11% more
• IDS is the preferred method when there is a large search space and the depth of the solution is unknown
Expanded:
A
A, B, C
A, B, D, E, C, F, G
A, B, D, H, I, E, J, K, C, F, L, M (goal)
B
D HIJ
E KL
Irena Koprinska, irena.koprinska@sydney.edu.au
COMP3308/3608 AI, week 2, 2021
66
Properties of IDS
• Combines the benefits of DFS and BFS
• Complete? As BFS:
b – branching factor
d – depth of least cost solution m – max depth
Yes [DFS: yes, if m is finite; no otherwise]*
• Optimal? As BFS:
No in general; Yes if step cost=1
[DFS: not optimal, even if step cost=1] *
• Time? As BFS:
(d+1)b0+db1+(d-1)b2+ … +bd = O(bd) [DFS: O(bm)] *
• Space? As DFS: O(bd), linear
• Where are the improvements of IDS in comparison to DFS?
• in completeness, optimality and time (shown with *)
• Can be modified to explore uniform-cost tree
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 2, 2021 67
Summary Example
• G is the goal. Give the list of expanded nodes and the solution path.
S
1
5
ABC
3
• DFS?
• SADEG, solution found: SAG (non optimal)
• BFS?
• SABCDEG, solution found: SAG (non-optimal solution; will find optimal solution only if step cost=1)
• UCS?
• Resolving ties: Among nodes with the same priority, expand the node that was added first to the fringe
8
• SADBCEG, solution found: SBG (optimal)
Among nodes with the same priority (E and C, g=8), the first added to the fringe (C) was chosen to be expanded first
7943
• IDS (l=2)
• S SABC SADEG, solution found: SAG (non- optimal solution; will find optimal solution only if step cost=1)
DEG
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 2, 2021 68
Real-World Path Finding Problems
• Planning trips from A to B – Google maps, planning public transport trips
• Example – web sites for planning air travel:
• Initial and goal states: specified by the user
• Actions: take any flight from the initial location, leaving after the current time with enough time for within-airport transfer
• Path cost: monetary cost, flight time, waiting time, time of the day (too early/too late), frequent-flyer millage awards, customs and immigration procedures
• VLSI layout – position millions of components and connections on a very small chip (to minimize area and circuits delays)
• Assembling objects by a robot – find the correct order for the parts; wrong order will require undoing some of the work already done
• Protein design – find a sequence of amino acids that will fold into a 3- dimensional protein with useful properties (i.e. curing a disease)
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 2, 2021 69
Informed (Heuristic) Search Strategies
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 2, 2021 70
Informed vs Uninformed Search
• A search strategy defines the order of node expansion
• Uninformed search strategies do not use problem specific knowledge beyond the definition of the problem, i.e. they do not use heuristic knowledge. They:
• expand nodes systematically, e.g. BFS: level by level, from left to right
• know if a given node is a goal or non-goal node
• cannot compare 2 non-goal nodes – they do not know if one non-goal node is better than another one based on heuristic knowledge
• UCS does this but it is not based on heuristic knowledge but path cost so far, so it is classified as uninformed
• are typically inefficient in finding the solution (time and space)
• Informed search strategies use problem-specific heuristic knowledge
to select the order of node expansion. They:
• can compare non-goal nodes – they know if one non-goal node is better than another one
• are typically more efficient
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 2, 2021 71
Best-first Search
• How can informed strategies compare non-goal nodes?
• By using domain specific knowledge to devise an evaluation function
which estimates how good each node is
• The evaluation function assigns a value to each node
• At each step, the best node is expanded (the one with the best value)
• This is called best-first search
• Note that we don’t really know which is the best node as we use an estimate based on the evaluation function. So best-first search expands the node that appears to be the best.
• Fringe: insert children in decreasing order of desirability
• We will study 2 best-first search algorithms: greedy and A*
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 2, 2021 72
Greedy Search
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 2, 2021 73
Romania with Step Coast and Straight-line Distance to Bucharest
Problem-specific knowledge
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 2, 2021 74
• • • •
• •
Greedy Search (GS)
It uses the so called h value as an evaluation function (h from heuristic)
The h(n) for a node n is the estimated cost from n to a goal node
E.g. for the Romania example we can use h(n)=SLD(n, Bucharest) = straight-line distance from n to Bucharest
Note that the h value of a goal node is 0, i.e. h(goal)=0
GS expands the node with the smallest h, i.e. • The note that appears to be closest to a goal
Thus: GS minimizes h, the estimated cost to a goal
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 2, 2021 75
Greedy Search for Romania Example
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 2, 2021 76
Greedy Search for Romania Example
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 2, 2021 77
Greedy Search for Romania Example
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 2, 2021 78
Greedy Search for Romania Example
Solution path: Arad-Sibiu-Fagaras-Bucharest, cost=450 Optimal =?
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 2, 2021 79
Greedy Search for Romania Example
found=450
shorter: 418
Solution path: Arad-Sibiu-Fagaras-Bucharest, cost=450 Optimal =?
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 2, 2021 80
Greedy Search – Another Example
• Given:
• Goal nodes: C, I, E and K
• Step path cost: along the links
• h value of each node: in () • RunGS
• List of expanded nodes =?
• Solution path =? Cost of the solution path=?
S
22
A (3) B
837
563
(4)
3
(0)
CD(5) EFG
(0)
(2)
(2)
4
(4 )
3
HIJK
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 2, 2021 81
( 0)
( 3)
(0)
• Fringe: S
• Expanded: nill
Solution
S
22
A (3) B
837
563
(0)
CD(5) EFG
(2)
(0)
(2)
4
(4)
3
(4 )
3
HIJK
( 0)
( 3)
(0)
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 2, 2021 82
• Fringe: (A,3), (B,4)
• Expanded: S
Solution
S
22
A (3) B
837
563
(4)
3
(0)
CD(5) EFG
(0)
(2)
(2)
4
(4 )
3
HIJK
( 0)
( 3)
(0)
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 2, 2021 83
Solution
• Fringe: (C,0), (B,4), (D, 5) //C and D are added and the fringe is ordered
• Expanded: S, (A,3)
S
22
A (3) B
837
563
(4)
3
(0)
CD(5) EFG
(0)
(2)
(2)
4
(4 )
3
HIJK
( 0)
( 3)
(0)
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 2, 2021 84
Solution
• C is selected for expanding; is it a goal node? Yes ->stop
• Expanded: S, A, C //note that the goal node is also considered to be
// expanded and is included in the list of expanded
• Solution path: SAC, path cost: 2+8=10
S
22
A (3) B
837
563
(4)
3
(0)
CD(5) EFG
(0)
(2)
(2)
4
(4 )
3
HIJK
( 0)
( 3)
(0)
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 2, 2021 85
Solution
• Is SAC the optimal solution (i.e. shortest path to a goal)?
S
22
A (3) B
837
563
(4)
3
(0)
CD(5) EFG
(0)
(2)
(2)
4
(4 )
3
HIJK
( 0)
( 3)
(0)
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 2, 2021 86
Properties of Greedy Search
• Complete? As DFS
• Yes, in finite space (if m is finite)
• No – fails in infinite spaces (and can get stuck in loops, e.g. Iasi->Neamt- >Iasi->Neamt)
• Optimal? No (e.g. Arad->Sibiu->R.Vincea->Pitesti->Buharest is shorter)
• Time? O(bm), but a good heuristic can give dramatic improvement
• Space? O(bm) , keeps every node in memory
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 2, 2021 87
Question
• g(n) = cost so far
• h(n) = estimated cost to the goal
• Greedy search uses h(n)
Suppose that we run a greedy search algorithm with h(n) = g(n). This greedy search will be equivalent to what kind of uninformed search?
In other words, which algorithm uses g(n)? 22
UCS
S
A (3) B
(4)
3
(0)
CD(5) EFG
837
4
563
(0)
(2)
(2)
(4 )
3
Irena Koprinska, irena.koprinska@sydney.edu.au
COMP3308/3608 AI, week 2, 2021
88
HIJK
( 0)
( 3)
(0)