ARTIFICIAL INTELLIGENCE
A* Search
Algorithm
Intelligent Pathfinding for Modern AI Systems
From Graph Theory to Autonomous Navigation
What is A* Search?
A* (pronounced "A-star") is a best-first search algorithm that finds the least-cost path from a start node to a goal node. It combines the strengths of Dijkstra's algorithm and greedy best-first search.
ORIGIN
Developed in 1968 by Peter Hart, Nils Nilsson, and Bertram Raphael
PROPERTY
Optimal and complete when using an admissible heuristic
APPROACH
Uses informed search with heuristics to guide exploration
Widely used in games, robotics, and navigation
The Core Formula
f(n) = g(n) + h(n)
f(n)
Total Estimated Cost
The evaluation function that determines which node to expand next
g(n)
Cost So Far
Actual cost from the start node to current node n
h(n)
Heuristic Estimate
Estimated cost from node n to the goal
Why This Works
A* always expands the node with the lowest f(n) value, balancing exploration of known paths with promising directions toward the goal.
Heuristic Functions
The heuristic h(n) guides the search. A good heuristic dramatically improves performance.
Manhattan
h = |x₁-x₂| + |y₁-y₂|
4-direction grid movement
✓ Tile puzzles, city maps
Euclidean
h = √[(Δx)² + (Δy)²]
Any-angle movement
✓ Robotics, drones
Diagonal
h = max(|Δx|, |Δy|)
8-direction grid
✓ Strategy games, chess
Admissibility: A heuristic is admissible if it never overestimates the true cost. This guarantees optimality.
How A* Works
Initialize
Add start node to OPEN list with f = h(start)
Select Best Node
Remove node with lowest f(n) from OPEN
Goal Check
If goal reached, reconstruct and return path
Expand Neighbors
For each neighbor, calculate f(n) = g(n) + h(n)
Update Lists
Add/update neighbors in OPEN, move current to CLOSED
Repeat
Continue from step 2 until goal or OPEN is empty
KEY DATA STRUCTURES
OPEN List
Priority queue of nodes to explore (sorted by f-value)
CLOSED List
Set of already explored nodes (prevents revisiting)
COMPLEXITY
Time
O(b^d)
Space
O(b^d)
b = branching factor, d = depth
A* in Action
Pathfinding on a 5×5 grid with obstacles
Search Process
A* expands nodes in order of their f-values, navigating around obstacles while minimizing total path cost.
KEY OBSERVATIONS
Only explores promising directions
Avoids exploring behind obstacles
Finds optimal path efficiently
Result
Path Length: 7
Nodes explored: 12 of 25
A* vs Other Algorithms
Algorithm
Optimal
Complete
Informed
A* Search
Dijkstra's
Greedy Best-First
BFS / DFS
WHY A* WINS
A* combines the optimality guarantee of Dijkstra's with the speed of greedy search by using heuristics to guide exploration toward the goal.
TRADE-OFF
A* requires more memory than DFS and computing heuristics adds overhead, but the dramatic reduction in nodes explored usually outweighs these costs.
BEST FOR
Single-source shortest path problems where a good heuristic is available and optimality is required.
AI Applications of A*
Robotics
Path planning for mobile robots, robotic arms, and autonomous vehicles navigating real-world environments.
3D navigation, obstacle avoidance
Video Games
NPC pathfinding, enemy AI, and real-time strategy games with thousands of units moving simultaneously.
Real-time, dynamic environments
GPS Navigation
Route planning in mapping applications, considering traffic, road types, and user preferences.
Multi-criteria optimization
Puzzle Solving
Solving 8-puzzles, Rubik's cubes, and other state-space search problems efficiently.
State space exploration
50+
YEARS IN USE
100+
VARIANTS DEVELOPED
#1
PATHFINDING ALGORITHM
Modern AI Integration
A* is being enhanced with modern AI techniques
Neural Network Heuristics
Deep learning models learn better heuristic functions from data, improving A* performance in complex domains.
Reinforcement Learning + A*
RL agents use A* for planning while learning value functions that serve as heuristics.
LLM-Guided Planning
Large language models propose actions while A* verifies and optimizes the resulting plans.
FEATURED: AUTONOMOUS VEHICLES
Perception
Neural networks detect obstacles
Planning
A* finds optimal trajectory
Control
RL refines execution in real-time
A* provides the backbone for safe, optimal navigation
💡 Key Insight: Classical algorithms like A* provide guarantees that pure neural approaches cannot match.
SUMMARY
Key Takeaways
Optimal & Complete
A* guarantees the shortest path when using an admissible heuristic
Heuristic is Key
The quality of h(n) determines search efficiency
Widely Applicable
Games, robotics, navigation, and AI planning systems
Combines Best of Both
Dijkstra's completeness + Greedy's speed
Evolving with AI
Neural heuristics and hybrid approaches extend its power
"A* remains the gold standard for informed search in AI"