The Optimality of A*

1 The Optimality of A*Presented byJarrell Waggoner&Jimmy Cleveland12/09/08 Overview1 IntroductionBasics ofA and definitions that will be used throughout thispresentation2 Dimensions of AnalysisThe contenders withA , the scoring system, and the problemsthat will be compared3 AnalysisExploration of two theorems that show the power, andlimitations ofA 4A A reformulation that solves some of the shortcomings ofA 5 ConclusionOverview of some of the other finding of this paper, andreferencesIntroductionDimensions of AnalysisAnalysisA ConclusionInformed SearchUninformed search:no information about the goal state,other than if it has been reached yetInformed search:some heuristic information about the goalstate is available at each node in the graphUninformed Search Informed SearchDepth-firstBest-firstBreadth-first A DijkstraPresented by Jarrell Waggoner & Jimmy ClevelandThe Optimality of A*IntroductionDimensions of AnalysisAnalysisA ConclusionIntroduction to A*Historical NotesA :Created in 1968 A Formal Basis for the Heuristic Determination ofMinimum Cost Paths Authored by Peter Hart, Nils Nilsson, and BertramRaphaelIn the original paper, the algorithm we now know asA wassimply labeled Algorithm A.

2 Since the star ( ) is used todenote Optimality , and Algorithm A was optimal when given anadmissible heuristic, it became known asA .Presented by Jarrell Waggoner & Jimmy ClevelandThe Optimality of A*IntroductionDimensions of AnalysisAnalysisA ConclusionIntroduction to A*Introduction to A*1:Put the start node,s, on a list calledOPENof unexpanded nodes2:if|OPEN|= 0then3:Exit no solution exists4:Remove a nodenfromOPEN, at whichf=g+his minimum and place iton a list calledCLOSED5:ifnis a goal nodethen6:Exit with solution7:Expand noden, generating all its successors with pointers back ton8:for allsuccessorn ofndo9:Calculatef(n )10:ifn / OPENANDn / CLOSED then11:Addn toOPEN12:Assign the newly computedf(n ) to noden 13:else14:If newf(n ) value is smaller than the previous value, then update withthe new value (and predecessor)15:Ifn was inCLOSED, move it back toOPEN16.

3 Go to (2)Presented by Jarrell Waggoner & Jimmy ClevelandThe Optimality of A*Map ExampleMap Example8-Puzzle Example8-Puzzle Example8-Puzzle ExampleIntroductionDimensions of AnalysisAnalysisA ConclusionIntroduction to A*Introduction to A* (cont.)Some notes aboutA :A is a class of algorithms, not a single, set algorithmDepth-first, breadth-first, uniform-cost, and Dijkstra salgorithm are specific instances ofA and vary only by thechoice of heuristic and tie-breaking ruleA is a specific case of best-first search, where the heuristicevaluation functionf(x) is defined asf(n) =g(n) +h(n).Best-first A Depth-firstBreadth-firstDijkstraPresente d by Jarrell Waggoner & Jimmy ClevelandThe Optimality of A*IntroductionDimensions of AnalysisAnalysisA ConclusionDefinitionsOptimalityOptimalit y (finding a shortest path):ProvidedA isgiven an admissible heuristic, it will always find ashortest path because the optimistic heuristicwill never allow it to skip over a possible shorterpath option when expanding nodesOptimality (number of node expansions).

4 Specifically,the number of node expansions verses otheralgorithms with the same heuristic information (asA is clearly more optimal than algorithms thatlack heuristic information)It is this second definition that we seek to by Jarrell Waggoner & Jimmy ClevelandThe Optimality of A*IntroductionDimensions of AnalysisAnalysisA ConclusionDefinitionsNotationGdirected locally finite graphG= (V,E)C the cost of the cheapest solution pathC(.)the cost function defined over all solution paths a set of goal nodes, VPni nja path inGbetween nodeniandnjPSa solution path, , a path inGfromsto some goal node c(n,n )cost of an arc betweennandn ,c(n,n ) >0, where is a constantf(.)evaluation function defined over partial paths, , to each nodenalong a given pathP=s1,n1,n2,..,nwe assign the valuefP(n)which is shorthand notation forf(s,n1,n2.)

5 ,n)g(n)the sum of the branch costs along the current path of pointers fromntosg (n)the cost of the cheapest path going fromstongP(n)the sum of the branch costs along pathPfromstonh(n)a cost estimate of the cheapest path betweennand h (n)the cost of the cheapest path going fromnto k(n,n )cost of the cheapest path betweennandn Presented by Jarrell Waggoner & Jimmy ClevelandThe Optimality of A*IntroductionDimensions of AnalysisAnalysisA ConclusionDefinitionsDefinitionsAdmissib le Heuristic:A heuristic functionh(n) is said to beadmissibleon (G, ) iffh(n) h (n) for everyn GConsistent Heuristic:A heuristic functionh(n) is said tobeconsistent(or monotone) onGiff for any pairof nodes,n andn, the triangle inequality holds:h(n ) k(n , n) +h(n)Surely Expanded:Nodes thatmustbe expanded to reach agoal node (regardless of the tie-breaking rule oralgorithm used)Presented by Jarrell Waggoner & Jimmy ClevelandThe Optimality of A*IntroductionDimensions of AnalysisAnalysisA ConclusionDefinitionsDefinitions (cont.

6 Admissible Algorithm:An algorithm that, given a problemspace whereh(n) h (n) for everyn G, willreturn least-cost solutionsDominance:AlgorithmAdominatesso me other algorithmBif the set of nodes thatAexpands is asubsetofthe nodes expanded byB(not just fewer nodes)Strictly Dominate:Astrictly dominatesBiffAdominatesBandBdoes not dominateAOptimal (strong definition):AlgorithmAis optimal overa classAof algorithms iffAdominates everymember ofAWeakly Optimal:No member ofAstrictly dominatesAPresented by Jarrell Waggoner & Jimmy ClevelandThe Optimality of A*IntroductionDimensions of AnalysisAnalysisA ConclusionOutline1 Introduction2 Dimensions of AnalysisHierarchy of Optimality3 Analysis4A 5 ConclusionPresented by Jarrell Waggoner & Jimmy ClevelandThe Optimality of A*IntroductionDimensions of AnalysisAnalysisA ConclusionHierarchy of OptimalityAlgorithm ClassesTo determine the Optimality ofA over other algorithms withthe same heuristic information, we group these algorithms intoclasses (sinceA is already a class of algorithms, each with adifferent tie-breaking rule):Aad: Algorithms that return least-cost solutions whengiven an admissible problem space (though not necessarilyan admissible heuristic to run on that problem space)Abf.

7 Subclass ofAadthat accepts any path-dependentevaluation function, but operates in a best-first mannerAgc: Subclass ofAadthat will return optimal solutionswheneverA does, but may not obeyh > h Presented by Jarrell Waggoner & Jimmy ClevelandThe Optimality of A*IntroductionDimensions of AnalysisAnalysisA ConclusionHierarchy of OptimalityAlgorithm Classes (cont.)Presented by Jarrell Waggoner & Jimmy ClevelandThe Optimality of A*IntroductionDimensions of AnalysisAnalysisA ConclusionHierarchy of OptimalityProblem InstancesProblem Instance:A particular setup of a by a quadruple:I= (G, s, , h)Gis the graph representation of the problemsis the start node in the graph is the set of goal nodeshis a heuristic that any algorithm run on this instance willuseIis asetof problem instances that share some common traitPresented by Jarrell Waggoner & Jimmy ClevelandThe Optimality of A*IntroductionDimensions of AnalysisAnalysisA ConclusionHierarchy of OptimalityProblem Instances (cont.)

8 There are four important sets of problem instances:IAD: The setI Ithat has an admissible heuristic:IAD={(G, s, , h)|h h on (G, )}ICON: The setI Ithat has a consistent heuristic:IAD={(G, s, , h)|his consistent onG}IAD: The non-pathological case ofIADICON: The non-pathological case ofICONP resented by Jarrell Waggoner & Jimmy ClevelandThe Optimality of A*IntroductionDimensions of AnalysisAnalysisA ConclusionHierarchy of OptimalityProblem Instances (cont.)Presented by Jarrell Waggoner & Jimmy ClevelandThe Optimality of A*IntroductionDimensions of AnalysisAnalysisA ConclusionHierarchy of OptimalityTie-Breaking RulesA can be considered a class of algorithms, defined by thetie-breaking rule chosenccPresented by Jarrell Waggoner & Jimmy ClevelandThe Optimality of A*IntroductionDimensions of AnalysisAnalysisA ConclusionHierarchy of Optimality0-3 OptimalityA is optimal relative toAin the following senses:0-Optimal:AllA s tie-breaking rules dominate all membersofA1-Optimal:One ofA s tie-breaking rules expands a subset ofallA s members2-Optimal:No member ofAexpands a proper subset of anyofA s members3-Optimal.

9 No tie-breaking rule inA (orA ) is strictlydominated by some member ofAStrongest Weakest0-Optimal 3-OptimalPresented by Jarrell Waggoner & Jimmy ClevelandThe Optimality of A*IntroductionDimensions of AnalysisAnalysisA ConclusionOutline1 Introduction2 Dimensions of Analysis3 AnalysisTheorem 1 Theorem 24A 5 ConclusionPresented by Jarrell Waggoner & Jimmy ClevelandThe Optimality of A*IntroductionDimensions of AnalysisAnalysisA ConclusionTheorem 1 Theorem 1 TheoremAny algorithm that is admissible onIADwill expand, in everyinstanceI ICON, all nodes surely expanded byA .MeaningProblems with a consistent heuristics cannot be solved anybetter thanA can solve them by algorithms with the by Jarrell Waggoner & Jimmy ClevelandThe Optimality of A*IntroductionDimensions of AnalysisAnalysisA ConclusionTheorem 1 Theorem 1 ProofProof :GivenI= (G, S, , h) ICON, and assuming thatnis surelyexpanded byA , then there exists a pathPs n Ps n, g(n ) +h(n )< C LetBbe an algorithm compatible withA that halts with costC inI.

10 Assume thatBdoes not expandn. We can then createG as follows:TranslationWhat we do here is setup a contradiction: ForBto be betterthanA , it must skip some nodenthatA visits. We assumeBdoes this, and setup a new graphG that will introduce by Jarrell Waggoner & Jimmy ClevelandThe Optimality of A*ConstructingGandG IntroductionDimensions of AnalysisAnalysisA ConclusionTheorem 1 Theorem 1 Proofwhere we have added a goal nodettoG. The costs oftis givenbyh(t) = 0 and the edge fromntotis given asc=h(n) +4where:4=12(C D)>0D=max{f(n )|n NG g+h}This creates a new pathP whose cost is C 4yet is stillconsistent (and admissible) on the newI .TranslationHere, we setup a new node inG and make sure it has theproper costs associated with it so that the newG obeys all therules that the by Jarrell Waggoner & Jimmy ClevelandThe Optimality of A*IntroductionDimensions of AnalysisAnalysisA ConclusionTheorem 1 Theorem 1 (cont.)