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 cscodehelp代写 加微信 cscodehelp

, 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代考 加微信: cscodehelp QQ: 2235208643 Email: kyit630461@163.com