CS B551: ELEMENTS OF ARTIFICIAL INTELLIGENCE 1 Instructor: Kris Hauser http://cs.indiana.edu/~hauserk AGENDA Searching, data structures, and algorithms Breadth-first search Depth-first search Uniform-cost search 2 DEFINING A SEARCH PROBLEM S State space S

Successor function: x S SUCC(x) 2S Initial state s0 Goal test: xS GOAL?(x) =T or F Arc cost 3 STATE GRAPH Each state is represented by a distinct node An arc (or edge) connects a node s to a node s if s SUCC(s)

The state graph may contain more than one connected component 4 SOLUTION TO THE SEARCH PROBLEM A solution is a path connecting the

initial node to a goal node (any one) The cost of a path is the sum of the arc costs along this path An optimal solution is a solution path of minimum cost There might be no solution ! G I 5 SEARCH GRAPH != STATE GRAPH 8

2 3 4 7 5 1 6 8 2 7 3

4 5 1 states are are allowed allowed to to be be revisited, revisited, IfIf states the search search tree tree may may be be infinite infinite even even

the when the the state state space space is is finite finite when 6 8 2 8 2 8 3

4 7 3 4 7 3 5 1 6 5

1 6 5 4 1 2 8 2 7 3 4

6 5 1 7 6 6 SEARCH GRAPH NODE != STATE 8 2 3 4 7

5 1 6 STATE PARENT-NODE BOOKKEEPING CHILDREN ... Action Right Depth

5 PathCost Expanded 5 yes Depth of a node N = length of path from root to N (depth of the root = 0) 7 FRINGE OF SEARCH TREE The fringe is the set of all search nodes that havent been expanded yet

8 2 3 4 7 5 1 6 8 2 7 3 4 5 1 6 8 2 3 4 7 5 1 6 8 2 3 4 7 5 1 6 8 2 7 3 4 5 1 6 8 2

3 4 7 5 1 6 SEARCH STRATEGY The fringe is the set of all search nodes that havent been expanded yet The fringe is implemented as a priority queue FRINGE INSERT(node,FRINGE) REMOVE(FRINGE) The ordering of the nodes in FRINGE defines the search strategy 9 SEARCH ALGORITHM #1 SEARCH#1

1. If GOAL?(initial-state) then return initialstate 2. INSERT(initial-node,FRINGE) 3. Repeat: 4. If empty(FRINGE) then return failure Expansion of N 5. N REMOVE(FRINGE) 6. s STATE(N) 7. For every state s in SUCCESSORS(s) 8. Create a new node N as a child of N 9. If GOAL?(s) then return path or goal state 10 BLIND SEARCH STRATEGIES 11

BLIND STRATEGIES Breadth-first Bidirectional Depth-first Arc cost = 1 Depth-limited Iterative deepening Uniform-Cost

(variant of breadth-first) Arc cost = c(action) 0 12 BREADTH-FIRST STRATEGY New nodes are inserted at the end of FRINGE 1 2 4 FRINGE = (1) 3 5 6

7 13 BREADTH-FIRST STRATEGY New nodes are inserted at the end of FRINGE 1 2 4 FRINGE = (2, 3) 3 5 6

7 14 BREADTH-FIRST STRATEGY New nodes are inserted at the end of FRINGE 1 2 4 FRINGE = (3, 4, 5) 3 5 6 7

15 BREADTH-FIRST STRATEGY New nodes are inserted at the end of FRINGE 1 2 4 FRINGE = (4, 5, 6, 7) 3 5 6 7

16 PERFORMANCE MEASURES Completeness A search algorithm is complete if it finds a solution whenever one exists [What about the case when no solution exists?] Optimality A search algorithm is optimal if it returns a minimum-cost path whenever a solution exists Complexity It measures the time and amount of memory required by the algorithm 17 IMPORTANT PARAMETERS

Maximum number of successors of any state branching factor b of the search tree Minimal length ( cost) of a path between the initial and a goal state depth d of the shallowest goal node in the search tree 18 EVALUATION b: branching factor d: depth of shallowest goal node Breadth-first search is: Complete?

Not complete? Optimal? Not optimal? 19 EVALUATION b: branching factor d: depth of shallowest goal node Breadth-first search is: Complete Optimal if step cost is 1 Number of nodes generated: ??? 20

EVALUATION b: branching factor d: depth of shallowest goal node Breadth-first search is: Complete Optimal if step cost is 1 Number of nodes generated: 1 + b + b2 + + bd = ??? 21 EVALUATION b: branching factor d: depth of shallowest goal node Breadth-first search is:

Complete Optimal if step cost is 1 Number of nodes generated: 1 + b + b2 + + bd = (bd+1-1)/(b-1) = O(bd) Time and space complexity is O(bd) 22 TIME AND MEMORY REQUIREMENTS d 2 4 6 8

10 12 14 # Nodes 111 11,111 ~106 ~108 ~1010 ~1012 ~1014 Time .01 msec 1 msec 1 sec 100 sec 2.8 hours 11.6 days 3.2 years

Memory 11 Kbytes 1 Mbyte 100 Mb 10 Gbytes 1 Tbyte 100 Tbytes 10,000 Tbytes Assumptions: b = 10; 1,000,000 nodes/sec; 100bytes/node 23 TIME AND MEMORY REQUIREMENTS d 2 4 6 8 10 12

14 # Nodes 111 11,111 ~106 ~108 ~1010 ~1012 ~1014 Time .01 msec 1 msec 1 sec 100 sec 2.8 hours 11.6 days 3.2 years Memory

11 Kbytes 1 Mbyte 100 Mb 10 Gbytes 1 Tbyte 100 Tbytes 10,000 Tbytes Assumptions: b = 10; 1,000,000 nodes/sec; 100bytes/node 24 REMARK If a problem has no solution, breadth-first may run forever (if the state space is infinite or states can be revisited arbitrary many times) 1

2 3 4 5 6 7 8 9 10 11 12 13 14 15 ?

1 2 3 4 5 6 7 8 9 10 11 12

13 15 14 25 BIDIRECTIONAL STRATEGY 2 fringe queues: FRINGE1 and FRINGE2 s Time and space complexity is O(bd/2) O(bd) if both trees have the same branching factor b Question: What happens if the branching factor is different in each direction? 26 DEPTH-FIRST STRATEGY New nodes are inserted at the front of FRINGE 1

2 4 FRINGE = (1) 3 5 27 DEPTH-FIRST STRATEGY New nodes are inserted at the front of FRINGE 1 2 4 FRINGE = (2, 3)

3 5 28 DEPTH-FIRST STRATEGY New nodes are inserted at the front of FRINGE 1 2 4 FRINGE = (4, 5, 3) 3 5

29 DEPTH-FIRST STRATEGY New nodes are inserted at the front of FRINGE 1 2 4 3 5 30 DEPTH-FIRST STRATEGY New nodes are inserted at the front of

FRINGE 1 2 4 3 5 31 DEPTH-FIRST STRATEGY New nodes are inserted at the front of FRINGE 1 2 4 3 5

32 DEPTH-FIRST STRATEGY New nodes are inserted at the front of FRINGE 1 2 4 3 5 33 DEPTH-FIRST STRATEGY New nodes are inserted at the front of

FRINGE 1 2 4 3 5 34 DEPTH-FIRST STRATEGY New nodes are inserted at the front of FRINGE 1 2 4 3 5

35 DEPTH-FIRST STRATEGY New nodes are inserted at the front of FRINGE 1 2 4 3 5 36 DEPTH-FIRST STRATEGY New nodes are inserted at the front of

FRINGE 1 2 4 3 5 37 EVALUATION b: branching factor d: depth of shallowest goal node m: maximal depth of a leaf node Depth-first search is: Complete? Optimal? 38

EVALUATION b: branching factor d: depth of shallowest goal node m: maximal depth of a leaf node Depth-first search is: Complete only for finite search tree Not optimal Number of nodes generated (worst case): 1 + b + b2 + + bm = O(bm) Time complexity is O(bm) Space complexity is O(bm) [or O(m)] [Reminder: Breadth-first requires O(bd) time and space]

39 DEPTH-LIMITED SEARCH Depth-first with depth cutoff k (depth at which nodes are not expanded) Three possible outcomes: Solution Failure (no solution) Cutoff (no solution within cutoff) 40 ITERATIVE DEEPENING SEARCH

Provides the best of both breadth-first and depth-first search Main idea: Totally horrifying ! IDS For k = 0, 1, 2, do: Perform depth-first search with depth cutoff k (i.e., only generate nodes with depth 41k) ITERATIVE DEEPENING 42 ITERATIVE DEEPENING

43 ITERATIVE DEEPENING 44 PERFORMANCE Iterative deepening search is: Complete Optimal if step cost =1 Time complexity is: (d+1)(1) + db + (d-1)b2 + + (1) bd = O(bd) Space complexity is: O(bd) or O(d)

45 CALCULATION db + (d-1)b2 + + (1) bd = bd + 2bd-1 + 3bd-2 + + db = (1 + 2b-1 + 3b-2 + + db-d)bd (Si=1,, ib(1-i))bd = bd (b/(b-1))2 46 NUMBER OF GENERATED NODES (BREADTH-FIRST & ITERATIVE DEEPENING) d = 5 and b = 2 BF

1 2 4 8 16 32 ID 1x6=6 2 x 5 = 10 4 x 4 = 16 8 x 3 = 24 16 x 2 = 32 32 x 1 = 32 120/63 ~ 2 47

NUMBER OF GENERATED NODES (BREADTH-FIRST & ITERATIVE DEEPENING) d = 5 and b = 10 BF 1 10 100 1,000 10,000 100,000 111,111 ID 6 50 400 3,000 20,000 100,000

123,456 48 123,456/111,111 ~ 1.111 RECAP BFS: Complete, optimal O(bd) DFS: Not complete nor optimal O(bd) time and space space, unbounded time

ID: Complete, optimal O(bd) space, O(bd) time 49 RELATED TOPICS Non-unit costs Revisited states Heuristic search 50 NON-UNIT COSTS Each arc has cost c > 0

Why? The cost of the path to each node N is g(N) = S costs of arcs Breadth-first is no longer optimal 51 UNIFORM-COST SEARCH Expand node in FRINGE with the cheapest path A 1 S S 10 5 B 5 G

15 C A 5 G Suboptimal path! 1 11 0 B 5

C 15 G 10 52 SEARCH ALGORITHM The goal test is applied a node when this node is #2to expanded, not when it is generated. SEARCH#2 1. If GOAL?(initial-state) then return initial-state 2. INSERT(initial-node,FRINGE)

3. Repeat: 4. If empty(FRINGE) then return failure 5. N REMOVE(FRINGE) 6. s STATE(N) 7. If GOAL?(s) then return path or goal state 8. For every state s in SUCCESSORS(s) 9. Create a new node N as a child of N 10. INSERT(N,FRINGE) 53 REVISITED STATES No Few Many 1 2 3 search tree is finite search tree is infinite

4 5 7 8 6 8-queens assembly planning 8-puzzle and robot navigation 54 AVOIDING REVISITED STATES Requires comparing state descriptions Breadth-first search: Store all states associated with generated nodes in VISITED

If the state of a new node is in VISITED, then discard the node 55 AVOIDING REVISITED STATES Requires comparing state descriptions Breadth-first search: Store all states associated with generated nodes in VISITED If the state of a new node is in VISITED, then discard the node Implemented as hash-table or as explicit data structure with flags 56

EXPLICIT DATA STRUCTURES 57 Robot navigation VISITED: array initialized to 0, matching grid When grid position (x,y) is visited, mark corresponding position in VISITED as 1 Size of the entire state space! HASH TABLES 0 1 VISITED: Hash table of size N 2

N-1 Hash function: map from S to {0,,N-1} 8 2 3 4 5 1 1 2

7 4 5 6 7 8 3 6 If hash function is chosen carefully to minimize chance of collision, then membership testing on M states averages O(M/ N) time 58

AVOIDING REVISITED STATES Depth-first search: Solution 1: Store all states associated with nodes in current path in VISITED If the state of a new node is in VISITED, then discard the node ?? 59

AVOIDING REVISITED STATES Depth-first search: Solution 1: Store all states associated with nodes in current path in VISITED If the state of a new node is in VISITED, then discard the node Only avoids loops Solution 2:

Store all generated states in VISITED If the state of a new node is in VISITED, then discard the node Same space complexity as breadth-first ! 60 AVOIDING REVISITED STATES IN UNIFORM-COST SEARCH For any state S, when the first node N such that STATE(N) = S is expanded, the path to N is the best path from the initial state to S

So: When a node is expanded, store its state into VISITED When a new node N is generated: If STATE(N) is in VISITED, discard N If there exits a node N in the fringe such that STATE(N) = STATE(N), discard the node -- N or N -with the highest-cost path 61 SEARCH ALGORITHM #3 SEARCH#3 1. If GOAL?(initial-state) then return initial-state 2. INSERT(initial-node,FRINGE) 3. Repeat: 4. If empty(FRINGE) then return failure 5. N REMOVE(FRINGE)

6. s STATE(N) 7. Add s to VISITED 7. If GOAL?(s) then return path or goal state 8. For every state s in SUCCESSORS(s) 9. Create a new node N as a child of N 10. If s is in VISITED then discard N 11. If there is N in FRINGE with STATE(N)=STATE(N) 12. If g(N) is lower than g(N) then discard N 13. Otherwise discard N 14. INSERT(N,FRINGE) 62 HOMEWORK Readings: R&N Ch. 3.5 63