Editing A* search algorithm (section)

==History==
[[File:SRI Shakey with callouts.jpg|thumb|right|A* was invented by researchers working on Shakey the Robot's path planning.]]
A* was created as part of [[Shakey the robot|the Shakey project]], which had the aim of building a mobile robot that could plan its own actions. Nils Nilsson originally proposed using the [[Graph traversal|Graph Traverser]] algorithm<ref>{{Cite journal|last1=Doran|first1=J. E.|last2=Michie|first2=D.|date=1966-09-20|title=Experiments with the Graph Traverser program|journal=Proc. R. Soc. Lond. A |volume=294|issue=1437|pages=235–259|doi=10.1098/rspa.1966.0205 |bibcode=1966RSPSA.294..235D|s2cid=21698093}}</ref> for Shakey's path planning.<ref name=":0">{{Cite book|url=https://ai.stanford.edu/~nilsson/QAI/qai.pdf|title=The Quest for Artificial Intelligence|last=Nilsson|first=Nils J.|author-link=Nils John Nilsson|date=2009-10-30|publisher=Cambridge University Press|isbn=9780521122931|location=Cambridge|language=en|quote=One of the first problems we considered was how to plan a sequence of 'way points' that Shakey could use in navigating from place to place. […] Shakey's navigation problem is a search problem, similar to ones I have mentioned earlier.}}</ref> Graph Traverser is guided by a heuristic function {{math|''h''(''n'')}}, the estimated distance from node {{mvar|n}} to the goal node: it entirely ignores {{math|''g''(''n'')}}, the distance from the start node to {{mvar|n}}. Bertram Raphael suggested using the sum, {{math|''g''(''n'') + ''h''(''n'')}}.<ref>{{Cite book|url=https://ai.stanford.edu/~nilsson/QAI/qai.pdf|title=The Quest for Artificial Intelligence|last=Nilsson|first=Nils J.|author-link=Nils John Nilsson|date=2009-10-30|publisher=Cambridge University Press|isbn=9780521122931|location=Cambridge|language=en|quote=Bertram Raphael, who was directing work on Shakey at that time, observed that a better value for the score would be the sum of the distance traveled so far from the initial position plus my heuristic estimate of how far the robot had to go.}}</ref> Peter Hart invented the concepts we now call [[Admissible heuristic|admissibility]] and [[Consistent heuristic|consistency]] of heuristic functions. A* was originally designed for finding least-cost paths when the cost of a path is the sum of its  costs, but it has been shown that A* can be used to find optimal paths for any problem satisfying the conditions of a cost algebra.<ref>{{Cite conference|last1=Edelkamp|first1=Stefan|last2=Jabbar|first2=Shahid|last3=Lluch-Lafuente|first3=Alberto|date=2005|contribution=Cost-Algebraic Heuristic Search|url=http://www.aaai.org/Papers/AAAI/2005/AAAI05-216.pdf|title=Proceedings of the Twentieth National Conference on Artificial Intelligence (AAAI)|pages=1362–1367 |isbn=978-1-57735-236-5}}</ref>

The original 1968 A* paper<ref name="nilsson" /> contained a theorem stating that no A*-like algorithm{{efn|"A*-like" means the algorithm searches by extending paths originating at the start node one edge at a time, just as A* does. This excludes, for example, algorithms that search backward from the goal or in both directions simultaneously. In addition, the algorithms covered by this theorem must be admissible, and "not more informed" than A*.}} could expand fewer nodes than A* if the heuristic function is consistent and A*'s tie-breaking rule is suitably chosen. A "correction" was published a few years later<ref>{{Cite journal|last1=Hart|first1=Peter E.|last2=Nilsson|first2=Nils J.|author-link2=Nils John Nilsson|last3=Raphael|first3=Bertram|date=1972-12-01|title=Correction to 'A Formal Basis for the Heuristic Determination of Minimum Cost Paths'|url=https://www.ics.uci.edu/~dechter/publications/r0.pdf|journal=ACM SIGART Bulletin|issue=37|pages=28–29|doi=10.1145/1056777.1056779|s2cid=6386648 }}</ref> claiming that consistency was not required, but this was shown to be false in 1985 in Dechter and Pearl's definitive study of A*'s optimality (now called optimal efficiency), which gave an example of A* with a heuristic that was admissible but not consistent expanding arbitrarily more nodes than an alternative A*-like algorithm.<ref name=":1" />