人工智能英文版课件：04 Informed Search and Exploration

1、Chapter 4 Informed Search and Exploration2OutlineInformed (Heuristic) Search StrategiesHeuristic FunctionsLocal Search Algorithms and Optimization ProblemsLocal Search in Continuous SpacesOnline Search Agents and Unknown Environments3Informed (Heuristic) Search StrategiesUninformed searchFind soluti

2、ons to problems by systematically generating new states and testing them against the goalIncredibly inefficient in most casesInformed searchUses problem-specific knowledge beyond the problem definition itselfCan find solutions more efficiently4Informed (Heuristic) Search StrategiesBest-first searchA

3、n instance of the general graph-search algorithmNode is selected for expansion based on an evaluation function f(n)The node with the lowest evaluation is selected for expansionThe evaluation measures distance to the goalBest-first search can be implemented within the general search framework via a p

4、riority queueA data structure that will maintain the fringe in ascending order of f-value5Informed (Heuristic) Search StrategiesBest-first searchIn fact, we may not really expand the best node firstIf we know which one is the best one already, no search is neededWe only expand the node appears to be

5、 the best oneIn reality, evaluation function is not exactly accurate and may lead the search astray6Informed (Heuristic) Search StrategiesHeuristic functionThere is a big family of best-first search with different evaluation functions.Heuristic function is one of the key componentsh(n) = estimated c

6、ost of the cheapest path from node n to a goal nodeThe cheapest cost between Arad and Bucharest could be estimated by their straight-line distanceAre the most common form in which additional knowledge of the problem is imparted to the search algorithmIf n is a goal node, h(n) = 07Informed (Heuristic

7、) Search StrategiesGreedy best-first searchExpand the node that is closest to the goalSounds goodwe are getting closer to the goal in each stepEvaluates nodes by using just the heuristic functionf(n) = h(n)8Informed (Heuristic) Search StrategiesStraight-line distance heuristic for driving from Arad

8、to BucharestIf goal is Bucharest, we will need to know the straight-line distances to BucharesthSLD(In(Arad) = 366hSLD can not be computed directly from the problem description (i.e. the map)From experience, the straight-line distance should be highly correlated with the driving distance9Informed (H

9、euristic) Search StrategiesArad366Mehadia241Bucharest0Neamt234Craiova160Oradea380Dobreta242Pitesti100Eforie161Rimnicu Vilcea193Fagaras176Sibiu253Giurgiu77Timisoara329Hirsova151Urziceni80Iasi226Vaslui199Lugoj244Zerind374Figure 4.1 Value of hSDLstraight-line distances to Bucharest10Informed (Heuristic

10、) Search Strategies11Informed (Heuristic) Search Strategies12Informed (Heuristic) Search Strategies13Informed (Heuristic) Search Strategies14Informed (Heuristic) Search StrategiesGreedy best-first searchStraight-line distance heuristic for driving from Arad to BucharestMinimal search costAll expande

11、d nodes are on the solution pathNot optimal solutionThe path Rimnicu Vilcea Pitesti is 32 km lessGreedy: get as close to the goal as it can at each stepMinimization of h(n) is susceptible to false startsSometimes may get in dead-end and fail to find the goal15Informed (Heuristic) Search StrategiesGr

12、eedy best-first searchFind the path from Iasi to FagarasNeamt will be expanded first, but it is a dead-endSolution: Vashi Urzuceni BucharestVashi is not selected because it is farther from the goal than that of NeamtRepeat states lead to trap of oscillate between two statesE.g. Neamt and Iasi16Infor

13、med (Heuristic) Search Strategies17Informed (Heuristic) Search StrategiesGreedy best-first searchResembles depth-first searchGo ahead on a single path until it hits a dead endSame to depth-first search, it is not optimalBecause it is incompleteWorst-case time and space complexities O(bm)Maximum dept

14、h of the search space mBranching factor bComplexity could be greatly reduced by a good heuristic18Informed (Heuristic) Search StrategiesA* searchThe most widely known best-first search methodIt combines cost of reaching the node and the cost of getting from the node to the goalf(n) = g(n) + h(n)g(n)

15、 the path cost from the start node to node nh(n) estimated cost of the cheapest path from n to the goalSo, f(n) estimated cost of the cheapest solution through n19Informed (Heuristic) Search StrategiesA* searchWe are trying to find the cheapest solution directlyReasonableCompleteOptimalA* is optimal

16、 if h(n) is an admissible heuristicProvided that h(n) never overestimates the cost to reach the goalAdmissible heuristics are by nature optimisticThe straight-line heuristic is admissibleThe shortest path between two cities is a straight-line20Informed (Heuristic) Search StrategiesA* searchThe value

17、 of g(n) is computed from the step cost and the value of hSLDIn the 5th step, Bucharest appears but is not selected becausef-cost of Bucharest = 450f-cost of Pitesti = 417 Although we arrived the goal, it may not be the optimal oneThe algorithm does not settle to a easier solution with higher cost,

18、so it will find the optimal solution21Informed (Heuristic) Search Strategies22Informed (Heuristic) Search Strategies23Informed (Heuristic) Search Strategies24Informed (Heuristic) Search Strategies25Informed (Heuristic) Search Strategies26Informed (Heuristic) Search Strategies27Informed (Heuristic) S

19、earch StrategiesA* searchLet C* to be the cost of the optimal solutionG2 is a suboptimal solution, h(G2) = 0f(G2) = g(G2) + h(G2) = g(G2) C*If we are on the optimal solution pathf(n) = g(n) + h(n) C*Owing to f(n) C* f(G2), G2 will not be expandedSo, A* must return the optimal solution28Informed (Heu

20、ristic) Search StrategiesA* searchThis is good with tree-search algorithmHowever, it breaks down when graph-search is usedSuboptimal solutionRepeated states are discardedOptimal solution may be discarded if its goal state is not the first one being generated There are two ways to deal with it29Infor

21、med (Heuristic) Search Strategies2 SolutionsModify the graph-search algorithm to discard the more expensive repeated nodeNeed to keep extra informationLeads to optimal solutionEnsure that the optimal path to any repeated state is always the first one followedSame to the case with uniform-cost search

22、Impose consistency (monotonicity) requirement on h(n)30Informed (Heuristic) Search StrategiesConsistencyA heuristic is consistent if, for every node n and every successor n of n generated by any action a, the estimated cost of reaching the goal from n is no greater than the step cost of getting to n

23、 plus the estimated cost of reaching the goal from n This is a form of the general triangle inequalityEach side of a triangle cannot be longer than the sum of the other two sidesAll consistent heuristics are admissiblenClosest goal of nn31Informed (Heuristic) Search StrategiesA* search using graph-s

24、earch is optimal if h(n) is consistencyConsistency is stricter requirement than admissibilityAdmissible: h(n) never overestimates the cost to reach the goalIn fact, this is quite hard to produce heuristics that are admissible but not consistenthSLD is consistentThe general triangle inequality is sat

25、isfied when each side is measured by the straight-line distance32Informed (Heuristic) Search StrategiesIf h(n) is consistency, then the values of h(n) along any path are nondecreasingSuppose n is a successor of n, for some action a:The sequence of nodes expanded by A* with graph-search is in nondecr

26、easing order of f(n). So, the first goal node selected must be an optimal solution33Informed (Heuristic) Search StrategiesContours in the state spaceThe fact that f-costs are nondecreasing along any pathLike the contours in a topographic mapInside the contour labeled 400, all nodes have f(n) less th

27、an or equal to 400The search of A* is similar to walking upward from the valley34Informed (Heuristic) Search Strategies35Informed (Heuristic) Search StrategiesContours in the state spaceWith the uniform-cost search, the bands will be circular around the start stateA* using h(n) = 0With more accurate

28、 heuristics, the bands will stretch toward the goal state and become more narrowly focused around the optimal pathIf C* is the cost of the optimal solution pathA* expands all nodes with f(n) C*A* might then expand some of the nodes (f(n) = C*) right on the “goal contour” before selecting a goal node

29、36Informed (Heuristic) Search StrategiesA* is optimally efficientAlgorithm that extend search path from the root, A* is optimally efficient for any given heuristic functionNo other optimal algorithm is guaranteed to expand fewer nodes than A*Except possibly through tie-breaking among nodes with f(n)

30、 = C*That is, the one finds out optimal solution among all nodes with the same cost in a faster way37Informed (Heuristic) Search StrategiesSubtree pruningEliminating possibilities from consideration without having to examine themTimisoara is not expanded even though it is a child of the rootThe subt

31、ree below Timisoara is prunedBecause hSLD is admissible, the algorithm can safely ignore this subtree while still guaranteeing optimality38Informed (Heuristic) Search StrategiesA* searchFor most problems, the number of nodes within the goal contour search space is still exponential in the length of

32、the solutionThe exponential growth will occur unless the error in the heuristic function grows no faster than the logarithm of the actual path costwhere h*(n) is the true cost of getting from n to the goalThe error is at least proportional to the path cost for almost all heuristic in practical useTh

33、e resulting exponential growth eventually overtakes any computer39Informed (Heuristic) Search StrategiesA* searchSo, it is often impractical to insist on finding an optimal solutionVariants of A* could find suboptimal solutions quicklyOr one can sometimes design heuristics that are more accurate, bu

34、t not strictly admissibleFor all cases, a good heuristic still provides huge savings compared to uninformed searchThe major drawback of A* is its computation timeIt keeps all generated nodes in memoryA* usually runs out of space long before it runs out of timeA* is not practical for large scale prob

35、lems40Informed (Heuristic) Search StrategiesMemory-bounded heuristic searchIterative-deepening A* (IDA*) algorithmAdapt the idea of iterative deepening to the heuristic search to reduce its memory requirementsThe cutoff used is the f-cost (g + h) rather than the depthPractical for many problems with

36、 unit step costsAvoid the substantial overhead associated with keeping a sorted queue of nodesMay have infinitely many iterations with real-valued costs41Informed (Heuristic) Search StrategiesRecursive best-first search (RBFS)Simple recursive algorithm that attempts to mimic the operation of standar

37、d best first search, but using only linear spaceSimilar to that of a recursive depth-first search, but it will not continuing indefinitely down the current pathIt keeps track of the f-value of the best alternative path available from any ancestor of the current nodeReplace the f-value of each node a

38、long the path with the best f-value of its children during the recursionSo, RBFS remembers the f-value of the best leaf in the forgotten subtree and can therefore decide whether it is worth re-expanding the subtree later42Informed (Heuristic) Search Strategies43Informed (Heuristic) Search Strategies

39、44Informed (Heuristic) Search Strategies45Informed (Heuristic) Search Strategies46Informed (Heuristic) Search StrategiesRecursive best-first search (RBFS)RBFS is somewhat more efficient than IDA*Still suffers from excessive node regenerationRBFS changes mind oftenEach mind change corresponds to an i

40、teration of IDA*Could require many re-expansions of forgotten nodes Every time the current best path is extended, there is a good chance that its f-value will increaseIn large search spaces, the second-best path might become the best pathThe search has to backtrack to follow it47Informed (Heuristic)

41、 Search StrategiesRecursive best-first search (RBFS)Optimal if the heuristic function is admissibleIts space complexity is linear in the depth of the deepest optimal solutionDifficult to characterize its time complexityDepend on the accuracy of the heuristic functionDepend on how often the best path

42、 changes as nodes are expandedBoth RBFS and IDA* are subject tot the potentially exponential increase in complexity associated with searching on graphCan not check for repeated states other than those on the current path48Informed (Heuristic) Search StrategiesMemory-bounded A* (MA*)IDA* and RBFS bot

43、h suffer from using too little memoryBetween iterations, IDA* retains only a single numberThe current f-cost limitRBFS retains more information in memory, but it uses only liner spaceEven if more memory were available, RBFS has no way to make use of itMA* and Simplified MA* use all available memory4

44、9Informed (Heuristic) Search StrategiesSimplified Memory-bounded A* (SMA*)Proceeds just like A*, expanding the best leaf until memory is fullIt can not add any more node to the search tree without dropping an old oneSMA* always drops the worst leaf nodeThe one with the highest f-valueLike RBFS, SMA*

45、 then backs up the value of the forgotten node to its parentAncestor of a forgotten subtree knows the quality of the best path in that subtree how worthwhile it is for revisitingSMA* regenerate the subtree only when all other paths have been shown to look worse than that in the forgotten subtree50In

46、formed (Heuristic) Search StrategiesSimplified Memory-bounded A* (SMA*)What if all nodes have the same f-value?The same node may be deleted and expanded in the same iterationSolved by expanding the newest node and deleting the oldest node among those nodes with the same f-valueThe only case that it

47、will still expand and delete the same nodeThere is only a single path from the root and fill all the memoryIf this node is not the goal node, even if it is on an optimal solution path, that solution is not reachable with the available memory51Informed (Heuristic) Search StrategiesSimplified Memory-b

48、ounded A* (SMA*)SMA* is complete if there is any reachable solutionSMA* is optimal if any optimal solution is reachableMight be the best general-purpose algorithm for finding optimal solution when the state space is a graphStep costs are not uniformNode generation is expensive compared to the additi

49、onal overhead of maintaining the open and closed lists52Informed (Heuristic) Search StrategiesSimplified Memory-bounded A* (SMA*)In difficult problems, SMA* is forced to switch back and forth continually between a set of candidate solution pathsOnly a small subset of which an fit in memoryExtra time

50、 required for regeneration of the same nodes means that problem that would be practically solvable by A*, given unlimited memory, become intractable for SMA*Memory limitations can make a problem intractable from the point of view of computation timeThere is no theory to guide the tradeoff between ti

51、me and memoryThe only way is to drop the optimality requirement53Informed (Heuristic) Search StrategiesLearning to search betterCould an agent learn how to search better?The method rests on an important concept called the metalevel state spaceEach state in a metalevel state space captures the intern

52、al state of a problem that is searching in an objective-level state space (e.g. our map for driving path finding)54Informed (Heuristic) Search StrategiesExampleThe internal state of the A* algorithm consists of the current search treeEach action in the metalevel state space is a computation step tha

53、t alters the internal stateE.g. expanding a nodeThe process of expanding the search tree in previous slides can be viewed as depicting a path in the metalevel state spaceEach state on the path is an object-level search tree55Informed (Heuristic) Search StrategiesMetalevel learningwe expanded a node

54、that is not on the solution pathSome missteps may not be helpful Metalevel learning algorithm can learn from these experiences to avoid exploring unpromising subtreesThe goal of learning is to minimize the total cost of problem solving, trading off computational expense and path cost56Informed (Heur

55、istic) Search StrategiesMetalevel learningwe expanded a node that is not on the solution pathSome missteps may not be helpful Metalevel learning algorithm can learn from these experiences to avoid exploring unpromising subtreesThe goal of learning is to minimize the total cost of problem solving, tr

56、ading off computational expense and path cost57Heuristic FunctionHeuristic for 8-puzzleObjective of 8-puzzleSliding tiles horizontally or vertically into the empty space until the configuration matches the goal configuration (state)58Informed (Heuristic) Search StrategiesHeuristic for 8-puzzleAverag

57、e solution cost for a randomly generated 8-puzzle instance is about 22 stepsBranching factor is about 3Exhaustive search to depth 22 would look at about 322 states, about 3.1 x 1010 statesWe could reduce it to about 170000 states by keeping track of repeated statesHowever, the number of states witho

58、ut repeating is still roughly 1013What can we do?59Informed (Heuristic) Search StrategiesHeuristic for 8-puzzle with A* searchWe need a good heuristic which will not overestimate the number of steps to the goalHeuristics for 15-puzzleh1 = the number of misplaced tilesIn our example, h1 = 8It is admi

59、ssible because every misplaced tile will be moved at least onceh2 = the sum of distances of the tiles from their goal positions Tiles can not be moved diagonally, so we count the number of vertical and horizontal move requiredAdmissible because every move can do is move one tile one step closer to t

60、he goalIn our example, h2 = 3 + 1 +2 + 2 + 2 + 3 +3 +2 = 18Neither of them overestimates the true solution cost (26)60Informed (Heuristic) Search StrategiesEffective branching factor b*If the total number of nodes generated by A* for a particular problem is N and the solution depth is d, then b* is