Report

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 If states are allowed to be revisited, the search tree may be infinite even when the state space is finite 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 Path-Cost 5 Expanded 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 haven’t 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 haven’t 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 initial-state 2. INSERT(initial-node,FRINGE) 3. Repeat: 4. If empty(FRINGE) then return failure 5. N REMOVE(FRINGE) Expansion of N 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. INSERT(N’,FRINGE) 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 k) 41 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 (BREADTHFIRST & ITERATIVE DEEPENING) d = 5 and b = 2 BF 1 2 4 8 16 32 63 ID 1x6=6 2 x 5 = 10 4 x 4 = 16 8 x 3 = 24 16 x 2 = 32 32 x 1 = 32 120 120/63 ~ 2 47 NUMBER OF GENERATED NODES (BREADTHFIRST & 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 DFS: Not complete nor optimal O(bd) time and space O(bd) 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 S 1 S 10 5 B 5 G 15 C A 5 Suboptimal path! G 1 11 B G 0 5 C 15 10 52 SEARCH ALGORITHM #2 The goal test is applied to a node when this node is 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 highestcost 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