AI-03-01 - Search in problem solving - Tagged PDF

Lecture 3 – Part 1: Search in Problem Solving (Problem-Solving Agent: Goal-based agent) C.-C. Hung Kennesaw State University (Slides used in the classroom only)  Important Chapter Summary Uninformed Search Strategies:...

Lecture 3 – Part 1: Search in Problem Solving (Problem-Solving Agent: Goal-based agent) C.-C. Hung Kennesaw State University (Slides used in the classroom only)  Important Chapter Summary Uninformed Search Strategies: – Breadth-First Search (BFS) – Depth-First Search (DFS) Informed Search Strategies: – Uniform-Cost Search (UCS) – Best-First Search – A* search Depth-First Iterative deepening search (IDS), Bidirectional search (BS) Time complexity and space complexity of each algorithm (above).  Lecture outline (Chapter 3) Graph Theory (a brief review) Strategies for State Space Search Search Methods Uninformed search algorithms Informed search algorithms Asymptotic complexity: Big O (appendix A: book) NP-completeness (appendix A: book) State Space Search  Recap: Predicate Calculus The advantage of the predicate calculus expressions provides a well-defined formal semantics and sound and complete inference rules. A good representation language.  Objectives: Problem-Solving Agent An agent can act by establishing goals and considering sequences of actions that might achieve those goals. A goal and a set of means for achieving the goal is called a problem, and The process of exploring what the means can do is called search.  Objectives: Problem-Solving Agent We will show what search can do, how it must be modified to account for adversaries, and what its limitations are.  Objectives: Problem-Solving Agent Solving problems by searching, in which we look at how an agent can decide what to do by systematically considering the outcomes of various sequences of actions that it might take.  Search for solutions (Generate and Test) Generating action sequences. – Data structures for search trees. Test/Search  Search Strategies (i.e. properties of search methods) Completeness Time complexity Space complexity Optimality Admissibility (Optimality + quickest) Irrevocability (often find suboptimal solutions) Search Technique/Algorithms BFS DFS …  Search Problems in the Algorithm Class Sequential Search Binary Search N-Queen Problem The Sum-of-Subsets Problem Graph Coloring Problem The Hamiltonian Circuits Problem 0-1 Knapsack Problem The Traveling Salesperson Problem  Search Questions need be answered: Is the problem solver guaranteed to find a solution? Will the problem solver always terminate? Can it become caught in an infinite loop? When a solution is found, is it guaranteed to be optimal? What is the complexity of the search process in terms of time usage? Memory usage? How can the interpreter most effectively reduce search complexity? How can an interpreter be designed to most effectively utilize a representation language?  Search Questions need be answered: The theory of state space search is our primary goal for answering these questions. By representing a problem as a state space graph, we can use graph theory to analyze the structure and complexity of both the problem and the search procedures that we employ.  Goal-based agents Goal-based agents can succeed by considering future actions and the desirability of their outcomes. – One kind of goal-based agent called a problem- solving agent. – Problem-solving agents decide what to do by finding sequences of actions that lead to desirable states. – Several general-purpose search algorithms can be used to solve the problems just described. Goal-Driven Search vs Data-Driven Search Goal-Drive Search starts at the goal and work back toward a start state by seeing what moves could led to the goal state (is known as backward chaining). Most search methods we will learn in this course are Data-Driven Search.  Data-Driven Search Data-Driven search starts from an initial state and uses actions that are allowed to move forward until a goal is reached (is known as forward chaining).  Examples of Search Problems Chess: search through a set of possible moves – Looking for one which will best improve position Route planning: search through a set of paths – Looking for one which will minimize distance Theorem proving: – Search through sets of reasoning steps Looking for a reasoning progression which proves theorem Machine learning: – Search through a set of concepts Looking for a concept which achieves target categorisation  Search Terminology States – “Places” where the search can visit Search space – The set of possible states Search path – The states which the search agent actually visits Solution – A state with a particular property Which solves the problem (achieves the task) at hand – May be more than one solution to a problem Strategy – How to choose the next step in the path at any given stage  Search Terminology … Goal Goal formulation Problem formulation: is the process of deciding what actions and states to consider, given a goal. Search  Well-defined problems and solutions A problem can be defined formally by four components: (page 66) – Initial state – Actions – Goal test – Path cost A problem is really a collection of information that the agent will use to decide what to do.  Specifying a Search Problem Three important considerations 1. Initial state – So the agent can keep track of the state it is visiting 2. Operators (actions) – Function taking one state to another – Specify how the agent can move around search space – So, strategy boils down to choosing states & operators 3. Goal test – How the agent knows if the search has succeeded  Example 1 - Chess Chess Initial state – As in picture Operators – Moving pieces Goal test – Checkmate king cannot move without being taken  Example 2 – Route Planning Initial state – City the journey starts in Operators Liverpool Leeds – Driving from city to city Nottingham Manchester Goal test Birmingham – If current location is Destination city London  Two types of Search Algorithms Uninformed search algorithms: they are given no information about the problem other than its definition. Informed search algorithms: the algorithms have some idea of where to look for solutions.  General Search Considerations 1. Path or Artefact 2. Completeness 3. Time and Space Trade-offs 4. Soundness 5. Additional Information  General Search Considerations 1. Path or Artefact Is it the route or the destination you are interested in? Route planning – Already know the destination, so must record the route (path) Solving anagram puzzle – Doesn’t matter how you found the word in the anagram – Only the word itself (artefact) is important Machine learning – Usually only the concept (artefact) is important Automated reasoning – The proof is the “path” of logical reasoning  General Search Considerations 2. Completeness Think about the density of solutions in space Searches guaranteed to find all solutions – are called complete searches Particular tasks may require one/some/all solutions – e.g., how many different ways to get from A to B? Pruning versus exhaustive searches – Exhaustive searches try all possibilities – If only one solution required, can employ pruning Rule out certain operators on certain states – If all solutions are required, we have to be careful with pruning Check no solutions can be ruled out  General Search Considerations 3. Time and Space Trade-offs With many computing projects, we worry about: – Speed versus memory Fast programs can be written – But they use up too much memory Memory efficient programs can be written – But they are slow We consider various search strategies – In terms of their memory/speed tradeoffs  General Search Considerations 4. Soundness Unsound search strategies: – Find solutions to problems with no solutions Particularly important in automated reasoning – Prove a theorem which is actually false Have to check the soundness of search Not a problem – If the only tasks you give it always have solutions Another unsound type of search – Produces incorrect solutions to problems More worrying, probably problem with the goal check  General Search Considerations 5. Additional Information Can you give the agent additional info? – In addition to initial state, operators and goal test Uninformed search strategies – Use no additional information Heuristic search strategies – Take advantage of various values To drive the search path Measuring problem-solving performance Completeness Optimality Time complexity Space complexity  Graph and Agenda Analogies Graph Analogy – States are nodes in graph, operators are edges – Choices define search strategy Which node to “expand” and which edge to “go down” Agenda Analogy – Pairs (State, Operator) are put on to an agenda – Top of the agenda is carried out Operator is used to generate new state from given one – Agenda ordering defines search strategy Where to put new pairs when a new state is found  Example Problem Genetics Professor – Wanting to name her new baby boy – Using only the letters D,N & A Search by writing down possibilities (states) – D,DN,DNNA,NA,AND,DNAN, etc. – Operators: add letters on to the end of already known states – Initial state is an empty string Goal test – Look up state in a book of boys names – Good solution: DAN  Uninformed Search Strategies 1. Breadth First Search (FIFO queue) BFS Every time a new state, S, is reached – Agenda items put on the bottom of the agenda e.g., New state “NA” reached – (“NA”,add “D”), (“NA”,add “N”),(“NA”,add “A”) – These agenda items added to bottom of agenda – Get carried out later (possibly much later) Graph analogy: – Each node on a level is fully expanded before the next level is looked at  Exercise – Web Spidering An example of the importance of choosing the right search strategy can be seen in spidering the world wide web (WWW). The assumption is made that the majority of the web is connected, meaning that it is possible to get from one page to another by following a finite number of links, were a link connects two pages together. Which search technique do we consider? DFS? BFS? Graph Theory Review (Data Structures)  Graph Terminology Graph: G=(V,E) Vertex set: V Edge set: E pairs of vertices which are adjacent  Directed and Undirected Graphs G directed if edges ordered pairs (u,v)   u v G undirected if edges unordered pairs {u,v}   u v  Proper Graphs and Subgraphs Proper graph: – No loops – No multi-edges Subgraph G‘ of G G‘ = (V‘, E‘) where V‘ is a subset of V, E‘ is a subset of E  Paths in Graphs Path p e1 e2 ek Vo V1 V2 Vk-1 Vk P is a sequence of vertices v0, v1, …, vk where for i=1,…k, vi-1 is adjacent to vi Equivalently, p is a sequence of edges e1, …, ek where for i = 2,…k edges  Simple Paths and Cycles Simple path no edge or vertex repeated, except possibly vo = vk Cycle a path p with vo = vk where k>1 Vk = Vo V1 V2 Vk-1 A Connected Undirected Graph G is connected if  path between each pair of vertices Connected Components of an Undirected Graph else G has  2 connected components: maximal connected subgraphs  Biconnected Undirected Graphs A biconnected component of a graph is the set of three or more nodes for which there are at least two paths between each node. Or G is a single edge. (or G is single edge) G is biconnected if  two disjoint paths between each pair of vertices  Size of a Graph Graph G = (V,E) n = |V| = # vertices m = |E| = # edges 1 size of G is n+m 2 3 4  Representing a Graph by an Adjacency Matrix Adjacency A is size n Matrix n A 1 2 3 4 1 0 1 1 0 1 (i,j)  E 2 1 0 1 0 A(i,j)   0 else 3 1 1 0 1 4 0 0 1 0 space cost n 2 -n  Adjacency List Representation of a Graph Adjacency Lists Adj (1),…,Adj (n) Adj(v) = list of vertices adjacent to v 1 2 3 2 1 3 3 1 2 4 4 3 space cost O(n+m)  Definition of an Undirected Tree Tree (T) T is graph with unique path between every pair of vertices n = # vertices n-1 = # edges Forest – set of trees  Definition of a Directed Tree Directed Tree T is digraph with distinguished vertex root r such that each vertex reachable from r by a unique path. r Family Relationships: - ancestors - descendants - parent - child - siblings leaves have no proper descendants  An Ordered Tree Ordered Tree – is a directed tree with siblings ordered A B C D F E H I  An Ordered Tree Definition of Ordered Tree – An ordered tree is an oriented tree in which the children of a node are somehow "ordered.“ – If T1 and T2 are ordered trees then T1 ≠ T2 else T1 = T2. T1 T2 A A B C B C  An Ordered Tree There are several types of ordered trees: – k-ary tree – Binomial tree – Fibonacci tree Some k-ary trees have special names – 2-ary trees are called binary trees. – 3-ary trees are called trinary trees or ternary trees. – 1-ary trees are called lists.  Tree Traversal: Preorder Preorder ? root (order vertices as pushed on stack) preorder left subtree A preorder right subtree B C D F E H I  Tree Traversal: Preorder Preorder A,B,C,D,E,F,H,I root (order vertices as pushed on stack) preorder left subtree A preorder right subtree B C D F E H I  Tree Traversal: Inorder Inorder ? The root is visited after visiting its left subtree but before visiting the right subtree A B C D F E H I  Tree Traversal: Inorder Inorder B, A, E, D, C, H, F, I The root is visited after visiting its left subtree but before visiting the right subtree A B C D F E H I  Tree Traversal: Postorder Postorder ? postorder left subtree postorder right subtree root (order vertices as popped off stack) A B C D F E H I  Tree Traversal: Postorder Postorder B,E,D,H,I,F,C,A postorder left subtree postorder right subtree root (order vertices as popped off stack) A B C D F E H I  Exercise: Tree Traversal Preorder Inorder Postorder  Spanning Tree A spanning tree, T, is a subset of Graph G, which has all the vertices covered with minimum possible number of edges. Hence, a spanning tree does not have cycles and it cannot be disconnected.. By this definition, we can draw a conclusion that every connected and undirected Graph G has at least one spanning tree.  Example Spanning Tree of a Graph root 1 tree edge back edge 2 5 9 12 3 6 8 10 11 7 cross edge 4 Classification of Edges of G with Spanning Tree T An edge (u,v) of T is tree edge An edge (u,v) of G-T is back edge if u is a descendent or ancestor of v. Else (u,v) is a cross edge  Minimum Spanning Tree (MST) Spanning tree of a connected graph G: a connected acyclic subgraph of G that includes all of G’s vertices. Minimum Spanning Tree of a weighted, connected graph G: a spanning tree of G of minimum total weight. 4 3 Example: 1 1 6 2 2 3 4  Examples: 4 3 1 1 6 2 2 3 4 5 a b 1 4 6 2 3 7 c d e  Search Strategies Uninformed search Informed (Heuristic) search 66 Uninformed Search Strategies Breadth-First Search (BFS) Depth-First Search (DFS) Depth-Limited Search (DLS) Iterative Deepening Search (IDS) or Called Iterative Deepening Depth-First Search Bidirectional Search (BS)  Breadth-First Search (BFS): Genetic Professor’s son name Branching rate/factor – Average number of edges coming from a node Uniform Search – Every node has same number of branches (as here)  An example for BFS A D N B F What is the search sequence starting at node A?  An example for BFS A B N D F What is the search sequence starting at node A?  BFS: Exercise 1 4 3 Initial 7 BK 6 State 5 8 2 Try to generate a state space of the 8-puzzle by using “move blank” operations (Operator) using the BFS search. 1 2 3 Goal 8 BK 4 7 6 5 State space of the 8-puzzle generated by “move blank” operations 72 Luger: Artificial Intelligence, 6th edition. © Pearson Education Limited, 2009 BFS of the 8-puzzle, showing order in which states were removed from open. 73 Luger: Artificial Intelligence, 6th edition. © Pearson Education Limited, 2009  “tic-tac-toe” state space graph How do we draw a tree for search? “tic-tac-toe” state space graph  Uninformed Search Strategies 2. Depth-First Search (LIFO queue) Same as breadth-first search – But the agenda items are put at the top of agenda Graph analogy: – Each new node encountered is expanded first Problem with this: – Search can go on indefinitely down one path – D, DD, DDD, DDDD, DDDDD, … Solution: – Impose a depth limit on the search – Sometimes the limit is not required Branches end naturally (i.e. cannot be expanded)  DFS dfs(v) { Label vertex v as reached. for (each unreached vertex u adjacenct from v) dfs(u); }  DFS Property All vertices reachable from the start vertex (including the start vertex) are visited.  An example for DFS A D N B F What is the search sequence starting at node A?  An example for DFS A B N D F What is the search sequence starting at node A?  DFS: Exercise 2 8 3 1 2 3 Initial Goal 1 6 4 8 BK 4 State State 7 BK 5 7 6 5 Try to generate a state space of the 8-puzzle by using “move blank” operations (Operator).  8-puzzle DFS 1 2 3 8 BK 4 7 6 5  Depth-First Search #1 Depth limit of 3 could (should?) be imposed Depth-First Search #2 (R&N)  DFS vs. BFS Suppose we have a search with branching rate b Breadth-first (FIFO queue) – Complete (guaranteed to find solution) – Time complexity b + b2 + b3 + … + bd = O(bd) – Requires a lot of memory Needs to remember up to bd-1 states to search down to depth d and bd in the frontier. Space complexity is O(bd). Depth-first (LIFO queue) – Not complete because of the depth limit – But is good on memory Only needs to remember up to b*d states to search to depth d Time complexity is still O(bd)  Recap: Breadth-First Search (BFS) Time complexity b + b2 + b3 + … + bd = O(bd)  Depth-Limited Search Solve the problem of DFS in infinite state spaces by supplying DFS search with a predetermined depth limit L. – Called Depth-Limited Search (DLS). – If L = infinite, DFS is a special case of DLS.  Iterative Deepening (depth-first) Search (IDS) First do DFS to depth 0 (i.e., treat start node as having no successors), then, if no solution found, do DFS to depth 1, etc. until solution found do DFS with depth cutoff c c = c+1 Complete Optimal/Admissible if all operators have the same cost. Otherwise, not optimal but guarantees finding solution of shortest length (like BFS). Time complexity seems worse than BFS or DFS because nodes near the top of the search tree are generated multiple times, but because almost all of the nodes are near the bottom of a tree, the worst case time complexity is still exponential, O(bd). i.e. IDS = (d)b + (d-1)b2 + … + (1)bd = O(bd)  IDS If branching factor is b and solution is at depth d, then nodes at depth d are generated once, nodes at depth d-1 are generated twice, etc. – IDS = (d) b + (d-1) b2 + … + (2) b(d-1) + bd = O(bd). – If b=4, then worst case is 1.78 * 4d, i.e., 78% more nodes searched than exist at depth d (in the worst case). However, let’s compare this to the time spent on BFS: – BFS : b + b2 + … + bd + (b(d+1) – b) = O(bd). – Same time complexity of O(bd), but BFS expands some nodes at depth d+1, which can make a HUGE difference: With b = 10, d = 5, BFS: 10 + 100 + 1,000 + 10,000 + 100,000 + 999,990 = 1,111,100 IDS: 50 + 400 + 3,000 + 20,000 + 100,000 = 123,450 IDS can actually be quicker in-practice than BFS, even though it regenerates early states.  IDS Exponential time complexity, O(bd), like BFS Linear space complexity, O(bd), like DFS Has advantage of BFS (i.e., completeness) and also advantages of DFS (i.e., limited space and finds longer paths more quickly) IDS is generally preferred uninformed search method for large state spaces where solution depth is unknown.  IDS example: Figure 3.19 (page 89) Figure 3.19 Four iterations of iterative deepening search on a binary tree  IDS … Figure 3.19 (cont.)  Bidirectional Search If you know the solution state – Looking for the path from initial to the solution state Liverpool Leeds – Then you can also work backwards from the solution Nottingham Advantages: Manchester Birmingham – Only need to go to half depth Difficulties Peterborough – Do you really know solution? Unique? – Cannot reverse operators – Record all paths to check they meet Memory intensive London  Bidirectional Search … Figure 3.20 A schematic view of a bidirectional search that is about to succeed, when a branch from the start node meets a branch from the goal node.  Bidirectional Search … The idea behind bidirectional search is to run two simultaneous searches – one forward from the initial state and the other backward from the goal, stopping when the two searches meet in the middle. The motivation is that bd/2 + bd/2 is much less than bd.  Comparing uninformed search strategies Verify these results at home!!!! Figure 3.21 (page 91): This comparison is for tree- search versions. Criterion BFS Uniform- DFS Depth- Iterative Bidirection Cost Limited Deepening Complete? Yes Yes No No Yes Yes Time O(bd) --- O(bm) O(bl) O(bd) O(bd/2) Space O(bd) --- O(bm) O(bl) O(bd) O(bd/2) Optimal? Yes Yes No No Yes Yes b: branching factor, d: depth, m: maximum depth of the search tree, l: depth limit. Uninformed Search? Difference: Best-first search, UCS and A* Uniform-cost search (UCS) expands the node with lowest path cost (i.e. with the lowest g(n)), whereas Best-first search (BFS) expand the node with closest to the goal. UCS = g(n) BFS = h(n) A* = g(n) + h(n)  Uniform-Cost Search (UCS) Uniform Cost search is similar to breadth-first search (BFS) and best-first search but expands the node with the lowest path cost g(n). Let g(n) be the sum of the edges costs from root to node n. If g(n) is our overall cost function, then the best-first search becomes Uniform Cost Search, also known as Dijkstra’s single-source-shortest-path algorithm.  Uniform-Cost Search (UCS) Enqueue nodes by path cost. That is, let g(n) = cost of the path from the start node to the current node n. Sort nodes by increasing value of g. – Called “Dijkstra’s Algorithm” in the algorithms literature and similar to “Branch and Bound Algorithm”. – Complete (*) – Optimal/Admissible (*) Admissibility depends on the goal test being applied when a node is removed from the nodes list, not when its parent node is expanded and the node is first generated In general, exponential time and space complexity, O(bd)  Example of Uniform-Cost Search Assume an example tree with different edge costs, represented by numbers next to the edges. a 2 1 b c 1 2 1 2 f gc dc ec Notations for this example: generated node expanded node  Example of Uniform-Cost Search a 2 1 Closed list: Open list: a 0  Example of Uniform-Cost Search a 2 1 b c 1 2 1 2 Closed list: a Open list: b c 2 1  Example of Uniform-Cost Search a 2 1 b c 1 2 1 2 dc ec Closed list: a c Open list: b d e 2 2 3  Example of Uniform-Cost Search a 2 1 b c 1 2 1 2 f gc dc ec Closed list: a c b Open list: d e f g 2 3 3 4  Example of Uniform-Cost Search a 2 1 b c 1 2 1 2 f gc dc ec Closed list: a c b d Open list: e f g 3 3 4  Example of Uniform-Cost Search a 2 1 b c 1 2 1 2 f gc dc ec Closed list: a c b d e Open list: f g 3 4  Example of Uniform-Cost Search a 2 1 b c 1 2 1 2 f gc dc ec Closed list: a c b d e f Open list: g 4  Example of Uniform-Cost Search a 2 1 b c 1 2 1 2 f gc dc ec Closed list: a c b d e f g Open list:  Exercise for UCS 5 a b 1 4 6 2 3 7 c d e  Conclusion BFS and DFS strategies do not attempt to estimate how far along the search is toward a goal. We can use a heuristic to obtain this estimate. We then use this heuristic to guide the search direction. How good the search is depends on how good the heuristic is.  Conclusion – Initial state, operators, goal test, state space, – BFS, Uniform-cost search, – DFS, Depth-limited search, – Iterative deepening search (IDS), – bidirectional search.  Summary Goal-based agents Representing states and operators Example problems Generic state-space search algorithm Specific algorithms – Breadth-first search (BFS) – Depth-first search (DFS) – Uniform cost search (UCS) – Depth-first iterative deepening (IDS)  The End Questions & Suggestions?