Peter Hart, Nils Nilsson, and Bertram Raphael introduced the A* algorithm in 1968 at Stanford Research Institute. Their paper described how to solve pathfinding problems for Shakey the Robot without human intervention.
Admissibility guarantees that an algorithm always returns the best possible result while consistency ensures each node is processed only once. Rina Dechter and Judea Pearl proved in 1985 that consistency is required for full optimality because inconsistent heuristics can cause exponential node expansion.
The algorithm stores every generated node in memory until completion which grows exponentially with deep solution paths or high branching factors. Memory-bounded approaches like Iterative Deepening A* were developed specifically to address these constraints.
Resolving ties using last-in-first-out logic makes A* behave similarly to depth-first search along optimal routes. Fibonacci heaps offer constant amortized time for decrease-priority operations while standard binary heaps require hash table augmentation for logarithmic-time updates.
D* handles changing graph weights during execution making it suitable for robotics navigating unknown terrain. Iterative Deepening A* reduces space requirements by performing repeated searches with increasing depth bounds.