Blind Search Algorithms PDF

Solving problems by searching References: Luger: Artificial Intelligence, 6th edition (chapter 3) Norvig, Russell: Artificial Intelligence A Modern Approach (chapter 3) Coppin: Artificial Intelligence Illuminated (chapter 4) 6/8/2020 CSCI 323 - Blind Sear...

Solving problems by searching References: Luger: Artificial Intelligence, 6th edition (chapter 3) Norvig, Russell: Artificial Intelligence A Modern Approach (chapter 3) Coppin: Artificial Intelligence Illuminated (chapter 4) 6/8/2020 CSCI 323 - Blind Search 1  Outline Problem-solving agents Problem types Problem formulation Example problems Basic search algorithms 6/8/2020 CSCI 323 - Blind Search 2  But first look at this: Is this program intelligent? Crystal Ball: http://www.dslextreme.com/users/exstatica/ psychic.swf (moved not working) 6/8/2020 CSCI 323 - Blind Search 3  How Intelligent is Alice? http://alicebot.blogspot.com/ 6/8/2020 CSCI 323 - Blind Search 4  Problem-solving agents 6/8/2020 CSCI 323 - Blind Search 5 Fig 3.8 State space of the 8-puzzle generated by “move blank” operations 6 Luger: Artificial Intelligence, 6th edition. © Pearson Education Limited, 2009  7 Luger: Artificial Intelligence, 6th edition. © Pearson Education Limited, 2009 Fig 3.9 An instance of the travelling salesperson problem 8 Luger: Artificial Intelligence, 6th edition. © Pearson Education Limited, 2009 Fig 3.10Search for the travelling salesperson problem. Each arc is marked with the total weight of all paths from the start node (A) to its endpoint. 9 Luger: Artificial Intelligence, 6th edition. © Pearson Education Limited, 2009 Fig 3.11An instance of the travelling salesperson problem with the nearest neighbor path in bold. Note this path (A, E, D, B, C, A), at a cost of 550, is not the shortest path. The comparatively high cost of arc (C, A) defeated the heuristic. 10 Luger: Artificial Intelligence, 6th edition. © Pearson Education Limited, 2009  Example: Romania 6/8/2020 CSCI 323 - Blind Search 11  Example: Romania On holiday in Romania; currently in Arad. Flight leaves tomorrow from Bucharest Formulate goal: be in Bucharest Formulate problem: states: various cities actions: drive between cities Find solution: sequence of cities, e.g., Arad, Sibiu, Fagaras, Bucharest 6/8/2020 CSCI 323 - Blind Search 12  ‘State Space’ r k b ki q b k r p p p p p p p p Initial state operators P P P P P P P P R K B KI Q B K R p p k q Goal state(s) KI 6/8/2020 CSCI 323 - Blind Search 13  The Water Jugs Problem 2 jugs 4 gallon 3 3 gallon 4 How can you get exactly 2 gallons into the 4 gallon jug? Possible operators: 1. Empty jug 2. Fill jug from tap 3. Pour contents from one jug into another 6/8/2020 CSCI 323 - Blind Search 14  Problem types Deterministic, fully observable  single-state problem Agent knows exactly which state it will be in; solution is a sequence Non-observable  sensorless problem (conformant problem) Agent may have no idea where it is; solution is a sequence Nondeterministic and/or partially observable  contingency problem percepts provide new information about current state often interleave} search, execution Unknown state space  exploration problem 6/8/2020 CSCI 323 - Blind Search 15  Example: vacuum world There are two rooms, vacuum know which room it is in and senses whether there is dirt on the floor or not? What type of problem is this? (in terms of environment and agents) Can we find the solution by search? What is the search space and how big it is? Location: L,R Current State: Sensor: Dirt, clean [left, clean] 6/8/2020 CSCI 323 - Blind Search 16  Example: vacuum world Deterministic Fully Observable: Single-state: start in #5. Solution? 6/8/2020 CSCI 323 - Blind Search 17  Example: vacuum world Single-state, start in #5. Solution? [Right, Suck] 6/8/2020 CSCI 323 - Blind Search 18  Example: vacuum world Non-observable Sensorless, Multi-state problem start in {1,2,3,4,5,6,7,8} e.g., Right goes to {2,4,6,8} Solution? [Right,Suck,Left,Suck] 6/8/2020 CSCI 323 - Blind Search 19  Sensorless vacuum world multi-state problems 6/8/2020 CSCI 323 - Blind Search 20  Example: vacuum world what is the problem type if: Suck may dirty a clean carpet Contingency Nondeterministic: Partially observable: location, dirt at current location. Percept: [L, Clean], i.e., start in #5 or #7 Solution? 6/8/2020 CSCI 323 - Blind Search 21  Contingency Problems Nondeterministic: Suck may dirty a clean carpet Partially observable: location, dirt at current location. Percept: [L, Clean], i.e., start in #5 or #7 Solution? [Right, if dirt then Suck] 6/8/2020 CSCI 323 - Blind Search 22  Single-state problem formulation Example: Romania 6/8/2020 CSCI 323 - Blind Search 23  Single-state problem formulation A problem is defined by four items: 1. initial state e.g., "at Arad" 2. 2. actions or successor function S(x) = set of action–state pairs e.g., S(Arad) = {, … } 3. goal test, can be explicit, e.g., x = "at Bucharest" implicit, e.g., Checkmate(x) 4. path cost (additive) e.g., sum of distances, number of actions executed, etc. c(x,a,y) is the step cost, assumed to be ≥ 0 A solution is a sequence of actions leading from the initial state to a goal state 6/8/2020 CSCI 323 - Blind Search 24  Selecting a state space Real world is absurdly complex  state space must be abstracted for problem solving (Abstract) state = set of real states (Abstract) action = complex combination of real actions e.g., "Arad  Zerind" represents a complex set of possible routes, detours, rest stops, etc. For guaranteed realizability, any real state "in Arad“ must get to some real state "in Zerind" (Abstract) solution = set of real paths that are solutions in the real world Each abstract action should be "easier" than the original problem 6/8/2020 CSCI 323 - Blind Search 25  Vacuum world state space graph states? actions? goal test? path cost? 6/8/2020 CSCI 323 - Blind Search 26  Vacuum world state space graph states? integer dirt and robot location actions? Left, Right, Suck goal test? no dirt at all locations path cost? 1 per action 6/8/2020 CSCI 323 - Blind Search 27  Example: The 8-puzzle states? actions? goal test? path cost? 6/8/2020 CSCI 323 - Blind Search 28  Example: The 8-puzzle states? locations of tiles actions? move blank left, right, up, down goal test? = goal state (given) path cost? 1 per move [Note: optimal solution of n-Puzzle family is NP-hard] 6/8/2020 CSCI 323 - Blind Search 29  Example: robotic assembly states?: real-valued coordinates of robot joint angles parts of the object to be assembled actions?: continuous motions of robot joints goal test?: complete assembly path cost?: time to execute 6/8/2020 CSCI 323 - Blind Search 30  Try This one: Cannibals and Priests There are three cannibals and Three priests, a river and a boat with two seats. We want to get all 6 people to other side of the river. But if the number of cannibals exceeds the number of priests, they would definitely eat them! If the number of priests exceed the number of cannibals, they would preach and bore the cannibals to death! Convert this problem into a search problem and solve it. 6/8/2020 CSCI 323 - Blind Search 31  A Representation The first step in solving the problem is to choose a suitable representation. We will show number of cannibals, missionaries and canoes on each side of the river. Start state is therefore: 3,3,1 0,0,0 6/8/2020 CSCI 323 - Blind Search 32  A Simpler Representation In fact, since the system is closed, we only need to represent one side of the river, as we can deduce the other side. We will represent the finishing side of the river, and omit the starting side. So start state is: 0,0,0 6/8/2020 CSCI 323 - Blind Search 33  Operators Now we have to choose suitable operators that can be applied: 1. Move one cannibal across the river. 2. Move two cannibals across the river. 3. Move one missionary across the river. 4. Move two missionaries across the river. 5. Move one missionary and one cannibal. 6/8/2020 CSCI 323 - Blind Search 34  The Search Tree Cycles have been removed. Nodes represent states, edges represent operators. There are two shortest paths that lead to the solution. 6/8/2020 CSCI 323 - Blind Search 35  Problem-solving agents 6/8/2020 CSCI 323 - Blind Search 36  Tree search algorithms Basic idea: offline, simulated exploration of state space by generating successors of already-explored states (a.k.a.~expanding states) 6/8/2020 CSCI 323 - Blind Search 37  Example: Romania From Arad to Bucharest 6/8/2020 CSCI 323 - Blind Search 38  Tree search example 6/8/2020 CSCI 323 - Blind Search 39  Tree search example 6/8/2020 CSCI 323 - Blind Search 40  Tree search example 6/8/2020 CSCI 323 - Blind Search 41  Implementation: general tree search 6/8/2020 CSCI 323 - Blind Search 42  Implementation: states vs. nodes A state is a (representation of) a physical configuration A node is a data structure constituting part of a search tree includes state, parent node, action, path cost g(x), depth The Expand function creates new nodes, filling in the various fields and using the SuccessorFn of the problem to create the corresponding states. 6/8/2020 CSCI 323 - Blind Search 43  Search strategies A search strategy is defined by picking the order of node expansion Strategies are evaluated along the following dimensions: completeness: does it always find a solution if one exists? time complexity: number of nodes generated space complexity: maximum number of nodes in memory optimality: does it always find a least-cost solution? Time and space complexity are measured in terms of b: maximum branching factor of the search tree d: depth of the least-cost solution m: maximum depth of the state space (may be ∞) 6/8/2020 CSCI 323 - Blind Search 44  Uninformed search strategies Uninformed search strategies use only the information available in the problem definition Breadth-first search Uniform-cost search Depth-first search Depth-limited search Iterative deepening search 6/8/2020 CSCI 323 - Blind Search 45  Breadth-first search Expand shallowest unexpanded node Implementation: fringe is a FIFO queue, i.e., new successors go at end 6/8/2020 CSCI 323 - Blind Search 46  Breadth-first search Expand shallowest unexpanded node Implementation: fringe is a FIFO queue, i.e., new successors go at end 6/8/2020 CSCI 323 - Blind Search 47  Breadth-first search Expand shallowest unexpanded node Implementation: fringe is a FIFO queue, i.e., new successors go at end 6/8/2020 CSCI 323 - Blind Search 48  Breadth-first search Expand shallowest unexpanded node Implementation: fringe is a FIFO queue, i.e., new successors go at end 6/8/2020 CSCI 323 - Blind Search 49  Properties of breadth-first search Complete? Yes (if b is finite) Time? 1+b+b2+b3+… +bd + b(bd-1) = O(bd+1) Space? O(bd+1) (keeps every node in memory) Optimal? Yes (if cost = 1 per step) Space is the bigger problem (more than time) 6/8/2020 CSCI 323 - Blind Search 50  Time and Memory Requirment 6/8/2020 CSCI 323 - Blind Search 51 Function breadth_first search algorithm 52 Luger: Artificial Intelligence, 6th edition. © Pearson Education Limited, 2009 A trace of breadth_first_search on the graph of Figure 3.13 53 Luger: Artificial Intelligence, 6th edition. © Pearson Education Limited, 2009 Fig 3.16Graph of Fig 3.15 at iteration 6 of breadth-first search. States on open and closed are highlighted. 54 Luger: Artificial Intelligence, 6th edition. © Pearson Education Limited, 2009  The Water Jugs Problem 2 jugs 4 gallon 3 gallon 4 3 How can you get exactly 2 gallons into the 4 gallon jug? Possible operators: 1. Empty jug 2. Fill jug from tap 3. Pour contents from one jug into another Problem Representations: States: 3,1 Initial State: 0,0 Goal State: 2,0 Fill jug from tap actions change one state to another: 0 , 0 3,0 6/8/2020 CSCI 323 - Blind Search 55  The Water Jugs Problem – Search Tree Blind Search – Breadth First 0,0 0,3 4,0 0,0 4,3 3,0 4,3 1,3 0,0 4,0 0,3 4,0 3,3 0,3 0,0 4,0 0,3 1,0 0,3 4,3 0,3 3,0 4,2 4,3 4,0 0,1 1,3 0,0 4,0 3,3 0,2 4,3 0,0 4,1 1,0 0,0 4,2 2,0 0,3 0,1 4,0 3,3 4,3 6/8/2020 CSCI 323 - Blind Search 56  Blind Search – Breadth First The path 0,0 0,3 4,0 4,3 3,0 4,3 1,3 3,3 1,0 This path also specifies the 4,2 0,1 sequence of actions that need to be taken in 0,2 4,1 order to solve this problem. 2,0 6/8/2020 CSCI 323 - Blind Search 57  Uniform-cost search Expand least-cost unexpanded node Implementation: fringe = queue ordered by path cost Equivalent to breadth-first if step costs all equal Complete? Yes, if step cost ≥ ε Time? # of nodes with g ≤ cost of optimal solution, O(bceiling(C*/ ε)) where C* is the cost of the optimal solution Space? # of nodes with g ≤ cost of optimal solution, O(bceiling(C*/ ε)) Optimal? Yes – nodes expanded in increasing order of g(n) 6/8/2020 CSCI 323 - Blind Search 58  Depth-first search Expand deepest unexpanded node Implementation: fringe = LIFO queue, i.e., put successors at front 6/8/2020 CSCI 323 - Blind Search 59  Depth-first search Expand deepest unexpanded node Implementation: fringe = LIFO queue, i.e., put successors at front 6/8/2020 CSCI 323 - Blind Search 60  Depth-first search Expand deepest unexpanded node Implementation: fringe = LIFO queue, i.e., put successors at front 6/8/2020 CSCI 323 - Blind Search 61  Depth-first search Expand deepest unexpanded node Implementation: fringe = LIFO queue, i.e., put successors at front 6/8/2020 CSCI 323 - Blind Search 62  Depth-first search Expand deepest unexpanded node Implementation: fringe = LIFO queue, i.e., put successors at front 6/8/2020 CSCI 323 - Blind Search 63  Depth-first search Expand deepest unexpanded node Implementation: fringe = LIFO queue, i.e., put successors at front 6/8/2020 CSCI 323 - Blind Search 64  Depth-first search Expand deepest unexpanded node Implementation: fringe = LIFO queue, i.e., put successors at front 6/8/2020 CSCI 323 - Blind Search 65  Depth-first search Expand deepest unexpanded node Implementation: fringe = LIFO queue, i.e., put successors at front 6/8/2020 CSCI 323 - Blind Search 66  Depth-first search Expand deepest unexpanded node Implementation: fringe = LIFO queue, i.e., put successors at front 6/8/2020 CSCI 323 - Blind Search 67  Depth-first search Expand deepest unexpanded node Implementation: fringe = LIFO queue, i.e., put successors at front 6/8/2020 CSCI 323 - Blind Search 68  Depth-first search Expand deepest unexpanded node Implementation: fringe = LIFO queue, i.e., put successors at front 6/8/2020 CSCI 323 - Blind Search 69  Depth-first search Expand deepest unexpanded nod Implementation: fringe = LIFO queue, i.e., put successors at front 6/8/2020 CSCI 323 - Blind Search 70  Properties of depth-first search Complete? No: fails in infinite-depth spaces, spaces with loops Modify to avoid repeated states along path  complete in finite spaces Time? O(bm): terrible if m is much larger than d but if solutions are dense, may be much faster than breadth-first Space? O(bm), i.e., linear space! Optimal? No 6/8/2020 CSCI 323 - Blind Search 71 Function depth_first_search algorithm 72 Luger: Artificial Intelligence, 6th edition. © Pearson Education Limited, 2009 A trace of depth_first_search on the graph of Figure 3.13 73 Luger: Artificial Intelligence, 6th edition. © Pearson Education Limited, 2009 Fig 3.17Breadth-first search of the 8-puzzle, showing order in which states were removed from open. 74 Luger: Artificial Intelligence, 6th edition. © Pearson Education Limited, 2009 Fig 3.18Graph of fig 3.15 at iteration 6 of depth-first search. States on open and closed are highlighted. 75 Luger: Artificial Intelligence, 6th edition. © Pearson Education Limited, 2009 Fig 3.19Depth-first search of the 8-puzzle with a depth bound of 5. 76 Luger: Artificial Intelligence, 6th edition. © Pearson Education Limited, 2009  The Water Jugs Problem – Search Tree 0,0 0,3 4,0 0,0 4,3 3,0 4,3 1,3 0,0 4,0 0,3 4,0 3,3 0,3 0,0 4,0 0,3 1,0 0,3 4,3 0,3 3,0 4,2 4,3 4,0 0,1 1,3 0,0 4,0 3,3 0, 4,3 0,0 4,1 1,0 2 0,0 4,2 2,0 0,3 0,1 4,0 3,3 4,3 6/8/2020 CSCI 323 - Blind Search 77  The Water Jugs Problem – Search Tree Blind Search – Depth First 0,0 0,3 0,0 4,3 3,0 Depth First: First follow a node to 4,0 0,3 4,0 3,3 deepest depth if solution was not found backtrack and search from the next 0,3 3,0 4,2 node. 4,0 3,3 0,2 0,0 4,2 2,0 6/8/2020 CSCI 323 - Blind Search 78  Blind Search – Depth First The path 0,0 0,3 3,0 3,3 4,2 0,2 2,0 6/8/2020 CSCI 323 - Blind Search 79  Depth-limited search = depth-first search with depth limit l, i.e., nodes at depth l have no successors Recursive implementation: 6/8/2020 CSCI 323 - Blind Search 80  Iterative deepening search 6/8/2020 CSCI 323 - Blind Search 81  Iterative deepening search l =0 6/8/2020 CSCI 323 - Blind Search 82  Iterative deepening search l =1 6/8/2020 CSCI 323 - Blind Search 83  Iterative deepening search l =2 6/8/2020 CSCI 323 - Blind Search 84  Iterative deepening search l =3 6/8/2020 CSCI 323 - Blind Search 85  Iterative deepening search Number of nodes generated in a depth-limited search to depth d with branching factor b: NDLS = b0 + b1 + b2 + … + bd-2 + bd-1 + bd Number of nodes generated in an iterative deepening search to depth d with branching factor b: NIDS = (d+1)b0 + d b1 + (d-1)b2 + … + 3bd-2 +2bd-1 + 1bd For b = 10, d = 5, NDLS = 1 + 10 + 100 + 1,000 + 10,000 + 100,000 = 111,111 NIDS = 6 + 50 + 400 + 3,000 + 20,000 + 100,000 = 123,456 Overhead = (123,456 - 111,111)/111,111 = 11% 6/8/2020 CSCI 323 - Blind Search 86  Properties of iterative deepening search Complete? Yes Time? (d+1)b0 + d b1 + (d-1)b2 + … + bd = O(bd) Space? O(bd) Optimal? Yes, if step cost = 1 6/8/2020 CSCI 323 - Blind Search 87  Summary of algorithms 6/8/2020 CSCI 323 - Blind Search 88  Bi-directional search 6/8/2020 CSCI 323 - Blind Search 89 6/8/2020 CSCI 323 - Blind Search 90  Repeated states Failure to detect repeated states can turn a linear problem into an exponential one! 6/8/2020 CSCI 323 - Blind Search 91  Graph search 6/8/2020 CSCI 323 - Blind Search 92 Fig 3.20State space graph of a set of implications in the propositional calculus. 93 Luger: Artificial Intelligence, 6th edition. © Pearson Education Limited, 2009 Fig 3.21And/or graph of the expression q Λ r → p. 94 Luger: Artificial Intelligence, 6th edition. © Pearson Education Limited, 2009  95 Luger: Artificial Intelligence, 6th edition. © Pearson Education Limited, 2009 Fig 3.22And/or graph of the expression q v r → p 96 Luger: Artificial Intelligence, 6th edition. © Pearson Education Limited, 2009 Fig 3.23And/or graph of a set of propositional calculus expressions. 97 Luger: Artificial Intelligence, 6th edition. © Pearson Education Limited, 2009 Fig 3.24And/or graph of part of the state space for integrating a function, from Nilsson (1971). 98 Luger: Artificial Intelligence, 6th edition. © Pearson Education Limited, 2009 The facts and rules of this example are given as English sentences followed by their predicate calculus equivalents: 99 Luger: Artificial Intelligence, 6th edition. © Pearson Education Limited, 2009 Fig 3.25The solution subgraph showing that Fred is at the museum. 100 Luger: Artificial Intelligence, 6th edition. © Pearson Education Limited, 2009 Five rules for a simple subset of English grammar are: 101 Luger: Artificial Intelligence, 6th edition. © Pearson Education Limited, 2009 Fig 3.26And/or graph searched by the financial advisor. 102 Luger: Artificial Intelligence, 6th edition. © Pearson Education Limited, 2009 Fig 3.27And/or graph for the grammar of Example 3.3.6. Some of the nodes (np, art, etc) have been written more than once to simplify drawing the graph. 103 Luger: Artificial Intelligence, 6th edition. © Pearson Education Limited, 2009 Fig 3.28Parse tree for the sentence “The dog bites the man.” Note this is a subtree of the graph of fig 3.27. 104 Luger: Artificial Intelligence, 6th edition. © Pearson Education Limited, 2009 Fig 3.29A graph to be searched. 105 Luger: Artificial Intelligence, 6th edition. © Pearson Education Limited, 2009  Summary Problem formulation usually requires abstracting away real- world details to define a state space that can feasibly be explored Variety of uninformed search strategies Breath first Depth First Uniform Cost Iterative deepening search uses only linear space and not much more time than other uninformed algorithms 6/8/2020 CSCI 323 - Blind Search 106  Lets look at the cannibals and priests problem as a search problem 6/8/2020 CSCI 323 - Blind Search 107 Fig 3.5 (a) The finite state graph for a flip flop and (b) its transition matrix. 108 Luger: Artificial Intelligence, 6th edition. © Pearson Education Limited, 2009 Fig 3.6 (a) The finite state graph and (b) the transition matrix for string recognition example 109 Luger: Artificial Intelligence, 6th edition. © Pearson Education Limited, 2009