1CS 2710 Foundations of AICS 2710 Foundations of AILecture 5Milos [email protected] Sennott SquareInformed (heuristic) search (cont). Constraint-satisfaction search.CS 2710 Foundations of AIAdministration• PS–1 due today– Report before the class begins– Programs through ftp• PS-2 is out– due next week on Tuesday, September 21, 2004• Report• Programs2CS 2710 Foundations of AIEvaluation-function driven search• A search strategy can be defined in terms of a node evaluation function• Evaluation function– Denoted– Defines the desirability of a node to be expanded next• Evaluation-function driven search: expand the node (state) with the best evaluation-function value• Implementation: priority queue with nodes in the decreasing order of their evaluation function value)(nfCS 2710 Foundations of AIUniform cost search• Uniform cost search (Dijkstra’s shortest path):– A special case of the evaluation-function driven search•Path cost function ; – path cost from the initial state to n• Uniform-cost search:– Can handle general minimum cost path-search problem:–weights or costs associated with operators (links).•Note: Uniform cost search relies on the problem definition only– It is an uninformed search method)(ng)()( ngnf=3CS 2710 Foundations of AIBest-first searchBest-first search• incorporates a heuristic function, , into the evaluation function to guide the search. Heuristic function:• Measures a potential of a state (node) to reach a goal• Typically in terms of some distance to a goal estimateExample of a heuristic function:• Assume a shortest path problem with city distances on connections• Straight-line distances between cities give additional information we can use to guide the search)(nf)(nhCS 2710 Foundations of AIExample: traveler problem with straight-line distance information• Straight-line distances give an estimate of the cost of the path between the two cities3661604CS 2710 Foundations of AIBest-first searchBest-first search • incorporates a heuristic function, , into the evaluation function to guide the search. •heuristic function: measures a potential of a state (node) to reach a goalSpecial cases (differ in the design of evaluation function):–Greedy search– A* algorithm+ iterative deepening version of A* : IDA*)(nf)()( nhnf=)()()( nhngnf+=)(nhCS 2710 Foundations of AIGreedy search method• Evaluation function is equal to the heuristic function•Idea: the node that seems to be the closest to the goal is expanded first)()(nhnf=5CS 2710 Foundations of AIProperties of greedy search• Completeness: No. We can loop forever. Nodes that seem to be the best choices can lead to cycles. Elimination of state repeats can solve the problem.•Optimality: No.Even if we reach the goal, we may be biased by a bad heuristic estimate. Evaluation function disregards the cost of the path built so far. •Time complexity:• Memory (space) complexity:)(mbO)(mbOWorst case !!! But often better!Often better!CS 2710 Foundations of AIExample: traveler problem with straight-line distance information• Greedy search resultTotal: 4506CS 2710 Foundations of AIExample: traveler problem with straight-line distance information• Greedy search and optimalityTotal: 450Total: 418CS 2710 Foundations of AIA* search• The problem with the greedy search is that it can keep expanding paths that are already very expensive.• The problem with the uniform-cost search is that it uses only past exploration information (path cost), no additional information is utilized•A* search• Additional A*condition: admissible heuristic)()()( nhngnf+=)(ng- cost of reaching the state)(nh- estimate of the cost from the current state to a goal)(nf- estimate of the path length)()(*nhnh ≤for all n7CS 2710 Foundations of AIA* search exampleArad366f(n)queueArad 366CS 2710 Foundations of AIA* search exampleAradZerind SibiuTimisoara36675140118449 393 447queueSibiu 393Timisoara 447Zerind 449f(n)8CS 2710 Foundations of AIA* search exampleAradZerindSibiuTimisoara75140118Zerind SibiuFagarasRimnicuVilceaOradeaArad366140151 99 80646 526417 413449 393 447Rimnicu V. 413Fagaras 417Timisoara 447Zerind 449Oradea 526Arad 646queuef(n)CS 2710 Foundations of AIA* search exampleAradZerindSibiuTimisoara75140118Zerind SibiuFagarasRimnicuVilceaOradeaArad366140151 99 80646 526417413449 393 447PitestiSibiuCraiova526415553146 97 80447Pitesti 415Fagaras 417Timisoara 447Zerind 449Oradea 526Craiova 526Sibiu 553Arad 646queuef(n)9CS 2710 Foundations of AIA* search exampleAradZerindSibiuTimisoara75140118Zerind SibiuFagarasRimnicuVilceaOradeaArad366140151 99 80646 526417413449 393 447PitestiSibiuCraiova526415 553146 97 80CraiovaBucharest60761541897 138 101RimnicuVilcea447447Fagaras 417Bucharest 418Timisoara 447Zerind 449Oradea 526Craiova 526Sibiu 553Rimnicu V. 607Arad 646queuef(n)CS 2710 Foundations of AIA* search exampleAradZerindSibiuTimisoara75140118Zerind SibiuFagarasRimnicuVilceaOradeaArad366140151 99 80646 526417413449 393 447PitestiSibiuCraiova526415 553146 97 80CraiovaBucharest60761541897 138 101RimnicuVilcea447447Bucharest 418Timisoara 447Zerind 449Oradea 526Craiova 526Sibiu 553Rimnicu V. 607Arad 646queuef(n)BucharestSibiu21199591 45010CS 2710 Foundations of AIA* search exampleAradZerindSibiuTimisoara75140118Zerind SibiuFagarasRimnicuVilceaOradeaArad366140151 99 80646 526417413449 393 447PitestiSibiuCraiova526415 553146 97 80CraiovaBucharest60761541897 138 101RimnicuVilcea447447Timisoara 447Zerind 449Oradea 526Craiova 526Sibiu 553Rimnicu V. 607Arad 646queuef(n)BucharestSibiu21199591 450Goal !!CS 2710 Foundations of AIProperties of A* search• Completeness: ? • Optimality: ? • Time complexity:– ?• Memory (space) complexity:– ?11CS 2710 Foundations of AIProperties of A* search• Completeness: Yes.• Optimality: ?• Time complexity:– ?• Memory (space) complexity:– ? CS 2710 Foundations of AIOptimality of A*• In general, a heuristic function :It can overestimate, be equal or underestimate the true distance of a node to the goal • Is the A* optimal for an arbitrary heuristic function?)(*nh)(nh12CS 2710 Foundations of AIOptimality of A*• In general, a heuristic function :Can overestimate, be equal or underestimate the true distance of a node to the goal • Is the A* optimal for an arbitrary heuristic function?•No !• Admissible heuristic condition–