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
Copyright By PowCoder代写 加微信 powcoder
, COMP3308/3608 AI, week 2, 2022 1
• Tutorials start this week
• 2 modes: face-to-face and Zoom – check your timetable
• There are multiple tutorials at the same time
• Please attend your allocated tutorial – see “activity code”
• 1 tutorial will be recorded and uploaded to Canvas (under “Recorded Lectures”)
• Weekly homeworks – 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 1pm (after the lecture time)
, COMP3308/3608 AI, week 2, 2022 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
COMP3308/3608 AI, week 2, 2022 3
Problem Solving and Search
, COMP3308/3608 AI, week 2, 2022 4
Solving Problems by Searching
• Many tasks can be formulated as search problems
• Task: to get from an initial 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
, COMP3308/3608 AI, week 2, 2022 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
, COMP3308/3608 AI, week 2, 2022 6
Romania Example – Map
• A simplified road map of Romania with road distances between cities in km
, COMP3308/3608 AI, week 2, 2022 7
http://en.wikipedia.org/wiki/File:Location_Romania_EU_Europe.PNG
, COMP3308/3608 AI, week 2, 2022 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
• Asetofpossibleactionstransformingonestatetoanother,e.g.
Arad->Zerind, Arad->Sibiu, etc.
• 4) Path cost function – assigns a numeric value to each path
• Reflectstheperformancemeasure
• E.g.time,pathlengthinkm,numberofoperatorsexecuted
• 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
, COMP3308/3608 AI, week 2, 2022
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 to 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
, COMP3308/3608 AI, week 2, 2022
• Operators?
• Goal state?
• Path cost?
1 state = 1 board configuration of the tiles
Move blank left, right, up, down
1 per move, i.e. path cost=length of path=number of steps
Example Problem 1: The 8-puzzle
a sliding block puzzle
, COMP3308/3608 AI, week 2, 2022
Example Problem 2: The 8-queens
• Place 8 queens on a chessboard (8×8) so that no queen attacks another queen
• Is this a solution?
•A queen attacks any piece in the same
row, column or diagonal
• 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
• Operators =? Put 1 queen on the board or move 1 queen
, COMP3308/3608 AI, week 2, 2022 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!
, COMP3308/3608 AI, week 2, 2022 13
8-queens – Incremental Formulation 1
• States? Any arrangement of 0 to 8 queens (1 state = 1 board configuration)
• 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!
, COMP3308/3608 AI, week 2, 2022 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!
, COMP3308/3608 AI, week 2, 2022 15
Searching for Solutions
• How can we solve the 8-queens puzzle or the Romania example?
• By searching the state space
• We consider algorithms that superimpose a search tree over the state space graph
• We can generate a search tree starting from the initial state and applying the operators
• Nodes correspond to states, edges to actions
• Root node of the tree corresponds to the initial state
, COMP3308/3608 AI, week 2, 2022 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
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
, COMP3308/3608 AI, week 2, 2022 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
, COMP3308/3608 AI, week 2, 2022 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
, COMP3308/3608 AI, week 2, 2022 19
Tree Search Example (2)
Fringe: Sibiu, Timisoara, Zerind Expanded: Arad
Is Sibiu a goal node? No => expand it
COMP3308/3608 AI, week 2, 2022 20
Tree Search Example (3)
Fringe: Timisoara, Zerind, Arad, Fagaras, Oradea, Expanded: Arad, Sibiu
, COMP3308/3608 AI, week 2, 2022 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
, COMP3308/3608 AI, week 2, 2022 22
(top of the fringe = most desirable child)
Nodes vs States
• A node is different than a state
• 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
, COMP3308/3608 AI, week 2, 2022 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) , COMP3308/3608 AI, week 2, 2022 24
Uninformed (Blind) Search Strategies
, COMP3308/3608 AI, week 2, 2022 25
Uninformed (Blind) Search Strategies
• Uninformed strategies:
• Do not use problem-specific heuristic knowledge to determine the
most promising node
• The heuristic knowledge estimates how far the goal is from the current node
• Generate the child nodes in a systematic way, e.g. level by level, from left to right
• Know only if a child node is a goal or non-goal
• In contrast, informed (heuristic) strategies 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
, COMP3308/3608 AI, week 2, 2022 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
, COMP3308/3608 AI, week 2, 2022 27
Breadth-First Search (BFS)
• Expands the shallowest unexpanded node
• Implementation: insert children at the end of the fringe
Fringe: B, C Expanded: A
, COMP3308/3608 AI, week 2, 2022 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
, COMP3308/3608 AI, week 2, 2022
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
, COMP3308/3608 AI, week 2, 2022 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
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)
, COMP3308/3608 AI, week 2, 2022 31
BFS for Romania Example
• There will be loops (repeated states)
• Needs a repeated state checking mechanism
, COMP3308/3608 AI, week 2, 2022 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!
Suppose C and J were goal nodes and J is a better solution than C; BFS will find C – not optimal
COMP3308/3608 AI, week 2, 2022 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!
, COMP3308/3608 AI, week 2, 2022 34
Did we Consider the Step Cost?
, COMP3308/3608 AI, week 2, 2022 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 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
, COMP3308/3608 AI, week 2, 2022 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
COMP3308/3608 AI, week 2, 2022 37
UCS for the Romania Example
Fringe: (Zerind, 75), (Timisoara, 118), (Sibiu, 140) Expanded: Arad
118 Timisoara
The fringe is ordered based on the path cost from the root
, COMP3308/3608 AI, week 2, 2022
UCS for the Romania Example
Fringe: (Timisoara, 118), (Sibiu, 140), (Oradea, 146), (Arad, 150) Expanded: Arad, (Zerind, 75)
118 Timisoara
The fringe is ordered based on the path cost from the root
, COMP3308/3608 AI, week 2, 2022
UCS for the Romania Example
Fringe: (Sibiu, 140), (Oradea, 146), (Arad, 150), (Arad, 228), (Lugoj, 229) Expanded: Arad, (Zerind, 75), (Timisoara, 118)
75 71 110 111
The fringe is ordered based on the path cost from the root
75 118 140
, COMP3308/3608 AI, week 2, 2022 40
UCS for the Romania Example
Fringe: (Oradea, 146), (Arad, 150), ( , 220), (Arad, 228), (Lugoj, 229), (Fagaras, 239), (Oradea , 291) Expanded: Arad, (Zerind, 75), (Timisoara, 118), (Sibiu, 140)
118 Timisoara
80 110 111 Arad
The fringe is ordered based on the path cost from the root
etc. – not finished
, COMP3308/3608 AI, week 2, 2022 41
Properties of UCS
• Complete? Yes ( if step cost>0 and we assume this )
• Optimal? Yes
• 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
COMP3308/3608 AI, week 2, 2022 42
UCS and BFS
• When is UCS equivalent to BFS? What should be the step cost and the g(n) cost?
• equivalent = will find the same solution
• Ties: 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!
, COMP3308/3608 AI, week 2, 2022 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
, COMP3308/3608 AI, week 2, 2022 44
Depth-First Search (DFS)
• Expands the deepest unexpanded node
• Implementation: insert successors at the front of the fringe
Fringe: B, C Expanded: A
, COMP3308/3608 AI, week 2, 2022 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
, COMP3308/3608 AI, week 2, 2022 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
, COMP3308/3608 AI, week 2, 2022 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
, COMP3308/3608 AI, week 2, 2022 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
, COMP3308/3608 AI, week 2, 2022
Depth-First Search (DFS)
• Expands the deepest unexpanded node
• Implementation: insert successors at the front of the fringe
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com