Artificial Intelligence: Uninformed Search, Problem Solving by Searching

Artificial Intelligence Solving Problems by Searching Uninformed search Artificial Intelligence – Solving Problems by Searching Slide ‹#› 1. Introduction to Search ◼ Search is one of the most powerful approaches to problem solving in AI ◼ Search is a universal problem solving...

Artificial Intelligence Solving Problems by Searching Uninformed search Artificial Intelligence – Solving Problems by Searching Slide ‹#› 1. Introduction to Search ◼ Search is one of the most powerful approaches to problem solving in AI ◼ Search is a universal problem solving mechanism that ◼ Systematically explores the alternatives ◼ Finds the sequence of steps towards a solution Artificial Intelligence – Solving Problems by Searching Slide ‹#› Introduction to Search: Popular Classical Problem Domains ◼ 8-puzzle ◼ Block World ◼ Tower of Hanoi ◼ Travelling Salesperson ◼ Missionaries and ◼ Crossword Puzzle Cannibals ◼ Crypt-arithmetic ◼ Vacuum World ◼ Wheel of Fortune ◼ Chess, Bridge, etc Artificial Intelligence – Solving Problems by Searching Slide ‹#› Search paradigms ◼ Uniformed search ◼ Blind, naïve ◼ Brute force ◼ Informed search ◼ Guided with heuristics ◼ Optimal Artificial Intelligence – Solving Problems by Searching Slide ‹#› 2. Defining a Search Problem ◼ State Space: described by an initial state and the set of possible actions available (operators). ◼ A path is any sequence of actions that lead from one state to another. ◼ Goal test: applicable to a single state problem to determine if it is the goal state. ◼ Path cost: relevant if more than one path leads to the goal, and we want the shortest (the least cost) path. Artificial Intelligence – Solving Problems by Searching Slide ‹#›  2.1 Toy Problems (1) 8-puzzle problem Fig 4.1 ◼ Initial State: The location of each of the 8 tiles in one of the nine squares ◼ Operators: blank moves (1) Left (2) Right (3) Up (4) Down ◼ Goal Test: state matches the goal configuration ◼ Path cost: each step costs 1, total path cost = no. of steps Artificial Intelligence – Solving Problems by Searching Slide ‹#›  Toy Problems (2) 8-queens problem Fig 4.2 ◼ Initial State: Any arrangement of 0 to 8 queens on board. ◼ Operators: add a queen to any square. ◼ Goal Test: 8 queens on board, none attacked. ◼ Path cost: not applicable or Zero (because only the final state counts). Artificial Intelligence – Solving Problems by Searching Slide ‹#› 2.2 Real-world Problems ◼ Route Finding - computer networks, automated travel advisory systems, airline travel planning. ◼ VLSI Layout - A typical VLSI chip can have as many as a million gates, and the positioning and connections of every gate are crucial to the successful operation of the chip. ◼ Robot Navigation - rescue operations ◼ Mars Pathfinder - search for Martians or signs of intelligent lifeforms ◼ Time/Exam Tables Artificial Intelligence – Solving Problems by Searching Slide ‹#› Simple Example ◼ Easiest to first look at simple examples based on searching for route on a map. School Factory Hospital Newsagent Library church Park University ◼ How do we systematically and exhaustively search possible routes, in order to find, say, route from library to university? Artificial Intelligence – Solving Problems by Searching Slide ‹#› 3. Search Strategies ◼ Breadth-first search ◼ Depth-first search ◼ Depth-limited search ◼ Bi-directional search Artificial Intelligence – Solving Problems by Searching Slide ‹#› General Search Problem graph Artificial Intelligence – Solving Problems by Searching Slide ‹#›  Criteria for Evaluating Search Strategies Each of the search strategies are evaluated based on: ◼ Completeness: is the strategy guaranteed to find a solution when there is one? ◼ Time complexity: how long does it take to find a solution ◼ Space complexity: how much memory does it need to perform the search? ◼ Optimality: does the strategy find the highest- quality solution when there are several solutions? Artificial Intelligence – Solving Problems by Searching Slide ‹#›  Tree Search Space ◼ The set of all possible states reachable from the initial state defines the search space. ◼ We can represent the search space as a tree. library school hospital park newsagent factory university church Artificial Intelligence – Solving Problems by Searching Slide ‹#›  Tree Search Space parent node library Level 0 (root) children node school hospital Level 1 park newsagent factory Level 2 university church Level 3 edges Artificial Intelligence – Solving Problems by Searching Slide ‹#› Tree search complexity ◼ Parameters ◼ b: branching factor ◼ m:tree depth ◼ d: tree depth of the solution ◼ l: search depth limit Artificial Intelligence – Solving Problems by Searching Slide ‹#› Breadth first search Explore nodes in tree order: library, school, hospital, factory, park, newsagent, uni, church. (conventionally explore left to right at each level) library school hospital ◼ park newsagent factory university church Artificial Intelligence – Solving Problems by Searching Slide ‹#› Algorithm for breadth first ◼ keep track of the list of nodes found, but for which routes from them have yet to be considered. ◼ E.g., [school, hospital] -have found school and hospital in tree, but not yet considered the nodes connected to these. ◼ List is sometimes referred to as an agenda. But implemented using a queue. ◼ Queue : A list where nodes are added to the end of the list but removed from the front (first in -first out) Artificial Intelligence – Solving Problems by Searching Slide ‹#› Algorithm for breadth first: ◼ Start with queue = [initial-state] and found=FALSE. While queue not empty and not found do: Remove the first node N from queue. If N is a goal state, then found = TRUE. Find all the successor nodes of N, and put them on the end of the queue. End While Means nodes of the subsequent level Artificial Intelligence – Solving Problems by Searching Slide ‹#› Algorithm for breadth first: Exercise : Apply manually this algorithm on the previous tree and observe the evolution of the queue. And count the number of iterations in that algorithm Artificial Intelligence – Solving Problems by Searching Slide ‹#› Breadth-First Search Features ◼ Completeness: Yes ◼ Time complexity: bd ◼ Space complexity: bd ◼ Optimality: Yes Artificial Intelligence – Solving Problems by Searching Slide ‹#› Depth-First Search ◼ DFS always expands one of the nodes at the deepest level of the tree. ◼ The search only go back once it hits a dead end (a nongoal node with no expansion) ◼ DFS have modest memory requirements, it only needs to store a single path from root to a leaf node. ◼ For problems that have many solutions, DFS may actually be faster than BFS, because it has a good chance of finding a solution after exploring only a small portion of the whole space.  Depth-first search ◼ Nodes explored in order: library, school, factory, hospital, park, newsagent, university. library school hospital park newsagent factory university church  Algorithms for depth first ◼ Similar to BS but using a stack instead of a queue ◼ Stack: a list where node are added to front of to the list and also removed from the front of the list (first in-last out) Algorithm for depth first: ◼Start with stack = [initial-state] and found=FALSE. While stack not empty and not found do: Remove the first node N from stack. If N is a goal state, then found = TRUE. Find all the successor nodes of N, and put them on the end of the stack. End(While) Depth first ◼ One problem with DFS is that it can get stuck going down the wrong path. ◼ Many problems have very deep or even infinite search trees. ◼ DFS should be avoided for search trees with large or infinite maximum depths. ◼ It is common to implement a DFS with a recursive function that calls itself on each of its children in turn. Depth first: ◼ Completeness: No ◼ Time complexity: bd ◼ Space complexity: bd (better than BFS) ◼ Optimality: No ◼ DFS may suffer from non-termination when the length of a path in the search tree is infinite Artificial Intelligence – Solving Problems by Searching Slide 26 Algorithm for depth first: Exercise : Apply manually this algorithm on the previous tree. Observe the evolution of the stack , and count the number of iterations in that algorithm Searching Graphs ◼ Generally a tree cannot represent all the possible action in the search space. ◼ For example : We cannot get to the same node by different routes We cannot move in circles and get back from nodes we started from ◼ Such actions can be represented however using a Graph  Searching Graphs: problems with simple tree search algorithms ◼ Simple tree search algorithms are not appropriate for arbitrary graphs, they might cause Repeat searching same nodes of the graph Infinite loops  Searching Graphs: Example of Search repetition library Consider this graph corresponding to maps with one-way streets, but more that one route to the school hospital pahramcy park newsagent Apply the simple depth- factory first algorithm, and observe how the search progresses. Count the Pharmacy church number of iterations university Cafeteria Union  Searching Graphs: Improved search techniques ◼ The simple search techniques can be improved by avoiding exploring the nodes that have been already visited ◼ For example by storing the visited nodes in a list or an array, that will be checked at each iteration  Searching Graphs: Improved depth-first techniques ◼ Start with stack = [initial-state], found=FALSE, ◼ Visited = [ ] ◼ While stack not empty and not found do: ◼ Remove the first node N from stack ◼ If N is not in visited then ◼ Add N to visited ◼ If N is a goal state, then found = TRUE. ◼ Find all the successor nodes of N, and put them on the end of the stack. ◼ End if ◼ End(While) Searching Graphs: Improved depth-first techniques ◼ Exercise: Apply the improved version of the depth first algorithm to the previous graph. ◼ Observe the search progress and count the number of iterations. Returning the path ◼ So far the algorithms just indicate whether or not a goal (target state) exists. They do not actually return the successful path. ◼ How we can extract the path? One way: Add an agenda for paths (list of paths)  Breadth first: returning the path ◼ Start with Q_node = [initial-state] ◼ Q_path =[ initial_path], and found=FALSE. While Q_node not empty and not found do: Remove the first node N from Q_node. Remove the first path P from Q_Path. If N is a goal state, then found = TRUE. Find all the successor nodes of N, and push them in Q_node. Find all the successor nodes of the path P, and put them in Q_path End(While)  Breadth first: returning the path ◼Q_path =[ initial_path], and found=FALSE. While Q_path node not empty and not found do: Remove the first path P from Q_Path. Take the last Node N in the path Q If N is a goal state, then found = TRUE. Find all the successor nodes of the N path P, and append each to Q_path End(While) Returning the path Example: In the previous breadth first algorithm. The agenda contains initially [ {l} ] l: library After the first iteration: [{l,s}, {l,h} ] After the second iteration [ {l,s,f}, {l,h} ] After the third iteration [ {l,h,n}, {l,h,p} ,{l,s,f} ]  Depth first: returning the path ◼ Start with S_node = [initial-state] ◼ S_path =[ initial_path], and found=FALSE. While S_node not empty and not found do: Remove the first node N from Q_node. Remove the first path P from Q_Path. If N is a goal state, then found = TRUE. Find all the successor nodes of N, and push them in S_node. Find all the successor nodes of the path P, and put them in S_path End(While)