A Star Is Born NASA

A* was created as part of 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 Traverser algorithm for Shakey’s path planning. Graph Traverser is guided by a heuristic function h(n),{displaystyle h(n),} the estimated distance from node n{displaystyle n} to the goal node: it entirely ignores g(n),{displaystyle g(n),} the distance from the start node to n. {displaystyle n. } Bertram Raphael suggested using the sum, g(n)+h(n){displaystyle g(n)+h(n)}. Peter Hart invented the concepts we now call admissibility and consistency of heuristic functions.   A* was originally designed for finding least-cost paths when the cost of a path is the sum of its edge 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.