Introduction to AI - Week 8 Search Represent a search problem as: * a state space that contains all possible configurations, (with start state and goal state) * a set of operators for manipulating states * start state and goal state (or a goal test) * path costs for measuring the cost going along a path _________________________________________________________________________________________________________ The Blocks World Blocks World: classical planning scenario: blocks that stand on a table or stand on top of each other or are hold by a robot hand (mutual relationship disregarded otherwise) and can be manipulated by a robot hand Description by predicates of the form Ontable(x) x stands on the table On(x,y) x stands on y Clear(x) nothing stands on x Handempty robot hand is empty Holds(x) robot hand holds x 0 0 0 100000000000000000000000 0 01 0 0 01 0 0 01 0 0 01 0 0 01 00001 0 100000000000000000000000 01 01 01 0 0 0 01 0 0 0 0 01 10 1 0 0 0 01 0000 0 0 0 01 0 0 0 01 0 0 0 01 0 1 1 0 0 000000000000000000000010 0 0 01 0 01 0 01 0 01 00000 0 01 0 10 0 01 0 00 0 01 01000 0 01 0 01 0 01 0 0 0 000000000000000000000010 000000000000000000000001 0 0 0 0 01 0 0 10 01 0 0 10 01 0 0 10 01 0000 0 0 000001 10 01 1 0 0 0 0 0 10 01 0 10 0 0 01000 10 01 0 10 0 0 0 01 10 01 000 1001 0 0 00000 10 01 0 0 10 01 0 0 10 01 0 0 10 111111111111111111 01 1111111111111111111 0 11111111111111111111111 0 1111111111111111111 10 11111111111111111111111111 Ontable(A) Ontable(B) On(D,A) On(C,D) Clear(C) Clear(B) Handempty _________________________________________________________________________________________________________ What is a "Search Problem"? Planning problem is given by initial state & goal state, e.g., goal: 0 0 0 0 0 0 00000000000000000000011 0 10 0 0 10 0 00000000000000000000000 10 0 0 0 10 0 0 0 10 0001 0 0 0 10 1 0 0 0 0 10 0 00 0 0 0 10 0 0 0 0 0 10 001 00 0 10 0 10 0 10 0 10 1111111111111111111 0 10 0 10 0 10 0 10 0 10 10000 0 10 0 0 0 10 0 0 0 10 0 0 0 10 0000 0 10 0 10 0 10 0 10 1111111111111111111 0 11111111111111111111111 10 1 0 0 11 0 10 0 0 0 10 0 0 0 10 0 0 0 10 01011 0 0 000 0 10 01 0 0 0 00 00 0 10 00010 0 0 10 0 10 0 0 0 0 0 1 0 10 00000 0 0 00001 0 10 0 0 0 10 0 0 0 10 0 0 0 11111111111111111111111 10 1111111111111111111 0 1111111111111111111111 0 1111111111111111111 0 111111111111111111111 Ontable(B) Ontable(C) On(D,B) On(A,D) Clear(A) Clear(C) Handempty For this transition are certain operators available. In blocks world PICKUP(x) picking up x from the table PUTDOWN(x) putting down x on the table STACK(x,y) putting x on y UNSTACK(x,y) picking up x from y Formalise operators! Find plan _________________________________________________________________________________________________________ Operators of the Blocks World -------- ------------- ------------- PICKUP(x) preconditions Clear(x) Ontable(x) Handempty delete list Clear(x) Ontable(x) Handempty add list Holds(x) PUTDOWN(x) preconditions Holds(x) delete list Holds(x) add list Clear(x) Ontable(x) Handempty -------- ------------- ------------- STACK(x,y) preconditions Holds(x) Clear(y) delete list Holds(x) Clear(y) add list Clear(x) On(x,y) Handempty UNSTACK(x,y) preconditions Clear(x) On(x,y) Handempty delete list Clear(x) On(x,y) Handempty add list Holds(x) Clear(y) -------- ------------- ------------- _________________________________________________________________________________________________________ General search algorithm function general-search(problem,insert) -> solution ;;; insert is a function to determine, where to ;;; insert the nodes which are newly expanded insertion-function(init(problem)) -> nodes while not null(nodes) or not goal-test(problem)(node) do first(nodes) -> node insert(nodes,expand(node,operators(problem))) -> nodes remove(node,nodes) -> nodes od if null(nodes) then failure else node -> solution _________________________________________________________________________________________________________ Breadth-first search Breadth-first is given by: insert appends the new nodes to the end of nodes Example: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 1 1 1 1 1 11 1 2 3 2 3 2 3 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 4 5 4 5 6 7 Breadth-first search finds optimal solutions implemented as Queue ("First in First Out") _________________________________________________________________________________________________________ An Example for Breadth-first search --- INIT B | | A c -------------- 1 1 1 111 11 1 111 2 01010 0110101 01 0 1100010 01101011 1100101 11010100 00010101 101010100 --- --- B |C| |B| A A C ---------------- -------------- 0 0 5 10110 0 7 3 10 001 4 11010101 1 1000 10 001 10101011 01 1001 00 000 01101010 00 6 0000 01 1 001 00 10 ---- --- --- --- --- C | | | | | | | | B | | B B B A C A A B C A C A C ----------- ----------- ------------- ------------ ------------------ 1 100 01 0 0 10 0 00 01 0 10 1 8 0 01 9 10 0 11 0 1 01 13 14 11 1 15 16 10 01 17 0 10 1 0 0 00 00 1 00 00 10 01 00 00 0 12 101 10 0 0 11 101 100 01 0 1 --- GOAL |A| B C ---------------- _________________________________________________________________________________________________________ Depth-first search Depth-first is given by: insert inserts the new nodes at the front of nodes Example: (assume no expansion possible when no successor) 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 11 11 1 1 1 11 1 1 1 1 1 1 1 1 1 1 1 11 1 11 11 1 1 1 1 1 1 1 1 1 1 1 1 1 2 3 2 3 2 3 2 3 2 3 2 3 1 1 1 1 1 1 1 1 1 1 1 1 1 1 4 5 4 5 5 5 5 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 6 7 8 9 8 9 8 9 1 1 1 1 1 1 1 1 10 11 10 11 1 1 1 1 12 13 Depth-first search can fail to find solutions implemented as Stack ("Last in First Out") _________________________________________________________________________________________________________ An Example for Depth-first search --- INIT B | | A c -------------- 1 1 1 111 11 1 111 01010 0110101 01 0 1100010 01101011 1100101 11010100 00010101 101010100 --- --- B |C| |B| A A C ---------------- -------------- 0 0 2 10 001 10 001 00 000 01 1 ---- --- C | | B | | B A C A ----------- ----------- 1 01 0 3 0 01 0 10 10 01 101 100 --- GOAL |A| B C ---------------- _________________________________________________________________________________________________________ Depth Limited Depth First As depth first, but do not generate nodes deeper in the tree than an a priori fixed limit. 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 LIMIT L=3 11 1 11 1 1 11 11 11 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 3 2 3 2 3 2 3 3 3 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 4 5 4 5 5 10 11 10 11 1 1 1 1 1 1 1 1 1 1 1 1 6 7 8 9 12 13 If there is no solution within limit l, then no solution will be found. _________________________________________________________________________________________________________ Iterative Deepening * Depth-Limited Search has the main advantage that the search process can't descend forever (in a branch without solution). * However, it will not find a solution if all solutions require a depth greater than the limit. * To overcome this problem (and to maintain the advantages of depth limited depth first search), one has introduced a form in which the limit is increased if there is no solution of a limit l. That is, choose initially l=1, iteratively increase l by 1, and perform on each level Depth Limited Depth First search until a solution is found. _________________________________________________________________________________________________________ Bi-Directional Search In bi-directional search, start the process simultaneously from the initial start and backwards from the goal state, in order to reduce the complexity. UNI-DIRECTIONAL BI-DIRECTIONAL START X START X 00 0 0 11 01 1111 0 1111 00 11111 0 1111 00 1111 01 111 00 111 100 11 0101 111 010 11 0110 1 00110 10110 0011100 101100 1001111100 1 0110 1 10011111111100 11 1010 11 0001111111111111001 111 000 11 100001111111111111111100001 1111 00 111 11000000000000000011100000000000000001 1111 00 11111 11 1111 10 1111 10 1111 x X GOAL GOAL The shaded area corresponds to the search effort _________________________________________________________________________________________________________ Avoiding Repeated States The safest way to avoid any repeated states is to store all states visited and compare each node whether it has been visited before. If yes, don't add it. The problem with this strategy is that firstly you have to store all states visited (space) and make many comparisons (time). Cheaper (albeit incomplete) forms are: * Do not return to the state you came from. That is, do not generate a node that is equal to your parent. * Do not create cycles. That is, do not generate a node that is equal to any of your ancestors. _________________________________________________________________________________________________________ Heuristic Search Assume a heuristic function h such that h(n) is the estimated cost of the cheapest path from the state at node n to a goal state. In best-first-search the insertion function orders the nodes with respect to some measure. function Best-First-Search(problem,eval-function) -> solution ;;; input: a problem and an evaluation function function orders nodes by eval-function -> queue-function general-search(problem,queue-function) -> solution _________________________________________________________________________________________________________ Greedy Search and A^*-Search greedy-search: insert best nodes at beginning of nodes according to h, that is, function Greedy-Search(problem) -> solution ;;; input: a problem best-first-search(problem,h) -> solution A^*-search: insert best nodes at beginning of nodes according to f=g+h with g actual cost to that node, h estimated cost to the goal. In the A^* algorithm the heuristic function h must be optimistic in order to find the best solution. function A-star(problem) -> solution ;;; input: a problem best-first-search(problem,g+h) -> solution _________________________________________________________________________________________________________ Example Assume you wanted to search for the shortest path from Arad to Bucharest (taken from [Russell-Norvig 2003]) ORADEA 000 NEAMT 71 0 0 000 87 0 01 11 000000 10 10 10001 IASI ZERIND 100 0 000 00 00 151 0 0 0 00 92 75 0 01 00 11 00 0 0 0 00 ARAD 000000000000000111111 01 SIBIU 99 FAGARAS 00 0 111 0000000011 0 01 0 140 0 11000001100000000 00 VASLUI 0 00 000 0 0 80 0 01 0 118 0 0 00 0 0 RIMNICU VILCEA 00 01 0 0 0 10 01 142 0 1001 00 11 100 0 00 97 10 0 000 TIMISOARA 0 0001 01 211 0 1001 0 000 PITESTI 10 0 0001 0 100 00 01 1000 0 1000 10 0 98 HIRSOVA 111 000 LUGOJ 0 1 1001 00 0 01 0 01 1000 10 85 100000000111000001100 0 0 146 0 000 00 0 0 70 0 0 0 101 000 0 00 URZICENI 1 01 0 10 000 01 01 1 MEHADIA 000 0 01 000000 0 0 0 01 001 0 75 0 0 0 138 0 BUCHAREST 86 0 0 120 0 0 0 0 000 0 10 10 0 DOBRETA 000000000100110000011 1 0000 00 10 1111100 01 90 11 0 000 CRAIOVA 1 0 100 1 000 GIURGIU EFORIE Task: Find path from Arad to Bucharest _________________________________________________________________________________________________________ Heuristic: Air distance Town Air Dist. Arad 366 Bucharest 0 Craiova 160 Dobreta 242 Eforie 161 Fagaras 176 Giurgiu 77 Hirsova 151 Iasi 226 Lugoj 244 Mehadia 241 Neamt 234 Oradea 380 Pitesti 100 Rimnicu Vilcea 193 Sibiu 253 Timisoara 329 Urziceni 80 Vaslui 199 Zerind 374 _________________________________________________________________________________________________________ Greedy Search in the Example Possibilities from Arad: Go to Zerind, Timisoara, or Sibiu? Take as heuristic the air distance: Zerind (374), Timisoara (329), or Sibiu (253) Closest air distance Sibiu, hence go to Sibiu. Possibilities from Sibiu: Arad, Fagaras, Oradea, or Rimnicu Vilcea? Take as heuristic the air distance: Arad (366), Fagaras (176), Oradea (380), or Rimnicu Vilcea (193) Closest air distance Fagaras, hence go to Fagaras. Possibilities from Fagaras: Go to Sibiu or Bucharest? Take as heuristic the air distance: Sibiu (253) or Bucharest (0)? Closest air distance Bucharest, hence go to Bucharest. That is 140km +99km +211km = 450km . _________________________________________________________________________________________________________ Greedy Search in the Example (Cont'd) ARAD 1 366 0100000111 101 101111110000011 00 11101 1000000001 00 10001 1000000001 10 SIBIU TIMISOARA ZERIND 353 329 374 1001 100111111 0001 11 001 0000001 000 11 000 1000001 1000 11 000 0000000 0001 11 000 1000001 100 11 000 0000000 11 1 ARAD FAGARAS ORADEA RIMNICU VILCEA 366 176 380 193 1000 00 100 00 10 00 00 00 00 00 00 SIBIU BUCHAREST 253 0 _________________________________________________________________________________________________________ A^*-Search in the Example Possibilities from Arad: Go to Zerind, Timisoara, or Sibiu? Take as heuristic the air distance plus cost to town: Zerind (374+75=449), Timisoara (329+118=447), or Sibiu (253+140=393) Most promising Sibiu, hence explore going to Sibiu. Possibilities from Sibiu: Arad, Fagaras, Oradea, or Rimnicu Vilcea? Take as heuristic the air distance plus cost to town: Arad (140+140+366=646), Fagaras (140+99+176=415), Oradea (140+151+380=671), or Rimnicu Vilcea (140+80+193=413) Overall most promising not expanded Rimnicu Vilcea, hence explore going to Rimnicu Vilcea _________________________________________________________________________________________________________ A^*-Search in the Example (Cont'd) Possibilities from Rimnicu Vilcea: Sibiu, Pitesti, or Craiova? Take as heuristic the air distance plus cost to town: Sibiu (140+80+80+253=553), Pitesti (140+80+97+100=417), or Craiova (140+80+146+160=526) Overall most promising not expanded Fagaras, hence explore going to Fagaras (from Sibiu) Possibilities from Fagaras: Sibiu, or Bucharest? Take as heuristic the air distance plus cost to town: Sibiu (140+99+99+253=591), or Bucharest (140+99+211+0=450) Overall most promising not expanded Pitesti, hence explore going to Pitesti (from Rimnicu Vilcea) _________________________________________________________________________________________________________ A^*-Search in the Example (Cont'd) Possibilities from Pitesti: Rimnicu Vilcea, Craiova, or Bucharest? Take as heuristic the air distance plus cost to town: Rimnicu Vilcea (140+80+97+97+193=607), Craiova (140+80+97+138+160=615) or Bucharest (140+80+97+101+0=418) Overall most promising go to Bucharest from Pitesti. Since there is no way to get on a shorter route to Bucharest the last one is taken. _________________________________________________________________________________________________________ A^*-Search in the Example (Cont'd) ARAD 1 366 0100000111 101 101111110000011 00 11101 1000000001 00 10001 1000000001 10 SIBIU TIMISOARA ZERIND 393 447 449 1001 100111111 0001 11 001 0000001 000 11 000 1000001 1000 11 000 0000000 0001 11 000 1000001 100 11 000 0000000 11 1 ARAD FAGARAS ORADEA RIMNICU VILCEA 646 415 617 413 1000 100001 00 100 00 0 000 00 10 00 11 1000 1 00 00 101 0 000 00 00 001 0 0001 00 00 00 10 01 SIBIU BUCHAREST CRAIOVA PITESTI SIBIU 591 450 526 417 533 100 001000 001 1 111 001 1 1000 001 1 0001 001 1 000 000 1 1000 000 1 00 10 BUCHAREST CRAIOVA RIMNICU VILCEA 418 615 607 _________________________________________________________________________________________________________ Properties of the A^*-Algorithm * Restriction on h: the heuristic function h may never overestimate the cost to reach the goal (such a heuristic is called admissible. Example: h as air distance is an optimistic estimate for a travel distance. * If h is admissible, then f=g+h is as well. * Along any path from the root, the f-cost never decreases, that is f is monotonic * If h is admissible, the search tree is finitely branching (and there is a solution), then the A^*-algorithm finds an optimal solution _________________________________________________________________________________________________________ Hill-Climbing and Simulated Annealing * Hill climbing is a search method, in which the next node to expand, is the node with the highest value of the nodes generated from the expansion of the current node. * Problems with hill-climbing: + local maxima (algorithm misses the total maximum) + plateaux (the evaluation function is flat and is not informative) + ridges (saddle shaped area, oscillation, without finding the way further up may happen) * Solutions: + Random restart hill-climbing + Simulated annealing: Allow for bad moves as well (that is, moves that lead down-hill), where the probability of such a move decreases exponentially with its badness. With decreasing temperature T, bad moves become less and less likely. _________________________________________________________________________________________________________ Heuristics in the Blocksworld Problem: Find a heuristic function h for estimating how far the current state is from goal state: * differences in Ontable(x) considered particularly high * differences in Handempty and Holds(x) very low * Optimally, the differences for On(x,y) would be considered the more the lower in a tower x and y are In the extreme case, the heuristic function exactly knows what to do. Then there is no search, but we have an algorithmic procedure. _________________________________________________________________________________________________________ Properties of Some Search Algorithm * Completeness: solution will eventually be found if there is one at all * Optimality: does it find the highest-quality solution when there are several * Time complexity: time to find a solution as function of the complexity of the problem * Space complexity: how much memory is necessary for the search as function of the complexity of the problem _________________________________________________________________________________________________________ Properties of Search Algorithms (Cont'd) Breadth-first Depth-first Greedy A^* -------- ------------- ------------- Complete Yes No No Yes Optimal Yes No No Yes Time exponential exponential exponential exponential Space exponential linear linear exponential Further Reading books-shelf1.jpg] * S. Russell, P. Norvig. Artificial Intelligence - A Modern Approach. 2nd Edition, Pearson Education, 2003. Chapters 3 & 4. * Judea Pearl: Heuristics - Intelligent Search Strategies for Computer Problem Solving, Addison-Wesley, 1984. Reading, Massachusetts. _________________________________________________________________________________________________________ _________________________________________________________________________________________________________ © Manfred Kerber, 2004, Introduction to AI 22.12.2004 The URL of this page is http://www.cs.bham.ac.uk/~mmk/Teaching/AI/Teaching/AI/l8.html. URL of module [1]http://www.cs.bham.ac.uk/~mmk/Teaching/AI/ References 1. http://www.cs.bham.ac.uk/~mmk/Teaching/AI/